集配一体化车辆路径规划的混合进化多目标优化

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

摘要/Abstract

摘要：

为了给各物流企业在车辆配送路径规划方面提供合理有效的决策支持，提出了一种多区域混合采样策略的全局搜索和基于个体间路线序列差异局部搜索相结合的混合进化多目标优化算法。对问题进行合理的数学模型构建，利用全局搜索策略使得种群个体从多个方向快速收敛至Pareto前沿面，并使用局部搜索策略来引导种群中表现差的个体朝着表现好的个体的方向进化，从而提高了个体的质量和算法的局部搜索能力。所提算法在集配一体化车辆路径问题的标准测试数据集上进行了一系列的实验，结果表明所提方法在收敛性上明显提升，同时搜索到的解具有良好的分布性能。

关键词: 集配一体化, 时间窗, 混合进化算法, 多区域采样策略, 多目标优化

Abstract:

In order to provide reasonable and effective decision support for logistics enterprises in vehicle distribution route planning, a hybrid evolutionary multi-objective optimization algorithm combining a multi-region mixed-sampling strategy for global search and a local search based on individual route sequence differences is proposed for the problem. A reasonable mathematical model is constructed and the global search strategy is used to make the population individuals to converge quickly to the Pareto front from multiple directions, and the local search strategy is employed to guide the poorly performing individuals in the population to evolve towards the direction of better performing individuals, thus improving both individuals quality and local search capability of the algorithm. By conducting a series of experiments on a standard benchmark of vehicle routing problem with simultaneous delivery and pickup and time windows (VRPSDPTW), and experimental results show that the proposed method significantly improves the convergence performance and produces solutions with good distribution.

Key words: simultaneous delivery and pickup, time windows, hybrid evolutionary algorithm, multi-region sampling strategy, multi-objective optimization

中图分类号:

U492.22

张闻强,王晓萌,张晓晓等 . 集配一体化车辆路径规划的混合进化多目标优化[J]. 系统仿真学报, 2024, 36(8): 1914-1928.

Zhang Wenqiang,Wang Xiaomeng,Zhang Xiaoxiao,et al . Hybrid Evolutionary Multi-objective Optimization Algorithm for Vehicle Routing Problem with Simultaneous Delivery and Pickup[J]. Journal of System Simulation, 2024, 36(8): 1914-1928.

图/表 19

图1

图2

图3

表1

图4

图5

图6

图7

表2

图8

图9

图10

图11

表3

表4

表5

表6

表7

图12

参考文献 26

1	Romeira Bárbara, Moura Ana. Optimizing Route Planning for Minimising the Non-added-value Tasks Times: A Simultaneous Pickup-and-delivery Problem[C]//Proceedings of the 11th International Conference on Operations Research and Enterprise Systems ICORES. Setúbal, Portugal: SciTePress, 2022: 153-160.
2	Schaffer J D. Multiple Objective Optimization with Vector Evaluated Genetic Algorithms[C]//Proceedings of the 1st International Conference on Genetic Algorithms. USA: L. Erlbaum Associates Inc., 1985: 93-100.
3	Wu Hongguang, Gao Yuelin. An Ant Colony Optimization Based on Local Search for the Vehicle Routing Problem with Simultaneous Pickup-delivery and Time Window[J]. Applied Soft Computing, 2023, 139: 110203.
4	Liu Fagui, Wang Lüshengbiao, Gui Mengke, et al. A Hybrid Heuristic Algorithm for Urban Distribution with Simultaneous Pickup-delivery and Time Window[J]. Journal of Heuristics, 2023, 29(2): 269-311.
5	He Linwei, Hu Dawei, Chen Xiqiong, et al. Comparison of Various Mathematical Models for Vehicle Routing Problem with Simultaneous Pickups and Deliveries with Time Window[C]//CICTP 2022. Reston, VA, USA: ASCE, 2022: 3097-3108.
6	Angelelli Enrico, Mansini Renata. The Vehicle Routing Problem with Time Windows and Simultaneous Pick-up and Delivery[C]//Quantitative Approaches to Distribution Logistics and Supply Chain Management. Berlin, Heidelberg: Springer Berlin Heidelberg, 2002: 249-267.
7	Mohammad Bagher Fakhrzad, Seyed Masoud Hoseini Shorshani, Hosseininasab Hasan, et al. Developing a Green Vehicle Routing Problem Model with Time Windows and Simultaneous Pickup and Delivery Under Demand Uncertainty: Minimizing Fuel Consumption[J]. International Journal of Nonlinear Analysis and Applications, 2023, 14(1): 2655-2669.
8	范厚明, 任晓雪, 刘浩. 带时间窗偏好的同时配集货且需求可拆分车辆路径问题[J]. 运筹与管理, 2022, 31(11): 65-71.
	Fan Houming, Ren Xiaoxue, Liu Hao. Split Delivery Vehicle Routing Problem with Simultaneous Delivery and Pick-up and Time Windows Preference[J]. Operations Research and Management Science, 2022, 31(11): 65-71.
