節線排程問題路線改善方法之研究

Abstract

車輛排程問題（ vehicle routing problem ）的探討一直是在作業研究 或物流業上，一個相當受人重視的問題。一個好的車輛排程系統，不僅可 以使得該單位的營運成本大幅下降，更可增進整體的服務水準。車輛排程 問題基本上可根據需求發生地點的不同而分成兩大類，分別是節點排程問 題（ node routing problems ）與節線排程問題（ arc routing problems ）。 由於節線排程問題並沒有類似節點排程問題有路線改善方 法之研究，而且相關文獻中所應用的路網型態並不符合實際情況。因此本 論文主要目的在於針對有路口轉向限制之有方向性路網，參考節點排程問 題之路線改善方法的概念，應用於節線排排程問題。本論文所發展之演算 法主要是參考節點排程問題之路線改善方法及區域搜尋法的概念（ local search algorithm ），發展出路線間之交換改善步驟，再輔以禁 制搜尋策略 (tabu search method) 來擴大搜尋範圍，尋找更佳的結果。 並利用節線間最短路徑矩陣，使演算法可擴大應用於有方向性與有轉向限 制（左轉或迴轉）之路網類型。以六個實際街道路網作為測試例題， 並 與適當修改之彭所發展之擴張 - 插入演算法 (Augment-Insert method) 作測試比較， 發現本研究所發展之節線交換改善法可以有效地改善由擴 張 - 插入演算法所得到的結果。 Studies about vehicle routing problem are always being emphasized. A good vehicle routing system will decrease operating cost and improve the level of service. Vehicle routing problems can be divided into node routing problems(NRP) and arc routing problems(NRP). There have been many studies solving NRP and many methods developed. ARP is very important and wide-spread on the applications in the real-world, too. However,compared with NRP, there are few studies discussing about ARP. ARP is mostly an NP-hard problem; therefore, real-world applications still reply on heuristic methods. This thesis is based on the swapping idea of node routing problems and the strategy of local search algorithm. We develop the algorithm of arc exchange method of ARP. Also we hope to use the algorithm on a more complicated network. Then we try to combine the algorithm with tabu search method to make it more efficiently and effectively. The set of 6 test problems digitized from real-world network is adopted to evaluate the performance of this route improving algorithm of ARP. compared with Augment-Insert algorithm, we found that route improving algorithm can effectively improve the result of Augment-Insert algorithm.