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

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

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

多貨艙車輛路線問題 ； 粒子群最佳化 ； 變動鄰域下降 ； 巨集啟發式方法 ； Multi-Compartment vehicle routing problem (MCVRP) ； Particle swarm optimization (PSO) ； Variable neighborhood descent (VND) ； Metaheuristic

運輸計劃季刊

45卷2期（2016 / 06 / 30）

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.

1. 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.
2. Ai, T. J.,Kachitvichyanukul, V.(2009).A Particle Swarm Optimization for the Vehicle Routing Problem with Simultaneous Pickup and Delivery.Computers & Operations Research,36(5),1693-1702.
3. Avella, P.,Boccia, M.,Sforza, A.(2004).Solving a Fuel Delivery Problem by Heuristic and Exact Approaches.European Journal of Operational Research,152(1),170-179.
4. Belmecheri, F.,Prins, C.,Yalaoui, F.,Amodeo, L.(2013).Particle Swarm Optimization Algorithm for a Vehicle Routing Problem with Heterogeneous Fleet, Mixed Backhauls, and Time Windows.Journal of Intelligent Manufacturing,24(4),775-789.
5. Brown, G. G.,Prins, C.,Wolfler Calvo, R.(1987).Real-Time, Wide Area Dispatch of Mobil Tank Trucks.Interfaces,17(1),107-120.
6. Chajakis, E. D.,Guignard, M.(2003).Scheduling Deliveries in Vehicles with Multiple Compartments.Journal of Global Optimization,26(1),43-78.
7. Chen, A. L.,Yang, G. K.,Wu, Z. M.(2006).Hybrid Discrete Particle Swarm Optimization Algorithm for Capacitated Vehicle Routing Problem.Journal of Zhejiang University-Science A,7(4),607-614.
8. Christofides, N.(Ed.)(1979).Combinatorial Optimization.Chichester, UK:Wiley.
9. Clerc, M.(1999).The Swarm and the Queen: Towards a Deterministic and Adaptive Particle Swarm Optimization.Proceedings of the IEEE Congress on Evolutionary Computation
10. Clerc, M.,Kennedy, J.(2002).The Particle Swarm-Explosion, Stability, and Convergence in a Multidimensional Complex Space.IEEE Transactions on Evolutionary Computation,6(1),58-73.
11. Crainic, T. G.(Ed.),Laporte, G.(Ed.)(1998).Fleet Management and Logistics.Boston, MA:Kluwer.
12. Eberhart, R. C.,Shi, Y.(1998).Comparison between Genetic Algorithms And Particle Swarm Optimization.Proceedings of the 7th International Conference on Evolutionary Programming VII
13. Fallahi, A. E.,Prins, C.,Wolfler Calvo, R.(2008).A Memetic Algorithm and a Tabu Search for the Multi-Compartment Vehicle Routing Problem.Computers & Operations Research,35(5),1725-1741.
14. Goksal, F. P.,Karaoglan, I.,Altiparmak, F.(2013).A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery.Computers & Industrial Engineering,65(1),39-53.
15. Jianyong, J.,Crainic, T. G.,Løkketangen, A.(2014).A Cooperative Parallel Metaheuristic for the Capacitated Vehicle Routing Problem.Computers & Operations Research,44,33-41.
16. Kachitvichyanukul, V.,Sombuntham, P.,Kunnapapdeelert, S.(2015).Two Solution Representations for Solving Multi-Depot Vehicle Routing Problem with Multiple Pickup and Delivery Requests via PSO.Computers & Industrial Engineering,89,125-136.
17. Kennedy, J.,Eberhart, R. C.(1995).Particle Swarm Optimization.Proceedings of IEEE International Conference on Neural Networks, Vol. IV
18. Lin, S.,Kernighan, B. W.(1973).An Effective Heuristic Algorithm for the Traveling-Salesman Problem.Operational Research,21(2),498-516.
19. Marinakis, Y.,Marinaki, M.,Dounias, G.(2010).A Hybrid Particle Swarm Optimization Algorithm for the Vehicle Routing Problem.Engineering Applications of Artificial Intelligence,23(4),463-472.
20. Mendoza, J. E.,Castanier, B.,Guéret, C.,Medaglia, A. L.,Velasco, N.(2010).A Memetic Algorithm for the Multi-Compartment Vehicle Routing Problem with Stochastic Demands.Computers & Operations Research,37(11),1886-1898.
21. Mladenović, N.,Hansen, P.(1997).Variable Neighborhood Search.Computers & Operations Research,24(11),1097-1100.
22. Muyldermans, L.,Ellis, C. J.,Graves, G. W.,Ronen, D.(2010).On the Benefits of Co-Collection: Experiments with a Multi-Compartment Vehicle Routing Algorithm.European Journal of Operational Research,206(1),93-106.
23. Norouzi, N.,Sadegh-Amalnick, M.,Yalaoui, F.,Alinaghiyan, M.(2015).Evaluating of the Particle Swarm Optimization in a Periodic Vehicle Routing Problem.Measurement,62,162-169.
24. Or, I.(1976).Northwestern University.
25. Osman, I. H.(1993).Metastrategy Simulated Annealing and Tabu Search Algorithms for the Vehicle Routing Problem.Annals of Operations Research,41(4),421-451.
26. Pongchairerks, P.,Kachitvichyanukul, V.(2005).A Non-homogenous Particle Swarm Optimization with Multiple Social Structures.Proceedings of International Conference on Simulation and Modeling
27. Potvin, J. Y.,Rousseau, J. M.(1993).A Parallel Route Building Algorithm for the Vehicle Routing and Scheduling Problem with Time Windows.European Journal of Operational Research,66(3),331-340.
28. Qi, C.(2011).Application of Improved Discrete Particle Swarm Optimization in Logistics Distribution Routing Problem.Procedia Engineering,15,3673-3677.
29. Reed, M.,Yiannakou, A.,Evering, R.(2014).An Ant Colony Algorithm for the Multi-Compartment Vehicle Routing Problem.Applied Soft Computing,15,169-176.
30. Sharda, R.(Ed.)(2005).Metaheuristic Optimization via Memory and Evolution.US:Springer.
31. Shi, Y.,Eberhart, R. C.(1998).A Modified Particle Swarm Optimizer.Evolutionary Computation Proceedings
32. Van der Bruggen, L.,Gruson, R.,Salomon, M.(1995).Reconsidering the Distribution Structure of Gasoline Products for a Large Oil Company.European Journal of Operational Research,81(3),460-473.
33. 林致瑄(2015)。碩士論文(碩士論文)。國立交通大學運輸與物流管理學系。
34. 韓復華、楊禮瑛(2013)。應用粒子群演算法求解OVRP 問題之研究。運輸學刊，25(2)，199-220。