Vehicle Routing Problem with Drones Considering Zoned Distribution of Epidemic Prevention Materials

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

Abstract

Abstract:

To address the shortcomings of current contactless delivery methods in the collaborative distribution of epidemic prevention supplies, we introduce a specialized model called the vehicle routing problem with drones considering zoned distribution (VRPD-ZD). In order to solve the problem, a linear programming model is established with the shortest delivery time as the optimization objective, and a two-stage heuristic algorithm is proposed. The initial solution is generated by greedy algorithm in the first stage. In the second stage, we develop a Tabu search algorithm with genetic algorithm (TSGA) hybrid. This enhanced algorithm integrates a taboo list and employs advanced chromosome encoding techniques to improve performance. The experimental results show that TSGA compares favourably with the adaptive algorithm based on genetic method (AAGM) as well as the simulated-annealing-based two-phase optimization (SATO) in terms of solution quality and solution time. This two-stage algorithm can effectively solve the VRPD-ZD problem and can improve the efficiency of cooperative vehicle-machine distribution of epidemic prevention materials.

Key words: truck-drone cooperation, zoned distribution, distribution of epidemic prevention supplies, two stage heuristic algorithm, genetic algorithm

CLC Number:

U116

Ma Huawei, Yan Boying. Vehicle Routing Problem with Drones Considering Zoned Distribution of Epidemic Prevention Materials[J]. Journal of System Simulation, 2025, 37(1): 234-244.

Figures/Tables 13

Fig. 1

Table 1

Symbols and definitions

符号类型	符号	含义
集合	$G$	定义问题的有向图
	$V$	节点集合
	$A$	所有弧集合
	$V 0$	仓库节点集合，包括出发点0(s)与返回点0(r)
	$V C$	顾客节点集合
	$K T$	={1,2,…,K}，车辆集合
	$K D$	={1,2,…,K}，无人机集合
	$V T$	车辆服务节点集合
	$V D$	无人机服务节点集合
	$V L$	无人机起飞节点集合
	$V R$	无人机降落节点集合
	$R k'$	无人机k′架次集合
	$V N T$	封控区内节点集合
	$D i$	服务节点i需求量
参数	$Q$	车辆最大载重
	$M$	能调用车辆最大数目
	$q$	无人机最大载重
	$B$	无人机最大续航
	$Γ i, j k$	车辆k经过弧(i,j)的运行时间
	$τ i, j k'$	无人机k'经过弧(i,j)的运行时间
	$T i k$	车辆k到达节点i的累计运行时间
决策变量	$t i k'$	无人机k'到达节点i的累计运行时间
	$v i k$	如果车辆k服务点i，则为1，否则为0
	$d i k'$	如果无人机k′服务点i，则为1，否则为0
	$x i, j k$	如果车辆k从点i行驶到点j，则为1，否则为0
	$y i, j p, k'$	如果无人机k'的第p个架次中从点i行驶到点j，则为1，否则为0，其中，p∈R $k'$
	$G k$	k型货车在给定路线下返回车辆段的时间，以及完成其服务路线后的总行驶时间

Table 1

Fig. 2

Fig. 3

Fig. 4

Fig. 5

Fig. 6

Fig. 7

Fig. 8

Fig. 9

Fig. 10

Table 2

Table 3

References 26

1	Tăbușcă Alexandru, Gabriel Eugen Garais. IoT and the Flying Answer to COVID-19[J]. Journal of Information Systems & Operations Management, 2020, 14(1): 162-173.
2	北京日报. 疫情期间, 京东无人配送"科技抗疫"[EB/OL]. (2020-04-13) [2023-07-15]. .
3	Wu Guohua, Mao Ni, Luo Qizhang, et al. Collaborative Truck-drone Routing for Contactless Parcel Delivery During the Epidemic[J]. IEEE Transactions on Intelligent Transportation Systems, 2022, 23(12): 25077-25091.
4	Macrina Giusy, Luigi di Puglia Pugliese, Guerriero Francesca, et al. Drone-aided Routing: A Literature Review[J]. Transportation Research Part C: Emerging Technologies, 2020, 120: 102762.
5	和媛媛, 姜盼松, 温禄兴, 等. 权衡公平-经济-效率的多品种防疫物资配送策略[J]. 工业工程与管理, 2021, 26(6): 146-153.
	He Yuanyuan, Jiang Pansong, Wen Luxing, et al. Distribution Strategy of Multiple Epidemic Prevention Materials Weighing Fairness, Economy and Efficiency[J]. Industrial Engineering and Management, 2021, 26(6): 146-153.
