時窗限制虛擬場站接駁補貨車輛途程問題之研究

Linehaul-Feeder Vehicle Routing Problem with Virtual Depots and Time Windows

許家筠(Chia-yuan Hsu)

指導教授 ： 陳惠國

國立中央大學/工學院/土木工程學系/碩士(2008年)

摘要

台灣都市地區部分巷道狹窄，致使大型貨車進出、臨時停車皆不容易；為因應此問題，已有部分物流業者利用載貨量大但機動性較低之大車(如貨車)搭配機動性高但載貨量較小之小車(如機車)進行接駁補貨的配送服務，針對配送方式，本研究提出「時窗限制之虛擬場站接駁補貨車輛途程問題」(linehaul-feeder vehicle routing problem with virtual depots and time windows, LFVRP-VD-TW)，即大車、小車須在客戶預期收取貨物的時段內各自完成每一客戶的貨物配送，當小車送貨完畢時，除了返回實際場站(physical depot, PD)補貨亦可選擇直接前往大車所在之虛擬場站(virtual depot)進行補貨，補貨完畢小車即可再進行配送服務，節省小車往返場站之次數、距離與時間。
本研究根據其問題特性建構數學模型，並發展出一套建構初始途程模組與途程改善模組之兩階段啟發式演算法，其中，途程改善模組以禁制搜尋法為主軸，並結合路線間節點1-1交換法。根據LFVRP-VD(何宗育，2007)研究，從The VRP Web題庫裡所挑選出的17題範例，作為本研究的範例基礎，並針對本研究之問題特性設計為LFVRP-VD-TW之測試例題並作測試結果分析。測試結果可知，17題範例的平均目標函數值為2673.15，平均運算時間54.61秒，改善率達10.59%。

關鍵字

接駁補貨 ； 實際場站 ； 虛擬場站 ； 禁制搜尋法

並列摘要

Due to the scarcity of land resources for the access limitations of local streets for accommodating large vehicles in urban areas, some home delivery companies have invented a new type of vehicle routing and operations which involves two types of vehicles. This problem can be regarded as an extension of the vehicle routing problem and is named as the linehaul-feeder vehicle routing problem with virtual depots and time windows (LFVRP-VD-TW). It means that a big vehicle departs from the physical depot (PD) and traverses all virtual depots (VD), whereas a set of small vehicles performs delivery to customers and, if necessary, reloads the commodity either from the PD or from the big vehicle at a VD before continuing their work. During the operation, all of vehicles must perform delivery during the time window of the customers.
In this research, the LFVRP-VD-TW is formally formulated as a mixed integer programming problem. In addition, a meta-heuristics which includes tour construction and tour improvement procedure which consists of the tabu search and the exchange method is proposed for solving it. Seventeen test problems modified from the LFVRP-VD (Chen et al., 2007) benchmark instances were extensively examined. The results show that the average objective value of the seventeen test problems is 2673.15, and it could be reduced 10.59% by the tour improvement procedure.

並列關鍵字

Linehaul-feeder ； Tabu search ； Virtual depot ； Physical depot

參考文獻

1. 王元鵬(2006)，仿水流離散優化演算法，國立台灣大學工業工程學研究所碩士論文，台北。

2. 毛皖亭(2007)，線上動態車輛巡迴路線演算法之發展：滾動平面法之應用，國立成功大學交通管理科學研究所碩士論文，台南。

6. Brandao, J. and Mercer, A. (1997), “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem,” European Journal of Operational Research, Vol. 100, No. 1, pp. 180-191.

7. Bräysy, O. and Gendreau, M. (2005a), “Vehicle routing problem with time windows, part I: route construction and local search algorithms,” Transportation Science, Vol. 39, No. 1, pp. 104-118.

8. Bräysy, O. and Gendreau, M. (2005b), “Vehicle routing problem with time windows, part II: metaheuristics,” Transportation Science, Vol. 39, No. 1, pp. 119-139.