Aerial-ground collaborative delivery route planning with UAV energy function and multi-delivery

doi:10.23919/JSEE.2025.000048

Journal of Systems Engineering and Electronics ›› 2025, Vol. 36 ›› Issue (2): 446-461.doi: 10.23919/JSEE.2025.000048

• SYSTEMS ENGINEERING • Previous Articles

Aerial-ground collaborative delivery route planning with UAV energy function and multi-delivery

Jingfeng GUO(), Rui SONG(), Shiwei HE()

Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing 100044, China

Received:2024-06-03 Online:2025-04-18 Published:2025-05-20
Contact: Rui SONG E-mail:616988704@qq.com;rsong@bjtu.edu.cn;shwhe@bjtu.edu.cn
About author:
GUO Jingfeng was born in 1995. He received his M.S. degree in transportation engineering from the Faculty of Architecture, Civil and Transportation Engineering, Beijing University of Technology, Beijing, China, in 2021. He is currently pursuing his Ph.D. degree in Beijing Jiaotong University, Beijing, China. His research interests are intelligent transportation systems, logistics modeling, and optimization. E-mail: 616988704@qq.com

SONG Rui was born in 1971. She received her Ph.D. degree in transportation planning and management from Southwest Jiaotong University, Chengdu, China, in 1997. She is currently a professor with the Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing, China. Her research interests are transportation planning and management, intelligent transportation systems, and logistics. E-mail: rsong@bjtu.edu.cn

HE Shiwei was born in 1969. He received his Ph.D. degree in railway operations from Southwest Jiaotong University, Chengdu, China, in 1996. He is currently a professor with the Key Laboratory of Transport Industry of Big Data Application Technologies for Comprehensive Transport, Beijing Jiaotong University, Beijing, China. His research interests are transportation theory and technology, transportation planning and management. E-mail: shwhe@bjtu.edu.cn
Supported by:
This work was supported by the Fundamental Research Funds for the Central Universities (2024JBZX038) and the National Natural Science Foundation of China (62076023).

Abstract

Abstract:

With the rapid development of low-altitude economy and unmanned aerial vehicles (UAVs) deployment technology, aerial-ground collaborative delivery (AGCD) is emerging as a novel mode of last-mile delivery, where the vehicle and its onboard UAVs are utilized efficiently. Vehicles not only provide delivery services to customers but also function as mobile warehouses and launch/recovery platforms for UAVs. This paper addresses the vehicle routing problem with UAVs considering time window and UAV multi-delivery (VRPU-TW&MD). A mixed integer linear programming (MILP) model is developed to minimize delivery costs while incorporating constraints related to UAV energy consumption. Subsequently, a micro-evolution augmented large neighborhood search (MEALNS) algorithm incorporating adaptive large neighborhood search (ALNS) and micro-evolution mechanism is proposed. Numerical experiments demonstrate the effectiveness of both the model and algorithm in solving the VRPU-TW&MD. The impact of key parameters on delivery performance is explored by sensitivity analysis.

Key words: aerial-ground collaborative delivery (AGCD), route planning, unmanned aerial vehicle (UAV) energy function, UAV multi-delivery, micro-evolution, adaptive large neighborhood search

Jingfeng GUO, Rui SONG, Shiwei HE. Aerial-ground collaborative delivery route planning with UAV energy function and multi-delivery[J]. Journal of Systems Engineering and Electronics, 2025, 36(2): 446-461.

Figures/Tables 16

Table 1

Fig 1

Fig 2

Table 2

Fig 3

Fig 4

Table 3

Table 4

Table 5

Table 6

Table 7

Fig 5

Table 8

Fig 6

Fig 7

Table 9

References 30

