A genetic local search algorithm for the multi-depot heterogeneous fleet capacitated arc routing problem

摘要

This paper studies the multi-depot heterogeneous fleet capacitated arc routing problem (MDHCARP), a problem with rare research in the past, but with many applications in real life. The MDHCARP extends the capacitated arc routing problem (CARP) by considering both the multi-depot case and limited heterogeneous fleet constraints. We propose a genetic local search (GLS) algorithm for the MDHCARP. The GLS is appraised on simplified MDHCARP cases and on general MDHCARP instances from CARP files; and computational results show that the GLS outperforms an extended memetic algorithm and meanwhile they both improve best-known solutions of the simplified MDHCARP benchmark cases.