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

Abstract

開放式車輛路線問題 (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題可以達到目前文獻已知最佳解。