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

doi:10.11772/j.issn.1001-9081.2021071361

《计算机应用》唯一官方网站 ›› 2022, Vol. 42 ›› Issue (9): 2926-2935.DOI: 10.11772/j.issn.1001-9081.2021071361

• 前沿与综合应用 • 上一篇

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

肖智豪, 胡志华(), 朱琳

上海海事大学物流研究中心，上海 201306

收稿日期:2021-07-30 修回日期:2021-10-13 接受日期:2021-10-14 发布日期:2021-10-25 出版日期:2022-09-10
通讯作者: 胡志华
作者简介:肖智豪（1997—），男，四川成都人，硕士研究生，主要研究方向：物流系统优化；
朱琳（1986—），女，天津人，讲师，博士，主要研究方向：车辆路径优化。
基金资助:
国家自然科学基金资助项目(71871136)

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

Zhihao XIAO, Zhihua HU(), Lin ZHU

Logistics Research Center，Shanghai Maritime University，Shanghai 201306，China

Received:2021-07-30 Revised:2021-10-13 Accepted:2021-10-14 Online:2021-10-25 Published:2022-09-10
Contact: Zhihua HU
About author:XIAO Zhihao， born in 1997， M. S. candidate. His research interests include optimization of logistics system.
ZHU Lin， born in 1986， Ph. D.， lecturer. Her research interests include vehicle routing optimization.
Supported by:
National Natural Science Foundation of China(71871136)

摘要/Abstract

摘要：

针对单一机制的自适应大邻域搜索算法存在早熟收敛、易陷入局部最优的问题，提出了一种混合自适应大邻域搜索算法来求解冷链物流时间依赖型车辆路径问题（TDVRP）。首先，根据连续型行驶时间依赖函数来刻画时变车速，采用综合油耗模型来评估实时燃油消耗量，并建立了以总成本最小化为目标的路径优化模型；然后，根据问题的NP-hard性质和时间依赖特性设计了多种破坏和修复解的大邻域搜索算子，并将破坏-修复大邻域搜索算子融入到人工蜂群（ABC）算法之中，以提高算法的全局搜索能力。仿真实验结果表明，与自适应可变邻域搜索精英蚁群（AVNS_EAC）算法、自适应大邻域搜索精英蚁群（ALNS_EAC）算法、自适应大邻域搜索精英遗传（ALNS_EG）算法和自适应大邻域搜索模拟退火（ALNS_SA）算法相比，所提出的自适应大邻域搜索人工蜂群（ALNS_ABC）算法在多组测试数据上的最优适应度值分别平均提高了46.3%、5.3%、36.8%和6%。可见所提算法计算性能更高、稳定性更强，能够为冷链物流企业兼顾经济效益和环境效益提供更为合理的决策依据。

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

Abstract:

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.

Key words: cold chain logistics, Vehicle Routing Problem （VRP）, time-dependent, hybrid metaheuristic algorithm, adaptive large neighborhood search, Artificial Bee Colony (ABC) algorithm

中图分类号:

TP273

肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 2022, 42(9): 2926-2935.

Zhihao XIAO, Zhihua HU, Lin ZHU. Hybrid adaptive large neighborhood search algorithm for solving time-dependent vehicle routing problem in cold chain logistics[J]. Journal of Computer Applications, 2022, 42(9): 2926-2935.

图/表 9

图1 接近真实路况的连续型时间依赖函数

Fig. 1 Continuous time dependent function close to real road conditions

表1 车辆参数定义与取值

Tab. 1 Definition and value of vehicle parameters

参数	定义	取值	参数	定义	取值
$ξ$	燃料与空气质量比	1	$g$	重力加速度/（m·s^-2）	9.8
$κ$	柴油热量值/（kJ·g^-1）	44	$μ$	车辆自重/kg	7 000
$ψ$	转换系数/（g·L^-1）	737	$ϕ$	道路角度	0
$k$	发动机摩擦因子	0.2	$C d$	空气阻力系数	0.7
$N e$	发动机转速	33	$C r$	滚动抵抗系数	0.01
$V$	发动机排量/L	5	$ε$	车辆传动系效率	0.4
$ρ$	空气密度/（kg·m^-3）	1.2	$ϖ$	柴油机效率系数	0.9
$A$	车辆迎风面/m²	7.135

