带取货点选择的电动车取送货路径优化的自适应大邻域搜索算法

doi:10.16381/j.cnki.issn1003-207x.2024.0142

Abstract

Abstract:

In the consumption mode of combining online e-commerce and offline stores， the goods purchased by consumers can be provided by multiple offline stores at the same time， which leads to the unfixed pickup point of goods. Therefore， it is necessary to make decisions on the selection of pickup points and the delivery routing when distributing goods. The electric vehicle pickup and delivery problem with pickup-point selection in the case of unfixed pickup point is studied. After characterizing the constraints such as time window， charging time and battery capacity of the pickup point and the customer delivery point， a mixed integer programming formulation is formulated to minimize the total distribution cost. According to the characteristics of the model， an improved adaptive large neighborhood search algorithm is developed. In order to expand the search space of feasible solution， a variety of destroy operators and repair operators are designed for charging station nodes and pickup-and-delivery nodes， and a new solution acceptance criterion based on simulated annealing is used to improve the search efficiency. In this paper， the greedy random adaptive repair operator and the minimum spanning tree destruction operator are first proposed. The effectiveness and superiority of the proposed algorithm are verified by a comprehensive numerical experiment analysis， The numerical results show that：（1） The influence of the selection of the pickup points on the total cost and the improvement effect of the proposed new operators on the algorithm are emphatically analyzed. （2） Considering the selection of pickup points can greatly reduce the number of vehicles and delivery costs. When logistics enterprise operators plan the route of pickup and delivery vehicles， the selection of pickup and delivery points should be made at the same time as the planning of the pickup and delivery path， rather than first deciding the pickup point and then optimizing the pickup and delivery routes. The selection of pickup points and the pickup and delivery routing are isolated into two independent issues for decision-making.The research results of this paper not only enrich the study of the route optimization of electric vehicles for pickup and delivery， but also provide a decision-making reference for logistics enterprises to design distribution and delivery schemes.

Key words: pickup and delivery, pickup-point selection, destroy operator, repair operator, adaptive large neighborhood search

CLC Number:

C935

Tingying Wu,Bingbing Liu,Yugang Yu. An Adaptive Large Neighborhood Search Algorithm for Electric Vehicle Pickup-and-Delivery Routing Problem with Pickup-Points Selection[J]. Chinese Journal of Management Science, 2026, 34(4): 144-155.

Figures/Tables 10

参数	定义
F	充电站集合
F΄	实际充电站和虚拟充电站集合
K	电动车集合
P	取货点集合
P_j	需求点j对应的取货点集合
D	客户点集合
0, N + 1	起始和终止车场
M	电动车固定成本
C	电动车最大负载
Q	电动车电池容量
v	电动车匀速行驶的速度
g	电动车充电率
h	电动车平均耗电率
B₁	固定车辆使用成本
B₂	单位运距路径成本
B₃	单位时间充电成本
d_ij	节点i和j之间的距离
q_i	节点i的需求
[e_i,l_i ]	节点i的时间窗限制
决策变量
s_i	服务节点i的时长
$x i j k$	0-1变量,电动车k经过弧(i, j)时为1
$z i j k$	0-1变量,电动车k从取货点i取货服务客户点j时为1
u_i	电动车k离开节点i的载重
t_i	电动车k到达节点i的时间
$w j k$	电动车k在充电站j的充电时间
$y i k$	电动车k到达节点i时的剩余电量

References 20

[1]	吴腾宇，张景露，余海燕. 非对称网络下的在线取送货路径优化问题［J］. 中国管理科学， 2023， 31（9）： 214-221.
	Wu T Y， Zhang J L， Yu H Y. The real-time pick-up and delivery problem with the asymmetric network［J］. Chinese Journal of Management Science， 2023， 31（9）： 214-221.
[2]	Drexl M. On the one-to-one pickup-and-delivery problem with time windows and trailers［J］. Central European Journal of Operations Research， 2021， 29（3）： 1115-1162.
[3]	边展，张倩，徐奇，等. 带时间窗取送货问题的混合算法［J］. 运筹与管理， 2020， 29（2）： 97-107.
	Bian Z， Zhang Q， Xu Q， et al. Hybrid algorithms for the pickup and delivery problem with time windows［J］. Operations Research and Management Science， 2020， 29（2）： 97-107.
