基于改进ALNS算法的多交付选项路径规划

doi:10.12305/j.issn.1001-506X.2025.01.18

Abstract

Abstract:

To address the problem of personalized delivery requirements in urban logistics, a path planning problem considering delivery satisfaction is proposed. Firstly, taking the customer personalized preference ranking for customer delivery methods as a measure of customer satisfaction, an optimization model is constructed with the objective of minimizing the total operating cost. It covers the fixed cost of electric vehicle, travel cost, charging cost and penalty cost for failing to meet the earliest service start time and location preferences of customer. Secondly, a hybrid heuristic algorithm combining adaptive large neighborhood search with tabu search is designed to solve large-scale customer scenarios. Finally, the correctness of the model and effectivenes of the algorithm is verified by benchmark data analysis. Results indicate that making delivery plans based on multi-delivery option model can help enterprises reduce cost, requiring low cost to achieve higher service quality, and improve customer satisfaction.

Key words: urban logistics, electric vehicle routing problem, delivery option, customer satisfaction, adaptive large neighborhood search (ALNS) algorithm, tabu search (TS)

CLC Number:

Qin LEI, Yanbing GAO, Yufeng ZHOU, Zhibin WU. Multi-delivery option path planning based on improved ALNS algorithm[J]. Systems Engineering and Electronics, 2025, 47(1): 173-181.

Figures/Tables 10

Fig.1

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

Fig.2

Fig.3

Fig.4

References 32

1	WASSMUTH K , KOEHLER C , AGATZ N , et al. Demand management for attended home delivery-a literature review[J]. European Journal of Operational Research, 2023, 311 (3): 801- 815. doi: 10.1016/j.ejor.2023.01.056
2	FLECKENSTEIN D , KLEIN R , STEIN-HARDT C . Recent advances in integrating demand management and vehicle routing: a methodological review[J]. European Journal of Operational Research, 2023, 306 (2): 499- 518. doi: 10.1016/j.ejor.2022.04.032
3	LIIMATAINEN H , VAN V O , APLYN D . The potential of electric trucks-an international commodity-level analysis[J]. Applied Energy, 2019, 236, 804- 814. doi: 10.1016/j.apenergy.2018.12.017
4	OU S, LIN Z H, WU Z X, et al. A study of China's explosive growth in the plug-in electric vehicle market[R]. Tennessess: The Oak Ridge National Laboratory, 2017.
5	刘瑶, 夏阳升, 石建迈, 等. 车载多无人机协同多区域覆盖路径规划方法[J]. 系统工程与电子技术, 2023, 45 (5): 1380- 1390. doi: 10.12305/j.issn.1001-506X.2023.05.14
	LIU Y , XIA Y S , SHI J M , et al. Path planning method for multi-area coverage by cooperated ground vehicle multi-drone[J]. Systems Engineering and Electronics, 2023, 45 (5): 1380- 1390. doi: 10.12305/j.issn.1001-506X.2023.05.14
6	李翰, 张洪海, 张连东, 等. 城市区域多物流无人机协同任务分配[J]. 系统工程与电子技术, 2021, 43 (12): 3594- 3602. doi: 10.12305/j.issn.1001-506X.2021.12.22
	LI H , ZHANG H H , ZHANG L D , et al. Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas[J]. Systems Engineering and Electronics, 2021, 43 (12): 3594- 3602. doi: 10.12305/j.issn.1001-506X.2021.12.22
7	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. doi: 10.1287/trsc.2013.0490
8	KESKIN M , CATAY B . Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65, 111- 127. doi: 10.1016/j.trc.2016.01.013
9	RAEESI R , ZOGRAFOS K G . The electric vehicle routing problem with time windows and synchronized mobile battery swapping[J]. Transportation Research Part B: Methodological, 2020, 140, 101- 129. doi: 10.1016/j.trb.2020.06.012
10	HIERMANN G , PUCHINGER J , ROPKE S , et al. The electric fleet size and mix vehicle routing problem with time windows and recharging stations[J]. European Journal of Operational Research, 2016, 252 (3): 995- 1018. doi: 10.1016/j.ejor.2016.01.038
11	MONTOYA A , GUERET C , MENDOZA J E , et al. The electric vehicle routing problem with nonlinear charging function[J]. Transportation Research Part B: Methodological, 2017, 103, 87- 110. doi: 10.1016/j.trb.2017.02.004
12	SHEN Y D , PENG L W , LI J P . An improved estimation of distribution algorithm for multi-compartment electric vehicle routing problem[J]. Journal of Systems Engineering and Elec-tronics, 2021, 32 (2): 365- 379. doi: 10.23919/JSEE.2021.000030
13	黄志红, 黄卫来, 郭放. 考虑电池损耗的电动汽车充电设施选址与充电策略协同优化研究[J]. 中国管理科学, 2024, 32 (6): 68- 78.
	HUANG Z H , HUANG W L , GUO F . Collaborative optimization of charging network and charging strategy with practical battery wear model[J]. Chinese Journal of Management Science, 2024, 32 (6): 68- 78.