表1 车辆参数定义与取值

Tab. 1 Definition and value of vehicle parameters

参数	定义	取值	参数	定义	取值
$ξ$	燃料与空气质量比	1	$g$	重力加速度/（m·s^-2）	9.8
$κ$	柴油热量值/（kJ·g^-1）	44	$μ$	车辆自重/kg	7 000
$ψ$	转换系数/（g·L^-1）	737	$ϕ$	道路角度	0
$k$	发动机摩擦因子	0.2	$C d$	空气阻力系数	0.7
$N e$	发动机转速	33	$C r$	滚动抵抗系数	0.01
$V$	发动机排量/L	5	$ε$	车辆传动系效率	0.4
$ρ$	空气密度/（kg·m^-3）	1.2	$ϖ$	柴油机效率系数	0.9
$A$	车辆迎风面/m²	7.135

表2 成本相关参数

Tab. 2 Cost related parameters

参数	参数设置	参数	参数设置
$F k$	200 元	$P f$	5.41 元/L
$P g$	18 元/kg	$P t$	30 元/t
$G t$	6 589 W/h	$Q m a x$	3 700 kg
$θ 1$	5 元/kW	$θ 2$	4 元/kW
$ϑ 1$	5 元/h	$ϑ 2$	12 元/h
$μ 1$	25 元/h	$μ 2$	50 元/h
$δ 1$	0.002	$δ 2$	0.003

表2 成本相关参数

Tab. 2 Cost related parameters

参数	参数设置	参数	参数设置
$F k$	200 元	$P f$	5.41 元/L
$P g$	18 元/kg	$P t$	30 元/t
$G t$	6 589 W/h	$Q m a x$	3 700 kg
$θ 1$	5 元/kW	$θ 2$	4 元/kW
$ϑ 1$	5 元/h	$ϑ 2$	12 元/h
$μ 1$	25 元/h	$μ 2$	50 元/h
$δ 1$	0.002	$δ 2$	0.003

表3 实例数据仿真结果

Tab. 3 Simulation results of data of a case

算法	最优结果	平均结果	最优配送路径
AVNS_EAC	1 785.12	1 830.49	0-15-1-12-10-11-0 0-6-3-7-8-13-0 0-5-4-2-9-14-0
ALNS_EAC	1 678.73	1 700.41	0-1-12-11-10-13-8-0 0-4-5-14-9-2-0 0-15-6-3-7-0
ALNS_EG		1 706.11
ALNS_SA		1 709.01
ALNS_ABC		1 694.69

表4 算例仿真结果

Tab. 4 Numerical example simulation results

编号	算例	ALNS_EG		ALNS_EAC		ALNS_SA		ALNS_ABC
编号	算例	最优结果	平均结果	最优结果	平均结果	最优结果	平均结果	最优结果	平均结果
1	R101-25	4 894.34	4 995.10	4800.97	4893.24	4 891.02	5 109.81	4800.97	4 904.19
2	R102-25	5 386.20	5 480.39	5273.47	5 334.78	5 388.56	5 516.26	5273.47	5334.57
3	R103-25	5 802.44	5 939.56	5 675.31	5769.04	5 730.97	5 920.48	5730.97	5 798.30
4	RC101-25	3030.48	3 115.84	3030.48	3 043.87	3 063.96	3 140.57	3030.48	3034.91
5	RC102-25	3 511.33	3 573.32	3492.98	3492.98	3 492.98	3 606.20	3492.98	3 499.67
6	RC103-25	3 944.12	4 013.58	3 910.64	3 917.33	3 910.64	4 003.94	3885.74	3907.60
7	R101-50	8 931.82	10 832.49	8 683.18	8 982.59	8 491.31	8 904.97	8368.07	8504.41
8	R102-50	10 192.11	11 366.46	9 479.40	9 777.37	9 197.99	9 607.79	9223.24	9423.52
9	R103-50	10 668.06	11 771.62	10 422.07	10 717.74	10009.64	10 674.36	10 044.99	10349.82
10	RC101-50	7 845.20	10 414.55	6 588.20	6 783.96	6 539.36	7 002.09	6478.17	6583.32
11	RC101-50	8 967.42	10 967.75	7 629.07	7 887.74	7500.31	7 967.25	7 540.41	7633.24
12	RC101-50	10 643.27	11 797.88	8 567.98	8 771.82	8 535.19	8 997.00	8371.44	8463.95

