International Journal of Industrial Engineering and Management
Volume 6, Issue 2, June 2015, PP 49-58
UDK: 656.07

A Metaheuristic ACO to Solve the Multi-Depot Vehicle Routing Problem with Backhauls

Jhon Jairo Santa Chávez, Mauricio Granada Echeverri, John Willmer Escobar, César Augusto Peñuela Meneses


In this paper, a metaheuristic algorithm based on the ant colony optimization is presented to solve the multi-depot vehicle routing problem with delivery and collection of package. Each performed route consists of one sub-route in which only the delivery task is done, in addition to one sub-route in which only the collection process is performed. The proposed algorithm tries to find the best order to visit the customers at each performed route. In addition, the proposed approach determines the best connection between the sub-routes of delivery and collection, in order to obtain a global solution with the minimum travelling cost. The efficiency of the proposed algorithm has been evaluated by considering a set of instances adapted from the literature. The computational results have been compared with a greedy heuristic algorithm based on the nearest neighborhood approach. Finally, conclusions and suggestions for future works are presented.


Key words: Ant Colony, Backhauls, Combinatorial Optimization,Computational Simulation, Multi-Depot Vehicle Routing Problem.
Article history: Received (11.05.2015); Revised (17.06.2015); Accepted (03.07.2015)
Number of downloads (since May 2017):