14	REYES D , SAVELSBERGH M , TORIELLO A . Vehicle routing with roaming delivery locations[J]. Transportation Research Part C: Emerging Technologies, 2017, 80, 71- 91. doi: 10.1016/j.trc.2017.04.003
15	OZBAYGIN G , KARASAN O E , SAVELSB-ERGH M , et al. A branch-and-price algorithm for the vehicle routing problem with roaming delivery locations[J]. Transportation Research Part B: Methodological, 2017, 100, 115- 137. doi: 10.1016/j.trb.2017.02.003
16	LOMBARD A , TAMAYO-GIRALDO S , FONTANE F . Vehicle routing problem with roaming delivery locations and stochastic travel times (VRPRDL-S)[J]. Transportation Research Procedia, 2018, 30, 167- 177. doi: 10.1016/j.trpro.2018.09.019
17	DENG Y , ZHU W H , LI H W , et al. Multi-type ant system algorithm for the time dependent vehicle routing problem with time windows[J]. Journal of Systems Engineering and Electro-nics, 2018, 29 (3): 625- 638. doi: 10.21629/JSEE.2018.03.20
18	CHEN M C , YERASANI S , TIWARI M K . Solving a 3-dimensional vehicle routing problem with delivery options in city logistics using fast-neighborhood based crowding differential evolution algorithm[J]. Journal of Ambient Intelligence and Humanized Computing, 2023, 14 (8): 10389- 10402. doi: 10.1007/s12652-022-03696-1
19	FREY C M M , JUNGWIRTH A , FREY M , et al. The vehicle routing problem with time windows and flexible delivery locations[J]. European Journal of Operational Research, 2023, 308 (3): 1142- 1159. doi: 10.1016/j.ejor.2022.11.029
20	SADATI M E H , AKBARI V , CATAY B . Electric vehicle routing problem with flexible deliveries[J]. International Journal of Production Research, 2022, 60 (13): 4268- 4294. doi: 10.1080/00207543.2022.2032451
21	ZHOU S Q , ZHANG D Z , JI B , et al. Two-echelon vehicle routing problem with direct deliveries and access time windows[J]. Expert Systems with Applications, 2024, 244, 121150. doi: 10.1016/j.eswa.2023.121150
22	ENTHOVEN D L J U , JARGALSAIKHAN B , ROODBERGEN K J , et al. The two-echelon vehicle routing problem with covering options: city logistics with cargo bikes and parcel lockers[J]. Computers & Operations Research, 2020, 118, 104919.
23	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. doi: 10.1016/j.ejor.2017.08.011
24	TILK C , OLKIS K , IRNICH S . The last-mile vehicle routing problem with delivery options[J]. OR Spectrum, 2021, 43 (4): 877- 904. doi: 10.1007/s00291-021-00633-0
25	DUMEZ D , LEHUEDE F , PETON O . A large neighborhood search approach to the vehicle routing problem with delivery options[J]. Transportation Research Part B: Methodological, 2021, 144, 103- 132. doi: 10.1016/j.trb.2020.11.012
26	VOIGT S , FRANK M , FONTAINE P , et al. The vehicle routing problem with availability profiles[J]. Transportation Science, 2023, 57 (2): 531- 551. doi: 10.1287/trsc.2022.1182
27	KARELS V C G , REI W , VEELENTURF L P , et al. A vehicle routing problem with multiple service agreements[J]. European Journal of Operational Research, 2024, 313 (1): 129- 145. doi: 10.1016/j.ejor.2023.07.029
28	周鲜成, 周开军, 王莉, 等. 物流配送中的绿色车辆路径模型与求解算法研究综述[J]. 系统工程理论与实践, 2021, 41 (1): 213- 230.
	ZHOU X C , ZHOU K J , WANG L , et al. Review of green vehicle routing model and its algorithm in logistics distribution[J]. Systems Engineering-Theory & Practices, 2021, 41 (1): 213- 230.
29	ZHANG H F , GE H W , YANG J L , et al. Review of vehicle routing problems: models, classifycation and solving algorithms[J]. Archives of Computational Methods in Engineering, 2022, 29, 195- 221. doi: 10.1007/s11831-021-09574-x
30	GENDREAU M , POTVIN J Y . Handbook of metaheuristics[M]. Cham: Springer, 2019.
31	SOLOMON M M , DESROSIERS J . Time window constrained routing and scheduling problems[J]. Transportation Science, 1988, 22 (1): 1- 13. doi: 10.1287/trsc.22.1.1
32	仪孝展. 基于改进遗传算法的物流车辆路径规划方法研究与应用[D]. 西安: 西安理工大学, 2018.
	YI X Z. Research and application of logistics vehicle routing planning based on improved genetic algorithm[D]. Xi'an: Xi'an University of Technology, 2018.

