摘要
为了给物流企业在车辆配送方案制定上提供决策支持,针对电动物流车与燃油物流车混合配送的模式,研究了带时间窗的动态需求车辆路径问题,建立了以配送总成本最小化为目标的两阶段整数规划模型。针对模型特点,设计了改进的自适应大规模邻域搜索(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的速度更快,质量更好,证明了该算法在求解时效性要求高的动态需求车辆路径问题的优越性。
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.
作者
南丽君
陈彦如
张宗成
Nan Lijun;Chen Yanru;Zhang Zongcheng(School of Economics&Management,Southwest Jiaotong University,Chengdu 610031,China)
出处
《计算机应用研究》
CSCD
北大核心
2021年第10期2926-2934,共9页
Application Research of Computers
基金
国家重点研发计划项目(2018YFB1601402)
国家自然科学基金项目(71771190)。
