CARP问题的小环路启发式求解方法

摘要：

弧路径规划问题(Arc Routing Problem,ARP)来源于回收垃圾,清洒街道,扫雪以及投递邮件等实际问题.CARP是车辆带有容积限制的ARP问题.本文研究了CARP与CVRP的转换,并提出了一种小环路方法来求解CARP.该方法先将CARP中所有弧分割为不同区域,每个区域会形成一个小环路,从而转换为CVRP问题进行求解.然后将CVRP求解结果释放为CARP的初始解,再用Tabu禁忌搜索方法进行优化.通过一个假设例子和两组标准算例的求解,结果验证了该算法的求解效率和精度,并为实际应用奠定了基础.

关键词：车辆路径规划、弧路径规划问题、启发式算法、小环路法

所属期刊栏目：21

分类号：O221.1(运筹学)

资助基金：国家自然科学基金70201008;高等学校博士学科点专项科研项目20020003092

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

页数：共7页

页码：502-507,543