%0 Journal Article
%T 基于Voronoi邻近的物流车辆路径快速优化算法
%A 涂伟
%A 方志祥
%A 李清泉
%A 鲁仕维
%J 地球信息科学学报
%P 781-787
%D 2012
%R 10.3724/SP.J.1047.2012.00781
%X 现代物流业需要快速高效并智能化制定物流运输方案。传统路径优化方法适合处理中小规模的车辆路径问题,计算时间较长,方案质量较低,故需发展短时间内能提供高质量路径方案的启发式算法。针对大规模物流车辆路径优化,本文提出了一种Voronoi邻近的快速优化方法。该方法先创建初始解,而后进行迭代优化。初始解创建利用Voronoi邻近关系,顾及车辆容量约束,自底向上进行客户点空间聚类,将问题降维;采用最廉价插入算法安排聚类内部路径,生成性质良好的初始解。迭代优化在客户点Voronoi邻近内进行有效的局部搜索,利用模拟退火机制接受较差解,从而跳出局部最优,不断提高解的质量。本文利用模拟生成的北京市大规模车辆路径问题进行实验,结果表明本文算法能够在4500s内优化客户点高达12000个物流车辆路径问题,计算时间较短,解的质量优良,算法性能稳定。本文与其他算法比较,能在较短时间内提供高质量车辆路径方案,适用于大规模物流车辆路径的优化。
%K Voronoi
%K 模拟退火
%K 空间聚类
%K 物流
%K 车辆路径问题
%U http://www.dqxxkx.cn/CN/abstract/abstract24754.shtml