A Hybrid Heuristic Algorithm for Solving the Green VRP with Priority Delivery

doi:10.16182/j.issn1004731x.joss.23-1125

Abstract

Abstract:

This paper considers the problem that some customers' goods cannot be mixed in logistics distribution. Based on the traditional green vehicle routing problem with simultaneous pickup and delivery,customers are divided into three types: priority delivery, non-priority only pickup without delivery, and non-priority pickup with delivery. A single objective nonlinear optimization model is established to minimize the total cost. A hybrid heuristic method based on simulated annealing and adaptive large neighborhood search algorithm is designed. An improved saving algorithm is used to construct the initial solution. And 5 kinds of destruction operators and 2 kinds of repair operators are used in the simulated annealing algorithm framework for adaptive large neighborhood search, until stability is achieved. The simulation results indicate that the proposed method can effectively reduce total costs and the number of vehicles, and has fast convergence speed and strong stability.

Key words: green vehicle routing problem, simultaneous pickup and delivery, savings algorithm, simulated annealing, adaptive large neighborhood search

CLC Number:

TP391.9

Cui Huanhuan, Guan Lihe. A Hybrid Heuristic Algorithm for Solving the Green VRP with Priority Delivery[J]. Journal of System Simulation, 2025, 37(2): 413-423.

Figures/Tables 8

Table 1

Explanation of notations

符号	含义
$N 1$	需要优先配送的客户集合
$N 2$	非优先只取不送的客户集合
$N 3$	非优先有取有送的客户集合
$N$	客户集合，包括配送中心0，且客户数为 $n$
$K 1$	用于优先配送客户的车辆集合
$K 2$	用于非优先配送客户的车辆集合
$K$	配送车辆集合，即 $K = K 1 ⋃ K 2$
$r k$	第 $k ∈ K$ 辆车的行驶路线
$d i, j$	客户 $i ∈ N$ 和 $j ∈ N$ 之间的距离
$Q$	车辆最大载重量
$q i$	客户 $i ∈ N / {0}$ 的配送需求量
$p i$	客户 $i ∈ N / {0}$ 的取货需求量
$u i, j k$	车辆 $k ∈ K$ 从客户 $i ∈ N$ 到客户 $j ∈ N$ ( $i ≠ j$ )时车载剩余送货量
$v i, j k$	车辆 $k ∈ K$ 从客户 $i ∈ N$ 到客户 $j ∈ N$ ( $i ≠ j$ )时车载已取货量
$x i, j k$	车辆 $k ∈ K$ 从客户 $i ∈ N$ 到客户 $j ∈ N$ ( $i ≠ j$ )时 $x i, j k = 1$ ，反之为0
$Q D$	配送中心需配送货物总量，且 $Q D = ∑ i ∈ N / {0} q i$
$Q P$	配送中心需取回货物总量，且 $Q P = ∑ i ∈ N / {0} p i$
$ρ i, j k$	车辆 $k ∈ K$ 从客户 $i ∈ N$ 到客户 $j ∈ N$ ( $i ≠ j$ )的油耗率
$ρ m i n$	车辆空载时的油耗率
$ρ m a x$	车辆满载时的油耗率
$c p$	司机薪资的每公里单价
$c f$	燃油成本单价
$c v$	车辆成本单价

Table 1

Table 2

Explanation of notations in algorithm

符号	含义
$R 1$	优先配送客户路径集合
$R 2$	非优先只取不送客户路径集合
$R 3$	非优先有取有送客户路径集合
$w$	$w = \| r k \|$ 为路线 $r k$ 服务的客户数
$L$	记路线 $r k$ 的客户 $k l$ 与客户 $k l + 1$ 之间的位置为第L个候选插入位置， $0 ≤ L = l ≤ w$
$L (k, j)$	路线 $r j$ 的客户插入路线 $r k$ 的可行候选插入位置集合
$H$	破坏算子集合 $H = {H 1, H 2, H 3, H 4, H 5}$
$I$	修复算子集合 $I = {I 1, I 2}$
$l$	删除列表
$s$	删除列表长度
$T 0$	初始温度
$T e n d$	终止温度
$m$	降温次数
$T m$	第m次降温后的温度
$P h T m$	算子 $h ∈ H ⋃ I$ 在温度 $T m$ 时被选择的概率
$η$	轮盘赌参数
$t$	每个温度下的迭代次数
$M$	最大迭代次数
$R b e s t$	当前最优解
$R c u r$	当前解
$α$	温度下降率
$π h T m$	算子 $h ∈ H ⋃ I$ 在温度 $T m$ 下的得分
$ω h T m$	算子 $h ∈ H ⋃ I$ 在温度 $T m$ 下已被使用次数
$δ 1$	新解优于当前最优解时算子得分
$δ 2$	新解劣于当前最优解但优于当前解时算子得分
$δ 3$	新解比当前解差但被接受时算子得分