6	何婷, 侯汉平, 杨建亮. 疫情背景下生鲜电商企业车辆路径优化研究[J]. 中国安全生产科学技术, 2020, 16(7): 183-188.
	He Ting, Hou Hanping, Yang Jianliang. Research on Vehicle Route Optimization of Fresh E-commerce Enterprises Under Background of Epidemic Situation[J]. Journal of Safety Science and Technology, 2020, 16(7): 183-188.
7	Lu Yichen, Yang Chao, Yang Jun. A Multi-objective Humanitarian Pickup and Delivery Vehicle Routing Problem with Drones[J]. Annals of Operations Research, 2022, 319(1): 291-353.
8	Shi Yuhe, Lin Yun, Li Bo, et al. A Bi-objective Optimization Model for the Medical Supplies' Simultaneous Pickup and Delivery with Drones[J]. Computers & Industrial Engineering, 2022, 171: 108389.
9	Barnawi Ahmed, Chhikara Prateek, Tekchandani Rajkumar, et al. A CNN-based Scheme for COVID-19 Detection with Emergency Services Provisions Using an Optimal Path Planning[J]. Multimedia Systems, 2023, 29(3): 1683-1697.
10	杨双鹏, 郭秀萍, 高娇娇. 无接触式"卡车+无人机"联合配送问题研究[J]. 工业工程与管理, 2022, 27(1): 184-194.
	Yang Shuangpeng, Guo Xiuping, Gao Jiaojiao. Research on Contactless "Truck+Drone" Joint Distribution Problem[J]. Industrial Engineering and Management, 2022, 27(1): 184-194.
11	刘长石, 吴张, 周愉峰, 等. 疫区应急物资供应的卡车-无人机动态协同配送路径优化[J]. 系统科学与数学, 2022, 42(11): 3027-3043.
	Liu Changshi, Wu Zhang, Zhou Yufeng, et al. The Optimization of Dynamic and Cooperative Truck-drone Distribution Routes for Emergency Supplies Delivery in Pandemic Areas[J]. Journal of Systems Science and Mathematical Sciences, 2022, 42(11): 3027-3043.
12	蒋丽, 梁昌勇, 臧晓宁. 卡车与无人机协同的无接触式配送问题的双层启发式算法[J/OL]. 中国管理科学. (2022-11-27) [2023-06-24]. .
	Jiang Li, Liang Changyong, Zang Xiaoning. A Bilevel Heuristic for the Contactless Delivery Problem Coordinated with Trucks and Drones[J/OL]. Chinese Journal of Management Science. (2022-11-27) [2023-06-24]. .
13	季金华, 刘亚君, 别一鸣, 等. 基于无人机与卡车协作的封控社区生活物资配送方法[J]. 交通运输系统工程与信息, 2022, 22(5): 264-272.
	Ji Jinhua, Liu Yajun, Bie Yiming, et al. Delivery Method of Living Goods in Controlled Communities Based on Cooperation Between Drones and Truck[J]. Journal of Transportation Systems Engineering and Information Technology, 2022, 22(5): 264-272.
