混合式粒子群最佳化演算法解容量限制車輛途程問題

A hybrid PSO algorithm for the CVRP problem

陳每(Mei Chen)

指導教授 ： 高有成

大同大學/經營設計學院/資訊經營學系所/碩士(2011年)

摘要

車輛途程問題是將地理位置相近的客戶貨品儘量安排於同一輛車，目的是要減少車輛運送的總距離，又不會超過各車輛容積限制，有節省人員工時、降低成本、減少能源浪費等等的好處。車輛途程問題是一種組合最佳化問題，已經被廣泛研究，隨著各種巨集啟發式演算法之提出，學者不斷地提出新方法論，解的品質及效能也不斷地進步。本研究應用粒子群最佳化演算法處理客戶分群問題，搭配模擬退火法處理客戶拜訪順序，期能產生更佳的車輛途程結果。實驗結果顯示，本研究所提出之演算法能夠有效解決容量限制車輛途程問題。

關鍵字

車輛途程問題 ； 粒子群最佳化演算法 ； 模擬退火法

並列摘要

The Capacitated Vehicle Routing Problem (CVRP) has been studied over five decades. The goal of CVRP is to minimize the total distance of the routes under the constraints of vehicles’ capacity. Because CVRP is one kind of NP-hard problems, a number of meta-heuristics have been proposed to solve the problem. This paper proposes a hybrid algorithm combining Combinatorial Particle Swarm Optimization (CPSO) with Simulated Annealing (SA) to solve the CVRP. The experimental results show that the proposed algorithm is an effective approach for solving the CVRP.

並列關鍵字

Particle Swarm Optimization ； Vehicle Routing Problem ； Simulated Annealing

參考文獻

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

[2] Araque J.R.G., Kudva, G., Morin, T.L., Pekny J.F. “A branch-and-cut algorithm for vehicle routing problems” Annals of Operations Research (50) 1994, pp:37-59.

[3] Baker, B.M. and Ayechew, M.A. “A genetic algorithm for the vehicle routing problem” Computers & Operations Research (30) 2003, pp:787-800.

[4] Bell, J.E. and McMullen, P.R. “Ant Colony Optimization techinques for the vehicle routing problem“ Advanced Engineering Informatics (18) 2004, pp:41-48.

[5] Bin, Y., Zhong-Zhen, Y. and Baozhen, Y. “An improved ant colony optimization for vehicle routing problem” European Journal of Operational Research (196) 2009 pp:171-176.