面向城市物流配送的车辆路径优化算法研究

doi:10.16182/j.issn1004731x.joss.24-0639

摘要/Abstract

摘要：

针对现有优化算法在求解带时间窗的车辆路径问题(vehicle routing problem with time windows, VRPTW)时存在易陷入局部最优解和收敛速度慢等问题，提出了一种基于K均值聚类和改进大规模邻域搜索算法(K-means clustering algorithm and improved large neighborhood search algorithm, K-means-ILNSA)。采用先聚类后优化的策略，利用K-means算法对待配送客户进行分组，以提高优化效率。采用遗传算法对聚类产生的每组客户进行单独优化，以初步规划配送路径。引入大规模邻域搜索(large neighborhood search, LNS)算法对配送路径进一步优化，以有效避免算法陷入局部最优解。实验结果表明：所提算法能够有效解决带时间窗的车辆路径问题，其生成的车辆总路程短，优化求解效率高。

关键词: 带时间窗的车辆路径问题, 遗传算法, K-means聚类, 大规模邻域搜索算法

Abstract:

Existing optimization algorithms for solving the vehicle routing problem with time windows (VRPTW) are prone to fall into local optimal solutions and have slow convergence speed. To address this issue, a K-means clustering algorithm and improved large neighborhood search algorithm (K-means-ILNSA) was proposed. A strategy of clustering before optimization was adopted, and the K-means algorithm was adopted to group the customers to be delivered, so as to improve the optimization efficiency. The genetic algorithm was adopted to optimize each group of customers generated by clustering separately to initially plan the distribution routes. The large neighborhood search (LNS) algorithm was introduced to further optimize the delivery routes, effectively avoiding the algorithm getting trapped in local optimal solutions. Experimental results show that the proposed algorithm can effectively solve the vehicle path problem with time windows, and the generated total distance of vehicle is short. The solving efficiency after optimization is high.

Key words: vehicle routing problem with time window(VRPTW), genetic algorithm, K-means clustering, large neighborhood search

中图分类号:

TP391.9

马振鹏,焦晗暘,张哲等 . 面向城市物流配送的车辆路径优化算法研究[J]. 系统仿真学报, 2025, 37(11): 2768-2777.

Ma Zhenpeng,Jiao Hanyang,Zhang Zhe,et al . Research on Vehicle Path Optimization Algorithms for Urban Logistics and Distribution[J]. Journal of System Simulation, 2025, 37(11): 2768-2777.

图/表 9

图1

图2

表1

表2

表3

表4

表5

表6

图3

参考文献 24