1	AGATZ N, BOUMAN P, SCHMIDT M Optimization approaches for the traveling salesman problem with drone. Transportation Science, 2018, 52 (4): 965- 981. doi: 10.1287/trsc.2017.0791
2	MASMOUDI M A, MANCINI S, BALDACCI R, et al Vehicle routing problems with drones equipped with multi-package payload compartments. Transportation Research Part E: Logistics and Transportation Review, 2022, 164, 102757. doi: 10.1016/j.tre.2022.102757
3	ARYA M N. China’s drone delivery platform Meituan joins NextGen FDI program. https://www.gccbusinessnews.com/meituan-uas-joins-nextgen-fdi-program/.
4	LI D W, IGNATIUS J, WANG D, et al A branch-and-price-and-cut algorithm for the truck-drone routing problem with simultaneously delivery and pickup. Naval Research Logistics, 2024, 71 (2): 241- 285. doi: 10.1002/nav.22151
5	YIN Y Q, LI D W, WANG D J, et al A branch-and-price-and-cut algorithm for the truck-based drone delivery routing problem with time windows. European Journal of Operational Research, 2023, 309 (3): 1125- 1144. doi: 10.1016/j.ejor.2023.02.030
6	MURRAY C C, CHU A G The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery. Transportation Research Part C: Emerging Technologies, 2015, 54, 86- 109. doi: 10.1016/j.trc.2015.03.005
7	HA Q M, DEVILLE Y, PHAM Q D, et al On the min-cost traveling salesman problem with drone. Transportation Research Part C: Emerging Technologies, 2018, 86, 597- 621. doi: 10.1016/j.trc.2017.11.015
8	TU P A, DAT N T, DUNG P Q. Traveling salesman problem with multiple drones. Proc. of the 9th International Symposium on Information and Communication Technology, 2018: 46−53.
9	MURRAY C C, RAJ R The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones. Transportation Research Part C: Emerging Technologies, 2020, 110, 368- 398. doi: 10.1016/j.trc.2019.11.003
10	LAN B. Traveling salesman problem with time windows and drones (TSPTWD). Ames: Iowa State University, 2020.
11	SCHERMER D, MOEINI M, WENDT O A matheuristic for the vehicle routing problem with drones and its variants. Transportation Research Part C: Emerging Technologies, 2019, 106, 166- 204. doi: 10.1016/j.trc.2019.06.016
12	SCHERMER D, MOEINI M, WENDT O A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations. Computers & Operations Research, 2019, 109, 134- 158.
13	WANG Z, SHEU J B Vehicle routing problem with drones. Transportation Research Part B: Methodological, 2019, 122, 350- 364. doi: 10.1016/j.trb.2019.03.005
14	KUO R J, LU S H, LAI P Y, et al Vehicle routing problem with drones considering time windows. Expert Systems with Applications, 2022, 191, 116264. doi: 10.1016/j.eswa.2021.116264
15	SACRAMENTO D, PISINGER D, ROPKE S An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones. Transportation Research Part C: Emerging Technologies, 2019, 102, 289- 315. doi: 10.1016/j.trc.2019.02.018
16	CHENG C, ADULYASAK Y, ROUSSEAU L M Drone routing with energy function: formulation and exact algorithm. Transportation Research Part B: Methodological, 2020, 139, 364- 387. doi: 10.1016/j.trb.2020.06.011
17	JEONG H Y, SONG B D, LEE S Truck-drone hybrid delivery routing: payload-energy dependency and no-fly zones. International Journal of Production Economics, 2019, 214, 220- 233. doi: 10.1016/j.ijpe.2019.01.010
18	MENG S S, GUO X P, LI D, et al The multi-visit drone routing problem for pickup and delivery services. Transportation Research Part E: Logistics and Transportation Review, 2023, 169, 102990. doi: 10.1016/j.tre.2022.102990
19	WU G H, MAO N, XU B J, et al The cooperative delivery of multiple vehicles and multiple drones based on adaptive large neighborhood search. Control and Decision, 2023, 38 (1): 201- 210.
20	MA H W, MA K, GUO J Research on vehicle routing problem with drones considering multi-delivery. Computer Engineering, 2022, 48 (8): 299- 305.
21	THIBBOTUWAWA A, NIELSEN P, ZBIGNIEW B, et al. Energy consumption in unmanned aerial vehicles: a review of energy consumption models and their relation to the UAV routing. Proc. of the 39th International Conference on Information Systems Architecture and Technology–ISAT 2018: Part II, 2019: 173−184.
22	PUGLIESE L D P, GUERRIERO F, MACRINA G Using drones for parcels delivery process. Procedia Manufacturing, 2020, 42, 488- 497. doi: 10.1016/j.promfg.2020.02.043
23	THIBBOTUWAWA A, BOCEWICZ G, RADZKI G, et al UAV mission planning resistant to weather uncertainty. Sensors, 2020, 20 (2): 515. doi: 10.3390/s20020515
24	ROPKE S, PISINGER D An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 2006, 40 (4): 455- 472. doi: 10.1287/trsc.1050.0135
25	LI W H, WANG R, HENG Y, et al Knowledge-guided evolutionary optimization for large-scale air defense resource allocation. IEEE Trans. on Artificial Intelligence, 2024, 5 (12): 6267- 6279. doi: 10.1109/TAI.2024.3375263
26	WU Y D, HE S W, ZHOU H Comprehensive optimization model and algorithm of operation plan for smart port station of heavy haul railway. Journal of Transportation Systems Engineering and Information Technology, 2023, 23 (6): 215- 226,261.
27	BRAYSY O, DULLAERT W, HASLE G, et al An effective multirestart deterministic annealing metaheuristic for the fleet size and mix vehicle-routing problem with time windows. Transportation Science, 2008, 42 (3): 371- 386. doi: 10.1287/trsc.1070.0217
28	WANG D C, MOON I, ZHANG R Y Multi-trip multi-trailer drop-and-pull container drayage problem. IEEE Trans. on Intelligent Transportation Systems, 2022, 23 (10): 19088- 19104. doi: 10.1109/TITS.2022.3156547
29	China Meteorological Administration. Specifications for surface meteorological observation-Wind direction and wind speed. https://www.cma.gov.cn/zfxxgk/gknr/flfgbz/bz/202209/t20220921_5099085.html.
30	ZHAO G H, QIN W X Vehicle joint UAV distribution path planning under weather factors. Logistics and Supply Chain Economy, 2023, 45 (9): 148- 155.

