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

Abstract

混合封閉與開放車輛路線問題 (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%.