[1]	Dantzig G B, Ramser J H. The Truck Dispatching Problem[J]. Management Science, 1959, 6(1): 80-91.
[2]	Elgharably N, Easa S, Nassef Ashraf, et al. Stochastic Multi-objective Vehicle Routing Model in Green Environment with Customer Satisfaction[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(1): 1337-1355.
[3]	Hulagu Selin, Hilmi Berk Celikoglu. An Electric Vehicle Routing Problem with Intermediate Nodes for Shuttle Fleets[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(2): 1223-1235.
[4]	Jia Yahui, Mei Yi, Zhang Mengjie. A Bilevel Ant Colony Optimization Algorithm for Capacitated Electric Vehicle Routing Problem[J]. IEEE Transactions on Cybernetics, 2022, 52(10): 10855-10868.
[5]	Stodola Petr, Nohel Jan. Adaptive Ant Colony Optimization with Node Clustering for the Multidepot Vehicle Routing Problem[J]. IEEE Transactions on Evolutionary Computation, 2023, 27(6): 1866-1880.
[6]	张伟, 魏万峰, 黄卫民. 求解高维优化问题的ITCSO算法[J]. 控制与决策, 2024, 39(2): 449-457.
	Zhang Wei, Wei Wanfeng, Huang Weimin. ITCSO Algorithm for Solving High Dimensional Optimization Problem[J]. Control and Decision, 2024, 39(2): 449-457.
[7]	白宇鑫, 陈振亚, 石瑞涛, 等. 基于改进哈里斯鹰算法的机器人路径规划研究[J]. 系统仿真学报, 2025, 37(3): 742-752.
	Bai Yuxin, Chen Zhenya, Shi Ruitao, et al. Research on Robot Path Planning Based on Improved Harris Hawks Algorithm[J]. Journal of System Simulation, 2025, 37(3): 742-752.
[8]	金东遥, 刘敏, 朱烨娜, 等. 基于混合遗传搜索求解载重约束的电动车辆路径问题[J]. 系统仿真学报, 2024, 36(11): 2528-2541.
	Jin Dongyao, Liu Min, Zhu Yena, et al. A Hybrid Genetic Search Algorithm for Capacitated Electric Vehicle Routing Problem[J]. Journal of System Simulation, 2024, 36(11): 2528-2541.
[9]	刘长石, 陈慧璇, 吴张. 城市物流配送的混合车辆路径规划模型与优化算法[J]. 控制与决策, 2023, 38(3): 759-768.
	Liu Changshi, Chen Huixuan, Wu Zhang. Programming Model and Optimization Algorithm for the Mixed Fleet Vehicle Routing Problem in Urban Logistics Distribution[J]. Control and Decision, 2023, 38(3): 759-768.
[10]	浦徐进, 李丽超, 付亚平. 改进蝴蝶优化算法在护理人员路径规划与调度中的应用[J]. 控制工程, 2024, 31(2): 281-287.
	Pu Xujin, Li Lichao, Fu Yaping. Medical Care Routing Planning and Scheduling for Multi-home Health Care Companies[J]. Control Engineering of China, 2024, 31(2): 281-287.
[11]	石小娟, 赵兴方, 闫龙, 等. 改进天鹰算法求解时间依赖型车辆路径问题[J]. 计算机工程与应用, 2024, 60(4): 355-365.
	Shi Xiaojuan, Zhao Xingfang, Yan Long, et al. Solving Time Dependent Vehicle Routing Problem Based on Improved Aquila Optimizer Algorithm[J]. Computer Engineering and Applications, 2024, 60(4): 355-365.
[12]	张政, 季彬. 考虑随机旅行时间与二维装载约束的越库配送车辆路径优化[J]. 控制与决策, 2023, 38(3): 769-778.
	Zhang Zheng, Ji Bin. Optimization for Two-dimensional Loading Constrained Vehicle Routing Problem with Cross-docking and Stochastic Travel Time[J]. Control and Decision, 2023, 38(3): 769-778.
[13]	Kinoshita Tomoya, Uchiya Takahiro. Diversity Maintenance Method Using Multiple Crossover in Genetic Algorithm for VRPTW[C]//2021 IEEE 10th Global Conference on Consumer Electronics (GCCE). Piscataway: IEEE, 2021: 563-565.
[14]	Duan Jiahui, He Zhenan, Yen G G. Robust Multiobjective Optimization for Vehicle Routing Problem with Time Windows[J]. IEEE Transactions on Cybernetics, 2022, 52(8): 8300-8314.
[15]	Li Jianxia, Liu Ruochen, Wang Ruinan. Elastic Strategy-based Adaptive Genetic Algorithm for Solving Dynamic Vehicle Routing Problem with Time Windows[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(12): 13930-13947.
[16]	Kuo R J, Fernanda Luthfiansyah M, Nur Aini Masruroh, et al. Application of Improved Multi-objective Particle Swarm Optimization Algorithm to Solve Disruption for the Two-stage Vehicle Routing Problem with Time Windows[J]. Expert Systems with Applications, 2023, 225: 120009.
[17]	Wang Yong, Wei Yuanhan, Wang Xiuwen, et al. A Clustering-based Extended Genetic Algorithm for the Multidepot Vehicle Routing Problem with Time Windows and Three-dimensional Loading Constraints[J]. Applied Soft Computing, 2023, 133: 109922.
[18]	Kuo Renjieh, Lu Shihhao, Lai Peiyu, et al. Vehicle Routing Problem with Drones Considering Time Windows[J]. Expert Systems with Applications, 2022, 191: 116264.
[19]	Schaap Hendrik, Schiffer Maximilian, Schneider Michael, et al. A Large Neighborhood Search for the Vehicle Routing Problem with Multiple Time Windows[J]. Transportation Science, 2022, 56(5): 1369-1392.
[20]	Liu Mingde, Shen Yang, Zhao Qi, et al. A Hybrid BSO-ACS Algorithm for Vehicle Routing Problem with Time Windows on Road Networks[C]//2020 IEEE Congress on Evolutionary Computation (CEC). Piscataway: IEEE, 2020: 1-8.
[21]	Wang Yingchao, Yang Chen, Hou Hanpo. Risk Management in Perishable Food Distribution Operations: A Distribution Route Selection Model and Whale Optimization Algorithm[J]. Industrial Management & Data Systems, 2020, 120(2): 291-311.
[22]	蔚帅, 蒋洪伟. 基于聚类的变邻域模拟退火算法求解VRPTW[J]. 北京信息科技大学学报(自然科学版), 2020, 35(5): 86-92.
	Yu Shuai, Jiang Hongwei. Simulated Annealing with Variable Neighborhood Based on Clustering for Vehicle Routing Problem with Time Window[J]. Journal of Beijing Information Science & Technology University, 2020, 35(5): 86-92.
[23]	Zhang Zhiwei, Dou Yajie, Cheng Wei, et al. A Tabu Search Algorithm Based on Density Peak Clustering to Solve VRPTW[C]//2022 8th International Conference on Big Data and Information Analytics (BigDIA). Piscataway: IEEE, 2022: 472-478.
[24]	郭庆腾, 董学士, 李清顺. 基于自适应大邻域搜索的遗传算法求解VRPTW研究[J]. 青岛大学学报(工程技术版), 2023, 38(2): 1-9.
	Guo Qingteng, Dong Xueshi, Li Qingshun. Genetic Algorithm for Vehicle Routing Problems with Time Windows Based on Adaptive Large Neighborhood Search[J]. Journal of Qingdao University (Engineering & Technology Edition), 2023, 38(2): 1-9.

算例	顾客规模	K-means-ILNSA		WPWOA			DBSCAN/SAVN
算例	顾客规模	车辆数	路程	车辆数	路程	路程偏差/%	车辆数	路程	路程偏差/%
C101	25	3	191.83	3	191.83	0	3	191.83	0
C101	50	5	363.24	5	426.40	‒14.81	5	363.24	0
C101	100	10	828.94	10	923.38	‒10.23	10	828.94	0
C103	25	3	190.83	3	190.83	0	3	190.83	0
C103	50	5	362.17	5	523.49	‒30.82	5	363.97	‒0.49
C103	100	10	828.94	10	1 052.10	‒21.21	10	830.06	‒0.13
C104	25	3	190.83	3	191.07	‒0.13	3	190.83	0
C104	50	5	362.1	5	527.15	‒31.30	5	363.46	‒0.35
C104	100	10	828.94	10	1 130.90	‒26.70	10	828.94	0
C201	25	2	215.57	3	228.58	‒5.69	2	215.57	0
C201	50	3	361.82	3	398.55	‒9.22	3	365.58	‒1.03
C201	100	3	626.80	3	707.92	‒11.46	3	650.24	‒3.60

算例	顾客规模	WPWOA	DBSCAN/ SAVN	K-means-ILNSA
C101	25	48.479	15.637	8.313
C101	50	150.585	30.988	10.408
C101	100	341.757	50.989	29.851
C103	25	48.007	15.723	8.676
C103	50	135.757	31.810	14.297
C103	100	386.347	55.602	37.758
C104	25	56.299	22.761	8.826
C104	50	145.851	29.277	13.225
C104	100	358.357	53.352	36.848
C201	25	85.584	53.586	25.982
C201	50	268.569	98.598	50.587
C201	100	359.854	216.497	112.347

算例	车辆数	顾客规模	K-means-ILNSA	WPWOA		DBSCAN/SAVN		DPC/TS
算例	车辆数	顾客规模	路程	路程	路程偏差/%	路程	路程偏差/%	路程	路程偏差
C101	10	100	828.94	953.38	‒13.05	828.94	0.00	828.94	0
C102	10	100	828.94	923.53	‒10.24	828.94	0.00	828.94	0
C103	10	100	828.94	1 052.10	‒21.21	830.06	‒0.13	828.94	0
C104	10	100	828.94	1 130.90	‒26.70	832.94	‒0.48	828.94	0
C105	10	100	828.94	934.42	‒11.29	828.94	0.00	828.94	0
C106	10	100	828.94	981.55	‒15.55	828.94	0.00	828.94	0
C107	10	100	828.94	951.23	‒12.86	828.94	0.00	828.94	0
C108	10	100	828.94	931.55	‒11.01	828.94	0.00	828.94	0
C109	10	100	828.94	984.57	‒15.81	828.94	0.00	828.94	0

算例	顾客规模	WPWOA	DBSCAN/SAVN	DPC/TS	K-means-ILNSA
C101	100	341.757	50.989	36.462	29.851
C102	100	385.758	45.952	35.864	30.451
C103	100	386.347	55.602	64.473	37.758
C104	100	358.357	53.352	47.753	36.848
C105	100	375.697	49.312	38.245	29.286
C106	100	356.788	48.313	35.866	28.909
C107	100	352.347	47.377	42.545	29.616
C108	100	378.587	49.698	45.563	30.406
C109	100	386.857	50.654	47.684	29.111

算例	车辆数	顾客规模	K-means-ILNSA	WPWOA		DBSCAN/SAVN		DPC/TS
算例	车辆数	顾客规模	路程	路程	路程偏差/%	路程	路程偏差/%	路程	路程偏差/%
C201	3	100	626.81	707.92	‒11.46	650.24	‒3.60	645.26	‒2.86
C202	3	100	678.53	739.37	‒8.23	690.94	‒1.80	684.26	‒0.84
C203	3	100	705.29	800.91	‒11.94	741.83	‒4.93	733.28	‒3.82
C204	3	100	650.57	831.24	‒21.73	770.62	‒15.58	697.43	‒6.72
C205	3	100	629.94	895.25	‒29.64	795.58	‒20.82	645.67	‒2.44
C206	3	100	620.27	751.98	‒17.52	644.35	‒3.74	647.84	‒4.26
C207	3	100	647.19	861.28	‒24.86	713.08	‒9.24	697.56	‒7.22
C208	3	100	620.27	798.58	‒22.33	782.69	‒20.75	665.46	‒6.79