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

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

多貨艙車輛路線問題（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.