带时间窗的多中心半开放式VRPSDP问题研究

doi:10.16182/j.issn1004731x.joss.22-0727

摘要/Abstract

摘要：

针对带时间窗的多中心半开放式同时送取货车辆路径问题，构建了配送中心车辆进出平衡且以车辆配送距离最小化为目标的带时间窗的多中心半开放式同时送取货车辆路径问题的数学模型。设计了混沌变异头脑风暴算法求解该问题，采用顺序交叉策略增加种群多样性，设置2种混沌映射进行混沌变异操作，利用混沌变异的多样性、遍历性和随机性，增强算法全局搜索能力。通过多组算例对比，不仅验证所提算法求解多种车辆路径问题的有效性与稳定性，还验证了带时间窗下的多中心半开放同时送取货配送模式优于多中心闭合式同时送取货配送模式。研究成果不仅拓展了车辆路径类的模型，还为相关物流企业提供一种决策参考。

关键词: 车辆路径问题, 多中心, 同时送取货, 时间窗, 混沌变异头脑风暴算法

Abstract:

To solve the multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows, this paper builds a mathematical model of a multi-depot half-open vehicle routing problem with simultaneous delivery-pickup and time windows by balancing the vehicle in and out of the distribution center and minimizing vehicle delivery distance as the goal. According to the characteristics of the problem, a brain storm algorithm based on chaotic mutation is designed to solve this problem,and the sequential crossover strategy is adopted to increase the population diversity. Meanwhile, the algorithm selects two chaotic maps for chaotic mutation operation, which employs the diversity, ergodicity, and randomness of chaotic mutation to enhance the overall search capability of the algorithm. Multiple numerical example comparison not only verifies the effectiveness and stability of the proposed algorithm for solving various vehicle routing problems but also indicates the distribution mode of multi-depot half-open simultaneous delivery-pickup and time windows is superior to that of multi-depot simultaneous delivery-pickup and time windows. The research results expand the vehicle routing problem and provide a decision-making reference for related logistics enterprises.

Key words: vehicle routing problem, multi-depot, simultaneous delivery-pickup, time windows, brain storm optimization algorithm based on chaotic mutation

中图分类号:

TP391.9

张颖钰,吴立云,贾胜钛 . 带时间窗的多中心半开放式VRPSDP问题研究[J]. 系统仿真学报, 2023, 35(11): 2464-2475.

Zhang Yingyu,Wu Liyun,Jia Shengtai . Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time Windows[J]. Journal of System Simulation, 2023, 35(11): 2464-2475.

图/表 12

图1

图2

图3

图4

表1

参数设置

n	N	T	J	J_max	D_max	P_o	P_t
$0 < n ≤ 25$	50	100~300	5~10	20	20~50	0.5~0.8	1-P_o
$25 < n ≤ 50$	100	100~300	5~10	20	20~50	0.5~0.8	1-P_o
$50 < n < 100$	100	100~500	5~10	20	20~50	0.5~0.8	1-P_o

表1

表2

表3

表4

表5

表6

图5

表7

参考文献 21

