A hybrid genetic algorithm with perturbation for the multi-depot capacitated arc routing problem

作者：Hu, Hongtao; Liu, Tiantang; Zhao, Ning; Zhou, Yiting; Min, Dequan

来源：Journal of Applied Sciences, 2013, 13(16): 3239-3244.

DOI：10.3923/jas.2013.3239.3244

• Capacitated arc routing problem
• Computational results
• Hybrid genetic algorithms
• Local search
• Perturbation
• Replacement methods
• Vehicle capacity constraints
• Vehicle Routing Problems

The Capacitated Arc Routing Problem (CARP) is a difficult vehicle routing problem, where given an undirected graph, the objective is to minimize the total cost of all vehicle tours that serve all required edges under vehicle capacity constraints. In this study, a Hybrid Genetic Algorithm with Perturbation (HGAP) is proposed to solve the multi-depot CARP (MDCARP) which generalizes the CARP by extending the single-depot to the multi-depot. The proposed HGAP incorporates a Genetic Algorithm (GA), a local search, a new replacement method and a perturbation mechanism. The proposed HGAP is evaluated on the MDCARP benchmark instances and computational results show that the HGAP is very competitive.

• 出版日期2013
• 单位上海海事大学; 上海交通大学