關於具時窗之多趟次車輛途程問題,其問題的特徵在於:(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.