Reference	Problem modelling							Algorithm
Reference	V	U	Obj	TW	CVU	UEC	UDM	Algorithm
Murray et al. [6]	1	1	CT	×	SC	ET	SD	Heuristic
Ha et al. [7]	1	1	CDW	×	SC	ET	SD	GRASP
Tu et al. [8]	1	N	CD	×	SC	ED	SD	GRASP-ALNS
Murray et al. [9]	1	N	CT	×	SC	ET	SD	Heuristic
Lan et al. [10]	1	1	CT	√	SC	ET	SD	Heuristic
Schermer et al. [11]	M	N	MS	×	SC	ED	SD	Matheuristic
Kuo et al. [14]	M	1	CD	√	SC	ET	SD	VNS
Sacramento et al. [15]	M	1	CD	×	SC	ET	SD	ALNS
Cheng et al. [16]	0	N	CE	√	−	EP	MD	Branch-and-cut
Jeong et al. [17]	1	1	CT	×	SC	EP	SD	Heuristic
Meng et al. [18]	M	1	CD	×	HC	EP	MD	ISA
Wu et al. [19]	M	N	MS	×	SC	EP	MD	ALNS
Ma et al. [20]	M	1	MS	×	SC	ET	MD	AAGM
This paper	M	1	CE	√	HC	EPW	MD	MEALNS

Parameter	Description
$ F $/J	Consumed energy
$ P $/W	UAV’s flight power
$ t $/s	Flight duration
$ {C_D} $	Drag coefficient
$ A $/m²	Front surface of UAV
$ \rho $	Air density
$ {v_a} $/(m/s)	UAV’s airspeed
$ W $/kg	UAV’s body weight
$ q $/kg	UAV’s payload
$ g $/(m/s²)	Gravitational acceleration
$ b $/m	UAV width
$ l $/m	Flight distance
$ {v_g} $/(m/s)	UAV’s ground speed
$v_w $/(m/s)	Wind speed
$ {\theta _a} $/rad	Angle of airspeed
$ {\theta _w} $/rad	Angle of wind speed
$ {\theta _g} $/rad	Angle of ground speed

Score	Description
$ {{\mathrm{sc}}_1} $	New solution sⁿ is better than global best solution s^*
$ {{\mathrm{sc}}_2} $	New solution sⁿ is better than the current solution s^c but worse than global best solution s^*
$ {{\mathrm{sc}}_3} $	New solution is worse than the cost of the current solution but f(sⁿ)−f(s^c) < T

Parameter	Value
Cost coefficient of UAV $ {c_{ijk}} $/(yuan/J)	1.68×10⁻⁷
Cost coefficient of vehicle $ {c_{ij}} $/(yuan/m)	0.0008
Maximum payload of vehicle/kg	1000
Maximum payload of UAV/kg	30
Battery volume/J	8667648
Airspeed/(m/s)	20
UAV empty weight/kg	25
Drag coefficient	0.54
The front surface of UAV/m²	1.8
UAV width/m	1.88
Air density	1.225

Parameter	Value
Population size	100
Iterations of micro-evolution	100
Percentage of removed customers β/%	20
$ {{\mathrm{sc}}_1} $	30
$ {{\mathrm{sc}}_2} $	18
$ {{\mathrm{sc}}_3} $	12
tol	0.01
phi	0.99975
ρ	0.6

