臺灣博碩士論文加值系統

本研究針對多車多場站種車輛路線問題(Multi-Depot and Heterogeneous Fleet Vehicle Routing Problem, MDHVRP)之巨集啟發式解法進行探討。HMDVRP可定義為：給予一個網路，包含M個場站與N個顧客，各場站皆有K種車輛可以使用且數量不限；在滿足各車種容量限制與路線最大距離等限制下，求出一組車輛路線使得車輛使用成本與路線行駛成本之總和達到極小化。門檻接受法(Threshold Accepting, TA)為一巨集啟發式方法，為1990年德國學者Dueck及Scheuer所提出，其由模擬鍛鍊法（Simulated Annealing, SA）改良而來，屬於門檻型演算法(Threshold Algorithm)的一種。近年來應用於求解最佳化問題具有不錯成效。
本研究之TA_HMDVRP的巨集啟發式求解方法。共分成三個模組：起始解構建模組、鄰域搜尋模組設計、門檻接受模組。其中起始解建構方式主要應用「先分群再排程（Cluster First, Route Second）」的概念來設計，分成以下二個步驟，(1) 顧客分群：依據各顧客點與各場站之相對位置，將顧客指派給距其最近的場站。(2) 路線構建：以最大容量與最小容輛的2車種為基礎，利用最遠起點之鄰近點法（Farthest-start Nearest Neighbor Method），分別構建各場站的車輛起始路線。在鄰域搜尋模組部分，應用2-Opt、Or-Opt、路線間節點交換、場站間節點交換，以及路線分解（大車換小車）等方法，進行起始解的改善，再配合門檻接受模組來求解標竿例題。
本研究以C#語言將上述提出的啟發式解法撰寫成電腦程式，並採用Salhi等人所使用的多車種轉換公式，將加拿大配送管理研究中心(CRCDM)共25個多場站車輛路線問題(Multi-Depot Vehicle Routing Problem, MDVRP)標竿例題轉修改成多場站多車種車輛路線問題的例題，並進行解題績效測試與分析。測試結果再起始解產生方面，以最大車容量所構建之起始解表現較好，再經由鄰域搜尋模組與門檻接受模組改善後，最小車容量構建之起始解，部分例題路線數雖較使用最大車容輛構建之起始解少，但路線成本仍然較高，整體仍以最大車容量所構建之解表現較佳。

The Heterogeneous Multi-Depot Vehicle Routing Problem (HMDVRP) is an extent of the classical Vehicle Routing Problem. HMDVRP can be defined as follows. Given a network includes M depots, N customers and K kinds of trucks in each depot with unlimited numbers, as well as subjected to vehicle capacity and maximum routing distance, HMDVRP aims to decide a set of routs that contributes the minimum sum of vehicle cost and traveling distance.
In this research, we develop a Threshold Accepting (TA) meta-heuristic, originally proposed by Dueck and Scheuer (1993), named as TA_HMDVRP, to solve the HMDVRP. TA_HMDVRP is based on the combination of Threshold Accepting (TA) and traditional Neighborhood Search heuristics. There are three modules: initial solution construction (ISC), local search (LS), and threshold accepting (TA) in the TA_HMDVRP framework. In ISC module, a two-stage approach that first assigns customers to the nearest depot and then utilizes the Farthest-start Nearest Neighbor (FNN) method to arrange routes of each depot. Moreover, two kinds of vehicle, the biggest truck and the smallest truck, are optionally selected to construct routes while executing FNN. Five exchange heuristics: 2-opt, Or-opt, Node Insert (Inter-route and Inter-depot), Node Exchange (Inter-route and Inter-depot), and Vehicle Exchange, are proposed in LS Module. Finally, a geometric descent TA mechanism is adopted in the TA module.
Due to the lack of HMDVRP instances, we transfer the MDVRP benchmark instances to a bank of twenty-five HMDVRP test instances, which is used to identify the performance of TA_HMDVRP. In the first experiment of testing ISC module, FNN with the biggest truck performs well than FNN with the smallest truck. In the second experiment, the average result after executing LS and TA modules to improve the initial solution is significantly good. The results of numerical experiments imply that Threshold Accepting meta-heuristic can be a potential procedure to solve the complicate HMDVRP.

