基于Voronoi邻近的物流车辆路径快速优化算法

摘要：

现代物流业需要快速高效并智能化制定物流运输方案.传统路径优化方法适合处理中小规模的车辆路径问题,计算时间较长,方案质量较低,故需发展短时间内能提供高质量路径方案的启发式算法.针对大规模物流车辆路径优化,本文提出了一种Voronoi邻近的快速优化方法.该方法先创建初始解,而后进行迭代优化.初始解创建利用Voronoi邻近关系,顾及车辆容量约束,自底向上进行客户点空间聚类,将问题降维；采用最廉价插入算法安排聚类内部路径,生成性质良好的初始解.迭代优化在客户点Voronoi邻近内进行有效的局部搜索,利用模拟退火机制接受较差解,从而跳出局部最优,不断提高解的质量.本文利用模拟生成的北京市大规模车辆路径问题进行实验,结果表明:本文算法能够在4500s内优化客户点高达12 000个物流车辆路径问题,计算时间较短,解的质量优良,算法性能稳定.本文与其他算法比较,能在较短时间内提供高质量车辆路径方案,适用于大规模物流车辆路径的优化.

关键词：物流、车辆路径问题、空间聚类、Voronoi、模拟退火

所属期刊栏目：14

资助基金：国家"863"计划项目2012AA12A403-4;国家自然科学基金重点项目40830530,41231171;国家自然科学基金项目40971233

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

页数：共7页

页码：781-787