Aerial-ground collaborative delivery route planning with UAV energy function and multi-delivery

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 16

References 30

Related Articles 6

Recommended Articles

Metrics

Comments

Case	Size	Dimension/km²	Gurobi		MEALNS			GAP/%
Case	Size	Dimension/km²	$ {Z_{{G}}} $/yuan	$ {r_G} $/s	$ {Z_{\min }} $/yuan	$ \overline Z $/yuan	$ \overline r $/s	GAP/%
1	8	10×10	42.594	191.830	61.753	62.867	10.315	32.247
2	8	8×8	36.620	44.040	35.920	39.808	10.743	8.009
3	10	10×10	57.304	438.730	64.072	67.654	11.746	15.298
4	10	8×8	41.106	701.250	39.514	41.962	11.583	2.038

Wind level	Speed range/(m/s)	Wind speed/(m/s)
Level 5	8.0−10.7	9
Level 6	10.8−13.8	12
Level 7	13.9−17.1	15
Level 8	17.2−20.7	19

[1]	Jingfeng GUO, Rui SONG, Shiwei HE. Vehicle and onboard UAV collaborative delivery route planning: considering energy function with wind and payload [J]. Journal of Systems Engineering and Electronics, 2025, 36(1): 194-208.
[2]	Jianmai SHI, Jiaming ZHANG, Hongtao LEI, Zhong LIU, Rui WANG. Joint mission and route planning of unmanned air vehicles via a learning-based heuristic [J]. Journal of Systems Engineering and Electronics, 2023, 34(1): 81-98.
[3]	Jiaming ZHANG, Zhong LIU, Jianmai SHI, Chao CHEN. Weapon configuration, allocation and route planning with time windows for multiple unmanned combat air vehicles [J]. Journal of Systems Engineering and Electronics, 2018, 29(5): 953-968.
[4]	Hao Chen, Jun Li, Ning Jing, and Jun Li. User-oriented data acquisition chain task planning algorithm for operationally responsive space satellite [J]. Journal of Systems Engineering and Electronics, 2016, 27(5): 1028-1039.
[5]	Pei Wang, Gerhard Reinelt, and Yuejin Tan. Self-adaptive large neighborhood search algorithm for parallel machine scheduling problems [J]. Journal of Systems Engineering and Electronics, 2012, 23(2): 208-215.
[6]	Guanghui Wang, Xuefeng Sun, Liping Zhang, and Chao Lv. Saturation attack based route planning and threat avoidance algorithm for cruise missiles [J]. Journal of Systems Engineering and Electronics, 2011, 22(6): 948-953.

Case	Size	Dimension/km²	Gurobi		MEALNS			GAP/%
Case	Size	Dimension/km²	$ {Z_{{G}}} $/yuan	$ {r_G} $/s	$ {Z_{\min }} $/yuan	$ \overline Z $/yuan	$ \overline r $/s	GAP/%
1	8	10×10	58.149	137.460	59.799	60.421	11.238	3.760
2	8	8×8	34.590	9.930	36.293	40.034	10.694	13.600
3	10	10×10	73.872	211.790	71.856	74.181	11.628	0.416
4	10	8×8	38.311	316.170	38.590	40.258	11.621	4.836

Case	Size	Dimension/km²	MEALNS				ALNS		GA
Case	Size	Dimension/km²	$ {\overline Z _{{\text{MEALNS}}}} $/yuan	${\overline S _{{\text{VRPTW}}}}$/%	$ {\overline S _{{\text{ini}}}} $/%	$ {\overline r _{{\text{MEALNS}}}} $/s	$ {\overline Z _{{\text{ALNS}}}} $/yuan	GAP1 /%	$ {\overline Z _{{\text{GA}}}} $/yuan	GAP2 /%
1	20	10×10	80.181	52.370	36.216	14.146	84.529	5.423	98.429	22.758
2	20	8×8	48.231	58.900	37.837	15.483	51.292	6.347	61.434	27.375
3	30	10×10	111.065	50.045	41.433	29.849	114.041	2.679	139.820	25.890
4	30	8×8	70.372	59.982	41.088	39.137	74.597	6.004	90.251	28.248
5	50	10×10	166.789	55.395	45.967	180.322	167.378	0.353	237.216	42.226
6	50	8×8	108.916	59.263	46.579	202.741	109.290	0.344	151.953	39.514