摘　要 i
Abstract ii
誌　謝 iii
目　錄 iv
圖目錄 vi
表目錄 vii
第一章 緒論 1
1.1研究動機與目的 1
1.2研究範圍與內容 1
1.3研究步驟與流程 2
第二章 文獻回顧 5
2.1多場站車輛路線問題(MDVRP) 5
2.1.1 MDVRP的定義 5
2.1.2 MDVRP之文獻回顧 6
2.2多車種車輛路線問題(HVRP) 9
2.2.1 HVRP問題定義 9
2.2.2 HVRP之文獻回顧 10
2.3 多車種多場站車輛路線問題(HMDVRP) 12
2.3.1 HMDVRP之文獻回顧 12
2.4車輛路線啟發式演算法探討 13
2.4.1傳統啟發式演算法 13
2.4.2門檻接受演算法 15
第三章 TA_HMDVRP之求解方法架構與模組設計 18
3.1求解方法架構 18
3.2起始解構建模組設計 19
3.3鄰域搜尋模組設計 20
3.4門檻接受模組設計 23
3.4.1 TA架構設計 23
3.4.2 TA控制參數 23
第四章 例題測試與結果分析 25
4.1例題產生與實驗設計 25
4.1.1例題產生 25
4.1.2實驗設計 26
4.2 測試結果分析 26
4.2.1 實驗一：起始解測試比較 26
4.2.2 實驗二：鄰域搜尋模組之求解績效測試 27
4.2.3 實驗三：門檻接受模組之求解績效測試 30
第五章 結論與建議 33
5.1結論 33
5.2建議 33
參考文獻 35
附錄A 門檻接受模組求解詳細表 37
附錄B 部份測試例題路線圖 42
附錄C HMDVRP之數學模式 45

參考文獻
1.卓裕仁(2001)，「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」，國立交通大學運輸工程與管理學系所博士論文。
2.高崇明(2005)，「多場站車輛路線問題巨集啟發式方法之研究」，中華大學科技管理研究所碩士論文。
3.殷德成(1998)，「以禁制搜尋法求解多車種車輛路線問題」，國防管理學院資訊管理研究所碩士論文。
4.張祖明(1994)，「多車種車輛路線問題啟發式解法之研究」，國立交通大學土木研究所運工管組碩士論文。
5.韓復華、卓裕仁、陳國清(1999)，「五種巨集啟發式解法在VRP問題上的應用與比較」，中華民國第四屆運輸網路研討會論文集，第72-82頁，國立成功大學：台南。
6.Andrew Lim and Fan Wang (2005), “Multi-Depot Vehicle Routing Problem: A One-Stage Approach,” IEEE Transactions on Automation Science and Engineering, Vol.2, No.4, pp.397-402, October.
7.Chao, I. M., B. L. Golden and E. Wasil (1993), “A New Heuristic for The Multi-Depot Vehicle Routing Problem That Improves Upon Best-Known Solutions,” American Journal of Mathematical & Management Science, Vol.13, No.2, pp.371-406.
8.Golden, B.L., A. Assad, L. Levy and F.G. Gheysens (1984), “The Fleet Size and Mix Vehicle Routing Problem,” Computers & Operations Research, Vol.11, pp.49-66.
9.Filip Ghetsens , Bruce Golden , Arjang Assad (1986), “A new heuristic for determining fleet size and composition,” Mathematical Programming Studies,Vol.26, pp.233-236.
10.Gunter Dueck and Tobias Scheuer, “Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing”, Journal of Computational Physics, Vol.90, No.1, pp.161 - 175 .
11.ID Giosa1, IL Tansini1 and IO Viera (2002), “New assignment algorithms for the multi-depot vehicle routing problem”, Journal of Operational Research Society, Vol.53, pp.977-984.
12.Jacques Renaud and Fayez F. Boctor (2002), “A sweep-based algorithm for the fleet size and mix vehicle routing problem,” European Journal of Operational Research 140, pp.618-628.
13.Jacques Renaud, Gilbert Laporte and Fayez F. Boctor (1996), “A Tabu Search Heuristic for the Multi-Depot Vehicle Routing Problem,” Computer Ops Res. Vol. 23, NO. 3, pp.229-235.
14.L. Bodin, B.L. Golden , A. Assad and M. Ball (1983), “Routing and schedule of vehicle and crew: the state of art,” Computers and Operations Research, Vol. 10, No. 2, pp.63-211.
15.L. Bodin, B. Golden, A. Assad and M. Ball (1983), "Routing and Scheduling of Vehicle and Crews: The State of Art," Special Issue of Computers and Operations Research, Vol.10, No.2, pp.63-211.
16.Michael Polacek, Richard F. Hartl and Karl Doerner (2004), “A Variable Neighborhood Search for the Multi Depot Vehicle Routing Problem with Time Windows”, Journal of Heuristics, Vol.10, No.6, pp.613–627.
17.Robert T. Sumichrast and Ina S. Markham (1995), “A heuristic and lower bound for a multi-depot routing problem”, Computers Ops Res. Vol.22, No.10, pp.1047-1057.
18.Salhi, S. and G..K. Rand (1993), "Incorporating Vehicle Routing into the Vehicle Fleet Composition Problem," European Journal of Operational Research, Vol.66, No.3, pp.313-330.
19.S. Salhi, M. Sari (1997), “A multi-level composite heuristic for the multi-depot vehicle fleet mix problem”, European Journal of Operational Research, Vol.101, pp.95-112.
20.http://www.hec.ca/chairedistributique/data/