车辆路径问题的改进分支切割法

钟石泉; 马寿峰

doi:10.12011/1000-6788(2009)10-152

PDF(653 KB)

系统工程理论与实践 ›› 2009, Vol. 29 ›› Issue (10) : 152-158. DOI: 10.12011/1000-6788(2009)10-152

论文

车辆路径问题的改进分支切割法

钟石泉;马寿峰

作者信息 +

文章历史 +

摘要

对容量约束车辆路径问题建立了数学模型并提出了一种改进的分支切割算法.算法结合启发式规则, 采用梳子不等式和连接不等式产生切割面,设置参数控制分支客户组合的大小和分支方向,通过不断调整问题下界来删除多余节点. 提出了切割面更新策略,设置切割面利用系数和切割面库, 通过动态更新来淘汰利用率低的切割面,保存利用率高的切割面. 采用多组CVRP算例进行计算,
并与其它算法优化CVRP的实验结果作了比较, 对运算结果进行了分析,给出了推荐的参数取值方案,说明了提出的分支切割算法对容量约束车辆路径问题的有效性.