Quantcast

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

Research paper by Tiantang Liu, Zhibin Jiang, Na Geng

Indexed on: 18 Oct '12Published on: 18 Oct '12Published in: Flexible Services and Manufacturing Journal



Abstract

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.