多车场CARP问题的改进遗传算法求解  

Resolve multiple depot capacitated arc routing problem based on improved genetic algorithm

作　　者：李小花[1] 朱征宇[1] 夏梦霜[1] 

机构地区：[1]重庆大学计算机学院,重庆400044

出　　处：《计算机工程与应用》2009年第11期230-234,共5页Computer Engineering and Applications

基　　金：高校博士学科点专项科研基金资助课题(No.20030611016)。

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] N945.15[自动化与计算机技术—计算机科学与技术]