Table 2

Fig. 1

Table 3

Results of two distribution strategy on Solomon instances

算例	TSD(单独配送)			SA-ALNS(优先配送)			相对偏差/%
算例	(C₁, Z₁)	(C₂, σ₁)	(Z₂, σ₂)	(C₁, Z₁)	(C₂, σ₁)	(Z₂, σ₂)	RE₁	RE₂	RE₃
Rdp101	(16, 18 862)	(16.1, 0.32)	(19 158, 241)	(14, 17 725)	(14.2, 0.42)	(17 949, 148)	14.29	6.41	6.74
Rdp102	(16, 18 990)	(16.3, 0.48)	(19 193, 164)	(14, 17 945)	(14.4, 0.52)	(18 239, 110)	14.29	5.82	5.23
Rdp103	(16, 18 830)	(16.5, 0.53)	(19 171, 261)	(14, 17 563)	(14, 0)	(17 670, 96)	14.29	7.21	8.50
Rdp104	(16, 18 866)	(17.1, 0.57)	(19 659, 349)	(14, 18 150)	(14.7, 0.48)	(18 312, 119)	14.29	3.95	7.35
Rdp105	(16, 18 771)	(16.6, 0.52)	(19 367, 342)	(15, 17 965)	(15, 0)	(18 069, 72)	6.67	4.49	7.19
Rdp106	(17, 18 877)	(17.3, 0.48)	(19 489, 385)	(14, 18 172)	(14.5, 0.53)	(18 330, 125)	21.43	3.88	6.32
Rdp107	(17, 19 338)	(17.1, 0.32)	(19 807, 246)	(15, 18 493)	(15, 0)	(18 669, 102)	13.33	4.57	6.09
Rdp108	(16, 18 783)	(16.3, 0.48)	(19 137, 211)	(14, 17 882)	(14.5, 0.53)	(18 220, 273)	14.29	5.03	5.03
Rdp109	(17, 19 271)	(17, 0)	(19 666, 204)	(15, 18 333)	(15, 0)	(18 374, 44)	13.33	5.12	7.03
Rdp110	(17, 19 778)	(17.1, 0.32)	(20 038, 182)	(15, 18 217)	(15, 0)	(18 491, 106)	13.33	8.57	8.37
Rdp111	(17, 19 539)	(18, 0.47)	(20 082, 259)	(15, 18 413)	(15, 0)	(18 540, 94)	13.33	6.11	8.32
Rdp112	(17, 19 317)	(17.4, 0.52)	(19 948, 298)	(15, 18 050)	(15, 0)	(18 290, 202)	13.33	7.02	9.06
平均值	(16.5, 19 102)	(16.9, 0.42)	(19 560, 262)	(14.5, 18 076)	(14.7, 0.21)	(18 263, 124)	13.85	5.68	7.10
Cdp101	(19, 20 810)	(19.6, 0.52)	(21 043, 147)	(15, 19 503)	(15.9, 0.32)	(19 781, 162)	26.67	6.70	6.38
Cdp102	(19, 22 149)	(19.5, 0.53)	(22 339, 195)	(14, 20 710)	(14, 0)	(20 865, 147)	35.71	6.95	7.07
Cdp103	(19, 22 763)	(19, 0)	(23 042, 217)	(16, 20 859)	(16, 0)	(20 954, 67)	18.75	9.13	9.97
Cdp104	(20, 21 247)	(20, 0)	(21 301, 24)	(15, 20 532)	(15.9, 0.32)	(20 904, 380)	33.33	3.48	1.90
Cdp105	(19, 21 696)	(19.1, 0.32)	(21 762, 96)	(14, 21 157)	(14, 0)	(21 367, 113)	35.71	2.54	1.85
Cdp106	(20, 22 439)	(20, 0)	(22 439, 0)	(14, 21 108)	(14, 0)	(21 163, 64)	42.86	6.30	6.03
Cdp107	(20, 21 976)	(20, 0)	(22 757, 275)	(15, 21 092)	(15.6, 0.52)	(21 198, 84)	33.33	4.19	7.36
Cdp108	(19, 21 967)	(19.3, 0.48)	(22 060, 65)	(14, 20 508)	(14.4, 0.52)	(21 153, 259)	35.71	7.12	4.29
Cdp109	(19, 21 668)	(19.7, 0.48)	(21 819, 92)	(16, 20 552)	(16, 0)	(20 653, 73)	18.75	5.43	5.64
平均值	(19.3, 21 857)	(19.6, 0.26)	(22 063, 123)	(14.8, 20 669)	(15.1, 0.19)	(20 893, 150)	31.20	5.76	5.61
RCdp101	(18, 23 336)	(18, 0)	(23 394, 69)	(14, 22 186)	(14, 0)	(22 385, 264)	28.57	5.18	4.51
RCdp102	(18, 23 678)	(18, 0)	(23 740, 37)	(14, 20 901)	(14, 0)	(21 236, 170)	28.57	13.29	11.79
RCdp103	(18, 25 139)	(18, 0)	(25 282, 86)	(14, 22 019)	(14, 0)	(22 174, 159)	28.57	14.17	14.02
RCdp104	(18, 23 887)	(18, 0)	(24 060, 121)	(14, 21 069)	(14.5, 0.53)	(21 420, 288)	28.57	13.37	12.32
RCdp105	(18, 23 635)	(18, 0)	(24 061, 279)	(14, 20 715)	(14, 0)	(20 913, 86)	28.57	14.09	15.06
RCdp106	(18, 22 866)	(18.1, 0.32)	(23 438, 408)	(14, 20 864)	(14.6, 0.52)	(21 195, 309)	28.57	9.59	10.58
RCdp107	(18, 24 685)	(18.2, 0.42)	(25 243, 360)	(14, 20 406)	(14, 0)	(20 525, 87)	28.57	20.97	22.99
RCdp108	(17, 23 488)	(17.9, 0.32)	(23 922, 295)	(14, 21 819)	(14, 0)	(21 932, 76)	21.43	7.65	9.07
平均值	(17.9, 23 839)	(18, 0.13)	(24 142, 207)	(14, 21 247)	(14.1, 0.13)	(21 472, 180)	27.68	12.29	12.54
总均值	(17.8, 21 264)	(18, 0.29)	(21 601, 204)	(14.4, 19 756)	(14.7, 0.18)	(19 964, 148)	23.05	7.53	8.14

