Abstract:

This paper introduces a new algorithm based on local search for the
capacitated arc routing problem (CARP) and the split-delivery capacitated arc routing
problem (SDCARP). We present a intermediate model to transfer CARP to SDCARP
and then solve the two problems by an algorithm which combines the iterated local
search and the memetic algorithm. We use crossovers to perform fully reproducible
initializations in each local search iteration and edge-marking to save computation
time. The computational results on 63 instances of standard benchmarks show that the
proposed algorithm outperforms most of the existing best-known solutions obtained
by other heuristics within a reasonable computing time. Furthermore, compared with
the CARP solutions, our algorithm finds three optimums for the SDCARP.

Key words: Capacitated arc routing problem , Split-delivery ,  Memetic algorithm ,  Iterated local search