利用巨網機制結合回溯式門檻接受法求解中繼補貨站車輛路線問題之研究

Abstract

中繼補貨站車輛路線問題 (Vehicle Routing Problem with Intermediate Replenishment Facilities, VRPIRF) 為傳統車輛路線問題 (Vehicle Routing Problem, VRP) 之延伸。不同於VRP，VRPIRF考慮車輛在服務途中可利用中繼站進行補貨或是卸貨的作業，進而提高車輛之使用率。對於實務操作也更具其適用性。 本研究求解架構主要分成三階段：首先採用先排程後分群 (Route First-Cluster Second) 的方式構建起始路線；接以1-0、1-1、2-opt*、3-opt與Or-opt等鄰域搜尋交換法來改善起始解；最後，在進一步利用調整後之回溯式門檻接受法 (Backtracking Adaptive Threshold Accepting, BATA) 進行求解。本研究另針對問題特性，設計中繼補貨站重置機制 (RD Relocation)。搭配路線內鄰域搜尋改善法，RD Relocation能為求解結果找到最佳的中繼補貨站利用方式。 除了BATA求解架構之實驗測試之外，本研究進一步加入多重起始解策略 (Multi-Start)，測試多重起始解對VRPIRF求解績效之影響。本研究以66題國際標竿例題進行測試，求解結果共突破48題文獻已知最佳解，5題平手，平均誤差為-0.85%。

The Vehicle Routing Problem with Intermediate Replenishment Facilities (VRPIRF) is a variant of the traditional Vehicle Routing Problem (VRP). Compared with VRP, VRPIRF considers a numerous replenishment depots with unlimited capacity, capacity of vehicles and limitation of total duration. With these conditions, VRPIRF can be more conform to many distribution operations in the reality. There are three modules in our proposed Metaheuristics to solve the VRPIRF. First, the Route First-Cluster Second method was adopted to construct the initial solution. Second, the Neighborhood Search (NS) module which includes 1-0, 1-1, 2-opt*, 3-opt and Or-opt. Finally, we applied a modified Backtracking Adaptive Threshold Accepting (BATA) process to further improve the solution. In addition, we developed RD-Relocation strategy combined with intra-route exchanges to find better locations of replenishment depots during the route improvement procedure. Moreover, we also conducted some multiple-start solution experiments with encouraging results. In order to identify the feasibility of our proposed Metaheuristics, we compared our best solutions with VRPIRF benchmark instances. Results showed that our proposed methods have generated 48 new best known solutions (BKS) and 5 reaching BKS. The average deviation of all the tested instances is -0.85%.