Table 3

Table 4

Table 5

Table 6

Fig. 2

References 18

1	周鲜成, 周开军, 王莉, 等. 物流配送中的绿色车辆路径模型与求解算法研究综述[J]. 系统工程理论与实践, 2021, 41(1): 213-230.
	Zhou Xiancheng, Zhou Kaijun, Wang Li, et al. Review of Green Vehicle Routing Model and Its Algorithm in Logistics Distribution[J]. Systems Engineering-Theory & Practice, 2021, 41(1): 213-230.
2	Erdoğan Sevgi, Miller-Hooks E. A Green Vehicle Routing Problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.
3	Ferreira K M, Queiroz T A, Toledo F M B. An Exact Approach for the Green Vehicle Routing Problem with Two-dimensional Loading Constraints and Split Delivery[J]. Computers & Operations Research, 2021, 136: 105452.
4	胡蓉, 陈文博, 钱斌, 等. 学习型蚁群算法求解绿色多车场车辆路径问题[J]. 系统仿真学报, 2021, 33(9): 2095-2108.
	Hu Rong, Chen Wenbo, Qian Bin, et al. Learning Ant Colony Algorithm for Green Multi-depot Vehicle Routing Problem[J]. Journal of System Simulation, 2021, 33(9): 2095-2108.