图2 不同混合算法的提升效果

Fig. 2 Improvement effect of different hybrid algorithms

图3 数据组R101-50、RC101-50的最优车辆运行图

Fig. 3 Optimal vehicle routing diagrams of data group R101-50 and RC101-50

图4 数据组R101-103-50、RC101-103-50的箱型图

Fig. 4 Box-plots of data group R101-103-50 and RC101-103-50

表5 不同算法的时间对比

Tab. 5 Comparison of time among different algorithms

算例	ALNS_EG		ALNS_EAC		ALNS_SA		ALNS_ABC
算例	收敛时间/s	CPU时间/s	收敛时间/s	CPU时间/s	收敛时间/s	CPU时间/s	收敛时间/s	CPU时间/s
R101-25	91.7	153.4	49.9	91.8	23.40	115.0	46.4	127.6
R102-25	91.5	150.7	48.7	89.5	21.40	118.5	44.5	117.3
R103-25	80.4	150.4	44.7	92.2	12.90	117.7	65.7	124.1
RC101-25	45.4	113.3	34.0	70.4	8.43	89.6	20.9	89.7
RC102-25	54.4	125.8	27.5	79.8	6.82	97.9	24.8	95.2
RC103-25	71.7	119.0	34.9	73.8	7.57	88.9	37.3	95.6
R101-50	233.9	396.2	202.0	343.2	148.90	302.4	200.6	315.1
R102-50	190.7	392.3	194.9	338.8	145.80	325.8	178.7	311.2
R103-50	256.7	419.0	167.8	366.1	203.70	332.4	205.0	322.7
RC101-50	230.8	349.3	140.4	302.1	72.10	248.8	145.0	262.1
RC101-50	211.1	335.0	126.2	288.9	99.10	240.1	194.6	243.7
RC101-50	180.5	334.5	111.2	291.2	119.80	256.7	139.2	244.1

参考文献 25

1	陈玉光，陈志祥. 基于准时送货和最小耗油的配送车辆路径问题研究［J］. 中国管理科学， 2015， 23（S1）：156-164.
	CHEN Y G， CHEN Z X. Study on vehicle routing problem with objectives of on-time delivery and oil consumption minimization［J］. Chinese Journal of Management Science， 2015， 23（S1）： 156-164.
2	HSIAO Y H， CHEN M C， LU K Y， et al. Last-mile distribution planning for fruit-and-vegetable cold chains［J］. The International Journal of Logistics Management， 2018， 29（3）： 862-886. 10.1108/ijlm-01-2017-0002
3	殷亚，张惠珍. 易腐生鲜货品车辆路径问题的改进混合蝙蝠算法［J］. 计算机应用， 2017， 37（12）：3602-3607. 10.11772/j.issn.1001-9081.2017.12.3602
	YIN Y， ZHANG H Z. Improved hybrid bat algorithm for vehicle routing problem of perishable fresh goods［J］. Journal of Computer Applications， 2017， 37（12）： 3602-3607. 10.11772/j.issn.1001-9081.2017.12.3602
4	方文婷，艾时钟，王晴，等. 基于混合蚁群算法的冷链物流配送路径优化研究［J］. 中国管理科学， 2019， 27（11）：107-115.
	FANG W T， AI S Z， WANG Q， et al. Research on cold chain logistics distribution path optimization based on hybrid ant colony algorithm［J］. Chinese Journal of Management Science， 2019， 27（11）： 107-115.
