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

摘要： 带有容量限制的弧路径规划问题来源于城市垃圾回收、街道清扫、邮件投递、校车路线安排和洒水车路线安排等实际问题，多车场CARP问题是具有多个车场的CARP问题。提出了一种先划分区域后进行路径规划的方法来求解多车场CARP问题。该方法先将各服务弧按照离车场距离的远近归并到距离最近的车场，从而转化为单车场CARP问题，然后用改进的遗传算法进行求解；在求解过程中，用模拟退火算法对部分服务弧进行局部调整，使服务弧在一定的范围内在不同的车场之间进行调换，从而避免局部收敛，达到全局优化的效果。以洒水车路线安排为实例，实验结果表明，该算法能有效求解一定规模的多车场CARP问题，为实际应用奠定了基础。

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