Title: New upper bounds for the multi-depot capacitated arc routing problem

Authors: Ali Kansou, Adnan Yassine

Addresses: Laboratoire de Mathematiques Appliquees du Havre, 25 rue Philippe Lebon, B.P. 540, 76058 Le Havre Cedex, France. ' Laboratoire de Mathematiques Appliquees du Havre (LMAH), 25 rue Philippe Lebon, B.P. 540, 76058 Le Havre Cedex, France; Institut Superieur d'Etudes Logistiques (ISEL), Quai Frissard, B.P. 1137, 76063 Le Havre cedex, France

Abstract: The multi-depot capacitated arc routing problem (MD-CARP) generalises the well-known capacitated arc routing problem (CARP) by extending the single depot to a multi-depot network. The CARP consists of designing a set of vehicle trips, so that each vehicle starts and ends at the single depot. The MD-CARP involves the assignment of edges, which have to be served, to depots and the determination of vehicle trips for each depot. The first proposed work is based on ant colony optimisation (ACO) combined with an insertion heuristic: the ACO is used to optimise the order of insertion of the edges and the heuristic is devoted to inserting each edge in the solution. The second one is a memetic algorithm based on a special crossover. The computational results on benchmark instances show the satisfactory quality of the proposed methods and the superiority of the memetic algorithm compared to the ACO method.

Keywords: multi-depot capacitated arc routing problem; MD-CARP; CARP; multiple depots; ant colony optimisation; ACO; insertion heuristics; memetic algorithms; metaheuristics.

DOI: 10.1504/IJMHEUR.2010.033124

International Journal of Metaheuristics, 2010 Vol.1 No.1, pp.81 - 95

Published online: 08 May 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article