利用迭代區域搜尋法求解綠能車輛路線問題之研究

Abstract

綠能車輛路線問題 (Green Vehicle Routing Problem, G-VRP) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 的衍生問題；該問題考慮替代能源車隊，在旅行時間與油箱容量所造成的哩程限制下，利用若干已知的能源補充站(Alternative Fuel Station, AFS)，以最小的總旅行距離服務完所有的顧客。本研究以迭代區域搜尋 (Iterated Local Search, ILS) 之巨集啟發式解法為基礎，對G-VRP建立有效之求解工具。 首先以平行式最遠起點最省插入法構建起始解，再以隨機變動鄰域搜尋 (Randomized Variable Neighborhood Descent, RVND) 模組進行路線改善；其中包含七種傳統交換法，與本研究針對G-VRP具有AFS之特性所設計的1-0_AFS以及AFS Relocation兩種鄰域搜尋法。最後搭配擾動機制反覆進行搜尋以提升求解的廣度。 本研究以C#程式語言撰寫G-ILS演算法，對兩組國際標竿題庫共52題例題進行測試，結果發現51題最佳結果，其中突破7題現有文獻最佳結果，總平均誤差為-0.02%。

Green vehicle routing problem (G-VRP) is an extension of the classical Vehicle Routing Problem. G-VRP is developed to aid organizations with alternative fuel-powered vehicle fleets in overcoming difficulties that exist as a result of limited vehicle driving range in conjunction with limited traveling time and limited Alternative Fuel Station (AFS). We apply the Iterated Local Search (ILS) metaheuristic approach for solving G-VRP. First, we use parallel farthest cheapest insertion to build initial solution, then use a Randomized Variable Neighborhood Descent (RVND) module for solution improvement. The RVND module includes seven conventional exchange operators and two innovative operators which we have designed for improving the use of AFS in the G-VRP, i.e., 1-0_AFS and AFS_relocation. Finally, the search repeats itself with a perturbation mechanism for diversification. We have tested our algorithms, and compared with the best known solutions (BKS) of G-VRP. The results show that, out of 52 benchmark instances tested, our proposed approach has found 51 best solutions including 7 new BKS. The average deviation is -0.02%.