以改良型可回溯式門檻接受法求解回程取貨車輛路線問題之研究

Using Modified BATA to Solve Vehicle Routing Problem with Backhauls

呂泓儒(Hong-Ru Lu)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸科技與管理學系/碩士(2009年)

https://doi.org/10.6842/NCTU.2009.00568

摘要

回程取貨車輛路線問題(vehicle routing problem with backhauls, VRPB) 是車輛路線問題 (vehicle routing problem, VRP) 的延伸，屬於解題複雜度高的NP-hard問題。其假設車輛必須先服務完所有送貨點顧客，之後利用回程的空車再開始服務取貨點顧客。此類型問題在相關產業的物流配送上應具有相當價值。
可回溯式門檻接受法(Backtracking Adaptive Threshold Accepting, BATA)是由Tarantilis et al. (2001) 首先提出，對於門檻回溯比率值 b 僅考慮b < 1的情形。本研究提出改良型可回溯式門檻接受法(Modified Backtracking Adaptive Threshold Accepting, MBATA)，除延用 b > 1 之門檻回溯公式(廖昱傑，2007)以外，另在門檻回溯機制中加入兩極跳躍法（Flip-Flop Method, FF）的概念，其目的即在於當陷入區域最佳解而難以改善時，使其在一個可接受的範圍(門檻值)內進行反向操作的搜尋，如此能增加搜尋機制的廣度。
在求解績效評估方面，本研究以Goetschalckx and Jocabs-Blencha (1989)的62題國際標竿例題進行測試。利用C#語言進行程式撰寫，在Intel(R)雙核心CPU為2.00GHz的個人電腦進行測試。就平均誤差率而言，本研究提出的MBATA比傳統的BATA在所有測試組合中，有15%結果相同，其餘 85% 均有較佳之結果。本研究也對MBATA進行參數測試，並提出建議之參數。最後再與近年來國際期刊之文獻進行比較。本研究62題標竿例題中共有37題找到文獻已知最佳解，而各題最佳結果與已知最佳解平均誤差僅0.16%，平均每題運算時間4.68秒。結果顯示，MBATA在求解VRPB問題上相當具有潛力。

關鍵字

門檻接受法 ； 可回溯式門檻接受法 ； 改良型可回溯式門檻接受法 ； 回程取貨車輛路線問題 ； 兩極跳躍法

並列摘要

Vehicle Routing Problem with Backhauls (VRPB), an extension of the classical Vehicle Routing Problem, is a very complicated NP-Hard problem. The VRPB assumes that all linehaul customers should be visited before any backhaul customer. Successful applications of the VRPB in real-world distribution will improve the performance of logistics in the related industry.
Backtracking Adaptive Threshold Accepting (BATA) was first proposed by Tarantilis et al. (2001), which only considers backtracking factor b < 1. In this paper, we proposed a Modified Backtracking Adaptive Threshold Accepting (MBATA) approach considering the case of b > 1. We also applied the concept of Flip-Flop Method (FF) in backtracking mechanism to enhance the diversification in the search process.
The 62 benchmark problems described by Goetschalckx and Jocabs-Blencha (1989) were selected for the evaluation of our meta-heuristics. Our proposed heuristics were coded in Visual C# and tested on a Intel(R) Core(TM)2 CPU 2.00GHz personal computer. We found that our proposed MBATA heuristics outperformed traditional BATA in the average deviation for 85% of all the cases we tested. As compared to the 62 benchmark results reported in recent literatures, we found 37 best-known solutions and the average deviation is merely 0.16%. The average computer time per instance is 4.68 CPU seconds which demonstrated the efficiency and potential applicability of our proposed method.

並列關鍵字

Threshold Accepting (TA) ； Backtracking Adaptive Threshold Accepting (BATA) ； Modified Backtracking Adaptive Threshold Accepting (MBATA) ； Vehicle Routing Problem with Backhauls (VRPB) ； Flip-Flop Method (FF)

參考文獻

42. 卓裕仁、朱佑旌，「兩階段回溯式門檻接受法求解時窗限制回程取貨車輛路線問題之研究」，運輸計畫季刊，第三十七卷，第四期，頁405-430，民國97年。

1. Anily, S., “The Vehicle Routing Problem with Delivery and Backhaul Options,” Naval Research Logistics, Vol. 43, pp. 415-434, 1996.

3. Brandao, J., “A new tabu search algorithm for the vehicle routing problem with backhauls,” European Journal of Operational Research, Vol. 173, pp. 540-555, 2006.

4. Braysy, O. and Gendreau, M., “Vehicle Routing Problem with Time Windows, Part I: Route Construction and Local Search Algorithms,” Transportation Science, Vol. 39, pp. 104-118, 2005.

5. Braysy, O. and Gendreau, M., “Vehicle Routing Problem with Time Windows, Part II: Metaheuristics,” Transportation Science, Vol. 39, pp. 119-139, 2005.