[4]	Ropke S， Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows［J］. Transportation Science， 2006， 40（4）： 455-472.
[5]	Sun P， Veelenturf L P， Hewitt M， et al. Adaptive large neighborhood search for the time-dependent profitable pickup and delivery problem with time windows［J］. Transportation Research Part E： Logistics and Transportation Review， 2020， 138： 101942.
[6]	Peng Z， Al Chami Z， Manier H， et al. A hybrid particle swarm optimization for the selective pickup and delivery problem with transfers［J］. Engineering Applications of Artificial Intelligence， 2019， 85： 99-111.
[7]	孙欣蕊，李昆鹏，刘腾博. 考虑订单取件时间和柔性时间窗的取送货车辆路径问题［J］. 运筹与管理， 2022， 31（7）： 9-16.
	Sun X R， Li K P， Liu T B. Pickup and delivery vehicle routing problem with order release dates and flexible time windows［J］. Operations Research and Management Science， 2022， 31（7）： 9-16.
[8]	吴斌，钱存华，董敏，等. 具有同时集送货需求车辆路径问题的混沌量子进化算法研究［J］. 控制与决策， 2010， 25（3）： 383-388.
	Wu B， Qian C H， Dong M， et al. Chaos quantum evolutionary algorithm for vehicle routing problem with simultaneous delivery and pickup［J］. Control and Decision， 2010， 25（3）： 383-388.
[9]	Dumez D， Lehuédé F， Péton O. A large neighborhood search approach to the vehicle routing problem with delivery options［J］. Transportation Research Part B： Methodological， 2021， 144： 103-132.
[10]	Zhou L， Baldacci R， Vigo D， et al. A multi-depot two-echelon vehicle routing problem with delivery options arising in the last mile distribution［J］. European Journal of Operational Research， 2018， 265（2）： 765-778.
[11]	Aziez I， Côté J F， Coelho L C. Exact algorithms for the multi-pickup and delivery problem with time windows［J］. European Journal of Operational Research， 2020， 284（3）： 906-919.
[12]	Takada Y， Shimazaki M， Hu Y， et al. Efficient algorithms for optimal pickup-point selection in the selective pickup and delivery problem with time-window constraints［J］. Journal of Advanced Mechanical Design， Systems， and Manufacturing， 2020， 14（5）： 1-8.
[13]	Schneider M， Stenger A， Goeke D. The electric vehicle-routing problem with time windows and recharging stations［J］. Transportation Science， 2014， 48（4）： 500-520.
[14]	Desaulniers G， Errico F， Irnich S， et al. Exact algorithms for electric vehicle-routing problems with time windows［J］. Operations Research， 2016， 64（6）： 1388-1405.
[15]	吴廷映，孙灏. 考虑载重影响耗电率的电动车车辆路径问题［J］. 控制与决策， 2023， 38（2）： 483-491.
	Wu T Y， Sun H. Electric vehicle routing problem with time window and linear weightrelated discharging［J］. Control and Decision， 2023， 38（2）： 483-491.
[16]	郭放，黄志红，黄卫来，等. 考虑自取服务和门到门服务的电动汽车物流网络优化策略研究［J］. 中国管理科学， 2022， 30（2）： 264-275.
	Guo F， Huang Z H， Huang W L， et al. Optimal planning of the electric vehicle routing and battery charging problem with self-pickup and door-to-door delivery service［J］. Chinese Journal of Management Science， 2022， 30（2）： 264-275.
[17]	Li L， Li T， Wang K， et al. Heterogeneous fleet electric vehicle routing optimization for logistic distribution with time windows and simultaneous pick-up and delivery service［C］//Proceedings of 2019 16th International Conference on Service Systems and Service Management （ICSSSM）， Shenzhen， China， July 13-15， IEEE， 2019： 1-6.
[18]	Goeke D. Granular tabu search for the pickup and delivery problem with time windows and electric vehicles［J］. European Journal of Operational Research， 2019， 278（3）： 821-836.
[19]	Soysal M， Çimen M， Belbağ S. Pickup and delivery with electric vehicles under stochastic battery depletion［J］. Computers & Industrial Engineering， 2020， 146： 106512.
[20]	Outalha A， Lakhal Y， Baghli F Z， et al. The efficiency of discrete event systems for the general pickup and delivery problem with electric vehicles［J］. E3S Web of Conferences， 2021， 229： 01011.

文献	年份	研究问题			求解方法
文献	年份	是否有取送货选择	是否带时间窗	配送车辆类型	精确方法	启发式算法
吴腾宇等	2023	否	否	燃油车		在线算法
Drexl	2021	否	是	燃油车		ALNS
边展等	2020	否	是	燃油车	列生成
Ropk和Pisinger	2006	否	是	燃油车		ALNS
Sun等	2020	否	是	燃油车		ALNS
Peng等	2019	否	是	燃油车		混合粒子群
孙欣蕊等	2022	否	是	燃油车	分支切割
吴斌等	2010	否	否	燃油车		混沌量子进化
Dumez	2021	是	是	燃油车		大邻域搜索
Zhou等	2018	是	否	燃油车		混合遗传算法
Aziez等	2020	是	是	燃油车	分支切割
Takada等	2020	是	是	燃油车	动态规划
Li等	2019	否	是	电动车		变邻域搜索
Goeke	2019	否	是	电动车		禁忌搜索
本文		是	是	电动车		EALNS