5	Poonthalir G, Nadarajan R. A Fuel Efficient Green Vehicle Routing Problem with Varying Speed Constraint (F-GVRP)[J]. Expert Systems with Applications, 2018, 100: 131-144.
6	高飞. 不确定因素下配送路径优化问题研究[D]. 北京: 北京交通大学, 2019.
	Gao Fei. Research on Distribution Routing Optimization Problems with Uncertain Factor[D]. Beijing: Beijing Jiaotong University, 2019.
7	Majidi S, Hosseini-Motlagh S M, Ignatius J. Adaptive Large Neighborhood Search Heuristic for Pollution-routing Problem with Simultaneous Pickup and Delivery[J]. Soft Computing, 2018, 22(9): 2851-2865.
8	Foroutan R A, Rezaeian J, Mahdavi I. Green Vehicle Routing and Scheduling Problem with Heterogeneous Fleet Including Reverse Logistics in the Form of Collecting Returned Goods[J]. Applied Soft Computing, 2020, 94: 106462.
9	Qi Rui, Li Junqing, Wang Juan, et al. QMOEA: A Q-learning-based Multiobjective Evolutionary Algorithm for Solving Time-dependent Green Vehicle Routing Problems with Time Windows[J]. Information Sciences, 2022, 608: 178-201.
10	Niu Yunyun, Yang Zehua, Wen Rong, et al. Solving the Green Open Vehicle Routing Problem Using a Membrane-inspired Hybrid Algorithm[J]. Sustainability, 2022, 14(14): 8661.
11	Majidi S, Hosseini-Motlagh S M, Yaghoubi S, et al. Fuzzy Green Vehicle Routing Problem with Simultaneous Pickup-delivery and Time Windows[J]. Rairo-Operations Research, 2017, 51(4): 1151-1176.
12	Olgun B, Koç C, Altıparmak F. A Hyper Heuristic for the Green Vehicle Routing Problem with Simultaneous Pickup and Delivery[J]. Computers & Industrial Engineering, 2021, 153: 107010.
13	Polat O, Kalayci C B, Topaloğlu D. Modelling and Solving the Milk Collection Problem with Realistic Constraints[J]. Computers & Operations Research, 2022, 142: 105759.
14	Wang Zheng, Li Ying, Hu Xiangpei. A Heuristic Approach and a Tabu Search for the Heterogeneous Multi-type Fleet Vehicle Routing Problem with Time Windows and an Incompatible Loading Constraint[J]. Computers & Industrial Engineering, 2015, 89: 162-176.
15	Kirkpatrick S, Gelatt C D, Vecchi M P. Optimization by Simulated Annealing[J]. Science, 1983, 220(4598): 671-680.
16	贺琪, 官礼和, 崔焕焕. 硬时间窗VRP的混合变邻域禁忌搜索算法[J]. 计算机工程与应用, 2023, 59(13): 82-91.
	He Qi, Guan Lihe, Cui Huanhuan. Hybrid Variable Neighborhood Tabu Search Algorithm for Vehicle Routing Problem with Hard Time Window[J]. Computer Engineering and Applications, 2023, 59(13): 82-91.
17	李珺, 段钰蓉, 郝丽艳, 等. 混合优化算法求解同时送取货车辆路径问题[J]. 计算机科学与探索, 2022, 16(7): 1623-1632.
	Li Jun, Duan Yurong, Hao Liyan, et al. Hybrid Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery-pickup[J]. Journal of Frontiers of Computer Science & Technology, 2022, 16(7): 1623-1632.
18	Wang Hsiaofan, Chen Yingyen. A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window[J]. Computers and Industrial Engineering, 2012, 62(1): 84-95.

