應用粒子群演算法求解OVRP問題之研究

Particle swarm optimization algorithms for the open vehicle routing problem

楊禮瑛

指導教授 ： 韓復華

國立交通大學/管理學院/運輸科技與管理學系/碩士(2011年)

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

摘要

開放式車輛路線問題 (Open Vehicle Routing Problem, OVRP) 為VRP的一種衍生問題，它與傳統VRP的主要區別在於路線型態，OVRP路線型態為Hamiltonian path，而VRP路線型態為Hamiltonian cycle。OVRP中車輛從場站出發，終於顧客，車輛並不會返回場站。本研究應用粒子群演算法 (Particle Swarm Optimization, PSO) 求解OVRP問題，主要求解架構為參考Ai 和 Kachitvichyanukul [1]的第二種編碼方式(SR-2)，並根據本研究問題稍作修改，與此文獻求解架構最大不同為增加了2-Opt*、Or-Opt、Reduction鄰域改善模組，加強演算法的深度搜尋，因此粒子數設定也不同，文獻使用粒子數為50，而本研究使用粒子數為20，求解時間為更有效率。
本研究以Christofides 等人[6]中C1至C14題、Fisher [11]題庫中F11及F12、Li 等人 [15]題庫O1至O8以及MirHassani和Abolghasemi [17]文獻中的15題，一共39題作為測試例題。以C語言進行程式撰寫，測試環境為Windows 7作業系統，Intel (R) i3-2100，3.10GHz的個人電腦。本研究求解之績效為，若不考慮旅行時間限制的例題，一共使用224輛車，總車輛數誤差為0輛，若考慮之，則總車輛數誤差為2輛；一共使用290輛車，總車輛數誤差為2輛；39題標竿例題中有20題可以達到目前文獻已知最佳解。另外將本演算法應用於求解VRP問題，以14題國際標竿例題進行測試，結果顯示，平均誤差為0.51%，14題中有7題可以達到目前文獻已知最佳解。

關鍵字

開放式車輛路線問題 ； 粒子群演算法

並列摘要

無資料

並列關鍵字

Open vehicle routing problem ； Particle Swarm Optimization

參考文獻

[32] 王雅賢，「粒子群最佳化演算法改良之研究」，中原大學，碩士論文，民國95年。

[33] 李佩玲，「以混合基因與粒子群演算法求解旅行銷售員問題」，中原大學，碩士論文，民國95年。

[1] Ai, T. J. and Kachitvichyanukul, V., “Particle swarm optimization and two solution representations for solving the capacitated vehicle routing problem,” Computers & Industrial Engineering, Vol. 56, No. 1, pp.380–387, 2009.

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

[5] Brandão, J., “A tabu search heuristic algorithm for open vehicle routing problem,” European Journal of Operational Research, Vol. 157, No. 3, pp. 552-564, 2004.