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

被引：10

作者：

但正刚

蔡临宁

吕新福

郑力

机构：

[1] 清华大学工业工程系

来源：

系统工程学报 | 2006年 / 05期

关键词：

车辆路径规划; 弧路径规划问题; 启发式算法; 小环路法;

D O I：

暂无

中图分类号：

O221.1 [线性规划];

学科分类号：

摘要：

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

引用

页码：502 / 507+543 +543

页数：7