5	SONG M X， LI J Q， HAN Y Q， et al. Metaheuristics for solving the vehicle routing problem with the time windows and energy consumption in cold chain logistics［J］. Applied Soft Computing， 2020， 95： No.106561. 10.1016/j.asoc.2020.106561
6	ZHAO B L， GUI H X， LI H Z， et al. Cold chain logistics path optimization via improved multi-objective ant colony algorithm［J］. IEEE Access， 2020， 8： 142977-142995. 10.1109/access.2020.3013951
7	MALANDRAKI C， DASKIN M S. Time dependent vehicle routing problems formulations， properties and heuristic algorithms［J］. Transportation Science， 1992， 26（3）： 185-200. 10.1287/trsc.26.3.185
8	ICHOUA S， GENDREAU M， POTVIN J Y. Vehicle dispatching with time-dependent travel times［J］. European Journal of Operational Research， 2003， 144（2）： 379-396. 10.1016/s0377-2217(02)00147-9
9	OSVALD A， ZADNIK STIRN L. A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food［J］. Journal of Food Engineering， 2008， 85（2）： 285-295. 10.1016/j.jfoodeng.2007.07.008
10	白秦洋，尹小庆，林云. 考虑路网中实时交通的冷链物流路径优化［J］. 工业工程与管理， 2021， 26（6）：56-65.
	BAI Q Y， YIN X Q， LIN Y. The optimization of cold chain logistics route considering real-time traffic in road network［J］. Industrial Engineering and Management， 2021， 26（6）：56-65.
11	杜琛，李怡靖. 基于客户满意度和最小损耗的冷链配送路径问题研究［J］. 工业工程与管理， 2020， 25（6）：163-71.
	DU C， LI Y J. Research on cold chain distribution routing problem based on customer satisfaction and minimum loss［J］. Industrial Engineering and Management， 2020， 25（6）： 163-171.
12	赵志学，李夏苗. 时变交通下生鲜配送电动车辆路径优化方法［J］. 交通运输系统工程与信息， 2020， 20（5）：218-225， 239. 10.16097/j.cnki.1009-6744.2020.05.032
	ZHAO Z X， LI X M. Electric vehicle route optimization for fresh logistics distribution based on time-varying traffic congestion［J］. Journal of Transportation Systems Engineering and Information Technology， 2020， 20（5）： 218-225， 239. 10.16097/j.cnki.1009-6744.2020.05.032
13	付朝晖，刘长石. 生鲜电商配送的开放式时变车辆路径问题研究［J］.计算机工程与应用， 2021， 57（1）：271-278. 10.3778/j.issn.1002-8331.2006-0317
	FU Z H， LIU C S. Research on open time-dependent vehicle routing problem of fresh e-commerce distribution［J］. Computer Engineering and Applications， 2021， 57（1）： 271-278. 10.3778/j.issn.1002-8331.2006-0317
14	任腾，罗天羽，李姝萱，等. 面向冷链物流配送路径优化的知识型蚁群算法［J］. 控制与决策， 2022， 37（3）： 545-554.
	REN T， LUO T Y， LI S X， et al. Knowledge based ant colony algorithm for cold chain logistics distribution path optimization［J］. Control and Decision， 2022， 37（3）： 545-554.
15	XIAO Y Y， ZHAO Q H， KAKU I， et al. Development of a fuel consumption optimization model for the capacitated vehicle routing problem［J］. Computers and Operations Research， 2012， 39（7）： 1419-1431. 10.1016/j.cor.2011.08.013
16	CHEN S F， CHEN R， WANG G G， et al. An adaptive large neighborhood search heuristic for dynamic vehicle routing problems［J］. Computers and Electrical Engineering， 2018， 67： 596-607. 10.1016/j.compeleceng.2018.02.049
17	CHEN C， DEMIR E， HUANG Y. An adaptive large neighborhood search heuristic for the vehicle routing problem with time windows and delivery robots［J］. European Journal of Operational Research， 2021， 294（3）： 1164-1180. 10.1016/j.ejor.2021.02.027
18	FRANCESCHETTI A， DEMIR E， HONHON D， et al. A metaheuristic for the time-dependent pollution-routing problem［J］. European Journal of Operational Research， 2017， 259（3）： 972-991. 10.1016/j.ejor.2016.11.026
19	CHEN L， LIU Y， LANGEVIN A. A multi-compartment vehicle routing problem in cold-chain distribution［J］. Computers and Operations Research， 2019， 111： 58-66. 10.1016/j.cor.2019.06.001
20	FRANCESCHETTI A， HONHON D， VAN WOENSEL T， et al. The time-dependent pollution-routing problem［J］. Transportation Research Part B： Methodological， 2013， 56： 265-293. 10.1016/j.trb.2013.08.008
21	BARTH M， BORIBOONSOMSIN K. Real-world carbon dioxide impacts of traffic congestion［J］. Transportation Research Record： Journal of the Transportation Research Board， 2008， 2058（1）： 163-171. 10.3141/2058-20
22	BARTH M， BORIBOONSOMSIN K. Energy and emissions impacts of a freeway-based dynamic eco-driving system［J］. Transportation Research Part D： Transport and Environment， 2009， 14（6）： 400-410. 10.1016/j.trd.2009.01.004
23	穆东，王超，王胜春，等. 基于并行模拟退火算法求解时间依赖型车辆路径问题［J］. 计算机集成与制造系统， 2015， 21（6）：1626-1636. 10.13196/j.cims.2015.06.027
	MU D， WANG C， WANG S C， et al. Solving TDVRP based on parallel-simulated annealing algorithm［J］. Computers Integrated Manufacturing Systems， 2015， 21（6）： 1626-1636. 10.13196/j.cims.2015.06.027
