关键词: 多车场, 带有容量限制的弧路径规划问题, 遗传算法, 模拟退火算法

Abstract: Capacitated Arc Routing Problem（CARP） generates from many real problems such as waste collection，street sweeping，mail delivery，school bus routing，sprinklers routing and so on.Multiple Depot Capacitated Arc Routing Problem（MDCARP） is the CARP with more than one depot.An Improved Genetic Algorithm（IGA） is proposed in this paper to resolve MDCARP.This method first divide the problem graph into several districts according to the distance between the required arcs to the depots，so as to translate the MDCARP into Single Depot Capacitated Arc Routing Problem（SDCARP），which will be resolved by an Improved Genetic Algorithm.Furthermore，during the computing process，a local adjusting mechanism is adopted through Simulated Annealing algorithm，and some of the required arcs are exchanged between different depots，so as to avoid early convergence，and achieve whole optimization.As an example，the sprinkler routing problem is resolved through the method proposed in this paper，and the computing results show that this method can solve MDCARP effectively，which tells the promised application future of this method.

Key words: multiple depot, Capacitated Arc Routing Problem（CARP）, genetic algorithm, simulated annealing algorithm