14	Wang Xingyin, Poikonen S, Golden B. The Vehicle Routing Problem with Drones: Several Worst-case Results[J]. Optimization Letters, 2017, 11(4): 679-697.
15	Daknama Rami, Kraus Elisabeth. Vehicle Routing with Drones[EB/OL]. (2017-05-18) [2023-07-15]. .
16	Wang Zheng, Sheu J B. Vehicle Routing Problem with Drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364.
17	Schermer Daniel, Moeini Mahdi, Wendt Oliver. A Hybrid VNS/Tabu Search Algorithm for Solving the Vehicle Routing Problem with Drones and en Route Operations[J]. Computers & Operations Research, 2019, 109: 134-158.
18	Sacramento David, Pisinger David, Ropke Stefan. An Adaptive Large Neighborhood Search Metaheuristic for the Vehicle Routing Problem with Drones[J]. Transportation Research Part C: Emerging Technologies, 2019, 102: 289-315.
19	Kitjacharoenchai P, Min B C, Lee S. Two Echelon Vehicle Routing Problem with Drones in Last Mile Delivery[J]. International Journal of Production Economics, 2020, 225: 107598.
20	彭勇, 黎元钧. 考虑疫情影响的卡车无人机协同配送路径优化[J]. 中国公路学报, 2020, 33(11): 73-82.
	Peng Yong, Li Yuanjun. Optimization of Truck-drone Collaborative Distribution Route Considering Impact of Epidemic[J]. China Journal of Highway and Transport, 2020, 33(11): 73-82.
