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

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

混合封閉與開放車輛路線問題 (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) 模組進行路線改善。本研究之RVND 模組除採用七種傳統交換法外，並針對問題之特性設計一套新的Open to Close (O2C) 模組。最後搭配擾動機制反覆進行搜尋以提升求解的廣度。本研究以兩組國際標竿題庫共42 題例題進行測試，其中求得24 題已知最佳解，突破16 題，平均誤差為-0.86%。

The Close-Open Mixed Vehicle Routing Problem (COMVRP) is a variant of theconventional Vehicle Routing Problem (VRP). The COMVRP considers how acompany, which has insufficient owned vehicles, to best dispatch both ownedvehicles and hired vehicles from outside. In this article, we propose an IteratedLocal Search (ILS) metaheuristic approach to solve the COMVRP. First, multipleinitial solutions are generated by a Node Insertion Route Addition (NIRA) procedure.These solutions are then improved by a Randomized Variable Neighborhood Descent(RVND) module. This module includes seven conventional exchange operators, anda novel Open to Close (O2C) operator that we have designed specifically for theCOMVRP. Finally, a perturbation is applied in each iterated procedure to enhancethe diversity of the search. Our proposed algorithms are tested with two sets ofbenchmark instances. Results show that, out of 42 instances tested, we have found24 best known solutions (BKS) and improved 16 BKS. The average deviation is-0.86%.