混合封閉與開放車輛路線問題 (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 the conventional Vehicle Routing Problem (VRP). The COMVRP considers how a company, which has insufficient owned vehicles, to best dispatch both owned vehicles and hired vehicles from outside. In this article, we propose an Iterated Local Search (ILS) metaheuristic approach to solve the COMVRP. First, multiple initial 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, and a novel Open to Close (O2C) operator that we have designed specifically for the COMVRP. Finally, a perturbation is applied in each iterated procedure to enhance the diversity of the search. Our proposed algorithms are tested with two sets of benchmark instances. Results show that, out of 42 instances tested, we have found 24 best known solutions (BKS) and improved 16 BKS. The average deviation is -0.86%.