9	袁晓建, 张岐山, 吴伶, 等. 带时间窗和同时送取货的车辆路径问题模型及算法[J]. 福州大学学报(自然科学版), 2020, 48(5): 566-572.
	Yuan Xiaojian, Zhang Qishan, Wu Ling, et al. Research on Vehicle Routing Problem Model and Algorithm with Time Window and Simultaneous Delivery[J]. Journal of Fuzhou University(Natural Science Edition), 2020, 48(5): 566-572.
10	王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[J]. 计算机集成制造系统, 2018, 24(3): 570-582.
	Wang Chao, Liu Chao, Mu Dong, et al. VRPSPDTW Problem Solving by Discrete Cuckoo Search[J]. Computer Integrated Manufacturing Systems, 2018, 24(3): 570-582.
11	王超, 高扬, 刘超, 等. 基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题[J]. 计算机集成制造系统, 2019, 25(9): 2237-2247.
	Wang Chao, Gao Yang, Liu Chao, et al. Vehicle Routing Problem with Simultaneous Delivery and Pickup Problem Solving by Backtracking Search Optimization Algorithm[J]. Computer Integrated Manufacturing Systems, 2019, 25(9): 2237-2247.
12	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[J]. 计算机应用, 2020, 40(4): 1097-1103.
	Zhang Qinghua, Wu Guangpu. Modeling and Memetic Algorithm for Vehicle Routing Problem with Simultaneous Pickup-delivery and Time Windows[J]. Journal of Computer Applications, 2020, 40(4): 1097-1103.
13	蔡菂迪. 改进遗传算法在车辆路径问题中的研究应用[D]. 哈尔滨: 哈尔滨工程大学, 2013.
	Cai Didi. Improved Genetic Algorithm to Solve the Vehicle Routing Problem[D]. Harbin: Harbin Engineering University, 2013.