24	SHAW P. Using constraint programming and local search methods to solve vehicle routing problems［C］// Proceedings of the 1998 International Conference on Principles and Practice of Constraint Programming， LNCS 1520. Berlin： Springer， 1998： 417-431.
25	HE M L， WEI Z X， WU X H， et al. An adaptive variable neighborhood search ant colony algorithm for vehicle routing problem with soft time windows［J］. IEEE Access， 2021， 9： 21258-21266. 10.1109/access.2021.3056067

[1]	李进, 王凤, 杨沈宇. 换电模式下电动车货运路径优化模型与算法[J]. 计算机应用, 2021, 41(6): 1792-1798.
[2]	魏博, 杨茸, 舒思豪, 万勇, 苗建国. 基于离子运动-人工蜂群算法的移动机器人路径规划[J]. 计算机应用, 2021, 41(2): 379-383.
[3]	李文霞, 刘林忠, 代存杰, 李玉. 基于多种群组合策略的人工蜂群算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3113-3119.
[4]	李华峰, 黄樟灿, 张蔷, 湛航, 谈庆. 求解需求可拆分车辆路径问题的改进的金字塔演化策略[J]. 计算机应用, 2021, 41(1): 300-306.
[5]	汤星峰, 徐卿钦, 马世纬. 基于路径探索的车载自组网贪婪路由算法[J]. 计算机应用, 2020, 40(6): 1738-1744.
[6]	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
[7]	张架鹏, 倪志伟, 倪丽萍, 朱旭辉, 伍章俊. 基于改进离散人工蜂群算法的同类机调度优化[J]. 计算机应用, 2020, 40(3): 689-697.
[8]	李卓, 李引珍, 李文霞. 应急物资运输路径多目标优化模型及求解算法[J]. 计算机应用, 2019, 39(9): 2765-2771.
[9]	张玉州, 徐廷政, 郑军帅, 饶舜. 考虑紧急度的救灾车辆路径问题建模与优化[J]. 计算机应用, 2019, 39(8): 2444-2449.
[10]	张志强, 鲁晓锋, 孙钦东, 王侃. 增强开发能力的改进人工蜂群算法[J]. 计算机应用, 2019, 39(4): 949-955.
[11]	张维存, 高蕊, 张曼. 作业车间环境下的采购生产配送联合调度模型[J]. 计算机应用, 2019, 39(11): 3383-3390.
[12]	方春林, 刘晓娟, 辛营营, 罗欢. 基于人工蜂群算法的轨道交通列车行车间隔优化[J]. 计算机应用, 2018, 38(9): 2725-2729.
[13]	石建力, 张锦. 行驶时间随机的分批配送车辆路径问题模型与算法[J]. 计算机应用, 2018, 38(2): 573-581.
[14]	何东东, 李引珍. 多车型绿色车辆路径问题优化模型[J]. 计算机应用, 2018, 38(12): 3618-3624.
[15]	梁冰, 徐华. 基于改进人工蜂群的核模糊聚类算法[J]. 计算机应用, 2017, 37(9): 2600-2604.

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

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

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 9

参考文献 25

相关文章 15

编辑推荐

Metrics