算例	CPLEX			EALNS			Gap (%)
算例	RN	TC	RT	RN	TC	RT	Gap (%)
c101c6	3	734.541	4.64	3	734.541	0.00	0.00
c103c6	2	326.941	23.95	2	326.941	0.00	0.00
c206c6	2	659.172	10.19	2	659.172	0.023	0.00
c208c6	1	555.049	444.00	1	555.049	0.116	0.00
r104c6	1	202.107	5.49	1	202.107	0.00	0.00
r105c6	1	231.052	3.59	1	231.052	0.00	0.00
r202c6	1	227.345	17.52	1	227.345	0.00	0.00
r203c6	1	311.411	99.00	1	311.411	0.001	0.00
rc105c6	2	457.624	3600	2	432.982	0.003	-5.38
rc108c6	2	515.611	3600	2	515.611	0.001	0.00
rc204c6	1	317.304	81.69	1	317.304	0.007	0.00
rc208c6	1	305.864	26.42	1	305.864	0.001	0.00
c104c10	2	995.637	3600	2	926.444	0.021	-6.95
c205c10	3	640.2	104.86	3	640.2	0.001	0.00
r201c10	1	321.036	3600	1	321.036	0.163	0.00
r203c10	1	314.378	3600	1	314.378	0.022	0.00
rc108c10	3	758.028	3600	3	758.028	0.032	0.00
rc201c10	1	402.08	3600	1	402.08	0.583	0.00
rc205c10	1	537.585	3600	1	537.585	0.078	0.00
c101c12	4	1206.57	3600	4	1206.57	0.039	0.00
c202c12	2	742.282	3600	1	722.333	0.028	-2.69
r102c12	3	566.284	3600	3	565.148	0.208	-0.20
r103c12	2	436.892	3600	2	396.384	0.644	-9.27
rc102c12	4	819.949	3600	4	819.949	0.002	0.00
c103c16	-	-	3600	4	1047.29	0.526	-
c106c16	3	830.362	3600	3	649.488	0.018	-21.78
c202c16	-	-	3600	4	1183.07	2.013	-
c208c16	2	1200.1	3600	2	947.848	0.27	-21.02
r105c16	-	-	3600	3	633.594	0.471	-
r202c16	2	636.781	3600	1	566.505	0.841	-11.04
r209c16	2	543.865	3600	1	434.906	1.289	-20.03
rc103c16	-	-	3600	3	768.757	1.66	-
rc108c16	-	-	3600	3	733.892	0.679	-
rc202c16	2	631.382	3600	2	631.382	0.001	0.00
rc204c16	2	688.604	3600	1	402.332	0.534	-41.57
r102c18	-	-	3600	4	841.155	0.033	-

算例	EALNS			ALNS			Gap (%)
算例	RN	TC	RT	RN	TC	RT	Gap (%)
lc101	12	3269.78	766.016	13	3289.19	353	-0.59
lc102	13	3525	684.585	15	3941.6	713	-10.57
lc103	12	2972.6	633.036	12	2971.95	261	0.02
lc104	10	2813.91	1049.44	11	3016.29	1128	-6.71
lc105	14	3381.1	989.3	14	3375.71	456	0.16
lc106	13	3297.49	1259.94	14	3323.36	550	-0.78
lc107	12	3415.64	249.133	13	3511.03	994	-2.72
lc108	13	3333.54	423.789	12	3340.87	1194	-0.22
lc109	11	2821.03	902.578	10	2832.21	427	-0.39
lc201	4	1603.65	1406.79	5	1689.24	641	-5.07
lc202	4	1434.47	851.724	4	1684.52	735	-14.84
lc203	3	1414.94	537.447	3	1414.05	1115	0.06
lc204	5	1781.62	1271.98	5	1730.17	1176	2.97
lc205	3	1420.09	1216.25	3	1451.55	827	-2.17
lc206	3	1451.18	532.971	3	1477.37	1006	-1.77
lc207	3	1387.75	1489.81	3	1478.03	550	-6.11
lc208	4	1375.22	1471.72	5	1545.95	612	-11.04
平均值							-3.52