14	Fatma Pinar Goksal, Karaoglan Ismail, Altiparmak Fulya. A Hybrid Discrete Particle Swarm Optimization for Vehicle Routing Problem with Simultaneous Pickup and Delivery[J]. Computers & Industrial Engineering, 2013, 65(1): 39-53.
15	Mst Anjuman Ara, Md Tanvir Ahmed, Yeasmin Nilufa. Optimisation Model for Simultaneous Delivery and Pickup Vehicle Routing Problem with Time Windows[J]. International Journal of Services and Operations Management, 2022, 43(2): 145-168.
16	李珺, 段钰蓉, 郝丽艳, 等. 混合优化算法求解同时送取货车辆路径问题[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.
17	Kirkpatrick S, Gelatt C D Jr, Vecchi M P. Optimization by Simulated Annealing[J]. Science, 1983, 220(4598): 671-680.
18	Li Hongye, Wang Lei, Xinghong Hei, et al. A Decomposition-based Chemical Reaction Optimization for Multi-objective Vehicle Routing Problem for Simultaneous Delivery and Pickup with Time Windows[J]. Memetic Computing, 2018, 10(1): 103-120.
19	李亚龙. 基于改进狼群算法的VRPSDPTW车辆路径优化研究[D]. 长春: 长春工业大学, 2022.
	Li Yalong. The VRPSDPTW Vehicle Path Based on the Improved Wolf Pack Algorithm Optimize the Study[D]. Changchun: Changchun University of Technology, 2022.
20	Cai Wangang, Zhang Yihao, Huang Fuyou, et al. Delivery Routing Problem of Pure Electric Vehicle with Multi-objective Pick-up and Delivery Integration[J]. PLoS One, 2023, 18(2): e0281131.
21	Hof Julian, Schneider Michael. An Adaptive Large Neighborhood Search with Path Relinking for a Class of Vehicle-routing Problems with Simultaneous Pickup and Delivery[J]. Networks, 2019, 74(3): 207-250.
22	Zhang Wenqiang, Gen Mitsuo, Jo Jungbok. Hybrid Sampling Strategy-based Multiobjective Evolutionary Algorithm for Process Planning and Scheduling Problem[J]. Journal of Intelligent Manufacturing, 2014, 25(5): 881-897.
23	Wang H F, Chen Y Y. A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window[J]. Computers and Industrial Engineering, 2012, 62(1): 84-95.
24	Deb K, Pratap A, Agarwal S, et al. A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.
25	Zitzler Eckart, Laumanns Marco, Thiele Lothar. SPEA2: Improving the Strength Pareto Evolutionary Algorithm[EB/OL]. (2001-05) [2022-10-10]. .
26	Zhang Qingfu, Li Hui. MOEA/D: A Multiobjective Evolutionary Algorithm Based on Decomposition[J]. IEEE Transactions on Evolutionary Computation, 2007, 11(6): 712-731.

步数	路线交换序列
1	(0,1)
2	(0,1) (1,3)
3	(0,5) (1,3) (2,7)
4	(0,5) (1,3) (2,7) (3,8)
5	(0,5) (1,3) (2,7) (3,8) (4,7)
6	(0,5) (1,3) (2,7) (3,8) (4,7) (5,8)
7	(0,5) (1,3) (2,7) (3,8) (4,7) (5,8) (6,9)
8	(0,5) (1,3) (2,7) (3,8) (4,7) (5,8) (6,9) (8,9)

实例集	HEMO-MRSS with IMP		HEMO-MRSS without IMP
实例集	Mean	Best	Mean	Best
cdp101	19.74	16	23.18	17
cdp102	19.69	15	22.22	17
cdp201	7.01	5	11.90	8
cdp202	6.61	5	10.28	7
rcdp101	35.55	28	32.12	29
rcdp102	30.82	26	28.75	26
rcdp201	9.13	8	12.37	9
rcdp202	8.49	7	11.46	9
rdp101	36.13	28	38.33	31
rdp102	33.11	27	33.09	28
rdp201	7.56	6	11.78	8
rdp202	6.85	6	9.77	7

参数	HEMO-MRSS	MOHEA	NSGA-II	SPEA2	MOEA/D
种群大小	50	50	50	50	50
精英种群大小	25	25	/	50	/
子种群大小	25	25	/	/	/
交叉率	0.7	0.7	0.7	0.7	0.7
变异率	0.2	0.2	0.2	0.2	0.2
RSD-LS截取比例	0.7	/	/	/	/

案例集	HEMO-MRSS	MOHEA		NSGA-II		SPEA2		MOEA/D
案例集	Mean	Mean	H.T.	Mean	H.T.	Mean	H.T.	Mean	H.T.
cdp101	1.75×10⁵	1.75×10⁵	*	1.65×10⁵	*	1.63×10⁵	*	8.87×10⁴	-
cdp102	1.27×10⁵	1.26×10⁵	*	1.13×10⁵	*	1.20×10⁵	*	7.27×10⁴	-
cdp201	2.13×10⁵	2.11×10⁵	*	1.22×10⁵	*	2.06×10⁵	*	1.39×10⁵	*
cdp202	1.71×10⁵	1.67×10⁵	*	1.19×10⁵	-	1.62×10⁵	*	1.26×10⁵	*
rcdp101	5.02×10³	5.28×10³	*	4.88×10³	*	4.80×10³	*	3.30×10³	-
rcdp102	4.35×10³	4.43×10³	*	4.01×10³	*	4.00×10³	-	2.87×10³	-
rcdp201	3.21×10⁴	3.03×10⁴	*	2.05×10⁴	-	2.93×10⁴	-	2.15×10⁴	*
rcdp202	2.47×10⁴	2.42×10⁴	*	1.71×10⁴	-	2.28×10⁴	-	1.68×10⁴	-
rdp101	3.48×10⁴	3.50×10⁴	*	3.43×10⁴	*	3.33×10⁴	*	1.62×10⁴	-
rdp102	2.10×10⁴	2.20×10⁴	*	2.00×10⁴	*	2.06×10⁴	*	9.48×10³	-
rdp201	3.42×10⁴	3.34×10⁴	*	1.83×10⁴	-	3.16×10⁴	-	2.53×10⁴	-
rdp202	3.52×10⁴	3.46×10⁴	*	2.46×10⁴	-	3.28×10⁴	*	2.69×10⁴	-

案例集	HEMO-MRSS	MOHEA		NSGA-II		SPEA2		MOEA/D
案例集	Mean	Mean	H.T.	Mean	H.T.	Mean	H.T.	Mean	H.T.
cdp101	1.06×10^-1	1.17×10^-1	*	6.51×10^-2	*	1.37×10^-1	*	3.18×10^-1	-
cdp102	5.11×10^-2	5.90×10^-2	*	7.66×10^-2	-	9.44×10^-2	-	3.14×10^-1	-
cdp201	6.04×10^-2	6.87×10^-2	*	3.49×10^-1	*	9.41×10^-2	-	3.53×10^-1	*
cdp202	8.11×10^-2	1.11×10^-1	-	3.03×10^-1	-	1.29×10^-1	*	2.84×10^-1	*
rcdp101	7.96×10^-2	5.93×10^-2	*	7.07×10^-2	-	9.59×10^-2	-	1.82×10^-1	*
rcdp102	6.77×10^-2	6.89×10^-2	*	8.71×10^-2	-	1.10×10^-1	*	1.82×10^-1	-
rcdp201	5.36×10^-2	1.07×10^-1	*	2.80×10^-1	*	1.31×10^-1	*	2.72×10^-1	*
rcdp202	3.65×10^-2	7.17×10^-2	-	2.26×10^-1	*	1.14×10^-1	*	2.52×10^-1	*
rdp101	6.97×10^-2	6.60×10^-2	*	6.64×10^-2	*	1.06×10^-1	-	3.18×10^-1	-
rdp102	7.92×10^-2	5.98×10^-2	*	5.60×10^-2	*	1.05×10^-1	*	2.86×10^-1	*
rdp201	1.51×10^-1	1.71×10^-1	*	2.63×10^-1	-	1.79×10^-1	-	2.54×10^-1	-
rdp202	3.72×10^-2	6.20×10^-2	-	2.62×10^-1	-	9.49×10^-2	-	2.33×10^-1	-