應用粒子群最佳化方法及迭代區域搜尋法求解多貨艙車輛路線問題

Abstract

多貨艙車輛路線問題 (Multi-Compartment Vehicle Routing Problem, MCVRP) 為VRP 的衍生問題之一，與傳統VRP不同的地方在於商品種類數與車輛貨艙(Compartment) 的空間分隔。在MCVRP中每位顧客有多種商品需求，不同的商品必須由其對應的車輛貨艙進行配送服務。依據個別顧客不同商品是否可由不同車輛配送，MCVRP又可分為「可分送」與「不可分送」兩種題型。 本研究分別以粒子群最佳化方法 (Particle Swarm Optimization, PSO) 及多重起點迭代區域搜尋法 (Multi-start Iterated Local Search, MS_ILS) 求解MCVRP問題。PSO方面主要在建立一套精簡為n維的編解碼方式可同時應用於求解可分送與不可分送的兩種題型。MS_ILS方面，首先運用n維編解碼構建多組起始解；其次再以隨機變動鄰域尋優模組 (RVND) 進行改善，其中包括2-opt、Or-opt、λ-interchanges與2-opt*等交換法；同時亦搭配使用擾動機制來增加求解廣度。 本研究以Fallahi et al. [9] 及Reed et al. [24] 所發表之四組題庫進行測試，每組題庫又分為不可分送與可分送題型，共136題國際標竿例題。結果顯示，整體而言MS_ILS的求解績效優於PSO；另方面，本研究提出PSO的n維編解碼方式在可分送問題上的求解則較原先的2n維度編解碼可節省約一半時間。於四組國際標竿題庫136個例題中，本研究提出的MS_ILS可求得23題巳知最佳解 (Best Known Solutions, BKS)，並突破38題；與BKS的平均誤差僅為0.18%。 關鍵詞：多貨艙車輛路線問題、粒子群演算法、迭代區域搜尋法、多重起始解

Multi-compartment vehicle routing problem (MCVRP) is an extension of the classical Vehicle Routing Problem (VRP) with multiple products that must be stored in the given compartments in the vehicle. The main difference between MCVRP and VRP is the compartment capacity limit for various products. Depending on if the different products of a customer can be shipped by different vehicles, the MCVRP can be classified into the split and non-split type of problems respectively. In this thesis, we apply the particle swarm optimization (PSO) method and a multi-start iterated local search (MS_ILS) approach for solving the MCVRP respectively. In the PSO part, we propose an n-dimension decoding method for solving both the non-split and split type of the MCVRP. In our MS_ILS, we first use the n-dimension decoding method to construct multiple initial solutions. Then, we apply a randomized variable neighborhood decent (RVND) module with the local search operators of 2-opt, Or-opt, λ-interchanges and 2-opt* to improve the solution. A p-point perturbation is also applied in the MS_ILS to increase the diversification of search. Our proposed algorithms were tested on four problem instance sets proposed by Fallahi et al. [9] and Reed et al. [24]. The results show that the MS_ ILS performs better than PSO. On the other hand, our proposed n-dimension decoding method of PSO can save about half computer time than the original 2n-dimension decoding method in solving the MCVRP for the split type of problems. Out of 136 instances tested, our MS_ILS has found 23 best known solutions (BKS) and 38 new best solutions. The average deviation from BKS is 0.18%. Key Words: Multi-Compartment Vehicle Routing Problem (MCVRP), Particle Swarm Optimization (PSO), Iterated Local Search (ILS), Multi-start