Journal of Computer Applications ›› 2022, Vol. 42 ›› Issue (9): 2926-2935.DOI: 10.11772/j.issn.1001-9081.2021071361
• Frontier and comprehensive applications • Previous Articles Next Articles
Zhihao XIAO, Zhihua HU(), Lin ZHU
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.Supported by:
通讯作者:
胡志华
作者简介:
肖智豪(1997—),男,四川成都人,硕士研究生,主要研究方向:物流系统优化;基金资助:
CLC Number:
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.
肖智豪, 胡志华, 朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2022, 42(9): 2926-2935.
Add to citation manager EndNote|Ris|BibTeX
URL: https://www.joca.cn/EN/10.11772/j.issn.1001-9081.2021071361
参数 | 定义 | 取值 | 参数 | 定义 | 取值 |
---|---|---|---|---|---|
燃料与空气质量比 | 1 | 重力加速度/(m·s-2) | 9.8 | ||
柴油热量值/(kJ·g-1) | 44 | 车辆自重/kg | 7 000 | ||
转换系数/(g·L-1) | 737 | 道路角度 | 0 | ||
发动机摩擦因子 | 0.2 | 空气阻力系数 | 0.7 | ||
发动机转速 | 33 | 滚动抵抗系数 | 0.01 | ||
发动机排量/L | 5 | 车辆传动系效率 | 0.4 | ||
空气密度/(kg·m-3) | 1.2 | 柴油机效率系数 | 0.9 | ||
车辆迎风面/m2 | 7.135 |
Tab. 1 Definition and value of vehicle parameters
参数 | 定义 | 取值 | 参数 | 定义 | 取值 |
---|---|---|---|---|---|
燃料与空气质量比 | 1 | 重力加速度/(m·s-2) | 9.8 | ||
柴油热量值/(kJ·g-1) | 44 | 车辆自重/kg | 7 000 | ||
转换系数/(g·L-1) | 737 | 道路角度 | 0 | ||
发动机摩擦因子 | 0.2 | 空气阻力系数 | 0.7 | ||
发动机转速 | 33 | 滚动抵抗系数 | 0.01 | ||
发动机排量/L | 5 | 车辆传动系效率 | 0.4 | ||
空气密度/(kg·m-3) | 1.2 | 柴油机效率系数 | 0.9 | ||
车辆迎风面/m2 | 7.135 |
参数 | 参数设置 | 参数 | 参数设置 |
---|---|---|---|
200 元 | 5.41 元/L | ||
18 元/kg | 30 元/t | ||
6 589 W/h | 3 700 kg | ||
5 元/kW | 4 元/kW | ||
5 元/h | 12 元/h | ||
25 元/h | 50 元/h | ||
0.002 | 0.003 |
Tab. 2 Cost related parameters
参数 | 参数设置 | 参数 | 参数设置 |
---|---|---|---|
200 元 | 5.41 元/L | ||
18 元/kg | 30 元/t | ||
6 589 W/h | 3 700 kg | ||
5 元/kW | 4 元/kW | ||
5 元/h | 12 元/h | ||
25 元/h | 50 元/h | ||
0.002 | 0.003 |
算法 | 最优结果 | 平均结果 | 最优配送路径 |
---|---|---|---|
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 |
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 |
编号 | 算例 | 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 |
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 |
算例 | 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 |
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 |
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] | Yan LI, Dazhi PAN, Siqing ZHENG. Improved adaptive large neighborhood search algorithm for multi-depot vehicle routing problem with time window [J]. Journal of Computer Applications, 2024, 44(6): 1897-1904. |
[2] | Jianqiang LI, Zhou HE. Hybrid NSGA-Ⅱ for vehicle routing problem with multi-trip pickup and delivery [J]. Journal of Computer Applications, 2024, 44(4): 1187-1194. |
[3] | Jian LIN, Jingxuan YE, Wenwen LIU, Xiaowen SHAO. Multimodal differential evolution algorithm for solving capacitated vehicle routing problem [J]. Journal of Computer Applications, 2023, 43(7): 2248-2254. |
[4] | Zhinan LI, Qinming LIU, Haoyang LU. Allocation model of urban emergency medical supplies based on random evolution from perspective of resilience [J]. Journal of Computer Applications, 2023, 43(3): 978-985. |
[5] | Yu XU, Yunyou ZHU, Xiao LIU, Yuting DENG, Yong LIAO. Multi-objective routing optimization of electric power material distribution based on deep reinforcement learning [J]. Journal of Computer Applications, 2022, 42(10): 3252-3258. |
[6] | Zhishuo LIU, Ruosi LIU, Zhe CHEN. Cold chain electric vehicle routing problem based on hybrid ant colony optimization [J]. Journal of Computer Applications, 2022, 42(10): 3244-3251. |
[7] | WEI Bo, YANG Rong, SHU Sihao, WAN Yong, MIAO Jianguo. Path planning of mobile robots based on ion motion-artificial bee colony algorithm [J]. Journal of Computer Applications, 2021, 41(2): 379-383. |
[8] | Wenxia LI, Linzhong LIU, Cunjie DAI, Yu LI. Artificial bee colony algorithm based on multi-population combination strategy [J]. Journal of Computer Applications, 2021, 41(11): 3113-3119. |
[9] | ZHANG Yuzhou, XU Tingzheng, ZHENG Junshuai, RAO Shun. Modeling and optimization of disaster relief vehicle routing problem considering urgency [J]. Journal of Computer Applications, 2019, 39(8): 2444-2449. |
[10] | ZHANG Zhiqiang, LU Xiaofeng, SUN Qindong, WANG Kan. Improved artificial bee colony algorithm with enhanced exploitation ability [J]. Journal of Computer Applications, 2019, 39(4): 949-955. |
[11] | ZHANG Weicun, GAO Rui, ZHANG Man. Procurement-production-distribution joint scheduling model in job shop environment [J]. Journal of Computer Applications, 2019, 39(11): 3383-3390. |
[12] | FANG Chunlin, LIU Xiaojuan, XIN Yingying, LUO Huan. Train interval optimization of rail transit based on artificial bee colony algorithm [J]. Journal of Computer Applications, 2018, 38(9): 2725-2729. |
[13] | SHI Jianli, ZHANG Jin. Model and algorithm for split delivery vehicle routing problem with stochastic travel time [J]. Journal of Computer Applications, 2018, 38(2): 573-581. |
[14] | LIANG Bing, XU Hua. Kernel fuzzy C-means clustering based on improved artificial bee colony algorithm [J]. Journal of Computer Applications, 2017, 37(9): 2600-2604. |
[15] | YANG Wang, HE Guochao, WU Yan. Density clustering based removal heuristic for vehicle routing problem [J]. Journal of Computer Applications, 2017, 37(8): 2387-2394. |
Viewed | ||||||
Full text |
|
|||||
Abstract |
|
|||||