Solving the Multi-Depot Vehicle Routing Problem using Ant Colony Optimization and Re-Assignment

Mengchun Xie, Takeshi Miyawaki, and Kenneth A. De Jong


Multi-Depot Vehicle Routing Problem, Ant Colony Optimization, Re-assignment, disaster, transportation


Earthquakes and many other natural disasters occur in Japan. The rapid delivery of aid supplies and the transportation of the injured are important for alleviating human suffering caused by disasters. This problem can be represented by the Multi-Depot Vehicle Routing Problem (MDVRP). In this paper, the method of solving the Multi-Depot Vehicle Routing Problem by Ant Colony Optimization (ACO) is proposed. The proposal technique is: first, make graphs from customers assigned to vehicles; second, apply ACO to the graph to optimize the Multi-Depot Vehicle Routing Problem; finally, reassign customers to vehicles based on searched routing. Two methods were proposed for assigning customers: the TSP method and the Orientation method. By repeatedly searching for a better route with ACO after reassigning customers based on the obtained delivery routes, good solutions were generated.

Important Links:

Go Back