臺灣博碩士論文加值系統

本論文是運用塔布搜尋法（Tabu Search）於具時窗限制及回程撿收的車輛途程問題（Vehicle Routing Problem with Backhaul and Time Window, VRPBTW）。具回程撿收的車輛途程問題（Vehicle Routing Problem with Backhaul, VRPB）是傳統車輛途程問題（Vehicle Routing Problem, VRP）的延伸。傳統車輛途程問題，只考慮運送（Linehaul）貨品，而具回程撿收（Backhaul）的車輛途程問題，則是將顧客分為兩個子集合：運送顧客，將貨品自中央場站配送至顧客處；撿收顧客，將自顧客處收集的貨品帶回中央場站。具回程撿收的車輛途程問題的研究中，大多限制撿收須在所有運送之後，這個限制的原因是如果為了撿收貨品而必須在車上重新安排貨品，是很不方便的，且通常運送的貨品具有較高的優先權。但是若按照裝卸貨的順序來堆放貨品且顧客的需求具有時窗限制，則這個限制就可以被取消。本研究嘗試取消此項限制，並以「撿收容許百分比」來限制前幾站不可為撿收顧客，以避免無法滿載出發的問題。而且，顧客開始被服務的時間必須在特定的時間區間之中。本研究以塔布搜尋法求解，運用三種初始解與三種交換法之組合，並利用田口方法找出最適合的因子組合。本研究以標準題庫測試，並以其他相關研究及最佳解比較。結果顯示，若在運送之前容許撿收之措施，將可有效地降低途程成本及車輛數。

This article describes a tabu search heuristic for the vehicle routing problem with backhaul and time window (VRPBTW). The vehicle routing problem with backhaul (VRPB) is the extension of the classical vehicle routing problem (VRP). The VRP only considers the delivery of customers to the stations. However, for the VRPB, the set of customers is partitioned into two subsets : linehaul customers where a given quantity of goods is delivered from a central depot, and backhaul customers where a given quantity of goods is collected from a backhaul customer and transported to the depot. To the VRPB problem, the backhaul must be served after the linehaul on each route. This constraint arises because it is often inconvenient to rearrange linehaul loads onboard in order to accommodate new pick-up loads, and linehaul are generally with higher priority stops than backhauls. If we arrange the load depend on route sequence and the load have time window constraint, this constraint will be relaxed. This study is to relax this constraint and find out its feasibility. We utilize pick-up allowance rate (PAR) to forbid the front of route which can’t be backhauled. Furthermore, the time of beginning of service at each customer must occur within a particular time interval. We utilized tabu search heuristic coupled with three initial solution and three exchange methods to solve the VRPB. Taquchi method was also utilized to find the best design parameters. Computational results are reported on standard set of test problems. The results shows that the use of PAR can reduce the route cost and number of vehicle.

中文摘要 ………………………………………………………………… i
英文摘要 ………………………………………………………………… ii
誌謝 ……………………………………………………………………… iii
目錄 ……………………………………………………………………… iv
表目錄 …………………………………………………………………… vi
圖目錄 …………………………………………………………………… vii
第一章 緒論 …………………………………………………………… 1
1.1 研究背景與動機 ………………………………………………… 1
1.2 研究目的 ………………………………………………………… 3
1.3 基本假設與限制條件 ……………………………………………3
1.4 研究流程 …………………………………………………………4
第二章 文獻探討 …………………………………………………………6
2.1 車輛途程問題之分類 …………………………………………………6
2.2 具時窗限制之車輛途程問題的求解方式 ……………………………7
2.3 回程撿收相關文獻整理 ………………………………………………8
2.4 塔布搜尋法簡介 ………………………………………………………9
2.5 塔布搜尋法之主要組成要素 ………………………………………… 12
第三章 模式設定與方法研究 …………………………………………… 16
3.1 數學模式 ……………………………………………………………… 16
3.2 初始解 ………………………………………………………………… 18
3.2.1最鄰近法 …………………………………………………………… 18
3.2.2循序插入法 ………………………………………………………… 18
3.2.3平行插入法 ………………………………………………………… 19
3.3 鄰近解 ………………………………………………………………… 24
3.4 研究方法 ……………………………………………………………… 26
第四章 測試題目介紹 …………………………………………………… 28
4.1 測試題目介紹 ………………………………………………………… 28
4.1.1 VRPTW測試題目 …………………………………………………… 28
4.1.2 VRPBTW測試題目 …………………………………………………… 29
4.2輸出/入畫面及說明 …………………………………………………… 29
第五章 結果分析 ………………………………………………………… 33
5.1 田口實驗設計 ………………………………………………………… 33
5.1.1 特性要因分析 ……………………………………………………… 34
5.1.2 實驗設計 …………………………………………………………… 34
5.1.3 試驗結果分析及確認實驗 ………………………………………… 36
5.2 測試VRPTW題庫 ……………………………………………………… 39
5.3 測試VRPBTW題庫 ……………………………………………………… 39
第六章 結論與未來研究 ………………………………………………… 45
6.1 結論 …………………………………………………………………… 45
6.2 未來研究 ……………………………………………………………… 45
參考文獻 …………………………………………………………………… 47
附錄一 Solomon題庫目前已初版最佳解 …..…………………………… 50
附錄二 本研究Solomon題庫最佳解途程 .……………………………… 52

