應用迭代區域搜尋法求解混合封閉與開放車輛路線問題

An Iterated Local Search heuristic for the Close-Open Mixed Vehicle Routing Problem

鄧全斌(Chuan-Pin Teng)

指導教授 ： 韓復華

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

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

摘要

混合封閉與開放車輛路線問題 (Close-Open Mixed Vehicle Routing Problem, COMVRP) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 的衍生問題。考慮在公司自有車隊數量不足，為了要滿足所有客戶需求，便可利用委外車隊進行服務。此類問題較能符合物流配送作業的實務情況，但目前國際上COMVRP相關文獻並未多見，因此本研究欲以迭代區域搜尋 (Iterated Local Search, ILS) 之巨集啟發式解法求解COMVRP。
首先以NIRA (Node Insertion Route Addition) 構建多重起始解，各起始解再以隨機變動鄰域尋優 (Randomized Variable Neighborhood Descent, RVND) 模組進行路線改善，包含七種傳統交換法與本研究針對COMVRP問題特性所設計的Open to Close (O2C) 改善模組。最後搭配擾動機制反覆進行搜尋以提升求解的廣度。
本研究以兩組國際標竿題庫共42題例題進行測試，其中求得24題已知最佳解，突破16題，平均誤差為-0.86%。

關鍵字

混合封閉與開放車輛路線問題 ； 迭代區域搜尋 ； 巨集啟發式解法 ； 隨機變動鄰域尋優

並列摘要

The Close-Open Mixed Vehicle Routing Problem (COMVRP) is a variant of the conventional Vehicle Routing Problem (VRP). Consider the case when the private car of company is insufficient. In order to meet the demand of customer, the company can use external collaborative carrier to serve its customer. COMVRP is more suitable for the work of logistics distribution, but there was just a little study on COMVRP. Therefore, we are going to develop an Iterated Local Search (ILS) Metaheuristic to solve COMVRP.
First, we use Node Insertion Route Addition (NIRA) to build multi-start solution. And then use Randomized Variable Neighborhood Descent (RVND), which includes seven traditional operators and the Open to Close (O2C) which we were aimed at the characteristic of COMVRP to improve the solution. Finally, it repeats search with perturbation mechanism to improve the breadth of solution space.
Our proposed algorithm was tested on two sets of 42 benchmark instances. Results showed that our proposed algorithm on benchmark instances can generate 24 best known solutions (BKS) and 16 new BKS. The average deviation is -0.86%.

並列關鍵字

Close-Open Mixed Vehicle Routing Problem ； Iterated Local Search ； Metaheuristic ； Randomized Variable Neighborhood Descent

參考文獻

[2] Ball, M. O., Golden, B. L., Assad, A. A., and Bodin, L. D., "Planning for truck fleet size in the presence of a common-carrier option", Decision Sciences, Vol. 14, pp. 103-120, 1983.

[3] Bolduc, M. C., Renaud, J., Boctor, F., and Laporte, G., "A perturbation metaheuristic for the vehicle routing problem with private fleet and common carriers", The Journal of the Operational Research Society, Vol. 59, pp. 776-787, 2008.

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

[5] Côté, J.-F., and Potvin, J.-Y., "A tabu search heuristic for the vehicle routing problem with private fleet and common carrier", European Journal of Operational Research, Vol. 159, pp. 464-469, 2009.

[6] Christofides, N., and Eilon, S., "An algorithm for the vehicle dispatching problem", Operational Research Quarterly, Vol. 20, pp. 309-318, 1969.