A guided local search procedure for the multi-compartment capacitated arc routing problem

In this paper, we introduce and study the multi-compartment capacitated arc routing problem—an extension of the classical capacitated arc routing problem, but where the required edges have a demand for different products, and multi-compartment vehicles are available to co-distribute these commodities. We present a local search algorithm that exploits well-known moves (2-opt, re-insert, relocate, exchange and cross). We take advantage of speed up tricks such as marking and neighbour lists, and we combine the procedure with the guided local search meta-heuristic in order to reach high quality solutions. We report on results from extensive computational experiments. Our aim is to reveal in what situations co-distribution by partitioned vehicles saves in routing costs as compared with separate distribution with un-partitioned trucks. We explore sensitivities in key problem characteristics including, the number of commodities, the vehicle capacity, the location of the depot and required edges, the density of required edges, and the demand per commodity for the required edges.