1	Angelelli E, Mansini R. 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.
2	Wang H F, Chen Y Y. A Genetic Algorithm for the Simultaneous Delivery and Pickup Problems with Time Window[J]. Computers & Industrial Engineering, 2012, 62(1): 84-95.
3	王超, 刘超, 穆东, 等. 基于离散布谷鸟算法求解带时间窗和同时取送货的车辆路径问题[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.
4	王超, 高扬, 刘超, 等. 基于回溯搜索优化算法求解带时间窗和同时送取货的车辆路径问题[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.
5	李珺, 段钰蓉, 郝丽艳, 等. 混合优化算法求解同时送取货车辆路径问题[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.
6	Li Jian, Li Yang, Pardalos P M. Multi-depot Vehicle Routing Problem with Time Windows Under Shared Depot Resources[J]. Journal of Combinatorial Optimization, 2016, 31(2): 515-532.
7	Bae H, Moon I. Multi-depot Vehicle Routing Problem with Time Windows Considering Delivery and Installation Vehicles[J]. Applied Mathematical Modelling, 2016, 40(13/14): 6536-6549.
8	王勇, 任音吉, 刘永, 等. 基于多中心车辆路径问题的收益分配优化研究[J]. 交通运输系统工程与信息, 2018, 18(3): 210-217.
	Wang Yong, Ren Yinji, Liu Yong, et al. Profit Allocation Optimization Based on Multi-center Vehicle Routing Problem[J]. Journal of Transportation Systems Engineering and Information Technology, 2018, 18(3): 210-217.
9	范厚明, 杨翔, 李荡, 等. 基于生鲜品多中心联合配送的半开放式车辆路径问题[J]. 计算机集成制造系统, 2019, 25(1): 256-266.
	Fan Houming, Yang Xiang, Li Dang, et al. Half-open Multi-depot Vehicle Routing Problem Based on Joint Distribution Mode of Fresh Food[J]. Computer Integrated Manufacturing Systems, 2019, 25(1): 256-266.
10	马冰山, 胡大伟, 陈希琼, 等. 半开放式的多配送中心纯电动车辆路径优化问题[J]. 交通运输系统工程与信息, 2019, 19(6): 199-205.
	Ma Bingshan, Hu Dawei, Chen Xiqiong, et al. An Optimization of Pure Electric Vehicle Routing Problem on Half-open Multi-distribution Center[J]. Journal of Transportation Systems Engineering and Information Technology, 2019, 19(6): 199-205.
11	辜勇, 袁源乙, 张列, 等. 带时间窗的多中心半开放式车辆路径问题[J]. 中国机械工程, 2020, 31(14): 1733-1740.
	Gu Yong, Yuan Yuanyi, Zhang Lie, et al. Multi-depot Half Open Vehicle Routing Problem with Time Windows[J]. China Mechanical Engineering, 2020, 31(14): 1733-1740.
12	张凯庆, 嵇启春. 速度时变的多中心半开放式车辆路径问题研究[J]. 系统仿真学报, 2022, 34(4): 836-846.
	Zhang Kaiqing, Ji Qichun. Research on Multi-depot Half-open Vehicle Routing Problem with Time-varying Speed[J]. Journal of System Simulation, 2022, 34(4): 836-846.
13	Yang Zhensu, Shi Yuhui. Brain Storm Optimization with Chaotic Operation[C]//2015 Seventh International Conference on Advanced Computational Intelligence (ICACI). Piscataway, NJ, USA: IEEE, 2015: 111-115.
14	Yu Yang, Gao Shangce, Cheng Shi, et al. CBSO: a Memetic Brain Storm Optimization with Chaotic Local Search[J]. Memetic Computing, 2018, 10(4): 353-367.
15	衣俊艳, 施晓东, 杨刚. 多分支混沌变异的头脑风暴优化算法[J]. 计算机工程与应用, 2022, 58(16): 129-138.
	Yi Junyan, Shi Xiaodong, Yang Gang. Brain Storm Optimization Based on Multi-branch Chaotic Mutation[J]. Computer Engineering and Applications, 2022, 58(16): 129-138.
16	Tlili T, Krichen S, Drira G, et al. On Solving the Multi-depot Vehicle Routing Problem[C]//Proceedings of 3rd International Conference on Advanced Computing, Networking and Informatics. New Delhi: Springer India, 2016: 103-108.
17	Fernando Bernardes de Oliveira, Enayatifar R, Sadaei H J, et al. A Cooperative Coevolutionary Algorithm for the Multi-depot Vehicle Routing Problem[J]. Expert Systems with Applications, 2016, 43: 117-130.
18	范厚明, 刘鹏程, 刘浩, 等. 多中心联合配送模式下集货需求随机的VRPSDP问题[J]. 自动化学报, 2021, 47(7): 1646-1660.
	Fan Houming, Liu Pengcheng, Liu Hao, et al. The Multi-depot Vehicle Routing Problem with Simultaneous Deterministic Delivery and Stochastic Pickup Based on Joint Distribution[J]. Acta Automatica Sinica, 2021, 47(7): 1646-1660.
19	张庆华, 吴光谱. 带时间窗的同时取送货车辆路径问题建模及模因求解算法[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.
20	Shi Yong, Zhou Yanjie, Boudouh T, et al. A Lexicographic-based Two-stage Algorithm for Vehicle Routing Problem with Simultaneous Pickup-delivery and Time Window[J]. Engineering Applications of Artificial Intelligence, 2020, 95: 103901.
21	Salhi S, Nagy G. A Cluster Insertion Heuristic for Single and Multiple Depot Vehicle Routing Problems with Backhauling[J]. Journal of the Operational Research Society, 1999, 50(10): 1034-1042.

算例	客户规模	BKS	ILS		CoES		AMAVNS		CMBSO
算例	客户规模	BKS	Best	Dev/%	Best	Dev/%	Best	Dev/%	Best	Dev/%
Ave	719.95		755.49	4.91	722.86	0.36	734.11	1.61	742.67	0.21
P01	50	576.87	606.11	5.07	576.87	0.00	576.87	0.00	576.87	0.00
P02	50	473.53	496.45	4.84	475.06	0.32	473.53	0.00	474.53	0.21
P03	75	641.19	675.32	5.32	643.57	0.37	646.33	0.80	642.27	0.17
P04	100	1 001.59	1 062.60	6.09	1 011.42	0.98	1 039.69	3.80	1 001.59	0.00
P05	100	750.03	782.34	4.31	752.39	0.31	765.98	2.13	877.86	0.16
P06	100	876.50	910.13	3.84	877.86	0.16	902.27	2.94	882.88	0.72

算例	客户规模	BKS	Best
算例	客户规模	BKS	DCS	MA	CMBSO
Rcdp1001	10	349.98	349.98	349.98	349.98
Rcdp1004	10	216.69	216.69	216.69	216.69
Rcdp1007	10	310.81	310.81	310.81	310.81
Rcdp2501	25	551.05	551.05	551.05	551.05
Rcdp2504	25	473.46	473.46	473.46	473.46
Rcdp2507	25	540.87	540.87	540.87	540.87
Rcdp5001	50	994.18	994.18	994.18	994.18
Rcdp5004	50	725.59	725.59	725.59	725.59
Rcdp5007	50	809.72	809.72	809.72	809.72

算例	客户规模	客户位置分布	时间窗宽紧
Rdp101	100	分散	较紧
Cdp101	100	聚集	较紧
Rcdp101	100	分散与聚集混合	较紧
Rdp201	100	分散	较宽
Cdp201	100	聚集	较宽
Rcdp201	100	分散与聚集混合	较宽

算例	BKS	DCS			BSA			VNS-BSTS			CMBSO
算例	BKS	Best		Dev/%	Best		Dev/%	Best		Dev/%	Best		Dev/%
Ave	1 227.81	1 284.17	4.54		1 280.72	4.26		1 269.78	3.20		1 259.99	2.59
Rdp101	1 650.20	1 658.65		0.51	1 659.77		0.58	1 650.80		0.04	1 650.80		0.04
Cdp101	963.96	998.29		3.56	992.88		3.00	976.04		1.25	976.04		1.25
Rcdp101	1 652.90	1 654.32		0.08	1 655.77		0.17	1 708.21		3.35	1 666.12		0.80
Rdp201	1 181.73	1 281.63		8.45	1 286.55		8.87	1 254.57		6.16	1 268.52		7.34
Cdp201	591.56	591.56		0.005	591.56		0.00	591.56		0.00	591.56		0.00
Rcdp201	1 326.19	1 520.56		14.66	1 497.80		12.94	1 437.48		8.39	1 406.94		6.09

算例	客户规模	MDHOVRPSDPTW					MDVRPSDPTW
算例	客户规模	Num	Best	Avg	Cpu/s	Dev/%	Num	Best	Avg	Cpu/s	Dev/%
pr01	48	5	1 201.26	1 285.31	4.3	6.54	5	1 310.31	1 351.47	3.7	3.05
pr02	96	9	1 977.52	2 073.01	13.6	4.61	9	2 118.88	2 140.52	20.4	1.01