粒子群最佳化巨集啟發式方法求解多貨艙車輛路線問題之研究

A PARTICLE SWARM OPTIMIZATION SOLUTION APPROACH FOR THE MULTI-COMPARTMENT VEHICLE ROUTING PROBLEM

韓復華(Anthony F. Han) ； 朱佑旌(Yu-Ching Chu) ； 林致瑄(Jhih-Syuan Lin)

《運輸計劃季刊》 45卷2期 (2016/06) Pp. 101-131

摘要

多貨艙車輛路線問題 (Multi-Compartment Vehicle Routing Problem, MCVRP) 是傳統車輛路線問題 (Vehicle Routing Problem, VRP) 的衍生問題之一。在MCVRP 中每位顧客可有多種物品需要配送，各車輛亦設有多個不同固定容量的隔艙，各自對應一種特定物品的裝載使用。MCVRP 依「不可分送」與「可分送」之條件分為兩種型態，前者要求每位顧客的多種物品必須由單一車輛服務；後者則允許同一顧客由多部車輛分批服務。本研究應用粒子群最佳化 (Particle Swarm Optimization, PSO) 巨集啟發式解法求解MCVRP。首先，依據「不可分送」與「可分送」的問題型態，分別設計兩種編解碼方法作為粒子解產生與演化學習的基礎。此外，各迭代則採用包括有兩種路線內與六種路線間交換法的變動鄰域下降 (Variable Neighborhood Descent, VND) 改善模組以增強搜尋之深度，其中針對「可分送」的問題型態亦提出一個新的 (1, 0)* 鄰域搜尋法。本研究以兩組國際標竿例題進行測試，發現80 題例題中，本研究可求得16 題現有文獻最佳解，並改善了34 題文獻最佳解結果。

關鍵字

多貨艙車輛路線問題 ； 粒子群最佳化 ； 變動鄰域下降 ； 巨集啟發式方法

並列摘要

Multi-compartment vehicle routing problem (MCVRP) is a variant of the conventional vehicle routing problem (VRP). The MCVRP considers multiple products to be delivered, and each product must load on a specific compartment in the vehicle. The problem considers two cases for customer delivery, ＂no split＂ and ＂split＂, depending on if the multiple products are allowed to be split among multiple routes.We applied the particle swarm optimization (PSO) metaheuristic approach to solve the MCVRP. Two new solution representation methods were designed to generate and evolve the particles for both the no-split and split cases respectively. A variable neighborhood descent (VND) module with an innovative (1, 0)* node-interchange operator was built to improve the quantity of particles during its evolution process. Two sets of benchmark instances for MCVRP were adopted to test the proposed PSO metaheuristic method. Results showed that the PSO method is very competitive as compared to the best algorithms published in the MCVRP literature. Out of the 80 benchmark instances tested, the PSO found 16, and improved 34 best known solutions.

並列關鍵字

Multi-Compartment vehicle routing problem (MCVRP) ； Particle swarm optimization (PSO) ； Variable neighborhood descent (VND) ； Metaheuristic

參考文獻

Kennedy, J.,Eberhart, R. C.(1995).Particle Swarm Optimization.Proceedings of IEEE International Conference on Neural Networks, Vol. IV.(Proceedings of IEEE International Conference on Neural Networks, Vol. IV).

Shi, Y.,Eberhart, R. C.(1998).A Modified Particle Swarm Optimizer.Evolutionary Computation Proceedings.(Evolutionary Computation Proceedings).

Eberhart, R. C.,Shi, Y.(1998).Comparison between Genetic Algorithms And Particle Swarm Optimization.Proceedings of the 7th International Conference on Evolutionary Programming VII.(Proceedings of the 7th International Conference on Evolutionary Programming VII).

Pongchairerks, P.,Kachitvichyanukul, V.(2005).A Non-homogenous Particle Swarm Optimization with Multiple Social Structures.Proceedings of International Conference on Simulation and Modeling.(Proceedings of International Conference on Simulation and Modeling).

Ai, T. J.,Kachitvichyanukul, V.(2009).Particle Swarm Optimization and Two Solution Representations for Solving the Capacitated Vehicle Routing Problem.Computers & Industrial Engineering.56(1),380-387.