Splitting algorithms for the multiple depot arc routing problem: application by ant colony optimization

This paper handles the Capacitated Arc Routing Problem with Multiple Depots (MD-CARP). The well known CARP problem 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 MD-CARP is NP-hard, to resolve him efficiently, two ant colony approaches are developed. The first proposed work is based on ant colony optimization (ACO) combined with an insertion heuristic: the ACO is used to optimize the order of insertion of the edges, and the heuristic is devoted to inserting each edge in the solution. A generalization for the splitting method of Ulusoy is incorporated with the ant colony optimization in the second approach. Computational results on benchmark instances show the satisfactory quality of the proposed methods and the superiority of the first algorithm compared to the second method on the large instances.