基于密度聚类构建物流配送问题的毁灭移除算法
来源：计算机应用杂志2017年第8期北京时间：
作者：阳旺, 何国超, 吴雁
单位：中南大学 信息科学与工程学院, 长沙 410083
摘要：研究多车型大规模物流配送问题，针对企业配送门店规模大且聚集的特点，在自适应大规模邻域搜索（ALNS）框架下提出一种新的邻域映射方式：基于密度聚类的毁灭移除算法。ALNS包含毁灭与重建两个阶段，通过不断对当前解进行破坏和重建得到更好解。在毁灭阶段，随机选择一条路线进行密度聚类得到簇集合，然后按簇对路线上的门店进行移除；重建阶段随机选择贪婪插入法或Regret-2插入法将移除的门店插入到合适的路线上得到新配送方案。通过国际基准测试案例验证了所提算法的有效性，与已有算法对比，基于密度聚类的毁灭移除算法的ALNS算法求解结果比案例已知最优解平均误差更低，求解质量更优；应用于实际场景中，该算法能在有限时间内求得较好的配送方案。
关键词：新零售,车辆路径问题,固定车辆数的多车型车辆路径问题,毁灭与重建,密度聚类,自适应大规模邻域搜索
基金资助：国家科技支撑计划项目（2015BAH05F02）。
