优先配送绿色VRP的混合启发式求解算法

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

摘要/Abstract

摘要：

考虑物流配送中部分客户货物存在不可混装的问题，在传统同时取送绿色车辆路径问题基础上，根据客户需求将客户划分为优先配送、非优先只取不送、非优先有取有送3种类型，并建立最小化总成本的单目标非线性优化模型。基于模拟退火和自适应大邻域搜索算法设计了一种混合启发式求解方法，采用改进的节约算法构造初始解，在模拟退火算法框架中利用5种破坏算子和2种修复算子进行自适应大邻域搜索，直至稳定。仿真结果表明：所提算法能有效降低总成本和减少车辆数，且具有较快的收敛速度和较强的稳定性。

关键词: 绿色车辆路径问题, 同时取送货, 节约算法, 模拟退火, 自适应大邻域搜索

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

中图分类号:

TP391.9

崔焕焕,官礼和 . 优先配送绿色VRP的混合启发式求解算法[J]. 系统仿真学报, 2025, 37(2): 413-423.

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.

图/表 8

表1

符号说明

符号	含义
$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$	车辆成本单价

表1

表2

算法过程中符号说明

符号	含义
$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$	新解比当前解差但被接受时算子得分

表2

图1

表3

两种配送策略在Solomon算例上的结果

算例	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

表3

表4

表5

表6

图2

参考文献 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]	徐强, 徐坚磊, 胡燕海, 陈海辉, 张行, 邢兆辉. 基于改进模拟退火遗传算法的机械臂轨迹优化[J]. 系统仿真学报, 2025, 37(2): 404-412.
[2]	张振利, 汪永壮, 秦耀, 杨杰. 基于Levant微分器的磁浮球控制算法研究[J]. 系统仿真学报, 2024, 36(7): 1586-1595.
[3]	张红历, 邓井双. 基于遗传算法的人工人口生成与应用研究[J]. 系统仿真学报, 2023, 35(9): 1965-1974.
[4]	杜利珍, 叶涛, 王宇豪, 张亚军, 宣自风. 改进粒子群算法的不相关并行批处理调度优化[J]. 系统仿真学报, 2023, 35(7): 1549-1561.
[5]	陈雪, 胡蓉, 王辉, 李作成, 钱斌, 李熠胥. 学习型蚁群算法求解一类复杂两级车辆路径问题[J]. 系统仿真学报, 2023, 35(11): 2476-2495.
[6]	邵良杉, 王振, 李昌明. 基于模拟退火与改进粒子群的矿井通风优化算法[J]. 系统仿真学报, 2021, 33(9): 2085-2094.
[7]	陆嘉波, 程培星, 黄羿, 姚进强, 杨雪梦, 马新强, 刘勇. 用于时敏目标打击链快速构建的智能方法[J]. 系统仿真学报, 2021, 33(2): 346-357.
[8]	蔡敏, 王艳, 纪志成. 基于多策略融合量子粒子群算法的MOFFJSP研究[J]. 系统仿真学报, 2021, 33(11): 2615-2626.
[9]	李珍萍, 赵雨薇, 张煜炜, 邢立宁, 任腾. 共同配送选址-路径问题及大邻域搜索算法[J]. 系统仿真学报, 2021, 33(10): 2518-2531.
[10]	沈鹏, 王艳, 纪志成, 张建华. 超启发式DE算法求解零等待发酵工艺调度[J]. 系统仿真学报, 2020, 32(11): 2235-2243.
[11]	赵文清, 覃智补. 采用改进型智能水滴算法的电力环境经济调度[J]. 系统仿真学报, 2018, 30(8): 3213-3218.
[12]	刘炜, 许嘉轩, 王沛沛, 刘瑞龙, 唐靖坤. 基于模拟退火算法的列车节能操纵研究[J]. 系统仿真学报, 2018, 30(6): 2320-2327.
[13]	王长涛, 孙晓彤, 韩忠华, 朱毅. 基于自适应模拟退火PSO算法建筑管道布置研究[J]. 系统仿真学报, 2018, 30(5): 1941-1949.
[14]	吉卫喜, 蔡酉勇, 张朝阳, 彭威. 异常事件驱动的离散制造车间重调度决策[J]. 系统仿真学报, 2018, 30(11): 4043-4052.
[15]	陈超, 王艳, 严大虎, 纪志成. 面向能耗的柔性作业车间动态调度研究[J]. 系统仿真学报, 2017, 29(9): 2168-2175.