符号	含义
N	所有客户集合
O_c	客户c的所有交付选项
L	地点集合
F	充电站集合
V	所有节点集
E	所有节点所形成的弧集
K	所有可用车辆集合
P	客户偏好等级数目
β_p	所有客户中以优先级不超过p的选项完成配送的客户比例
d_ij	两节点之间的距离
t_ij	两节点之间的行驶时间
s_i	交付选项i的服务时间
e_i	交付选项i的最早开始服务时间
l_i	交付选项i的最晚开始服务时间
q_o	客户在选项o处的需求量
p_o	选项o对应的偏好水平
C	车辆最大载荷量
Q	车辆电池容量
c_r	充电成本
c_v	车辆固定成本
c_t	时间惩罚系数
c_pt	地点偏好惩罚系数
g	充电速率
r	车辆电池消耗速率
y_o	表示交付选项o是否会被选择
r_f^k	表示车辆k在充电站f的充电量
v_i^k	表示车辆k在离开节点i的剩余电量
h_i^k	表示车辆k在节点i的开始服务时间
x_ij^k	表示车辆k是否经过弧(i, j)

参数Ψ	描述
Ψ₁	新产生的解为全局最优解
Ψ₂	新产生的解优于当前解
Ψ₃	新产生的解不优于当前解，但被接受了
Ψ₄	新产生的解被拒绝

n	Gurobi			ALNS-TS
n	TC	Gap/%	t/s	TC	t/s	Δ/%
5	270.11	0	11	270.11	0	0
6	272.5	0	193	272.5	1	0
7	272.5	0	717	272.5	1	0
8	279.41	54.5	7 200	279.41	1	0
9	328.25	52.7	7 200	328.25	1	0
10	534.09	75	7 200	534.09	1	0
11	534.68	74.3	7 200	532.66	1	-0.38
12	540.34	77.6	7 200	534.83	1	-1.02

算例	已知最优解		ALNS-TS
算例	NV	TD	NV	TD	时间/s
C101	10	829	10	829	22
C104	10	825	10	825	65
C201	3	592	3	592	25
C204	3	591	3	591	37
R101	19	1 651	19	1 654	62
R104	9	1 007	11	1 003	50
R201	4	1 252	6	1 212	63
R204	2	826	4	742	75
RC101	14	1 697	16	1 673	28
RC108	10	1 140	11	1 148	45
RC201	4	1 407	5	1 364	55
RC208	3	828	4	861	48

算例	ALNS-TS		LNS-SPP		HGA
算例	NV	TD	NV	TD	NV	TD
C1	10	828.45	10	828.38	10	843.6
C2	3.1	589.88	3.3	616.81	3	594.96
R1	13.9	1 207.81	12	1 211.83	11.9	1 242
R2	4	921.84	2.75	965.73	2.7	958.23
RC1	13.3	1 380.99	11.53	1 384.83	11.5	1 384.17
RC2	4.9	1 050.55	3.25	1 141.36	3.3	1 119.23

Multi-delivery option path planning based on improved ALNS algorithm

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 32

Related Articles 1

Recommended Articles

Metrics

Comments

算例	交付选项的数量	Gurobi			ALNS-TS
算例	交付选项的数量	TC	Gap/%	t/s	TC	t/s	Δ/%
U_25large_1	50	991.25	74.75	7 200	956.94	8.98	-3.46
U_25large_5	50	914.17	83.31	7 200	874.22	8.52	-4.37
U_25medium_2	50	1 144.88	84.21	7 200	886.7	7.75	-22.55
U_25medium_7	50	815.06	79.64	7 200	805.74	7.96	-1.14
U_25small_3	50	1 155.40	78.51	7 200	920.22	7.20	-20.36
U_25small_6	50	869.94	79.60	7 200	826.82	7.33	-4.96
U_50large_2	100	2 649.80	90.64	7 200	1 963.81	48.58	-25.89
U_50large_8	100	3 011.46	91.62	7 200	1 890.5	51.82	-37.22
U_50medium_1	100	2 191.47	87.68	7 200	1 816.27	46.86	-17.12
U_50medium_6	100	2 280.68	89.66	7 200	1 892.04	44.04	-17.04
U_50small_2	100	1 756.97	86.54	7 200	1 717.16	30.88	-2.27
U_50small_8	100	2 381.76	89.05	7 200	1 776.86	31.22	-25.40
V_25large_2	38	1 097.95	80.54	7 200	996.84	5.39	-9.21
V_25large_6	38	1 326.16	85.28	7 200	1 035.22	4.63	-21.94
V_25medium_10	38	1 103.72	78.71	7 200	1 019.83	8.66	-7.60
V_25medium_9	38	1 106.36	83.89	7 200	870.96	4.95	-21.28
V_25small_10	38	995.95	61.50	7 200	967.39	7.36	-2.87
V_25small_4	38	934.13	73.91	7 200	901.1	4.17	-3.54
V_50large_10	76	2 513.05	86.98	7 200	1 992.4	28.53	-20.72
V_50large_2	76	2 369.52	88.42	7 200	2 023.2	18.54	-14.62
V_50medium_3	76	1 964.08	86.52	7 200	1 487.74	18.00	-24.25
V_50medium_6	76	2 171.31	87.22	7 200	1 622.29	28.26	-25.29
V_50small_2	76	1 824.64	84.48	7 200	1 779	24.35	-2.50
V_50small_7	76	1 888.75	83.55	7 200	1 572.32	16.56	-16.75