Multiple center capacitated arc routing problems: A tabu search algorithm using capacitated trees

In the capacitated arc routing problem with multiple centers (M-CARP) the objective is to find routes starting from the given depots or centers such that each required arc is served, capacity (and usually additional) constraints are satisfied and total travel cost is minimized. In this paper we consider a heuristic transformation of the M-CARP into a multiple center capacitated minimum spanning tree problem with arc constraints, that we call arc-constrained CMST. An algorithm for determining initial feasible solutions as well as an improvement procedure for this problem are described and the ‘re-translation’ of CMST solutions into the CARP context is explained. It is shown that the objective function value of the obtained CARP solution is easily derived from the respective value of the corresponding heuristic CMST solution. Furthermore, the possibility of including side constraints and the consideration of additional objective functions is discussed. Computations on real-world benchmark problems compare the results of the tabu search and simulated annealing metastrategies embedded in the improvement procedure.