三起點迭代區域搜尋法求解兼具自有與委外之車輛路線問題

A Tri-Start Iterated Local Search Algorithm for the Vehicle Routing Problem with Private Fleet and Common Carrier

張雅婷(Ya-Ting Chang)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸與物流管理學系/碩士(2017年)

摘要

兼具自有與委外之車輛路線問題 (Vehicle Routing Problem with private fleet and common carriers, VRPPC)考慮現今企業除了自有車隊配送顧客外，亦可付費委託外部第三方物流公司來服務的最佳配送方式，是近年重要的物流課題之一。本研究以迭代區域搜尋 (Iterated Local Search, ILS)巨集啟發式解法為架構求解VRPPC問題。首先同時考慮路線插入、新增路線與委外服務三種方式進行起始解之構建; 並以系統性與隨機性方法構建三組起始解，以增加求解廣度。再以八組交換改善法之鄰域構成一個隨機變動鄰域改善模組(Randomized Variable Neighborhood Descent, RVND) 加強深度搜尋能力，以進行路線改善。最後搭配擾動機制反覆進行搜尋，以強化求解廣度。本研究使用C#撰寫程式，對現有國際標竿題庫進行測試; 測試結果在68題標竿例題中求得38最佳解，包括32題最新的文獻最佳解，總平均誤差為0.11。

關鍵字

具自有與委外之車輛路線問題 ； 迭代區域搜尋 ； 隨機變動鄰域改善模組

並列摘要

The Vehicle Routing Problem with Private Fleet and Common Carrier (VRPPC), which considers the best use of both owned fleet and outside logistics service provider, is an important issue for modern logistics operation. This paper applies an Iterated Local Search metaheuristic approach to solve the VRPPC. First, we simultaneously consider node-insertion, route-addition, and the common carrier assignment to construct our initial solutions. Both systematic and random procedures are adopted to form three sets of initial solution to increase the diversification of our search. Then we use a module of Randomized Variable Neighborhood Descent (RVND), which includes eight exchange neighborhoods, to intensify the improvement of the solutions. Finally, a perturbation mechanism is applied to further diversify our search of solution. We have coded our algorithms in C# and tested with all existing VRPPC instance sets. The results show that, out of 68 benchmark instances tested, we have found 38 best solutions including 32 new ones. The average deviation is 0.11%.

並列關鍵字

VRPPC ； ILS ； RVND

參考文獻

[25] 吳善哲 ，「兼具自有與委外之車輛路線問題：巨集啟發式解法之研究」，國立交通大學，碩士論文，民國105年

[26] 鄧全斌 ，「應用迭代區域搜尋法求解混和封閉與開放車輛路線問題」，國立交通大學，碩士論文，民國104年

[17] Lourenço, H., Martin, O., & Stützle, T., "Iterated local search", In F. Glover & G. Kochenberger (Eds.), Handbook of Metaheuristics, Vol. 57, pp. 320-353, Springer US. 2003

[2] Bolduc, M. C., Renaud, J., Boctor, F., & Laporte, G., "A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers", Journal of Operations Research Societies, Vol. 59, No. 6, pp. 776-787, 2008.

[3] Bräysy, O., Hasle, G., & Dullaert, W., "A multi-start local search algorithm for the vehicle routing problem with time windows". European Journal of Operational Research, Vol. 159, No.3, pp. 586-605, 2004.