臺灣博碩士論文加值系統

由於都市地區土地價格偏高，大多數的物流與貨運業者皆將其營業據點或場站設置於市郊；此舉可能造成配送距離與次數的增加。為減少車輛往返場站的次數與距離，近年來已有某些業者利用大型卡車來進行中途的接駁。亦即，以大型卡車為指定點，當小貨車配送完第一趟的顧客點後，直接至指定點向大型卡車補貨而不需再回到場站，然後進行第二趟的配送服務。
本研究之目的即針對上述的接駁配送方式，提出一個新型態的車輛路線模式，稱之為「指定點接駁車輛路線問題（Linehaul-Feeder Vehicle Routing Problem, LFVRP）」；並針對其問題特性設計啟發式求解方法。本研究所設計的啟發式解法主要包含三個步驟：首先，利用八種選擇指定點方法從所有顧客點中找出最佳位置做為指定點；然後利用最近鄰點法分別將兩群顧客插入至場站與指定點之間，以形成第一類與第二類的路線；最後，再使用2-Opt、Or-Opt、路線間節點交換等鄰域搜尋法進行路線改善。
為驗證LFVRP之可行性與適用性，本研究蒐集了60個傳統車輛路線問題的國際標竿例題做為LFVRP的測試例題，並依其場站所在位置與顧客點分佈型態分成四組。本研究以C#語言撰寫上述啟發式解法之電腦程式，並以LFVRP例題進行解題績效分析。經與各標竿例題的文獻已知最佳解相比，結果發現LFVRP在場站位置偏遠的兩組例題表現優於另兩組場站位置居中型的例題，顯示接駁式的配送確實較適合於場站位置偏遠的情形；並將所有測試例題與八種選擇指定點方法進行分析，可得知SF2這種選擇指定點方法較不適合使用在各類型的測試例題。本文最後亦提出了LFVRP之後續研究建議。

Because of the high price of megalopolis land, most of the distribution centers (DC) located at the suburbs area. This far-away location may cause an increase in the number of round-trips and in the traveling distance. In order to reduce the vehicles’ round-trip and traveling distance, recently some carriers have developed a new type of operation that dispatches a heavy truck as the movable depot to serve other trucks for the second loading and delivery.
The purposes of this research are to transfer above-mentioned operation into a special Vehicle Routing Problem, named as the Linehaul-Feeder Vehicle Routing Problem (LFVRP), and to design a simple heuristic to solve the LFVRP. This heuristic includes three steps: (1) selecting a specific customer as the movable depot, (2) constructing routes to serve customers between DC and the movable depot, and (3) improving routes by neighborhood search heuristics. In the first step, we propose eight rules to select movable depot; in the second step, we utilize the Nearest Neighbor (NN) method to construct the initial routes; in the final step, we used three neighborhood search methods: 2-Opt, Or-Opt and Inter-route node exchange to improve routes’ distance.
In order to verify the feasibility and suitability of the LFVRP model, this research generated a bank of sixty LFVRP instances that are modified from classical VRP benchmark instances, and divided them into four groups according to the position of DC and the geographic distribution of customers. Then, we use the C# computer language to coding the above heuristic method and use the LFVRP instances to test its performance. Through comparing with the best-found solutions, we found that LFVRP seems to be suitable for the instances which DC is located on side and customers are clustered.

