基于改进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)

中图分类号:

雷勤, 高颜兵, 周煜丰, 吴志彬. 基于改进ALNS算法的多交付选项路径规划[J]. 系统工程与电子技术, 2025, 47(1): 173-181.

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.

图/表 10

图1

表1

表2

表3

表4

表5

表6

图2

图3

图4

参考文献 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