算例	EALNS			ALNS			Gap (%)
算例	RN	TC	RT	RN	TC	RT	Gap (%)
lr101	19	3643.24	506.358	19	3661.16	346	-0.49
lr102	17	3383.97	832.055	17	3483.69	1333	-2.86
lr103	14	3036.67	1134.32	15	3145.69	260	-3.47
lr104	12	2587.37	965.7	12	2627.47	993	-1.53
lr105	17	3586.03	731.73	18	3746.4	636	-4.28
lr106	15	3146.27	1325.03	15	3229.76	274	-2.59
lr107	12	2678.38	1128.56	13	2768.6	1393	-3.26
lr108	10	2216.52	1269.55	11	2321.85	379	-4.54
lr109	14	3050.54	489.294	15	3116.6	768	-2.12
lr110	13	2867.14	834.899	13	2899.6	396	-1.12
lr111	13	2773.06	920.368	13	2748.61	1216	0.89
lr112	12	2581.72	993.154	12	2604.69	1130	-0.88
lr201	4	1745.82	1502.36	5	1971.63	777	-11.45
lr202	3	1725.94	1504.67	4	1883.95	1504	-8.39
lr203	3	1442.83	2215.64	3	1480.84	2429	-2.57
lr204	3	1307.12	2392.92	3	1316.6	2311	-0.72
lr205	4	1595.42	2201.2	4	1677.55	2300	-4.90
lr206	4	1637.46	2193.47	4	1605.96	2904	1.96
lr207	3	1372.77	2283.79	3	1371.75	2923	0.07
lr208	2	1279.22	2245.51	3	1363.38	2424	-6.17
lr209	4	1505.95	1871.63	4	1504.67	2228	0.09
lr210	3	1679.3	1864.41	4	1777.96	2159	-5.55
lr211	3	1283.23	1833.14	3	1492.1	2676	-14.00
平均值							-3.52

算例	EALNS			ALNS			Gap (%)
算例	RN	TC	RT	RN	TC	RT	Gap (%)
lrc101	17	3766.05	698.313	17	3794.25	876	-0.74
lrc102	16	3803.58	702.657	16	3797.74	764	0.15
lrc103	15	3316.71	979.913	15	3330.14	752	-0.40
lrc104	13	2956.94	1056.12	12	2981.22	1052	-0.81
lrc105	16	3513.93	871.096	17	3628.74	1150	-3.16
lrc106	15	3649.43	1152.26	16	3784.35	715	-3.57
lrc107	14	3199.08	244.868	14	3374.75	426	-5.21
lrc108	12	2845.72	552.54	13	2921.96	1307	-2.61
lrc201	4	1980.66	1704.04	4	2101.06	2234	-5.73
lrc202	4	1889.88	2359.8	4	1990.11	1369	-5.04
lrc203	3	1465.35	2510.82	3	1618.54	1791	-9.46
lrc204	3	1246.51	1350.87	3	1253.13	997	-0.53
lrc205	4	1702.17	2105.25	4	1955.27	1804	-12.94
lrc206	4	1671.1	2220.5	3	1696.38	516	-1.49
lrc207	4	2039.77	1579.54	4	2057.82	1828	-0.88
lrc208	4	1560.14	1974.64	4	1773.69	2204	-12.04
平均值							-4.03

An Adaptive Large Neighborhood Search Algorithm for Electric Vehicle Pickup-and-Delivery Routing Problem with Pickup-Points Selection

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 20

Related Articles 7

Metrics

Comments

Recommended 0

算例	RN	TC	ΔRN	ΔTC	Gap (%)
lc101	15	3556.22	-3	-286.44	-8.05
lc102	12	3566.64	1	-41.64	-1.17
lc103	14	3481.46	-2	-508.86	-14.62
lc104	12	3243.11	-2	-429.2	-13.23
lc105	15	3471.18	-1	-90.08	-2.60
lc106	15	3489.49	-2	-192	-5.50
lc107	14	3590.45	-2	-174.81	-4.87
lc108	15	3592.83	-2	-259.29	-7.22
lc109	11	2862.1	0	-41.07	-1.43
lc201	5	1917.18	-1	-313.53	-16.35
lc202	5	1933.18	-1	-498.71	-25.80
lc203	5	1922.4	-2	-507.46	-26.40
lc204	5	1821.31	0	-39.69	-2.18
lc205	5	1751.97	-2	-331.88	-18.94
lc206	5	1771.38	-2	-320.2	-18.08
lc207	5	1770.2	-2	-382.45	-21.60
lc208	4	1607.5	0	-232.28	-14.45
平均值			-1.35	-273.51	-11.91

