求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法  

Hybrid adaptive large neighborhood search algorithm for solving time-dependent vehicle routing problem in cold chain logistics

作　　者：肖智豪 胡志华[1] 朱琳 XIAO Zhihao;HU Zhihua;ZHU Lin(Logistics Research Center,Shanghai Maritime University,Shanghai 201306,China)

机构地区：[1]上海海事大学物流研究中心,上海201306

出　　处：《计算机应用》2022年第9期2926-2935,共10页journal of Computer Applications

基　　金：国家自然科学基金资助项目(71871136)。

摘　　要：针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题,提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题(TDVRP)。首先,根据连续型行驶时间依赖函数来刻画时变车速,采用综合油耗模型来评估实时燃油消耗量,并建立了以总成本最小化为目标的路径优化模型;然后,根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子,并将破坏-修复大邻域搜索算子融入到人工蜂群(ABC)算法之中,以提高算法的全局搜索能力。仿真实验结果表明,与自适应可变邻域搜索精英蚁群(AVNS_EAC)算法、自适应大邻域搜索精英蚁群(ALNS_EAC)算法、自适应大邻域搜索精英遗传(ALNS_EG)算法和自适应大邻域搜索模拟退火(ALNS_SA)算法相比,所提出的自适应大邻域搜索人工蜂群(ALNS_ABC)算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强,能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。Aiming at the problems of premature convergence and easily falling into local optimum in the adaptive large neighborhood search algorithms with single mechanism,a hybrid adaptive large neighborhood search algorithm was proposed to solve Time-Dependent Vehicle Routing Problem(TDVRP)in cold chain logistics. Firstly,the time-varying vehicle speed was described according to the continuous driving time dependent function,the real-time fuel consumption was evaluated by using the comprehensive fuel consumption model,and a routing optimization model with the goal of minimizing the total cost was established. Then, according to the NP(Non-deterministic Polynomial)-hard property and time-dependent characteristics of the problem,a variety of large neighborhood search operators for destroying and repairing solutions were designed,and the destroy-repair large neighborhood search operators were integrated into Artificial Bee Colony(ABC)algorithm to improve the global search ability of the algorithm. Simulation results show that compared with Adaptive Variable Neighborhood Search Elite Ant Colony(AVNS_EAC)algorithm,Adaptive Large Neighborhood Search Elite Ant Colony(ALNS_EAC)algorithm,Adaptive Large Neighborhood Search Elite Genetic(ALNS_EG)algorithm and Adaptive Large Neighborhood Search Simulated Annealing(ALNS_SA) algorithm,the proposed Adaptive Large Neighborhood Search Artificial Bee Colony(ALNS_ABC)algorithm has the optimal fitness values increased by 46. 3%,5. 3%,36. 8% and 6%respectively and averagely on multiple test data groups. It can be seen that this algorithm has higher computational performance and stronger stability,and can provide a more reasonable decision-making basis for cold chain logistics enterprises to take into account economic and environmental benefits at the same time.

关 键 词：冷链物流 车辆路径问题 时间依赖型 混合元启发式算法 自适应大邻域搜索 人工蜂群算法 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置] TP301.6[自动化与计算机技术—控制科学与工程]