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

摘要：

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

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

所属期刊栏目：45

分类号：TP301.6;N945.15(计算技术、计算机技术)

资助基金：高校博士学科点专项科研基金资助课题20030611016

在线出版日期：2009-05-22（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：230-234