Vehicle and onboard UAV collaborative delivery route planning: considering energy function with wind and payload

doi:10.23919/JSEE.2025.000020

Journal of Systems Engineering and Electronics ›› 2025, Vol. 36 ›› Issue (1): 194-208.doi: 10.23919/JSEE.2025.000020

• SYSTEMS ENGINEERING • Previous Articles

Vehicle and onboard UAV collaborative delivery route planning: considering energy function with wind and payload

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-03-01 Online:2025-02-18 Published:2025-03-18
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 from the Faculty of Architecture, Civil and Transportation Engineering, Beijing University of Technology, Beijing, China, in 2021. He is currently a Ph.D. candidate in Beijing Jiaotong University, Beijing, China. His research interests are intelligent transportation system, 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, transportation, 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 National Natural Science Foundation of China (62076023).

Abstract

Abstract:

The rapid evolution of unmanned aerial vehicle (UAV) technology and autonomous capabilities has positioned UAV as promising last-mile delivery means. Vehicle and onboard UAV collaborative delivery is introduced as a novel delivery mode. Spatiotemporal collaboration, along with energy consumption with payload and wind conditions play important roles in delivery route planning. This paper introduces the traveling salesman problem with time window and onboard UAV (TSP-TWOUAV) and emphasizes the consideration of real-world scenarios, focusing on time collaboration and energy consumption with wind and payload. To address this, a mixed integer linear programming (MILP) model is formulated to minimize the energy consumption costs of vehicle and UAV. Furthermore, an adaptive large neighborhood search (ALNS) algorithm is applied to identify high-quality solutions efficiently. The effectiveness of the proposed model and algorithm is validated through numerical tests on real geographic instances and sensitivity analysis of key parameters is conducted.

Key words: vehicle and onboard unmanned aerial vehicle (UAV) collaborative delivery, energy consumption function, route planning, mixed integer linear programming model, adaptive large neighborhood search (ALNS) algorithm

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.

Figures/Tables 16

Fig 1

Table 1

Fig 2

Fig 3

Table 2

Fig 4

Fig 5

Table 3

Table 4

Table 5

Table 6

Fig 6

Table 7

Fig 7

Fig 8

Table 8

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	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
3	DING Y D, WAN J Q, LIN W, et al Coordinated last-mile deliveries with trucks and drones: a comparative study of operational modes. Journal of the Air Transport Research Society, 2024, 3, 100025.
4	CHANG C W, LO L Y, CHEUNG H C, et al Proactive guidance for accurate UAV landing on a dynamic platform: a visual-inertial approach. Sensors, 2022, 22 (1): 404. doi: 10.3390/s22010404
5	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
6	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
7	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.
8	WANG X Y, POIKONEN S, GOLDEN B The vehicle routing problem with drones: several worst-case results. Optimization Letters, 2017, 11, 679- 697. doi: 10.1007/s11590-016-1035-3
9	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
10	LAN B. Traveling salesman problem with time windows and drones (TSPTWD). Ames: Iowa State University, 2020.
11	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
12	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
13	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
14	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
15	MULUMBA T, NAJY W, DIABAT A The drone-assisted pickup and delivery problem: an adaptive large neighborhood search metaheuristic. Computers & Operations Research, 2024, 161, 106435.
16	BERGHAUS M, LAMBERTY S, EHLERS J, et al Vehicle trajectory dataset from drone videos including off-ramp and congested traffic–analysis of data quality, traffic flow, and accident risk. Communications in Transportation Research, 2024, 4, 100133. doi: 10.1016/j.commtr.2024.100133
17	HU D, LI S, DU J, et al Automating building damage reconnaissance to optimize drone mission planning for disaster response. Journal of Computing in Civil Engineering, 2023, 37 (3): 04023006. doi: 10.1061/(ASCE)CP.1943-5487.0001061
18	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
19	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
20	PENG Y, LI Y J Optimization of truck-drone collaborative distribution route considering the impact of epidemic situation. China Journal of Highway and Transport, 2020, 33 (11): 73- 82.
21	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.
22	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, 2019: 173−184.
23	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
24	MENG S S, GUO X P Logistics optimization in truck-drone joint pick-up and delivery. Journal of Systems & Management, 2022, 31 (3): 555- 566.
25	THIBBOTUWAWA A, BOCEWICZ G, RADZKI G, et al UAV mission planning resistant to weather uncertainty. Sensors, 2020, 20 (2): 515. doi: 10.3390/s20020515
26	GENDREAU M, POTVIN J Y. Handbook of metaheuristics. New York: Springer, 2019.
27	MA W J, ZENG L, AN K Dynamic vehicle routing problem for flexible buses considering stochastic requests. Transportation Research Part C: Emerging Technologies, 2023, 148, 104030. doi: 10.1016/j.trc.2023.104030
28	YU X P, HU Y S, WU P The consistent vehicle routing problem considering driver equity and flexible route consistency. Computers & Industrial Engineering, 2024, 187, 109803.
29	JARUMANEEROJ P, SAKULSOM N An adaptive large neighborhood search for the multiple-day music rehearsal problems. Computers & Industrial Engineering, 2021, 157, 107279.
30	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.

