Multi-depot Half-open Vehicle Routing Problem with Simultaneous Delivery-pickup and Time Windows

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

Abstract

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

CLC Number:

TP391.9

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.

Figures/Tables 12

Fig. 1

Fig. 2

Fig. 3

Fig. 4

Table 1

Parameter setting

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

Table 1

Table 2

Table 3

Table 4

Table 5

Table 6

Fig. 5

Table 7

References 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