21	Jeong H Y, Duk Song Byung, Lee S. Truck-drone Hybrid Delivery Routing: Payload-energy Dependency and No-fly Zones[J]. International Journal of Production Economics, 2019, 214: 220-233.
22	颜瑞, 陈立双, 朱晓宁, 等. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30(5): 144-155.
	Yan Rui, Chen Lishuang, Zhu Xiaoning, et al. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction[J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.
23	Lin Shen. Computer Solutions of the Traveling Salesman Problem[J]. The Bell System Technical Journal, 1965, 44(10): 2245-2269.
24	Solomon M M. Benchmarking Problems[EB/OL]. (2005-03-24) [2023-06-15]. .
25	马华伟, 马凯, 郭君. 考虑多投递的带无人机车辆路径规划问题研究[J]. 计算机工程, 2022, 48(8): 299-305.
	Ma Huawei, Ma Kai, Guo Jun. Research on Vehicle Routing Problem with Drones Considering Multi-delivery[J]. Computer Engineering, 2022, 48(8): 299-305.
26	Hong Fangyu, Wu Guohua, Luo Qizhang, et al. Logistics in the Sky: A Two-phase Optimization Approach for the Drone Package Pickup and Delivery System[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(9): 9175-9190.

算例	TSGA		GAP/%	CPLEX
算例	最好解	时间/s	GAP/%	最好解	时间/s
平均值		3.26			2 530.52
c10-n1	27.17	1.14	1.30	26.82	3.57
c20-n2	141.34	2.96	0.21	141.05	212.86
c30-n3	242.56	3.50	0.17	242.18	6 120.24
c50-n5	510.78	3.94
r10-n1	125.90	2.08	1.05	151.31	5.19
r20-n2	270.03	4.23	0.11	269.72	314.51
r30-n3	395.16	4.29	0.07	394.87	8 320.38
r50-n5	651.29	4.80
rc10-n1	102.41	2.11	0.12	102.29	7.24
rc20-n2	250.54	3.01	0.63	248.97	170.56
rc30-n3	627.67	3.29	0.08	627.15	7 620.16
rc50-n5	947.80	3.79

算例	TSGA		GAP/%	AAGM		GAP/%	SATO
算例	最好解	时间/s	GAP/%	最好解	时间/s	GAP/%	最好解	时间/s
平均值		3.27	-2.68		7.27	-2.56		16.40
c101	1 529.86	3.17	-2.52	1 569.41	6.23	-3.97	1 593.11	14.13
c102	1 530.32	3.13	-1.87	1 559.48	6.35	-1.25	1 549.69	13.85
c103	1 533.75	3.11	-5.74	1 627.20	6.47	0.08	1 532.52	14.47
c104	1 533.12	3.22	-3.12	1 582.49	6.59	-4.14	1 599.33	13.89
c105	1 543.94	3.37	-0.93	1 558.43	6.71	-3.10	1 593.33	13.71
r101	1 359.70	3.42	-4.18	1 419.01	8.18	-2.52	1 394.85	17.68
r102	1 367.59	3.54	0.67	1 358.49	7.89	-3.66	1 419.55	18.19
r103	1 322.03	3.58	-5.28	1 395.72	8.21	0.42	1 316.50	17.71
r104	1 354.41	3.30	-2.36	1 387.15	8.13	-4.32	1 415.56	17.93
r105	1 349.77	3.64	0.45	1 343.72	8.04	-2.73	1 387.65	18.64
rc101	2 211.19	3.12	-4.61	2 318.05	7.12	-0.91	2 231.50	16.92
rc102	2 209.63	3.13	-1.82	2 250.59	7.24	-2.31	2 261.88	16.94
rc103	2 214.98	2.93	-3.44	2 293.89	7.36	-3.88	2 304.39	17.26
rc104	2 192.45	3.09	0.22	2 187.64	7.28	-1.6	2 228.10	16.98
rc105	2 185.25	3.26	-5.63	2 315.62	7.19	-4.43	2 286.54	17.59

[1]	Xiao Peng, Xie Feng, Ni Haihong, Zhang Min, Tang Zhili, Li Ni. Research on Collaborative Optimization Method of Multi-UAV Task Allocation and Path Planning [J]. Journal of System Simulation, 2024, 36(5): 1141-1151.
[2]	Tang Jinjun, Hu Lipeng, Li Mingyang, Zhang Xuan. Optimization of Highway Emergency Lane Control Based on Kriging Genetic Algorithm [J]. Journal of System Simulation, 2024, 36(5): 1165-1178.
[3]	Wan Yuanpeng, Liang Chengji, Wang Sihong, Wang Yu. Joint Distribution-Inventory Optimization and Simulation for Cold Chain Logistics Considering Order Substitution [J]. Journal of System Simulation, 2024, 36(3): 578-594.
[4]	Yan Shiliang, Wang Yinling, Lu Dandan, Pan Xiaoqin. Simulation and Optimization of Permanent Magnet Linear Machine Based on Deep Neural Network [J]. Journal of System Simulation, 2024, 36(3): 713-725.
[5]	Wei Xiang, Liu Xingxuan, Fu Dianzheng, Yang Tianji, Yang Jiaxuan. Platform Path Optimization Method Based on Cumulative Detection Probability of Sonar Search [J]. Journal of System Simulation, 2024, 36(11): 2674-2683.
[6]	Chen Jiajun, Tan Dailun. Multi-strategy Partheno-genetic Algorithm Based on Dynamic Reduction Mechanism for Solving CVRP Problem [J]. Journal of System Simulation, 2024, 36(10): 2396-2412.
[7]	Zhang Hongli, Deng Jingshuang. Research on Artificial Population Generation and Application Based on Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(9): 1965-1974.
[8]	Yuwen Wu, Zhiyue Niu, Zhenping Li. Picking Path Planning of Container Robots Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2023, 35(5): 1086-1097.
[9]	Hongliang Zhang, Jingru Xu, Bo Tan, Gongjie Xu. Dual Resource Constrained Flexible Job Shop Energy-saving Scheduling Considering Delivery Time [J]. Journal of System Simulation, 2023, 35(4): 734-746.
[10]	Zhiqiang Li, Yuanlong Li, Laixiang Yin, Xiangping Ma. Research on Unmanned Swarm Combat System Adaptive Evolution Model Simulation [J]. Journal of System Simulation, 2023, 35(4): 878-886.
[11]	Hucheng Zhang, Jingyu Yang. Research on Intelligent Optimization Method of Combat SoS Based on GABC Algorithm [J]. Journal of System Simulation, 2023, 35(1): 221-227.
[12]	Jia Xu, Fengqing Han, Qixin Liu, Xiaoxia Xue. Bioinformation Heuristic Genetic Algorithm for Solving TSP [J]. Journal of System Simulation, 2022, 34(8): 1811-1819.
[13]	Meng Yu, Zhenli Xu, Tianjiao Tan. Scheduling Optimization and Comparative Analysis of Twin 40 Feet Yard Crane Based on SAGA [J]. Journal of System Simulation, 2022, 34(8): 1885-1898.
[14]	Miao Yu, Manru Li, Yu Zhao. Joint Shift Scheduling Method for Call Center with Mechanism of Delay Information [J]. Journal of System Simulation, 2022, 34(7): 1651-1661.
[15]	Zhijie Li, Haoqi Shi, Changhua Li, Jie Zhang. Image Center Layout Optimization Method Based on Improved Genetic Algorithm [J]. Journal of System Simulation, 2022, 34(6): 1173-1184.