算例	RN	TC	ΔRN	ΔTC	Gap (%)
lr101	23	4376.78	-4	-733.54	-16.76
lr102	20	4122.78	-3	-738.81	-17.92
lr103	19	3972.06	-5	-935.39	-23.55
lr104	15	3296.68	-3	-709.31	-21.52
lr105	21	4528.09	-4	-942.06	-20.80
lr106	19	4084.72	-4	-938.45	-22.97
lr107	16	3524.84	-4	-846.46	-24.01
lr108	14	3274.91	-4	-1058.39	-32.32
lr109	19	4006.6	-5	-956.06	-23.86
lr110	16	3402.76	-3	-535.62	-15.74
lr111	17	3651.01	-4	-877.95	-24.05
lr112	15	3261.02	-3	-679.3	-20.83
lr201	6	2363.23	-2	-617.41	-26.13
lr202	5	1978.35	-2	-252.41	-12.76
lr203	4	1729.38	-1	-286.55	-16.57
lr204	4	1814.67	-1	-507.55	-27.97
lr205	4	1778.81	0	-183.39	-10.31
lr206	5	2231.49	-1	-594.03	-26.62
lr207	4	1916.01	-1	-543.24	-28.35
lr208	3	1459.54	-1	-180.32	-12.35
lr209	4	1748.88	0	-242.93	-13.89
lr210	4	1919.38	-1	-240.08	-12.51
lr211	4	1605.57	-1	-322.34	-20.08
平均值			-2.48	-605.29	-20.52

算例	RN	TC	ΔRN	ΔTC	Gap (%)
lrc101	22	4941.13	-5	-1175.08	-23.78
lrc102	20	4636.75	-4	-833.17	-17.97
lrc103	17	3786.21	-2	-469.5	-12.40
lrc104	15	3482.97	-2	-526.03	-15.10
lrc105	20	4537.75	-4	-1023.82	-22.56
lrc106	18	4158.98	-3	-509.55	-12.25
lrc107	16	3812.99	-2	-613.91	-16.10
lrc108	15	3390.85	-3	-545.13	-16.08
lrc201	5	2390.89	-1	-410.23	-17.16
lrc202	4	2277.48	0	-387.6	-17.02
lrc203	4	2012.23	-1	-546.88	-27.18
lrc204	4	1398.36	-1	-151.85	-10.86
lrc205	5	2075.34	-1	-373.17	-17.98
lrc206	4	1754.42	0	-83.32	-4.75
lrc207	5	2283.79	-1	-244.02	-10.68
lrc208	5	2226.68	-1	-666.54	-29.93
平均值			-1.94	-534.99	-16.99

[1]	Shuai Zhang, Siliang Liu, Wenyu Zhang. Vehicle Routing Problems with Time Windows under the Collaborative Delivery Mode of Electric Vehicle-drone [J]. Chinese Journal of Management Science, 2025, 33(4): 131-141.
[2]	Jianhua Xiao, Wenxue Zhang, Yuya Pan, Jiuhong Xiao, Yunyun Niu. A Multi-period Multi-compartment Vehicle Routing Problem for Sorted-waste Collection with Timeliness [J]. Chinese Journal of Management Science, 2025, 33(10): 86-97.
[3]	WANG Yong, LUO Si-yu, ZHEN Lu, XU Mao-zeng. Multi-center Pickup and Delivery Network Alliance Optimization Considering Default Penalties and Loss Compensations for Breach of Contract [J]. Chinese Journal of Management Science, 2023, 31(3): 10-25.
[4]	HU Xue-jun, ZHAO Yan, SHAN Mi-yuan, WANG Jian-jiang, BIE Li. An Adaptive Large Neighborhood Search Metaheuristic for Robust Multi-project Scheduling [J]. Chinese Journal of Management Science, 2022, 30(9): 217-231.
[5]	XU Dong-yang, LI Kun-peng, CUI Li-gang, TIAN Qian-nan. Multi-commodity Unpaired Supply-demandand Split Pickup and Delivery Vehicle Routing Problem with Multi-depot and Multi-type Trucks [J]. Chinese Journal of Management Science, 2021, 29(1): 127-137.
[6]	GUO Dong-wei, DING Gen-hong, LIU Wei. Improved Multi-Strategy Grouping Genetic Algorithm for the Pickup and Delivery Problem with Time Windows [J]. Chinese Journal of Management Science, 2020, 28(7): 204-211.
[7]	GUO Fang, YANG Jun, YANG Chao. Study on the Electric Vehicle Routing Problem in the Present of Charging Strategy and Battery Consumption [J]. Chinese Journal of Management Science, 2018, 26(9): 106-118.