算例	n	HH-ILS[12]			SA-ALNS			相对偏差(%)
算例	n	(C₁, Z₁₎	(C₂, σ₁)	(Z₂, σ₂)	(C₁, Z₁)	(C₂, σ₁)	(Z₂, σ₂)	RE₁	RE₂	RE₃
平均值		(17.9, 23 517)	(19, 0.9)	(24 863, 954)	(14.5, 20 110)	(14.6, 0.2)	(20 411, 205)	22.87	18.02	23.20
CMTX1	50	(8, 11 501)	(8.5, 0.7)	(11 966, 402)	(7, 9 332)	(7, 0)	(9 462, 108)	14.29	23.24	26.47
CMTX2	75	(13, 14 030)	(14.1, 0.7)	(15 606, 623)	(11, 12 420)	(11.3, 0.5)	(12 596, 148)	18.18	12.96	23.90
CMTX3	100	(16, 21 872)	(17.8, 1.6)	(23 290, 994)	(12, 17 672)	(12.1, 0.3)	(17 710, 43)	33.33	23.77	31.51
CMTX4	150	(22, 28 793)	(23.3, 1.2)	(29 769, 1 115)	(19, 24 089)	(19, 0)	(24 236, 87)	15.79	19.53	22.83
CMTX5	199	(32, 38 297)	(32.8, 0.9)	(41 115, 1 488)	(25, 32 737)	(25, 0)	(33 010, 154)	28.00	16.98	24.56
CMTX6	50	(9, 12 133)	(10, 0.7)	(12 878, 547)	(7, 9 301)	(7, 0)	(9 301, 0)	28.57	30.44	38.46
CMTX7	75	(15, 15 100)	(16.4, 1.1)	(15 939, 604)	(11, 12 562)	(11.1, 0.3)	(12 769, 84)	36.36	20.21	24.83
CMTX8	100	(18, 22 980)	(19.1, 0.7)	(24 120, 970)	(13, 17 270)	(13, 0)	(17 408, 118)	38.46	33.07	38.56
CMTX9	150	(22, 29 050)	(23.9, 0.9)	(30 139, 687)	(19, 23 932)	(19, 0)	(24 062, 100)	15.79	21.38	25.25
CMTX10	199	(33, 40 029)	(33.6, 0.7)	(41 740, 1 519)	(25, 32 683)	(25.4, 0.5)	(33 252, 263)	32.00	22.48	25.53
CMTX11	120	(16, 27 745)	(16.9, 0.9)	(28 421, 516)	(14, 25 949)	(14.3, 0.5)	(26 409, 442)	14.29	6.92	7.62
CMTX12	100	(15, 20 963)	(16.3, 0.9)	(22 429, 1 349)	(13, 19 143)	(13.3, 0.5)	(20 037, 529)	15.38	9.51	11.94
CMTX13	120	(16, 26 295)	(17.4, 0.7)	(28 856, 1 124)	(14, 25 850)	(14.4, 0.5)	(26 293, 383)	14.29	1.72	9.75
CMTX14	100	(15, 20 456)	(15.7, 0.7)	(21 818, 1 414)	(13, 18 593)	(13, 0)	(19 215, 412)	15.38	10.02	13.54

算例	SA-ALNS	SA-ALNS-H₁	SA-ALNS-H₂	SA-ALNS-H₃	SA-ALNS-H₄	SA-ALNS-H₅
算例	Z₂	∆Z₂-H₁	∆Z₂-H₂	∆Z₂-H₃	∆Z₂-H₄	∆Z₂-H₅
平均值		+354	+240	+399	+227	+200
Rdp101	17 949	+22	+9	+161	+21	+93
Rdp103	17 670	+71	+73	+90	+56	+17
Rdp105	18 069	+145	+16	+230	+48	+2
Cdp102	20 865	+673	+334	+400	+273	+302
Cdp103	20 954	+276	+67	+150	+119	+104
Cdp105	21 367	+336	+117	+145	+146	+98
RCdp103	22 174	+16	+45	+399	+9	+13
RCdp104	21 420	+1 071	+1 040	+1 419	+879	+676
RCdp105	20 913	+577	+459	+596	+491	+496

算例	SA-ALNS	SA-ALNS-I₁	SA-ALNS-I₂
算例	Z₂	∆Z₂-I₁	∆Z₂-I₂
平均值		+281	+251
Rdp101	17 949	+80	+23
Rdp103	17 670	+74	+60
Rdp105	18 069	+112	+58
Cdp102	20 865	+349	+214
Cdp103	20 954	+105	+67
Cdp105	21 367	+168	+181
RCdp103	22 174	+55	+96
RCdp104	21 420	+1 040	+1 098
RCdp105	20 913	+542	+461

[1]	Xu Qiang, Xu Jianlei, Hu Yanhai, Chen Haihui, Zhang Xing, Xing Zhaohui. Trajectory Optimization of Robotic Arm Based on Improved Simulated Annealing Genetic Algorithm [J]. Journal of System Simulation, 2025, 37(2): 404-412.
[2]	Zhang Zhenli, Wang Yongzhuang, Qin Yao, Yang Jie. Maglev Ball Control Algorithm Based on Levant Differentiator [J]. Journal of System Simulation, 2024, 36(7): 1586-1595.
[3]	Zhang Hongli, Deng Jingshuang. Research on Artificial Population Generation and Application Based on Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(9): 1965-1974.
[4]	Lizhen Du, Tao Ye, Yuhao Wang, Yajun Zhang, Zifeng Xuan. Improved Particle Swarm Algorithm of Unrelated Parallel Batch Scheduling Optimization [J]. Journal of System Simulation, 2023, 35(7): 1549-1561.
[5]	Shao Liangshan, Wang Zhen, Li Changming. Optimization Algorithm of Mine Ventilation Based on SA-IPSO [J]. Journal of System Simulation, 2021, 33(9): 2085-2094.
[6]	Lu Jiabo, Cheng Peixing, Huang Yi, Yao Jinqiang, Yang Xuemeng, Ma Xinqiang, Liu Yong. An Intelligent Method for Rapid Construction of Time Sensitive Target Strike Chain [J]. Journal of System Simulation, 2021, 33(2): 346-357.
[7]	Cai Min, Wang Yan, Ji Zhicheng. Research on MOFFJSP Based on Multi-strategy Fusion Quantum Particle Swarm Optimization [J]. Journal of System Simulation, 2021, 33(11): 2615-2626.
[8]	Li Zhenping, Zhao Yuwei, Zhang Yuwei, Xing Lining, Ren Teng. Joint Distribution Location-routing Problem and Large Neighborhood Search Algorithm [J]. Journal of System Simulation, 2021, 33(10): 2518-2531.
[9]	Shen Peng, Wang Yan, Ji Zhicheng, Zhang Jianhua. Hyper-heuristic DE Algorithm for Solving Zero-wait Fermentation Process Schedulinge [J]. Journal of System Simulation, 2020, 32(11): 2235-2243.
[10]	Zhao Wenqing, Qin Zhibu. Improved Intelligent Water Drops Algorithm Applied to Power Economic Emission Dispatch [J]. Journal of System Simulation, 2018, 30(8): 3213-3218.
[11]	Liu Wei, Xu Jiaxuan, Wang Peipei, Liu Ruilong, Tang Jingkun. Train Energy Saving Operation Based on Simulated Annealing Algorithm [J]. Journal of System Simulation, 2018, 30(6): 2320-2327.
[12]	Wang Changtao, Sun Xiaotong, Han Zhonghua, Zhu Yi. A Study of Adaptive Simulated Annealing Particle Swarm Optimization (ASAPSO) Algorithm for Building Pipe Routing Design [J]. Journal of System Simulation, 2018, 30(5): 1941-1949.
[13]	Ji Weixi, Cai Youyong, Zhang Chaoyang, Peng Wei. Abnormal Event Driven Rescheduling Decision Making in Discrete Manufacturing Workshop [J]. Journal of System Simulation, 2018, 30(11): 4043-4052.
[14]	Chen Chao, Wang Yan, Yan Dahu, Ji Zhicheng. Research on Dynamic Flexible Job Shop Scheduling Problem for Energy Consumption [J]. Journal of System Simulation, 2017, 29(9): 2168-2175.
[15]	Xu Shipeng, Wu Dinghui, Kong Fei, Ji Zhicheng. Solving Flexible Job-Shop Scheduling Problem by Improved Chicken Swarm Optimization Algorithm [J]. Journal of System Simulation, 2017, 29(7): 1497-1505.