地球信息科学学报 ›› 2012, Vol. 14 ›› Issue (6): 781-787.doi: 10.3724/SP.J.1047.2012.00781

• 地球信息科学理论与方法 • 上一篇    下一篇

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

涂伟1, 方志祥1,2, 李清泉1,2,3, 鲁仕维1   

  1. 1. 武汉大学 测绘遥感信息工程国家重点实验室, 武汉 430079;
    2. 武汉大学 时空数据智能获取技术与应用教育部工程研究中心, 武汉 430079;
    3. 深圳大学 时空信息智能感知与服务深圳市重点实验室, 深圳 518061
  • 收稿日期:2012-11-02 修回日期:2012-12-01 出版日期:2012-12-25 发布日期:2012-12-25
  • 通讯作者: 方志祥(1977-),博士,副教授,主要从事时空分析研究。E-mail:zxfang@whu.edu.cn E-mail:zxfang@whu.edu.cn
  • 作者简介:涂伟(1984-),男,博士研究生,研究方向为时空建模、分析和优化。E-mail:tuweiwhu@gmail.com
  • 基金资助:

    国家"863"计划项目(2012AA12A403-4);国家自然科学基金重点项目(40830530; 41231171); 国家自然科学基金项目(40971233)。

A Fast Algorithm for Large Scale Vehicle Routing Optimization Based on Voronoi Neighbors

TU Wei1, FANG Zhixiang1,2, LI Qingquan1,2,3, LU Shiwei1   

  1. 1. State Key Laboratory of Information Engineering in Surveying, Mapping and Remote Sensing, Wuhan University, Wuhan 430079, China;
    2. Engineering Research Center for Spatio-Temporal Data Smart Acquisition and Application, Ministry of Education, Wuhan 430079, China;
    3. Shenzhen Key Laboratorg of Spatial-temporal Smart Sensing and Service, Shenzhen University, Shenzhen 518061, China
  • Received:2012-11-02 Revised:2012-12-01 Online:2012-12-25 Published:2012-12-25

摘要:

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

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

Abstract:

Logistic requires designing delivery plan intelligently and quickly. Traditional vehicle routing optimal algorithms can only solve vehicle routing problem no more than 2000 customers, and cost much computing efforts. This paper proposes a fast heuristic algorithm for large scale logistic vehicle routing optimization based on Voronoi neighbors. This algorithm creates an initial solution and improves it iteratively. The creation makes use of the Voronoi neighbors to cluster customers into groups from bottom to up, considering the vehicle capacity constraint. The route in each group is generated by the cheapest insertion algorithm. The improvement employs local search in k-order Voronoi neighbors to search the promising neighbor solution. The simulated annealing criterion is adopted to accept some bad solutions, escaping from local minima. The computational test has been done with a synthetic large scale vehicle routing problem dataset in Beijing. The result indicates the proposed algorithm could solve vehicle routing problem up to 12 000 customers in 4500 seconds. It costs few computational efforts, and has a quite stable performance. Comparison to other heuristics shows the proposed algorithm could provide high quality solution in a short time. The conclusion indicates the proposed algorithm is suitable for large scale logistic vehicle routing optimization.

Key words: spatial cluster, simulated annealing, logistic, Voronoi, vehicle routing problem