《计算机应用研究》|Application Research of Computers

改进的自适应大规模邻域搜索算法求解动态需求的混合车辆路径问题

Improved adaptive large neighborhood search algorithm for mixed fleet routing problem of dynamic demands

免费全文下载 (已被下载 次)  
获取PDF全文
作者 南丽君,陈彦如,张宗成
机构 西南交通大学 经济管理学院,成都 610031
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2021)10-008-2926-09
DOI 10.19734/j.issn.1001-3695.2021.02.0050
摘要 为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(improved adaptive large neighborhood search,IALNS)算法,提出新的删除、修复算子及动态阶段加速策略,分别针对大规模的静态算例与动态算例进行算法性能测试。结果表明,与无改进策略的IALNS(IALNS-ND)相比,静态问题中在相同的求解时间内75%的算例(12个算例中9个)IALNS得到的最小值和平均值优于IALNS-ND,动态问题中95%(60个算例中57个算例)的算例可以得到成本和时间均优于IALNS-ND的解;与三种算法——自适应大规模邻域搜索算法(ALNS)、大规模邻域搜索算法(LNS)以及变邻域搜索算法(VNS)相比,静态问题中所有算例IALNS获得的总成本的最小值和平均值均优于三个对比算法,动态问题中58%(60个算例中35个算例)的算例IALNS能够以少于三个对比算法1.5倍甚至10倍的时间获得更优的解。同时随着问题动态度的提高,IALNS的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。
关键词 动态需求; 电动车车辆路径问题; 混合车队; 改进的自适应大规模邻域搜索算法
基金项目 国家重点研发计划项目(2018YFB1601402)
国家自然科学基金项目(71771190)
本文URL http://www.arocmag.com/article/01-2021-10-008.html
英文标题 Improved adaptive large neighborhood search algorithm for mixed fleet routing problem of dynamic demands
作者英文名 Nan Lijun, Chen Yanru, Zhang Zongcheng
机构英文名 School of Economics & Management,Southwest Jiaotong University,Chengdu 610031,China
英文摘要 In order to provide decision support for vehicle scheduling of logistics companies, this paper investigated the routing problem with time windows and dynamic demands considering a mixed fleet of electric and conventional vehicles, and proposed a two-stage integer programming model to minimize the total distribution cost. This paper designed an improved adaptive large-scale neighborhood search algorithm(IALNS), proposed the new deletion and repair operators and acceleration strategy in the dynamic stages. It conducted the extensive large-scale computational experiments with both static and dynamic demands to examine the performance of proposed IALNS. The results show that, compared to IALNS-ND, IALNS performs better in term of the minimum and average values in 75% of the static problems(9 out of 12 cases). In 95%(57 out of 60 examples) of the dynamic cases, IALNS works better than IALNS-ND in terms of the cost and computation time. Moreover, compared to ALNS, LNS and VNS, IALNS performs best in term of the best minimum and average values of the total costs for all static cases. In 58%(35 out of 60 examples) of the dynamic case, the IALNS can achieve a better solution in 1.5 times or even 10 times less computation time than the rest algorithms. Also the larger the degree of dynamism of a experiment is, the better the obtained solution obtained by IALNS in a shorter time. Thus IALNS performs best in solving the time-sensitive dynamic demand vehicle routing problem.
英文关键词 dynamic demands; electric vehicle routing problem; mixed fleet; IALNS
参考文献 查看稿件参考文献
 
收稿日期 2021/2/9
修回日期 2021/4/2
页码 2926-2934
中图分类号 TP301.6;F506
文献标志码 A