粒子群演算法應用於多車種固定車隊之車輛途程問題

Applying the Particle Swarm Optimization (PSO) Algorithm to Solve the Heterogeneous Fixed Fleet Vehicle Routing Problem

胡智維(Chih-Wei Hu)

指導教授 ： 胡黃德

元智大學/工程學院/工業工程與管理學系/碩士(2013年)

https://doi.org/10.6838/YZU.2013.00222

摘要

近年來，隨著科技與交通運輸上蓬勃的發展，使得物流運輸這個領域越來越被重視。而臺灣也隨著網路購物等商業行為的成長，也造就了近年宅配物流業的迅速發展，如黑貓宅急便、新竹貨運及臺灣宅配通等。本研究將針對其配送服務問題歸納為有限制車隊之多車種車輛途程問題 (The Heterogeneous Fixed Fleet Vehicle Routing Problem, HFFVRP)，乃是由車輛途程問題 (Vehicle Routing Problem, VRP) 所衍生而來。其不同於VRP，乃考量其固定車隊為不同的車種、車容量及變動成本所組成。本研究之目的是將以粒子群演算法 (Particle Swarm Optimization, PSO) 進行HFFVRP的求解，尋求其總運送成本的最小化，而其中將對於方法之編碼 (SR-2) 作一修改。最後，透過 Golden 所訂定之國際例題 (共8題) 進行求解之測試，來確認本研究之PSO於HFFVRP的適用性與效果。而由實驗結果中，可知有一例題之最佳解達到目前已知最佳解，且各例題測試結果之最佳解平均誤差為2.46%，表示本研究之求解方法適用於HFFVRP的求解。

關鍵字

多車種 ； 固定車隊 ； 粒子群演算法 (PSO)

並列摘要

Recently, the development of technology and traffic transportation makes logistics operation more important. In Taiwan, with the market of online shopping grow rapidly, the home delivery industry becomes a booming business, e.g., President Transnet Corp., HCT Logistics and Taiwan Pelican Express Co.. The logistics operation problem of these companies belongs to Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP), and it is a variant of vehicle routing problem (VRP). Unlike Capacitated VRP, the HFFVRP considers a fixed fleet with different capacities and variable costs of vehicles. In this paper, we apply Particle Swarm Optimization (PSO) algorithm with a modification version of SR-2 decoding method for solving the HFFVRP. Finally, study the proposed meta-heuristics were applied to 8 benchmark test problems from Golden to demonstrate the applicability and practicability. The computational results show that our PSO (SR-2) have generated one best known solution and the average deviation of all the test problems is 2.46%.

並列關鍵字

Heterogeneous Fleets ； Fixed Fleet ； Particle Swarm Optimization (PSO)

參考文獻

[28] 吳宗勳, "多車種固定車隊車輛路線問題之啟發式解法研究," 國立交通大學運輸科技與管理學系, 2012.

[33] 馬凱賢, "結合區域搜尋之遺傳演算法求解多車種之車輛途程問題," 國立暨南國際大學土木工程學系, 2007.

[36] 莊凱智與黃士滔, "應用改良式粒子群演算法於旅行銷售員問題," 工程科技與教育學刊, vol. 8, no. 3, pp. 533-546, 2011.

[38] 陳育群, "運用專案完成機率與PSO演算法建立趕工專案期望利潤模式之研究," 元智大學工業工程與管理學系所, 2008.

[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.