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

Abstract

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