利用迭代區域搜尋法求解中繼補貨站車輛路線問題之研究

An Iterated Local Search Heuristic for the Vehicle Routing Problem with Intermediate Replenishment Facilities

易鼐恩(Nai-En Yi)

指導教授 ： 韓復華

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

摘要

中繼補貨站車輛路線問題(Vehicle Routing Problem with Intermediate Replenishment Facilities, VRPIRF)是由傳統車輛路線問題(Vehicle Routing Problem, VRP)演化而來。VRPIRF透過具補貨(卸貨)功能的中繼站來提高車輛使用率，增加車輛路線的服務能量，降低物流成本; 故在實務的應用上可有效提昇企業競爭力。本研究新設計一個鄰域改善中繼補貨站位置的RD_ReAssignment的程序，並以迭代區域搜尋法(Iterated Local Search, ILS)之巨集啟發式解法為基礎，對VRPIRF構建一套稱之為RD_ILS (ILS with RD_ReAssignment)的求解演算法。
RD_ILS求解架構主要可分為三階段：首先採用巨網切割法構建雙重啟始解；再分別以隨機變動鄰域尋優法(Randomized Variable Neighborhood Descent, RVND)模組進行改善；其中包含八種傳統交換法，並搭配本研究針對VRPIRF的中繼站指派所設計的RD_ReAssignment來加強深度搜尋。隨後再依顧客點、路段及路線不同層次，設計三種擾動方式，進行反覆的RVND搜尋以提升求解的廣度及品質。
本研究以三套VRPIRF國際標竿題庫對RD_ILS演算法進行測試。結果發現在76個標竿題測題中，本研究可求得18題巳知最佳解 (Best Known Solutions, BKS)，並且突破33題; 與BKS的 平均誤差為 -0.52%。

關鍵字

中繼補貨站車輛路線問題 ； 迭代區域搜尋演算法 ； 隨機變動鄰域尋優法

並列摘要

Vehicle Routing Problem with intermediate replenishment facilities (VRPIRF) is an extension of the classical Vehicle Routing Problem. Unlike the VRP which considers a single depot, the VRPIRF considers multiple replenishment depots (RD) with unlimited capacity, capacity of vehicles and limitation of total duration. The best decisions of vehicle routing and the use of those intermediate RDs in the VRPIRF would help the business to further reduce the logistics cost and gain more competitive advantage.
In this thesis, we propose a heuristic approach called RD_ILS for solving the VRPIRF. This RD_ILS approach is based on the Iterated Local Search (ILS) metaheuristic framework. The proposed RD_ILS approach consists of three modules. First, we build and split giant tours to construct multiple initial solutions. Then, a Randomized Variable Neighborhood Descent (RVND) module is applied for solution improvement. This RVND module includes eight conventional exchange operators each is conducted with a novel operator RD_ReAssignment to enhance the intensification of search. Finally, we implement three types of perturbations for customers, segments and routes to enrich the diversification of search.
We have tested the RD_ILS algorithms with three VRPIRF benchmark problem sets. The results show that, out of 76 instances tested, our proposed approach has found 18 best known solutions (BKS) and 33 new best solutions; the average deviation from the BKS is -0.52%.

並列關鍵字

Vehicle Routing Problem with intermediate replenishment facilities (VRPIRF) ； Iterated Local Search (ILS) ； Randomized Variable Neighborhood Descent (RVND)

參考文獻

[1] Clarke, G. and Wright, J. W. “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points.” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.

[2] Crevier, B., Cordeau, J. F. and Laporte, G. “The Multi-depot Vehicle Routing Problem with Inter-depot Routes.” Journal, Vol., pp. 756-773, 2007.

[3] Dantzig, G. B. and Ramser, R. H. “The Truck Dispatching Problem.” Journal, Vol. 6, pp. 80-91, 1959.

[4] Hemmelmayr, V., Doerner, K. F., Hartl and R.F. “A heuristic solution method for node routing based solid waste collection problems.” Journal, Vol. 19, pp. 129-156, 2013.

[5] Lin, S. “Computer Solutions of the Traveling Salesman Problem.” Journal, Vol. 44, pp. 2245-2269, 1965.