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

作者：Liu, Tiantang; Jiang, Zhibin^*; Geng, Na

来源：Flexible Services and Manufacturing Journal, 2014, 26(4): 540-564.

DOI：10.1007/s10696-012-9166-z

• Multi-depot heterogeneous fleet capacitated arc routing problem
• Genetic algorithm
• Local search
• Memetic algorithm

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.

• 出版日期2014-12
• 单位上海交通大学