目錄
摘要 i
Abstract ii
誌謝 iii
目錄 iv
圖目錄 vi
表目錄 vii
第一章　緒論 1
1.1 研究動機與目的 1
1.2 研究範圍與內容 2
1.3 研究步驟與流程 3
第二章　文獻回顧 6
2.1 車輛路線問題相關文獻 6
2.1.1 VRP問題定義 6
2.1.2 VRP解法回顧 9
2.2 接駁式車輛路線問題相關文獻 11
2.3 卡車拖車路線問題相關文獻 12
2.4 小結 19
第三章　解題架構設計 20
3.1 整體解題架構 20
3.2 起始解構建模組 20
3.2.1 選擇指定點 21
3.2.2 路線構建 28
3.3 鄰域搜尋改善模組 28
3.3.1 路線內交換改善模組 29
3.3.2 路線間交換改善 32
第四章　LFVRP測試與結果分析 36
4.1 測試例題產生與實驗設計 36
4.1.1 測試例題產生 36
4.1.2 實驗設計 38
4.2 結果分析 39
4.2.1 實驗一：起始解之解題績效 39
4.2.2 實驗二：起始解與最佳結果之分析 43
4.2.3 實驗三：選擇指定點方法與鄰域搜尋改善模組之組合分析 44
4.2.4 實驗四：測試例題類型與選擇指定點方法之組合分析 46
第五章　結論與建議 48
5.1 結論 48
5.2 建議 50
參考文獻 52
附錄一 實驗四結果 54
附錄二 各種類型測試例題之路線圖 58

1.王生德(2003)，「以巨集啟發式方法求解時窗限制回程取貨車輛路線問題(VRPBTW)之研究」，中華大學科技管理研究所碩士論文。
2.卓裕仁(2001)，「以巨集啟發式方法求解多車種與週期性車輛路線問題之研究」，交通大學運輸工程與管理學系所博士論文。
3.卓裕仁、張高文、高崇明(2002)，「時效性商品配送車隊組成與配送策略之研究」，發表於中華民國第七屆運輸網路研討會。
4.吳志仁(2003)，「一般化卡車拖車路線問題」，交通大學運輸科技與管理學系碩士論文。
5.涂紓瑜、賴淑娟、黎燕萍(2001)，「時間限制VRP之應用研究－以網路訂購便當之配送車隊排程為例」，中華大學交通與物流管理學系畢業專題報告。
6.高崇明(2005)，「多場站車輛路線問題巨集啟發式方法之研究」，中華大學科技管理研究所碩士論文。
7.張靖、卓裕仁、黃勇智(2001)，「時間限制車輛途程模式應用於網路訂購便當車隊途程規劃之探討」，發表於中國工業工程學會九十年度年會暨學術研討會，高雄。
8.劉建宏(2005)，「含時窗限制式卡車與拖車途程問題之研究」，中央大學土木工程學系碩士論文。
9.蔡裕峰(2002)，「軸輻式物流網路區位與途程之啟發式解法，高雄第一科技大學運輸與倉儲營運系所碩士論文。
10.韓復華、卓裕仁(2001)，「網路節點服務TSP與VRP問題回顧」，運輸網路分析，pp.202-223
11.Bodin, L., Golden , B.L., Assad, A., and M. Ball (1983), “Routing and schedule of vehicle and crew: the state of art”, Computers & Operations Research, Vol. 10, No. 2, pp.63-211.
12.Chao, I-Ming (2002), “A tabu search method for the truck and trailer routing problem”, Computers & Operations Research, Vol. 29, pp.33-51.
13.Christofides, N.and Eilon, S. (1969), “An Algorithm for Vehicle Dispatching Problem,” Operational Research Quarterly, Vol. 20, pp.309-318.
14.Christofides, N., Mingozzi, A., and Toth, P. (1979), Combinatorial Optimization, John willey & Sons, inc..
15.Gerdessen, Johanna C. (1996), “Vehicle routing problem with trailers”, European Jornal of Operational Research, Vol. 93, pp.135-147.
16.Scheuerer, Stephan (2006), “A tabu search heuristic for the truck and trailer routing problem”, Computers & Operations Research, Vol. 33, pp.894-909
17.Solomon, M. (1983), Vehicle routing and scheduling with time window constraints : models and algorithms, Ph.D. Dissertation, Dept. of Decision Sciences, University of Pennsylvania.
18.Toth, Paolo and Vigo, Daniele (2002), The vehicle routing problem, SIAM - Monographs on Discrete Mathematics and Applications, 2002 pp.1-26
19.http://neo.lcc.uma.es/radi-aeb/WebVRP/