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

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

10.6402/TPJ.200812.0405

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

時窗限制回程取貨車輛路線問題 ； 巨集啓發式解法 ； 兩階段回溯式門檻接受法 ； Vehicle routing problem with backhauls and time windows VRPBTW ； Meta-heuristics ； Two-phase backtracking threshold accepting TBTA

運輸計劃季刊

37卷4期（2008 / 12 / 30）

405 - 429

繁體中文

時窗限制回程取貨車輛路線問題(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.

1. Casco, D,Golden, B.,Wasil, E.,Assad, A. (eds.)(1988).Vehicle Routing: Methods and Studies.Amsterdam:North-Holland.
2. Cheung, R.,Hang, D.(2003).Multi-Attribute Label Matching Algorithms for Vehicle Routing Problems with Time Windows and Backhauls.IIE Transactions,35,191-205.
3. Cho, Y. J.,Wang, S. D.(2005).A Threshold Accepting Meta-Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows.Journal of the Eastern Asia Society for Transportation Studies,6,3022-3037.
4. 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
5. Dueck, G.,Scheuer, T.(1990).Threshold Accepting: A General Purpose Optimization Algorithm Appearing Superior to Simulated Annealing.Journal of Computational Physics,90,161-175.
6. Duhamel, C.,Potvin, J.,Rousseau, J.(1997).A Tabu Search Heuristic for the Vehicle Routing Problem with Backhauls and Time Windows.Transportation Science,31(1),49-59.
7. Gélinas, S.,Desrochers, M.,Desrosiers, J.,Solomon, M.(1995).A New Branching Strategy for Time Constrained Routing Problems with Application to Backhauling.Annals of Operations Research,61,91-109.
8. Hasama, T.,Kokubugata, H.,Kawashima, H.(1998).Proceedings of the 5th World Congress on Intelligent Transport Systems (ITS).ITS Korea:
9. Lin, C. K. Y.,Haley, K. B.,Sparks, C.(1995).A Comparative Study of Both Standard and Adaptive Versions of Threshold Accepting and Simulated Annealing Algorithms in Three Scheduling Problems.European Journal of Operational Research,83,330-346.
10. Osman, I.(1993).Metastrategy Simulation Annealing and Tabu Search Algorithms for the Vehicle Routing and Scheduling Problem with Time Windows.European Journal of Operational Research,41,421-451.
11. Potvin J.,Duhamel, C.,Guertin, F.(1996).A Genetic Algorithms for Vehicle Routing Problem with Backhauling.Applied Intelligence,6,345-355.
12. Rego, C.(2001).Node-Ejection Chains for the Vehicle Routing Problem: Sequential and Parallel Algorithms.Parallel Computing,27,201-222.
13. Reimann, M.,Doerner, K.,Hartl, R.(2002).Insertion Based Ants for Vehicle Routing Problems with Backhauls and Time Windows.LNCS,2463,135-148.
14. Reimann, M.,Ulrich, H.(2006).Comparing Backhauling Strategies in Vehicle Routing Using Ant Colony Optimization.Central European Journal of Operations Research,14(2),105-123.
15. Ropke, S.,Pisinger, D.(2006).A Unified Heuristic for a Large Class of Vehicle Routing Problems with Backhauls.European Journal of Operational Research,171,750-775.
16. Solomon, M.(1983).University of Pennsylvania.
17. Tarantilis, C.,Kiranoudis, C.,Vassiliadis, V.(2003).A List Based Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem.Journal of the Operational Society,54,65-71.
18. Tarantilis, C,Kiranoudis, C.,Vassiliadis, V.(2004).A Threshold Accepting Metaheuristic for the Heterogeneous Fixed Fleet Vehicle Routing Problem.European Journal of Operation Research,152,148-158.
19. Thangiah, R.,Potvin, J.,Sun, T.(1996).Heuristic Approach to Vehicle Routing with Backhauls and Time Windows.Computers and Operations Research,23(11),1043-1057.
20. Yano, C.,Chan, T.,Richter, L.,Cutler, T.,Murty, K.,McGettigan, D.(1987).Vehicle Routing at Quality Stores.Interfaces,17(2),52-63.
21. Zhong, Y.,Cole, M.(2005).A Vehicle Routing Problem with Backhauls and Time Windows: A Guided Local Search Solution.Transportation Research Part E,41,131-144.
22. 申生元(1999)。博士論文(博士論文)。國立交通大學工業工程與管理研究所。
23. 卓裕仁、王生德(2004)。第一屆臺灣作業研究學會學術研討會暨2004年科技與管理學術研討會論文集。臺灣作業研究學會。
24. 卓裕仁、王生德(2003)。中華民國運輸學會第18屆學術論文研討會論文集。中華民國運輸學會。

1. 韓復華、陳仲豪(2010)。應用時窗離散策略與可回溯式門檻接受法求解VRPBTW問題之研究。運輸學刊，22(3)，285-306。
2. 韓復華、呂泓儒、朱佑旌(2011)。以改良型回溯門檻接受法求解回程取貨車輛路線問題之研究。運輸計劃季刊，40(2)，213-232。