應用PSO求解多艙種車輛路線問題

A Particle Swarm Optimization Solution Approach for the Multi-Compartment Vehicle Routing Problem

林致瑄(Jhih-Syuan Lin)

指導教授 ： 韓復華

國立交通大學/管理學院/運輸與物流管理學系/碩士(2015年)

https://doi.org/10.6842/NCTU.2015.00484

摘要

多艙種車輛路線問題 (Multi-Compartment Vehicle Routing Problem, MC-VRP) 為VRP 的衍生問題之一，與傳統VRP不同的地方在於商品種類數與車輛艙種(Compartment) 的空間分隔。在MC-VRP中每位顧客會有多種的商品需求且車輛本身亦允許有多個艙種，對於不同的商品有別於傳統VRP，可由不同車輛運送。
本研究應用粒子群演算法 (Particle Swarm Optimization, PSO) 求解MC-VRP問題，主要求解架構為修改Ai and Kachitvichyanukul [1] 中所使用的編碼方式 (SR-1) 針對問題可分送特性並以顧客分群之概念產生一套精簡的編碼方式 (MCSR-1、MCSR-2) 構建起始路線解。再以鄰域搜尋模組改進，共包括2-Opt、Or-Opt、Inter-Route Exchange與2-Opt*等數種。同時，本研究根據問題之可分送服務特性改良交換法，增加修改與判斷機制進行交換，並建立1-0*交換法，以提升交換法搜尋績效。本研究使用粒子數為30，求解迭代數為750，以增加解之多樣性並提升求解效率。
本研究以Fallahi et al.[2] 所發表的兩大套題庫，共40題國際標竿例題進行測試，其中又分為不可分送與可分送特性。使用C#語言進行程式撰寫，並於Intel® Core(TM) i7-3770 CPU @ 3.40GHz的個人電腦進行測試。於40題標竿例題中，不可分送共有17題突破，平手8題文獻已知最佳解。在可分送特性中，突破29題，平手4題，就平均誤差而言，四組題庫與已知最佳解相比分別求得平均誤差為1.10%、-0.26%、-1.09%與-0.82%，求解效果不錯。

關鍵字

多艙種車輛路線問題 ； 粒子群演算法

並列摘要

Multi-compartment vehicle routing problem (MC-VRP) is an extension of the classical Vehicle Routing Problem with multiple products which must be stored in the given compartment in the vehicle. The main difference between MC-VRP and VRP is the compartment capacity limit for various products and customer’s different products could be delivery separately namely set of requested products can be delivered in several times.
In this thesis, we applied the particle swarm optimization (PSO) algorithm for solving MC-VRP. We modified a solution representation and the corresponding decoding method proposed by Ai and Kachitvichyanukul [1] then created a new and streamlined solution representation method to generate the initial solution for both non-split and split problem. In addition, we added the Inter-Route Exchange、2-Opt*、2-Opt and Or-Opt local improvement procedures into the PSO framework. We also improved the local search methods for the split problem and designed the 1-0* methods in response to problem features which various products could be distribute respectively. To make a more efficient implementation of PSO, we used 30 instead of 50 particles.
Our proposed algorithms tested on a set of 40 benchmark problems described by Fallahi et al.[2]. By our algorithm we found out the solution gap in four patterns of problems are 1.10%, -0.26%, -1.09% and -0.82% to the best known solution, respectively. Therefore our algorithm is appropriate in solving the MC-VRP.

並列關鍵字

Multi-Compartment Vehicle Routing Problem (MC-VRP) ； Particle Swarm Optimization (PSO)

參考文獻

1. Ai, T. J. and Kachitvichyanukul, V., “A particle swarm optimization for the vehicle routing problem with simultaneous pickup and delivery,” Computers and Operations Research, Vol. 36, No. 5, pp. 1693-1702, 2009.

2. Fallahi, A. E., Prins, C., and Wolfler Calvo, R., “A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem.” Computers and Operations Research, Vol. 35, No. 5, pp. 1725-1741, 2008.

5. Rosenkrantz, D. J., Stearns, R. E., and Lewis II, P. M., “An analysis of several heuristics for the traveling salesman problem,” SIAM journal on computing, Vol. 6, No. 3, pp. 563-581, 1977.

7. Cordeau, J. F., et al., “Vehicle routing,” In Berhant, C. and Laporte, G. (Eds.), Handbooks in Operations Research and Management Science: Transportation, Vol. 14, Elsevier B.V., pp. 367-428, 2005.

8. Clarke, G. and Wright, J.W., “Scheduling of vehicles from a central depot to a number of delivery points.” Operations Research, Vol. 12, No. 4, pp. 568-581, 1964.