具時窗之多趟次車輛途程問題

Multi-trip Vehicle Routing Problem with Time Windows

林惠民(Hui-Min Lin)

指導教授 ： 申生元

元智大學/資訊學院/資訊管理學系/碩士(2002年)

摘要

關於具時窗之多趟次車輛途程問題，其問題的特徵在於：(1)車輛配送服務方面，除考慮顧客需求數量總和需滿足車輛容量限制外，尚需滿足顧客指定的配送時間內到達之時窗限制；(2)在排程方面，允許車輛具有多趟次來回場站進行配送服務的彈性。本論文係針對單一場站及同類型車隊之研究前題下，進行具時窗多趟次路線規劃演算法的發展。
本研究從不同思維角度，設計四種以插入虛擬場站為主的多趟次路線構建方法。在解題方法上分為兩個階段，第一階段為路線構建階段，使用多趟次路線構建方法求得初始路線解，演算法之主要差異係基於虛擬場站於路線構建中之插入時機、構建路線過程中是否允許非可行路線及是否須估計起始車輛數等因子決定；第二階段為路線改善階段，以禁忌搜尋法為主要架構，結合相關路線改善的局部搜尋法以及路線調整的多趟次路線構建方法。在演算法之發展上掌握多趟次的特性，並兼顧求解品質與計算時間。測試結果顯示本論文所提出之具時窗多趟次路線演算法相較於傳統具時窗單趟次之演算法，有明顯效益提升。
目前關於此多趟次方面研究在學術上較少被探討，但在實務應用方面，對於如何降低營運成本及善加使用車隊服務顧客，卻是運輸管理人員處於電子商務時代所必須面臨的挑戰。本研究所發展的四種演算法試提供不同的解題思維與建議，期望對於車輛途程問題之未來研究及實務應用上有所助益。

關鍵字

多趟次車輛途成問題 ； 禁忌搜尋法 ； 時間窗 ； 虛擬場站

並列摘要

The multi-trip vehicle routing problem with time windows is a variant of the standard VRPTW in which a tour consisting of several trips during a given planning period is served by the same vehicle. In this thesis, we adopt conventional two-phase approach, tour construction and tour improvement, as a basic operational framework. We propose four dummy depot insertion-based algorithms in construction of a set of feasible tours as an initial solution, then followed by applying a tabu search heuristic in the improvement phase.
The primary distinctions among the four different tour construction algorithms are summarized as follows.
(1)When should we insert dummy depots into a set of tours?
(2)Do we need an estimator to the number of vehicles required during the construction phase?
(3)Do we maintain tour feasibility all the way during the tour construction phase?
For computational study, Solomon’s data sets originally used for standard VRPTW were modified with different settings of capacity and time windows. Extensive computational results reported in the thesis indicate that our algorithms can yield high quality solutions on a series of test problems, in particular to the highly capacity-constrained problems.

並列關鍵字

Multi-trip Vehicle Routing Problem ； Tabu Search ； Time Windows ； Dummy Depot

參考文獻

[1] Brandao, J. and Mercer, A., "A tabu search algorithm for the multi-trip vehicle routing and scheduling problem", European Journal of Operations Research 100, 180-191, 1997.

[4] Clarke, G. and Wright, W.J., “Scheduling of vehicles from a central depot to a number of delivery points” Operations Research 12, 568-581, 1964.

[5] Fisher, M.L., "Optimal solution of vehicle routing problems using minimum k-trees ", Operations Research 42, 626-642, 1994.

[6] Glover, F., “Tabu Search-Part I”, Journal on Computing 1, 190-206, 1989.

[7] Kolen, A.W.J., Rinnooy, K. and Trienekens, J.M., “Vehicle Routing with Time Windows”, Operations Research 35, 266-273, 1987.