Reference	Model						Methodology
Reference	V	U	Obj	TW	Collaboration	UAV endurance	Methodology
Murray et al. [5]	1	1	CT	×	Soft	Time	Re-assign heuristic
Ha et al. [6]	1	1	DCDW	×	Soft	Time	GRASP
Tu et al. [7]	1	N	DCD	×	Soft	Distance	GRASP+ALNS (SA)
Murray et al. [19]	1	N	CT	×	Soft	Time	Three-phrase heuristic
Peng et al. [20]	1	1	CT	×	Soft	ETP	HNS
Lan et al. [10]	1	1	CT	√	Soft	Time	LP-based metaheuristics
Schermer et al. [9]	M	N	Makespan	×	Soft	Distance	Matheuristic method
Sacramento et al. [2]	M	1	DCD	×	Soft	Time	ALNS (SA)
Kuo et al. [12]	M	1	DCD	√	Soft	Time	VNS
Jeong et al. [13]	1	1	CT	×	Soft	EP	TPCSA
Cheng et al. [23]	0	N	DCE	√	×	EP	Branch-and-cut
Meng et al. [24]	M	1	DCD	×	Hard	EP	ISA
This paper	1	1	DCE	√	Hard	EPW	ALNS (TA)

Symbol	Description
$N$	Set of all nodes $N = \left\{ {0,1, \cdots ,n} \right\}$
$C$	Set of customer nodes $C = \left\{ {1,2, \cdots ,n} \right\}$
${N_0}$	Set of departing nodes ${N_0} = \left\{ {0,1,2, \cdots ,n} \right\}$
${N_ + }$	Set of arriving nodes ${N_ + } = \left\{ {1,2, \cdots ,n,n + 1} \right\}$
$A$	Set of directed links for vehicle $A = \left\{ {(i,j)\|i,j \in N,i \ne j} \right\}$
$ S $	Set of UAV feasible sorties $ S = \{ \left\langle {i,j,k} \right\rangle \|i\in N_0,j \in {C},k \in {N_ + },i \ne j \ne k\} $
${\mathrm{TL}}$	Time spent on UAV launch
$ {\mathrm{TR}} $	Time spent on UAV recovery
$ S{e^d} $	Service time spent by UAV
$ S{e^v} $	Service time spent by vehicle
$ {\tau '_{ij}} $	Travel time of UAV from node i to j
$ {\tau _{ij}} $	Travel time of vehicle from node i to j
$ {c_{ijk}} $	Cost coefficient of UAV sortie
$ {c_{ij}} $	Cost coefficient of vehicle travel distance
$ {E_m} $	UAV’s maximum battery volume
${e_{ijk}}$	Energy consumption of UAV sortie $ < i,j,k > $
${d_{ij}}$	Travel distance of vehicle from node i to j
$ {o_i} $	Opening time for serving customer i
$ {e_i} $	Closing time for serving customer i
$ M $	A sufficiently large number, $ M = {e_0} $
$ {x_{ij}} $	Binary decision variable indicating whether vehicle travels from node i to j
$ {y_{ijk}} $	Binary decision variable indicating whether the sortie $ < i,j,k > $ is in the vehicle’s route
${t_i}$	Continuous variable indicating the vehicle’s departure time from node i
${t'_i}$	Continuous variable indicating the UAV’s departure time from node i
$ {u_i} $	Non-negative integer variable indicating the position of the visit i in the vehicle’s route
$ {r_{ij}} $	Binary decision variable indicating whether node i is visited before node j in the vehicle’s route

Score	Description
$ {{\mathrm{sc}}_1} = 30 $	The new solution is accepted as global best solution
$ {{\mathrm{sc}}_2} = 18 $	The new solution results in a solution which is accepted with a cost better than the cost of the current solution
$ {{\mathrm{sc}}_3} = 12 $	The new solution results in a solution which is accepted with a cost worse than the cost of the current solution
$ {{\mathrm{sc}}_4} = 0 $	The new solution is rejected

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

No.	Size	Dims/km²	Gurobi		ALNS
No.	Size	Dims/km²	${Z^*}$/RMB	${r^*}$/s	$ {Z_{\min }} $/RMB	$ \bar Z $/RMB	GAP/%	$ \bar r $/s
1	6	8×8	23.096	1.709	23.096	24.232	4.920	0.242
2	6	5×5	10.589	1.879	9.803	10.961	3.514	0.206
3	8	8×8	25.434	17.311	25.735	28.497	12.045	0.518
4	8	5×5	16.098	26.977	14.723	15.019	−6.703	0.541
5	10	8×8	28.398	68.757	28.684	29.812	4.980	0.960
6	10	5×5	11.665	64.095	10.909	11.470	−1.675	0.786

Vehicle and onboard UAV collaborative delivery route planning: considering energy function with wind and payload

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

Share this article

Figures/Tables 16

References 30

Related Articles 3

Recommended Articles

Metrics

Comments

No.	Size	Dim/km²	ALNS						GA
No.	Size	Dim/km²	$ {\bar Z _{{\mathrm{ALNS}}}} $/RMB	${\bar Z _{{\mathrm{tsp}}}}$/RMB	${\bar Z _{{\mathrm{ini}}}}$/RMB	${\bar S _{{\mathrm{tsp}}}}$	$ {\bar S _{{\mathrm{ini}}}} $	Avg. time/s	$ {\bar Z _{{\mathrm{GA}}}} $/RMB	GAP/%
1	20	8×8	25.297	93.587	77.900	0.728	0.674	9.563	42.870	−40.992
2	20	5×5	19.199	57.266	52.790	0.664	0.634	8.680	35.042	−45.212
3	30	8×8	25.380	122.982	92.006	0.793	0.723	45.815	54.362	−53.313
4	30	5×5	18.098	74.970	59.389	0.758	0.689	48.035	22.025	−17.828
5	50	8×8	47.132	239.305	187.480	0.802	0.745	672.018	94.623	−50.189
6	50	5×5	29.006	128.419	112.544	0.774	0.741	488.961	54.298	−46.580

Condition	I	II	III
Type	Soft	Fresh	Strong
Wind level	Level 4	Level 5	Level 6
Speed range/(m/s)	5.5−7.9	8.0−10.7	10.8−13.8
Wind speed/(m/s)	6	10	12
Wind direction/(°)	150	150	150

[1]	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.
[2]	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.
[3]	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.

No.	Size	Dims/km²	Gurobi		ALNS
No.	Size	Dims/km²	${Z^*}$/RMB	${r^*}$/s	$ {Z_{\min }} $/RMB	$ \bar Z $/RMB	GAP/%	$ \bar r $/s
1	6	8×8	21.193	1.809	20.767	22.100	4.277	0.201
2	6	5×5	10.115	1.949	9.170	10.718	5.961	0.180
3	8	8×8	25.648	12.502	25.414	26.482	3.250	0.626
4	8	5×5	12.719	13.191	10.171	12.058	−5.197	0.624
5	10	8×8	26.916	42.799	26.703	29.667	10.219	0.893
6	10	5×5	11.332	59.916	9.992	10.753	−5.108	0.831