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

Density clustering based removal heuristic for vehicle routing problem

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

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.