兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究

A Two-Phase Backtracking Threshold Accepting Meta-Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows

卓裕仁(Yuh-Jen Cho) ； 朱佑旌(You-Jing Chu)

《運輸計劃季刊》 37卷4期 (2008/12) Pp. 405-429

https://doi.org/10.6402/TPJ.200812.0405

摘要

時窗限制回程取貨車輛路線問題(vehicle routing problem with backhaul and time windows, VRPBTW)是車輛路線問題(vehicle routing problem, VRP)的延伸，屬於解題複雜度很高的NP-hard問題，其在物流配送實務上具有很高的應用價值。本研究結合門檻接受法(threshold accepting, TA)與傳統啟發式方法，設計一套可求解VRPBTW之兩階段回溯式門檻接受法(two-phase backtracking threshold accepting, TBTA)，並採用15題國際標竿例題進行測試，以分析此TBTA巨集啟發式解法之解題績效。測試結果發現：車輛數之平均誤差百分比為3.52%，行駛時間之平均誤差百分比為2.81%，CPU之平均運算時間為33.69秒；此結果顯示TBTA法在求解VRPBTW上具有應用潛力。

關鍵字

時窗限制回程取貨車輛路線問題 ； 巨集啓發式解法 ； 兩階段回溯式門檻接受法

並列摘要

The vehicle routing problem with backhauls and time windows (VRPBTW), which simultaneously considers the operations of delivery and pickup, is a variant of the classical vehicle routing problem (VRP). Successful application of the VRPBTW in real-world distribution will improve the performance of logistics. Due to the NP-hard complexity of VRPBTW, the most solution methods are heuristics and meta-heuristics. This paper aims to develop a two-phase backtracking threshold accepting (TBTA) meta-heuristic approach, which combines the threshold accepting (TA) meta-strategy and the traditional local search algorithms, to solve the VRPBTW. We adopted fifteen VRPBTW benchmark instances to test and analyze the performance of the proposed TBTA meta-heuristic. The average error percentages of TBTA are 3.52% for the objective of fleet size and 2.81% for the objective of traveling time. Moreover, the average value of CPU running time is merely 33.69 seconds. Computational results implied that the TBTA actually provides an efficient tool for VRPBTW applications.

並列關鍵字

Vehicle routing problem with backhauls and time windows VRPBTW ； Meta-heuristics ； Two-phase backtracking threshold accepting TBTA

參考文獻

Yano, C.,Chan, T.,Richter, L.,Cutler, T.,Murty, K.,McGettigan, D.(1987).Vehicle Routing at Quality Stores.Interfaces.17(2),52-63.

Casco, D,Golden, B.,Wasil, E.,Assad, A. (eds.)(1988).Vehicle Routing: Methods and Studies.Amsterdam:North-Holland.

卓裕仁、王生德(2003)。中華民國運輸學會第18屆學術論文研討會論文集。中華民國運輸學會。

卓裕仁、王生德(2004)。第一屆臺灣作業研究學會學術研討會暨2004年科技與管理學術研討會論文集。臺灣作業研究學會。

Deif, I.,Bodin, L.(1984).Extension of the Clarke-Wright Algorithms for Solving the Vehicle Routing with Backhauling.Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management.(Proceedings of the Babson Conference on Software Uses in Transportation and Logistics Management).