應用粒子群演算法求解開放式車輛路線問題之研究

Particle Swarm Optimization Algorithms for the Open Vehicle Routing Problem

本研究應用粒子群演算法（Particle Swarm Optimization,PSO）求解開放式車輛路線問題 （Open Vehicle Routing Problem,OVRP），應用Ai and Kachitvichyanukul提出之SR-2編碼方式以及GLNPSO的學習策略作為主要求解方法，並額外增加2-Opt*與Or-Opt鄰域改善模組以加強演算法的深度搜尋，以降低求解粒子數之運用，兼顧求解效率及其品質。本研究以32題國際標竿例題進行測試，求解績效顯示：總車輛數誤差為0輛；距離成本方面，18題可求得文獻已知最佳解。本研究另外將所設計之演算法應用於求解VRP問題，以14題國際標竿例題進行測試，結果求得7題目前文獻已知最佳解，平均誤差僅為0.51％。

This paper applies a Particle Swarm Optimization (PSO) algorithm for solving the Open Vehicle Routing Problem (OVRP). We adopted the SR-2 solution representation and the corresponding decoding method in the PSO framework proposed by Ai and Kachitvichyanukul. The major difference between their work and this paper is that we added the 2-Opt* and Or-Opt local improvement procedures into the PSO framework. The addition of local improvement procedures has significant effects on the solution quality and the computational efficiency. The proposed algorithm was tested on 32 OVRP benchmark instances. Results showed that our proposed algorithm can find 18 best-known solutions out of the 32 benchmark instances tested. We also applied the proposed method for solving the conventional VRP, and found 7 best-known solutions among 14 instances tested. The average deviation from the best-known solution is 0.51%.