Journal of Computer Applications ›› 2017, Vol. 37 ›› Issue (8): 2387-2394.DOI: 10.11772/j.issn.1001-9081.2017.08.2387

Previous Articles     Next Articles

Density clustering based removal heuristic for vehicle routing problem

YANG Wang, HE Guochao, WU Yan   

  1. School of Information Science and Engineering, Central South University, Changsha Hunan 410083, China
  • Received:2017-02-21 Revised:2017-04-18 Online:2017-08-10 Published:2017-08-12
  • Supported by:
    This work is supported by the National Key Technology R&D Program (2015BAH05F02)

基于密度聚类构建物流配送问题的毁灭移除算法

阳旺, 何国超, 吴雁   

  1. 中南大学 信息科学与工程学院, 长沙 410083
  • 通讯作者: 阳旺
  • 作者简介:阳旺(1982-),男,湖南湘潭人,副教授,博士,CCF会员,主要研究方向:计算机算法;何国超(1991-),男,广东湛江人,硕士研究生,主要研究方向:车辆路径问题;吴雁(1992-),女,湖南涟源人,硕士研究生,主要研究方向:车辆路径问题。
  • 基金资助:
    国家科技支撑计划项目(2015BAH05F02)。

Abstract: Focusing on large-scale vehicle routing problem with heterogeneous fleet, a new neighborhood mapping method, namely density clustering based removal heuristic algorithm, was proposed under the Adaptive Large Neighborhood Search (ALNS) frame work. ALNS includes two phases:destruction and reconstruction, which provides optimized solution by destroying and reconstructing current solution. In the destruction phase, a routine was randomly selected to get clusters by density clustering, and then the stores were removed from the routine according to the clusters. In reconstruction, Greedy or Regret-2 insert algorithm was randomly chosen to place those removed stores into proper routine. Test results on benchmark instances validate the effectiveness of the proposed method. Compared with other existing algorithms, the ALNS density clustering based removal heuristic algorithm has lower rate of error and better quality of solutions; in real situations, the proposed algorithm can provide optimized solution in limited time.

Key words: new retail, Vehicle Routing Problem (VRP), Heterogeneous Fixed Fleet Vehicle Routing Problem (HFFVRP), ruin and recreate, density clustering, adaptive large neighborhood search

摘要: 研究多车型大规模物流配送问题,针对企业配送门店规模大且聚集的特点,在自适应大规模邻域搜索(ALNS)框架下提出一种新的邻域映射方式:基于密度聚类的毁灭移除算法。ALNS包含毁灭与重建两个阶段,通过不断对当前解进行破坏和重建得到更好解。在毁灭阶段,随机选择一条路线进行密度聚类得到簇集合,然后按簇对路线上的门店进行移除;重建阶段随机选择贪婪插入法或Regret-2插入法将移除的门店插入到合适的路线上得到新配送方案。通过国际基准测试案例验证了所提算法的有效性,与已有算法对比,基于密度聚类的毁灭移除算法的ALNS算法求解结果比案例已知最优解平均误差更低,求解质量更优;应用于实际场景中,该算法能在有限时间内求得较好的配送方案。

关键词: 新零售, 车辆路径问题, 固定车辆数的多车型车辆路径问题, 毁灭与重建, 密度聚类, 自适应大规模邻域搜索

CLC Number: