粒子群演算法應用於具容量限制的開放式車輛途程問題

Particle Swarm Optimization (PSO) for the Capacitated Open Vehicle Routing Problem

簡銓蔚(Chuan-Wei Chien)

指導教授 ： 胡黃德

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

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

摘要

輸成本在企業營運成本中所佔比例甚重，企業是否需要擁有自己的運輸車隊是必須考量的重點。企業委外請第三方物流業者從場站運送貨物給每個需求點，當運送完最後一個需求點之後，第三方物流業者可不需回到場站，這種有車輛需求限制、單一場站且不必再回到場站的問題便稱作具容量限制的開放式車輛途程問題 (Capacitated Open Vehicle Routing Problem, COVRP) 。本研究使用粒子群最佳化演算法 (PSO) 求解COVRP，透過參數比較設計以PSO為求解基礎的架構，來探討此演算法在求解COVRP問題的成效與其精確度，期望滿足總配送成本最小化的目標。本研究以國際期刊MirHassani＆Abolghasemi (2011) 文獻中的標竿題庫，當作例題測試依據，一共包含15題。本研究有9題達到文獻已知最佳解，1題超越其最佳解，其餘的例題誤差皆在3.76％以內。在車輛數方面，本研究15題測試例題皆可以達到最小所需車輛數，因此與文獻最佳解的車輛使用成本相同。

關鍵字

具容量限制的開放式車輛途程問題 ； 粒子群最佳化演算法

並列摘要

The transportation cost accounts for large portion of the expenses of enterprises, hence the decision of owning motorcades becomes an important issue. Third party logistics (TPLs) transports merchandises from the depot to customers, and TPLs do not return to the depot after the last delivery. With the conditions of limited vihicle capacity, a single depot, and without returning to the depot, this kind of problem is called the capacitated open vehicle routing problem (COVRP). In this study, an algorithm was developed by the particle swarm optimization (PSO) to solve the COVRP. The results and the corresponding accuracies were discussed via comparing the parameters. All 15 case problems in the MirHassani＆Abolghasemi (2011) were compared. In this research, nine cases have the same optimal solutions, one cases has a better solution, and the solutions of the rest are less than 3.757%. In this study, 15 questions can reach the minimum required number of vehicles, so that we have the same vehicle used with the best solutions.

並列關鍵字

Capacitated Open Vehicle Routing Problem ； Particle Swarm Optimization

參考文獻

曹餘偉，「應用禁忌搜尋法求解多車種多物流中心之區位途程問題」，私立元智大學，工業工程與管理研究所，2006。

Aksen, D., Ozyurt, Z., Aras, N., “ The open vehicle routing problem with driver nodes and time deadlines,” Journal of the Operational Research, Vol. 132, pp. 760-768, 2007.

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

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

Bullnheimer, B., R. F. Hartl and C. Strauss., “An improved ant System algorithm for thevehicle Routing Problem,” Annals of Operations Research, Vol. 89, pp. 319-328, 1999.