參考文獻
申生元，「時窗限制車輛途程問題」，交通大學工業工程與管理系博士論
文，1999。
林書銘，「塔布搜尋法於含時窗與裝載限制車輛途程問題解算之研究」，
元智大學工業工程所碩士論文，1998。
敖君瑋，「禁制搜尋法於軟性時窗限制之車輛途程問題研究」，元智大學
工業工程所碩士論文，1999。
黃聖峰，「考量回程撿收之車輛途程問題研究」，大葉大學工業工程所碩
士論文，1999。
廖亮富，「含時窗限制多部車車輛途程問題解算之研究」，元智大學工業
工程所碩士論文，1998。
鄭春生，「品質管理」，育有圖書有限公司，1997，初版。
鍾清章等，「品質工程（田口方法）」，中華民國品質管制學會，1994，
初版。
Bowerman, R. L., P. H. Calamai and G. B. Hall,“The
Spacefilling Curve with Optimal Partition Heuristic for
Vehicle Routing Problem,”European Journal of Operational
Research, 1994, Vol. 76, pp. 128-142.
Desrochers, M. and T. W. Verhoog,“A New Heuristic for the
Fleet Size and Mix Vehicle Routing Problem,”Computers Ops.
Res., 1991, Vol. 18, No. 3, pp. 263-274.
Duhamel, C., J. Potvin and J. Rousseau,“A Tabu Search
Heuristic for the Vehicle Routing Problem with Backhauls
and Time Windows,”Transportation Science, 1997, Vol. 31,
No. 1, pp. 49-59.
Gendreau, M., A. Herts, G. Laporte and M. Stan,“A Generalized
Insertion Heuristic for the Traveling Salesman Problem with
Time Windows,”Operations Research, 1998, Vol. 43, No. 3,
pp. 330-335.
Goeschalcky, M. and C. Jacobs-Blecha ,“The Vehicle Routing
Problem with Backhauls,”European Journal of Operational
Research, 1998,Vol. 42, pp. 39-51
Gur, M.,“Vehicle Routing with Pick-up and Delivery Tour
Partitioning Heuristics,”Computers Ind. Engng., 1998, Vol.
34, No. 3, pp. 669-684.
Kontoravdis, G. and J. F. Bard,“A GRASP for the Vehicle
Routing Problem with Time Windows,”ORSA Journal on
Computing, 1995, Vol. 7, No. 1, pp. 10-23.
Nagraj, B.,“Simple Heuristics for the Vehicle Routing Problem
with Soft Time Windows,”Journal of the Operational
Research Society, 1993,Vol. 44, No. 3, pp. 279-287.
Potvin, J. and J. Rousseau,“A Parallel Route Building
Algorithm for the Vehicle Routing and Scheduling Problem
with Time Windows,”European Journal of Operational
Research, 1993, Vol. 66, pp. 331-340.
Potvin, J., C. Duhamel and F. Guertin,“A Genetic Algorithm for
Vehicle Routing with Backhauls,”Applied Intelligence,
1996, Vol. 6, pp. 345-355.
Russell, A. R.,“Hybrid Heuristic for the Vehicle Routing
Problem with Time Windows,”Transportation Science, 1995,
Vol. 29, No. 2, pp. 156-166.
Said, S.,“Incorporating Vehicle Routing into the Vehicle Fleet
Composition Problem,”European Journal of Operational
Research, 1993,Vol. 66, pp. 313-330.
Shoshana, A.,“The Vehicle Routing Problem with Delivery and
Back—Haul Options,”Naval Research Logistic, 1996, Vol.
43, pp. 669-684.
Solomon, M. M.,“Algorithms for the Vehicle Routing and
Scheduling Problems with Time Window Constraints,”
Operations Research, 1987, Vol. 35, No. 2, pp. 254-265.
Taillard, E.,“Parallel Iterative Search Methods for Vehicle
Routing Problems,”Networks, 1993, Vol. 23, pp. 661-673.
Taillard, E. and P. Badeau,“A Tabu Search Heuristic for the
Vehicle Routing Problem with Soft Time Windows,”
Transportation Science, 1997,Vol. 31, No. 2, pp. 170-183.
Thangiah, S. R., J. Potvin and T. Sun,“Heuristic Approaches to
Vehicle Routing with Backhauls and Time Windows,”Computers
Ops. Res., 1996, Vol. 23, No. 11, 1996, pp. 1043-1057.
Toth, P. and D. Vigo,“An Exact Algorithm for the Vehicle
Routing Problem with Backhauls,”Transportation Science,
1997, Vol. 31, No. 4, pp.372-385.
Toth, P. and D. Vigo,“A Heuristic Algorithm for the Symmetric
and Asymmetric Vehicle Routing Problems with Bakhauls,”
European Journal of Operational Research, 1999, Vol. 113,
pp. 528-543.
Yiannis, A K., B. P. Powell, and M. M. Solomon,“An
Optimization—Based Heuristic for Vehicle Routing and
Scheduling with Soft Time Window Constraints,”
Transportation Science, 1992, Vol. 26, No. 2,
pp. 69-85.