See discussions, stats, and author profiles for this publication at: https://www.researchgate.

net/publication/349620239

The Unmanned Aerial Vehicle Routing Problem with Recharging

Article · February 2021

DOI: 10.12074/202101.00070

CITATIONS READS
0 92

4 authors, including:

Jianmai Shi Zhongbao Zhou

68 PUBLICATIONS   1,014 CITATIONS   
Hunan University
92 PUBLICATIONS   1,179 CITATIONS   
SEE PROFILE
SEE PROFILE

Some of the authors of this publication are also working on these related projects:

Covering service facility View project

UAV routing View project

All content following this page was uploaded by Jianmai Shi on 26 February 2021.

The user has requested enhancement of the downloaded file.

> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 1

The Unmanned Aerial Vehicle Routing Problem

with Recharging
Huiting Mao, Jianmai Shi, Zhongbao Zhou and Long Zheng

operations. Small UAVs can fly at low altitude and hover over
Abstract—The application of Unmanned aerial vehicles (UAVs) the targets to collect accurate information, and also the
in both civilian and military domains is drawing increasing advantages in miniaturization, strong concealment, easy
attention recently. This paper investigates a new routing problem maintenance and low cost facilitate their application on
of small UAVs for information collection, where UAVs can be
recharged at platforms (ground vehicles or stations) distributed in
Intelligence, Surveillance and Reconnaissance (ISR) missions
the area. Different from the previous works on UAV routing, the [6].
UAVs are allowed to partially recharge their batteries according Due to the limited capacity of battery power, the small UAVs’
to the requirement in the following route. A mixed integer endurance range is relatively small, which is viewed as a main
nonlinear programming model is developed to formulate the barrier of their application on more ISR missions in large areas.
problem, where both the overall time for completing all targets’ Especially when the small UAV has to travel in a large area, the
observation and the number of UAVs are minimized. An improved
adaptive large neighborhood search (ALNS) algorithm with
UAV need to recharge its battery during the flying route. Many
simulated annealing criterion is designed, and a recharging researches focused on extending the endurance range of small
platform insertion heuristic is developed to determine the UAVs have been conducted, e.g. new energy supported design
recharging strategy and construct feasible solutions. To verify the and the solar power system [7], automated battery swapping
effectiveness of the proposed ALNS algorithm, a set of new and recharging [8], and efficient power allocation [9].
benchmark instances are designed based on the well-known In order to cope with the limitation of UAV's endurance, we
Solomon dataset and solved. The computational results are
compared with those obtained by the ant colony optimization and
proposed a new application mode of small UAVs, where their
variable neighborhood search, which shows that ALNS performs battery can be recharged at some platforms distributed in the
significantly better and stable. Furthermore, analysis of the area. Recently, dynamic wireless charging (DWC) technology
experimental results indicates that many advantages can be [10] is applied as a novel way of recharging electric vehicles,
obtained through introducing the recharging strategy for small and the battery of EVs can be recharged remotely while it is
UAVs. staying around the infrastructure equipped with DWC. With the
miniaturization and intelligence of wireless charging equipment,
Index Terms—Unmanned aerial vehicle, routing, heuristic,
recharging fast wireless charging devices can be installed on many stations
and ground vehicles, which make them act as recharging
platforms for small UAVs. When the battery power of small
I. INTRODUCTION UAV is insufficient, it can visit the near recharging platform to
recharge the battery and then continue to carry out the mission.
S MALL Unmanned aerial vehicles (UAVs) or drones play
an increasing role in both civilian and military areas, for
instance, agriculture monitoring, disaster relief, battlefield
In this case, the routing of UAVs should consider the decisions
on the selection of recharging platform and the recharging level
of the battery.
reconnaissance, border patrol and logistic delivery. In the
The UAV routing problem with recharging has some
civilian applications, UAVs showed great market potential
similarity to the electric vehicle routing problem (EVRP) in
which leads to significant cost savings in the last-mile package
commercial field [11]. An important characteristic of EVRP is
delivery, information collection, wild search & rescue, and
that EVs need to visit the recharging station during the route to
agriculture monitoring etc [1]. Many companies around the
extend the endurance range and complete all the delivery tasks.
world including UPS [2], DHL [3], Alibaba [4] and Amazon [5]
The main difference is that the EVs do not consume the battery
have adopted UAVs in the “last-mile-delivery” so as to reduce
power when waiting and serving customers, while small UAVs
the logistics cost and increase the distribution efficiency. Since
consume battery power when waiting and collecting
UAVs can access targets in dangerous environment without
information above the target, and the power consumption speed
losses of human lives, they are widely used in military

The research is supported by the National Natural Science Foundation of * Jianmai Shi is the corresponding author.
China (grant no. 71771215) and the Natural Science Fund for Distinguished Z. Zhou is with School of Business Administration, Hunan University,
Young Scholars of Hunan Province (2018JJ1035). Changsha, P. R. China. (e-mail: Z.B.Zhou@163.com ).
H. Mao and J. Shi are with the Science and Technology on Information L. Zheng is with Technical Service Center of Military Vocational Education,
Systems Engineering Laboratory, College of System Engineering, National National University of Defense Technology, Changsha, 410073, P. R. China.
University of Defense Technology, Changsha, 410073, P. R. China. (e-mail: (e-mail:zhenglong@nudt.edu.cn).
mht126carrie@126.com; jianmaishi@gmail.com).
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 2

is usually faster when UAV is collecting information due to optimization and planning framework considering the
additional power consumption by carried sensors. uncertainty of drone package delivery. To solve the problem,
In this paper, we investigated the UAV routing problem with they formulated a three-stage stochastic integer programming
recharging and established a mixed integer nonlinear model with a decomposition method. In the work [26], the
programming (MINLP) model to formulate the problem. An UAVs were used for dynamic wildfire tracking since the UAVs
improved adaptive large neighborhood search (ALNS) can work in hazardous fire tracking instead of humans, and a
embedded with a recharging platform insertion strategy is distributed control framework was proposed for the UAV team.
proposed to find the global better solutions for the problem. However, due to the endurance range of small UAV, the
Moreover, we designed a set of benchmark instances based on radius of its endurance range is restricted, which greatly limited
the dataset in [12], and the performance of the proposed ALNS their applications in large areas. To overcome this difficulty,
algorithm is tested. Also, the performance and efficiency of the Liu et al. [6] and Luo et al. [20] proposed a novel two-echelon
ALNS algorithm is compared with the ant colony optimization ground vehicle (GV) and UAV cooperated routing problem
(ACO) and variable neighborhood search (VNS) algorithms. (2E-GUCRP) for ISR missions, where the GV serves as the
Computational results show that the ALNS can achieve much mobile platform carrying the UAVs and recharging the UAV’s
better solutions in shorter computation time for most of the battery. In this new mode, UAV can enlarge its endurance range
instances. through multiple starting on the GVs. In recently years, the
The reminder of this paper is organized as follows: In the application of UAVs in the civilian operation is drawing
second section, related literatures are reviewed. In the third increasing attention, many commercial logistic companies used
section, the problem is illustrated and formulated as a MINLP UAVs for the ‘last-mile-delivery’ to save the cost for logistic
model. To find the feasible solution in a short time for large distribution. Chiang et al. [27] proposed a GV and UAV
instances, an improved ALNS algorithm is proposed in Section cooperated system where GVs are the mobile platform for
IV. The performance of the ALNS algorithm is tested by newly UAVs to start and land on, and both of them can deliver the
designed benchmark dataset in the 5th section. Finally, the packages during the route. To overcome the limited endurance
whole work is summarized and future directions are discussed. range of the small UAVs, Sungwoo and Ilkyeong [28]
investigated a truck-drone system, where a fixed drone station
II. LITERATURE REVIEW is built to collect drones and recharging equipments, and a truck
In this section, the two streams of relevant literatures are is employed to connect the station and the logistics distribution
reviewed, which are the UAV routing problem and the EVRP. center. Liu et al. [29] designed a Simulated Annealing
UAV routing problems have been investigated in the Military algorithm (SA) to solve the 2E-GUCRP problem for package
and Civilian application domains. Shetty et al. [13] proposed a delivery. In these studies, with the assistance of ground vehicles,
tactical routing problem of a team of UAVs to conduct the endurance range of UAV is effectively extended. However,
attacking mission based on the priorities of targets, where the UAV can only visit targets which are restricted by the path of
UAV can carry ammunition to attack different targets. GV. To extend the endurance range and release the UAV’s
Ceccarelli et al. [14] investigated a micro UAV routing problem dependence on GV, Coelho et al. [30] designed a two-level
for reconnaissance and carried on the simulation experiments routing problem model, where the UAV can be recharged at a
for finding the robust solution in the presence of randomly given recharging station to complete the tour. Li et al. [31]
perturbed wind. Mufalli et al. [15] considered the simultaneous proposed a mission planning method which considered both the
sensors selection and routing of UAVs where the loads are the routing of UAVs and recharging stations location, and assumed
influencing factors of endurance range and a new mathematical the recharging procedure takes a fixed time. Ribeiro et al. [32]
model is constructed to solve the problem. Avellar et al. [16] studied the application of UAVs for belt conveyor inspection
routed a group of UAVs for area coverage to optimize the system in the mining industry where UAVs are restricted to be
minimum coverage time, where intelligence collection can be fully charged at the recharging station. To extend the UAV
carried out in the fixed area and the specified time windows of mission coverage, Noureddine et al. [33] utilized the public land
targets are taken into consideration. Evers et al. [17] studied the transport vehicle carrying the UAV during part of its route for
routing problem of multiple UAVs for reconnaissance mission, saving the energy consumption, and the recharging power is set
taking the uncertainty in the fuel usage into account. Mahmud to a fixed parameter. Yu et al. [34] studied the UAV route
and Cho [18] investigated the UAV routing problem where planning by allowing it to visit the fixed recharging stations and
UAVs need to avoid being predicted by the enemy, and the unmanned ground vehicles (UGVs) serve as mobile stations.
Vanegas et al. [19] considered the routing problem of UAVs in The routing problem with recharging is also studied in the
the environmental uncertainty. In civilian application, UAVs EVRP. Schneider et al. [12] studied the EVRP with Time
can be used for logistics delivery [20], medical material Windows (EVRPTW), where the full fast recharging strategy is
transportation [21], efficient road detection and tracking [22] applied. They designed a metaheuristic through integrating the
and disaster relief operations [23]. Kevin et al. [24] investigated VNS algorithm with Tabu search, which is tested by instances
the vehicle routing problem for drone delivery scenarios which generated from the Solomon dataset. Ding et al. [35] studied the
minimizes both the cost and the overall delivery time EVRP where the partial recharging for electric vehicles (EVs)
considering an energy consumption model. Sawadsitang et al. is allowed and the capacity of the recharging station is taken
[25] proposed the joint ground and aerial delivery service into consideration. Keskin and Çatay [36] investigated the
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 3

EVRPTW in which EVs are also allowed partially recharged. UAV start to work and consume battery power. The
More works on EVRP can be found in the comprehensive consumption rate is related to the accuracy and duration of
review by [37]. reconnaissance at the target. At other times, the sensor is turned
From the related literature presented above, we can see that off and does not consume battery power. However, the power
it is an important research topic to investigate different consumption is still existed when the UAV is hovering above
recharging strategies for enlarging the endurance of UAV. The the target and waiting, which is the third part. In this paper,
mode of UAVs recharged by smart wireless recharging UAVs start from the base and must return to it after finishing
platforms is a new research area, and more efficient models and all the reconnaissance missions within the specified time.
algorithms are required. 2）Recharging platform
Many ground vehicles in the battlefield are equipped with
III. PROBLEM FORMULATION wireless charging devices, which can recharge the UAVs
The initial motivation of the UAV routing problem with quickly. The recharging level of the UAV’s battery is related to
recharging is from an application of reconnaissance missions in the recharging time. The location of these platforms and the
battlefield, where multiple small UAVs start from the base and base are known.
collect information at a set of targets. There are a certain 3）Targets
number of ground (combat) vehicles distributed in the A set of targets are located at different positions in the area,
battlefield, which are configured with fast wireless charging and each target can only be detected in a specified time window.
devices and act as recharging platforms of UAVs. Before the If the UAV arrives earlier than the earliest start time, the UAV
UAV’s battery powers off, it can fly to any of these platforms needs to hover over the target and wait. The time windows and
for recharging and then continue to visit the following targets. the location information of all the targets are given before the
Fig. 1 presents an illustrative example of the problem. The mission planning period.
different battery icons denote the power level of the UAV’s The objective of the problem is to minimize the total mission
battery after visiting each target. The UAV start from the unique time and the number of UAVs utilized through optimizing the
base with a fully charged battery, and after visiting target T3, flight routes for reconnaissance and recharging.
the battery power cannot support it to visit the next target T4, The notations applied in the following model formulation are
and therefore the UAV finds the nearby recharging platform P2 summarized in TABLE I:
for recharging its battery partially. After recharging, the UAV
continues its tour for visiting T4 and T5, and then flies back to TABLE I
the base. Furthermore, the UAV is allowed to visit recharging NOTATIONS USED IN THE FOLLOWING MODEL
platforms more than once. Sets
V1 set of targets;
F set of recharging platforms and their copies;
{0} the starting base;
{n + 1} the ending base;
set of targets, recharging platforms and the starting
V0 base, V 0 = V1 F 0 ;
set of targets, recharging platforms and ending base,
V n+1 V n+1 = V1 F n + 1 ;
V set of all vertices;
Parameters
dij the travel distance between node i and j ;
tij the travel time between node i and j ;
Fig. 1 An illustrative example of the UAV routing problem with recharging
g the battery charge rate;
Although the UAV routing problem with recharging is si the reconnaissance time of target i ;
initially inspired form a military application, there are also ei the earliest starting time of reconnaissance at target
i;
many potential applications in civil area, e.g. information
li the latest starting time of reconnaissance at target i ;
collection in wild areas, wild search & rescue, and agriculture
Q the capacity of the UAV’s battery;
monitoring etc. The main factors and constraints in problem are
 the weight coefficient of unit UAV;
as follows:
 the weight coefficient of total reconnaissance time,
1）UAVs and α+β=1；
Small UAV is driven by the lithium battery whose capacity cd the power consuming rate of UAV for travelling;
is limited. The battery consumption is mainly divided into three cr the power consuming rate of UAV for
parts. Firstly, UAV consumes power during the flight between reconnaissance;
cw the power consuming rate of UAV for waiting;
targets visited, and the speed of battery power consumption is
related with the flying speed and distance. Secondly, when the cuav fixed cost of a UAV;
UAV is collecting the information at a target, the sensors on the
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 4

Decision In the model, the UAV’s battery is allowed to be recharged

variables
partially, and thus only required battery power for the following
ui the starting time of reconnaissance target i , i  V1 ;
route would be recharged so as to save time and energy.
yi the remaining power level when the UAV arrives at
the node i , i  V1 ;
IV. ADAPTIVE LARGE NEIGHBORHOOD SEARCH ALGORITHM
qi the recharging quantity at recharging platform i ,
iF ; In this section, an improved adaptive large neighborhood
Yi the power level when the UAV leaves the recharging search (ALNS) algorithm embedded with a recharging platform
platform i ， i  F ; insertion heuristic is proposed. The ALNS framework was
i the waiting time of the UAV at target i , i  V1 ; firstly proposed by Pisinger and Ropke [38-40], and has been
xij 1, if a UAV travels from node i to node j ; widely used for solving the VRP [41-43] and EVRP [44-45].
otherwise 0; The basic idea of ALNS is to employ different combinations of
1, if the recharging platform i is selected for destroy and repair operators to obtain new neighborhood
zi
recharging; otherwise 0;
solutions while the utilizing probability of each operator is
adaptively updated based on its weight which is related to its
The mathematical model of the UAV routing problem is performance in the search process.
formulated as follows：
 
Min  =   cuav 
jV1 F
x0 j +     xij tij + zi qi g +  i +  si 
i , jV iF iV1 iV1 
(1)

Subject to
 xij = 1
jV n +1 ,i  j
, i V1 , (2)
 xij  1
jV n +1 ,i  j
, i  F , (3)
 xij =  x ji
iV 0 ,i  j iV n +1 ,i  j
, j V1 (4)
ui + (tij + si ) xij − l0 (1 − xij )  u j i V 0 , j V n+1 , i  j
, , (5)
ui + tij xij + gqi zi − (l0 + gQ)(1 − xij )  u j i  F , j V n+1 , i  j
, , (6)
e j  u j  l j j  V
, , (7)
0  y j  yi − (cd  dij ) xij − cr si xij − cw i  xij + Q(1 − xij )
,
i V1 , j V n+1 , i  j
, (8)
0  y j  Yi − (cd  dij ) xij + Q(1 − xij ) i  F , j V n+1 , i  j
, , (9)
Yi = zi ( yi + qi ) i  F
, , (10)
Yi  Q i  F
, , (11)
xij {0,1} i V 0 , j V n+1 , i  j
, , (12)
z j {0,1} i  F
, , (13)
qi  0 i  F
, , (14)
Objective (1) is to minimize a weighted sum of the total
number of UAVs and the overall time for completing all targets’
reconnaissance mission, where the weighted coefficients are
determined by the planner. Constraint (2) ensures each target is
visited only once, while constraint (3) handles the connectivity
between the nodes (targets and recharging platforms).
Constraint (4) guarantees that the number of outgoing arcs
equals to the number of incoming arcs at each vertex.
Constraints (5) and (6) enforce the feasibility of the time flow. In this section, a two-stage constructive heuristic is used to
Constraint (7) ensures the time windows of the targets and base. generate an initial feasible solution for the problem. First, the
Constraints (8) and (9) balance the residual battery level after a nearest neighborhood heuristic is utilized to construct a solution
visit to a target or a recharging platform and ensure that it is without regarding the battery capacity constraint. In this stage,
always non-negative. Constraint (10) determines the battery each UAV’s route satisfies the constraints on time window,
level after recharging at a recharging platform. Constraint (11) while the battery capacity may be not enough to support the
makes sure that the battery level at recharging platform is UAV to complete the flight of the route. Thus, in the second
restricted to the UAV recharging capability. Constraints (12)- stage, a recharging platform insertion heuristic is designed to
(14) define the decision variables. optimize where to recharge the UAV and how much energy
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 5

should be recharged, so as to make the route feasible. The detail distance violates the maximum battery capacity, the UAV starts
process of the insertion heuristic is described in the following from the base and travels along the route until the target that
Subsection A. cannot be visited within the left battery level. Then find the
In the search process of ALNS, any change on the targets in nearest recharging platform which it could reach by the current
a route could affect the recharging decisions. In order to battery power, and insert it after the current target. To find the
improve the search efficiency, the destroy and repair operations best inserting position of the recharging platform, all possible
in ALNS are conducted on the Non-Charged (NC) solution insertions between adjacent targets are compared. Considering
where all the recharging platforms are removed from the UAVs’ the two routes (a) and (b) in Fig. 2 as an example, route (a) and
routes. When a NC solution is generated after the destroy and route (b) are the two different feasible routes after inserting
repair operations, the recharging platform insertion heuristic is recharging platforms into the same NC route at different
employed to make it feasible. Thus, each neighborhood search insertion places. Although UAV in route (b) need to be
operation follows a rule of ‘Search Firstly, and Insertion recharged twice, the total time is a little shorter than that of
Afterwards’. The new feasible solution is accepted with the SA route (a) due to the distribution of recharging platforms. In this
criterion and the main procedure of the ALNS is shown in condition, we would choose route (b) instead of (a).
Algorithm 1.
A. Recharging platform insertion heuristic
Due to the battery capacity, the endurance range of UAV is
limited. If the total energy consumption of UAV exceeds its
battery capacity, it has to visit a recharging platform for
recharging so as to visit the following targets. A recharging
platform insertion heuristic is proposed to optimize the
recharging decisions on where and how much to recharge. The
main steps of the recharging platform insertion heuristic are
shown in Algorithm 2.
Fig. 2. An illustration for different insertion places of recharging platforms

After the insertion position of the recharging platform is

determined, the UAV can be partially recharged and the
recharging level is determined by the required battery power of
the subsequent route. After the recharging level at each
recharging platform is known, the time windows of the targets
after the recharging platform are influenced and the feasibility
should be checked again. If there are targets whose time
windows are not satisfied, they should be removed into the list
of V unvisit . As shown in Fig. 3, after inserting P4 between target
3 and target 4, the time windows of target 4 is violated due to
the long recharging time at P4. Thus, target 4 needs to be
removed from the route. For the targets in V unvisit , we iteratively
use the two-stage constructive heuristic until a feasible solution
is generated. Finally, many feasible routes will be generated
based on the same NC route after inserting recharging platforms
in different positions, and the best route will be accepted which
keeps more targets and consumes shorter time for completing
the route in the second place.

Fig. 3. Check the time windows

B. Neighborhood Structures
Given an initial feasible solution, remove all the platforms
and generate a NC solution. The neighborhood search is applied
In Algorithm 2, the insertion position of recharging platform
through different destroy and repair operators on the NC
is firstly optimized. For an NC route where the total travel
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 6

solution. Firstly, a removal operator is selected and a certain Proximity-based Target Removal In this operator, the first
number of targets are removed based on the corresponding target is randomly selected, and then the nearest target to the
removal rule. Then, an insertion operator is conducted to repair former selected one is selected. In each selection, we always
the destroyed NC solution through inserting the removed select the target nearest to the former one. According to this
targets into the current solution. Finally, the recharging strategy, a set of  targets are selected one by one and removed.
platform insertion heuristic is used to insert the recharging The working way of the operator is illustrated in Fig. 4.
platforms in the NC solution and generate a feasible solution.

1) Removal operators
The destroy mechanism of the proposed ALNS framework
consists of different removal operators. And nine removal
operators are adapted, which are grouped into two types: Route
Removal (RR) and Targets Removal (TR). In RR, a UAV route
is selected and removed. In TR, a subset of  targets are
selected and moved into the removal list  . The value of
Fig. 4. Proximity-based target removal Fig. 5. Zone removal
parameter  is determined according to the overall number of
targets nc , and here it is generated between nc and nc following Time-based Target Removal Similar to the Proximity-
the uniform distribution. All removal operators are introduced based Target Removal, this operator selects a number of targets
below. with proximate time windows and removes them from the
Random Route Removal A route is randomly chosen from current solution.
the set of all routes, in which all the targets are removed and Zone Removal The operator firstly randomly defines an area
added into the removal list  . The randomly choosing strategy with a predefined size in the Cartesian coordinate system and
can extend the search range in the solution space and increase randomly selects  targets to remove which are located in the
the probability of finding the global optimum. area. If there are less than  targets in the selected area, then
Shortest Route Removal This operator chooses the shortest reselects an area with the same size, and continue the same
route in the current solution and removes all the targets in this procedure until  nodes are removed. As Fig. 5 presents, the
selected route. The purpose of this operator is to maximize the green rectangular box represents the selected area and then
utility of the UAV and reduce the number of UAVs. randomly selects target T4, T5, T6, T7 and T9 in the area to
Random Target Removal A set of  targets are randomly remove. The pseudocode of zone removal is given in Algorithm
removed from different routes in the current solution. The goal 3.
of random selection is also to diversify and enlarge the search
range in the solution space.
Worst-Distance Target Removal The worst distance targets
are selected one by one and removed from the current solution.
Here the distance of a target means a sum of the distance from
the current target to its preceding target and the distance from
the current target to its succeeding target in the route.
Worst-Time Target Removal This operator calculates, for
each target i , the difference between reconnaissance start time
and the corresponding earliest start time ei , and then iteratively
removes the target with the largest difference. The purpose is to
avoid long wait or delayed reconnaissance starting time in order
to satisfying the time windows of more targets to the maximum
extent.
Modified Shaw Removal The idea of this operator is to
remove a set of targets according to a specified rule. This
operator is adapted from the Shaw Removal which was
proposed by Shaw (1998). The difference of general rule
between the modified and the origin Shaw Removal is that
UAVs routing do not consider the load capacity but consider
the reconnaissance time since the reconnaissance duration
effect the power consumption. Thus, operator starts by
removing a node i randomly. Let lij = −1 if the target i and
target j are both detected by the same UAV in the same route, 2) Insertion operator
otherwise lij = 1 and selects a node Five insertion operators are introduced, which are used for
j * = arg min{1dij +  2 ei − e j + 3lij +  4 | si − s j |}
inserting the removed targets back into the routes to generate a
, where 1 −  4 are
new NC solution. In the inserting process, the constraints on
the weights parameters.
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 7

time windows must be satisfied, while the battery capacity is score  i of operator i is determined by the sum of  1 ,  2 ,  3
not considered. obtained in each iteration.
Greedy Insertion The operator calculates the insertion cost
of each removed target in the best insertion position, and D. Acceptance and stopping criteria
repeatedly inserts the node with the least insertion cost in its The simulated annealing strategy is adopted as an acceptance
best feasible position of the current solution. The insertion cost criterion in the framework of ALNS algorithm. During the
here is calculated as the increased distance. searching process,  best is the global best solution,  current is the
Regret-2 Insertion Let fi represent the difference in the current solution before the iteration begins, and new is the new
objective function value after inserting target i in the current feasible solution after the iteration. Let c( ) denotes the
solution. Let i* = arg max i { fi 2 −  fi1} , where fi1 is the objective function value of solution  , a solution new is
difference after inserting target i in the best feasible insertion always accepted if c( new )  c(current ) , and accepted with
place and fi 2 is the difference after inserting target i in the
probability e−(c( )−c( ))/T . If c( new )  c(current ) , where T
new current

second-best insertion place.

denotes the temperature. In the iteration process, the
Regret-3 Insertion Similar to the Regret-2 Insertion
temperature is gradually decreased at a constant rate of hT ,
operator, fi represents the same meaning. Let
where 0  h  1 is a constant parameter. The algorithm returns
i* = arg max i { fi 3 −  fi1}
, where fi1 is the difference after the global best solution after the maximum number of iterations.
inserting the target i in the best feasible insertion place and fi 3
is the difference after inserting the target i in the third-best V. COMPUTATIONAL EXPERIMENTS
insertion place. As it is the first work to investigate UAV routing problem
Time-based Insertion The idea of this operator originates with recharging, there is no benchmark dataset exists. To
from the Greedy Insertion, the unique difference between the analyze the performance of the proposed ALNS algorithm, we
two operator is the calculation of the insertion cost. The designed a new set of benchmark instances based on the well-
operator defines the insertion cost as the change in the finish known Solomon dataset. All the algorithms were programmed
time of the route. with Visual C++, and all experiments are conducted on a laptop
Zone Insertion The operator selects the removed targets by with Intel Core i5 processor (3GHz) and 8GB RAM. The data
the criterion of the Time-based Insertion operator above. The set in the following subsections are presented in the
unique difference is that it only considers the routes in a specific supplement[53].
zone, instead of investigating all routes in the current destroyed
solution. A. Experiment design
A set of 56 large instances are designed, and there are 100
C. Adaptive adjustment of the operators’ weight targets and 21 recharging platforms in each instance. The
The selection of the removal and insertion operators is distribution of targets and recharging platforms is referred the
governed by a roulette-wheel mechanism. If we have k data set in [12], which is designed based on the Solomon dataset.
operators with weights wi , i {1,2,...,k} and we choose the These instances can be divided into 3 classes according to the
operator j with probability geographical distribution of targets: Random distribution (R),
wj clustered distribution (C) and a mixture of both (RC). Further,
p select
j k
(15) the instances with narrow time windows are classified in group
w
i =1
i R1, C1 and RC1, while the ones with wide time windows are
At the beginning, all removal or insertion operators have the classified in group R2, C2 and RC2. The detail information for
same probability. Thus, in this paper, there are nine removal all nodes in the 56 instances can be found in the supplement.
operators and five insertion operators, the initial weight of each The battery capacity of UAV is a constant and is set as 150.
removal operator and insertion operator is set to 1/9 and 1/5, Depending on different conditions, the battery power
respectively. During the searching process, they are updates as consumption rate is set to 1 when UAV is flying en-route, and
follows: is set to 0.5 when it is hovering above targets and waiting. When
wit +1 = wit (1 − r ) + r   i i (16) the UAV is collecting information on a target, it consumes more
battery power than any time during the travelling and the energy
where wit +1 is the wight of operator i in iteration round t + 1 , consumption rate is set to 2. Besides, the average velocity of
r is the roulette-wheel parameter,  i is the score of the UAV is set to 1 and the inverse recharging rate is set to 0.33
operator i and i is the number of times it was used during the which means that a complete recharging from zero battery level
requires 50 minutes.
last NW iterations. If a new global best solution is obtained, the
score  i of the operator i is increased by  1 . If the new B. Algorithm performance
feasible solution is not a global best solution but better than the To analyze the performance of ALNS, it is compared with two
current solution, the score  i is increased by  2 . If the solution widely used metaheuristics for routing problems, which are the
ant colony optimization (ACO) algorithm and the variable
is worse than the current solution but can be accepted within a
neighborhood search (VNS) algorithm. ACO is firstly proposed
certain probability, the score  i is increased by  3 . Thus, the
by Dorigo et al. [46] and were widely used to solve the VRP
and EVRP [47-49]. VNS performs local search on large
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 8

neighborhoods and its effectiveness is also verified by former The 23 R type instances can be further divided into two
works [12, 50-51]. In this experiment, we applied the classes, noted as R1 and R2. Targets in R1 instances have
framework of ACO and traditional VNS from the work [52]. narrow time windows, while targets in R2 instances have wide
All the 56 instances are solved by ALNS, ACO and VNS time windows. The computational results in TABLE II show
respectively. In TABLE II-IV, the objective function value of that the ALNS algorithm can achieve better solutions than other
best solution in 10 runs are reported. Furthermore, we calculate algorithms for all the R instances. Furthermore, the value of
the relative gaps between ALNS and ACO ( 1 % )for the objective function for all R1 instances are reduced by an
objective function value, where average of 19.81% to ACO and an average of 18.27% to VNS,
1 %= ( Obj. ALNS − Obj. ACO ) Obj. ALNS , and the gaps between while the value of objective function for all R2 instances the
instances are reduced by an average of 24.58% to ACO and an
ALNS and VNS ( 2 % ), where
average of 24.99% to VNS.
2 %= ( Obj. ALNS − Obj.VNS) Obj. ALNS . Thus, a negative value of There are also two classes of instances in the C type and RC
1 % /  2 % means relative improvement obtained by ALNS. type data set respectively, which are noted as C1/RC1 and
C2/RC2. TABLE III reports all the computational results of C
TABLE II type instances, and TABLE IV reports the results of RC type
THE RESULTS OF R TYPE INSTANCES UNDER DIFFERENT METHODS instances. It can be found that the ALNS algorithm performs
Objective
Inst. 1 % 2 % better than ACO and VNS for all C and RC instances. Generally
ALNS ACO VNS
R101 2268.48 2956.03 2926.82 -23.59 -22.49 speaking, the results for C2 and RC2 instances are also better
R102 2027.17 2755.44 2631.63 -26.43 -22.97 compared to those of C1 and RC1 respectively. Therefore, it
R103 1780.75 2302.98 2318.19 -22.68 -23.18 shows that the ALNS algorithm works better for instances with
R104 1557.14 1969.71 1916.42 -20.95 -18.75 wide time window, and the ALNS algorithm can efficiently
R105 1823.43 2318.40 2250.37 -21.35 -18.97
R106 1789.65 2216.38 2292.68 -19.25 -21.94 enlarge the search space in the situation with loose constraints
R107 1663.56 2184.44 2143.02 -23.85 -22.37 on time window.
R108 1580.92 1793.02 1795.81 -11.83 -11.97
R109 1745.17 2115.57 2132.72 -17.51 -18.17 TABLE IV
R110 1559.72 1949.06 1863.35 -19.98 -16.30 THE RESULTS OF RC TYPE INSTANCES UNDER DIFFERENT METHODS
R111 1598.49 2010.06 1933.80 -20.48 -17.34 Objective
Inst. 1 % 2 %
R112 1522.88 1687.59 1599.38 -9.76 -4.78 ALNS ACO VNS
Average -19.81 -18.27 RC101 2333.83 2856.69 2869.70 -18.30 -18.67
R201 864.59 1155.83 1296.84 -25.20 -33.33 RC102 2233.72 2778.83 2662.54 -19.62 -16.11
R202 781.24 1209.12 1272.52 -35.39 -38.61 RC103 2055.01 2507.59 2396.11 -18.05 -14.24
R203 741.97 1107.75 1121.97 -33.02 -33.87 RC104 1787.31 2032.21 1969.86 -12.05 -9.27
R204 702.30 906.33 985.42 -22.51 -28.73 RC105 2185.81 2605.71 2594.42 -16.12 -15.75
R205 800.17 968.27 1003.73 -17.36 -20.28 RC106 2047.81 2400.05 2372.10 -14.68 -13.67
R206 757.01 1108.67 1004.70 -31.72 -24.65 RC107 1861.90 2132.97 2019.12 -12.71 -7.79
R207 715.33 942.56 968.66 -24.11 -26.15 RC108 1734.64 1970.73 1787.89 -11.98 -2.98
R208 706.93 837.72 844.08 -15.61 -16.25 Average -15.44 -12.31
R209 750.02 981.09 929.40 -23.55 -19.30 RC201 557.43 865.43 788.91 -35.59 -29.34
R210 749.06 1085.46 976.31 -30.99 -23.28 RC202 475.83 827.74 789.15 -42.52 -39.70
R211 755.92 848.93 844.52 -10.96 -10.49 RC203 430.69 679.95 736.78 -36.66 -41.54
Average -24.58 -24.99 RC204 379.19 500.88 558.89 -24.30 -32.15
RC205 459.21 722.68 739.63 -36.46 -37.91
TABLE III RC206 429.98 601.60 598.37 -28.53 -28.14
THE RESULTS OF C TYPE INSTANCES UNDER DIFFERENT METHODS RC207 400.72 580.31 560.59 -30.95 -28.52
RC208 338.62 449.39 419.52 -24.65 -19.28
Objective 1 % 2 %
Inst. Average -32.46 -32.07
ALNS ACO VNS
C101 1402.02 1621.00 1746.16 -13.51 -19.71
C102 1350.14 1844.74 1675.53 -26.81 -19.42 The results verify that the performance of ALNS has
C103 1277.20 1744.82 1670.86 -26.80 -23.56 significant superiority for solving the URP-RC problem. The
C104 1192.49 1450.37 1306.90 -17.78 -8.75
C105 1275.09 1415.71 1524.82 -9.93 -16.38 ALNS obtained the best solution in all 56 instances. As for the
C106 1262.51 1413.80 1408.24 -10.70 -10.35 fixed cost of vehicles, the ALNS always reached the minimum
C107 1196.36 1357.22 1423.80 -11.85 -15.97 which contributes to the best solution in a great measure.
C108 1198.96 1267.97 1404.42 -5.44 -14.63
C109 1138.29 1219.00 1334.79 -6.62 -14.72
Average -14.38 -15.94 C. Analysis on the impact of the recharging strategy
C201 381.28 468.33 602.79 -18.59 -36.75
C202 382.64 472.10 548.81 -18.95 -30.28 An important characteristic of the investigated problem is
C203 377.88 483.49 563.14 -21.84 -32.90 allowing the UAV to be recharged in the route, which is
C204 360.83 397.35 437.16 -9.19 -17.46 expected to expand the endurance range of UAV and improve
C205 371.66 388.31 484.85 -4.29 -23.35
C206 363.27 386.11 401.39 -5.92 -9.50 the routing efficiency with lower cost. To analyze the impact of
C207 365.47 393.93 468.23 -7.22 -21.95 recharging strategy, the ALNS algorithm is used to solve all the
C208 365.39 389.16 398.28 -6.11 -8.26 instances with recharging (URP-RC) and without recharging
Average -11.51 -22.56 (URP). We analyzed the number of UAVs (m), total mission
completing time (TT) and the objective function value (Obj)
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 9

respectively. ALNS is run 10 times for each instance, and the C207 5 247.16 373.58 10 74.36 537.18
best solutions for all instances are reported in TABLE V-VII. C208 5 241.82 370.91 9 71.72 485.86
From the computational results, it can be seen that the causes the objective function value is smaller in general. And
number of UAVs for URP-RC is much less than that for URP. the results of RC type instances in TABLE VII shows that URP-
For the R1 and RC1 type instances, the total completing time RC performs better for each aspect of the objective than URP.
for URP-RC is also less than that for URP, while for the other From TABLE V-VII, we can see that URP-RC obtained
instances, the URP mode can complete the task in much less better solution with much lesser number of UAVs and smaller
time. That is because the UAVs in URP-RC have to visit objective function values for all the instances compared to URP.
multiple recharging platforms in the routes for most of the Therefore, the recharging strategy does improve the efficiency
situations, which consume much additional time. Usually, the and reduce the cost of UAVs.
UVAs are critical resources in both military and civil
application, and its cost are relatively higher than the routing
cost. The number of UAVs is greatly reduced in URP-RC which D. Sensitivity analysis on the battery capacity
The battery capacity plays a key role in the UAV routing
TABLE V problem. In order to analyze the impact of different battery
THE RESULTS OF R TYPE INSTANCES BETWEEN URP-RC AND URP
capacities, we vary the value of battery capacity from 120 to
URP-RC URP
Inst.
m TT Obj m TT Obj 300 while the value of other parameters keep unchanged. The
R101 20 2757.78 2378.89 35 2831.96 3165.98 number of UAVs (m) and the overall mission time (TT) are
R102 19 2364.90 2132.45 32 2461.78 2830.89 calculated under different battery capacities respectively by
R103 17 2139.18 1919.59 30 2146.56 2573.28 ALNS. Also, we compared the impact of battery capacities
R104 16 1877.20 1738.60 29 1934.60 2417.30 between URP-RC and URP. The results for R101 instance are
R105 17 2038.62 1869.31 31 2276.36 2688.18 reported in Fig. 6. The experimental results on other instances
R106 17 1931.54 1815.77 29 2142.44 2521.22 are similar, and the parallel analysis on the other instances are
R107 16 1969.50 1784.75 29 2035.20 2467.60 omitted here.
TABLE VII
R108 15 1921.74 1710.87 28 1919.48 2359.74
THE RESULTS OF RC TYPE INSTANCES BETWEEN URP-RC AND URP
R109 16 1940.00 1770.00 29 2044.30 2472.15 URP-RC URP
R110 15 1863.86 1681.93 28 1937.58 2368.79 Inst.
m TT Obj m TT Obj
R111 16 1916.68 1758.34 29 1984.68 2442.34 RC101 20 3086.26 2801.74 41 3646.58 3873.29
R112 15 1677.68 1588.84 28 1869.66 2334.83 RC102 19 2836.84 2559.44 39 3410.76 3655.38
R201 9 904.74 902.37 19 663.34 1281.67 RC103 18 2492.08 2536.54 37 3171.60 3435.80
R202 9 821.40 860.70 18 469.38 1134.69 RC104 15 2203.28 2231.74 37 3075.14 3387.57
R203 8 736.68 768.34 18 383.98 1091.99 RC105 20 2675.84 2665.50 38 3318.66 3559.33
R204 8 671.36 735.68 17 370.60 1035.30 RC106 19 2527.52 2527.76 38 3259.80 3529.90
R205 9 725.58 812.79 17 393.14 1046.57 RC107 16 2318.62 2150.62 37 3171.94 3435.97
R206 8 714.76 757.38 18 374.66 1087.33 RC108 15 2154.04 2056.74 37 3100.46 3400.23
R207 8 678.68 739.34 17 352.08 1026.04 RC201 5 755.06 660.02 8 586.24 693.12
R208 8 637.84 718.92 17 326.10 1013.05 RC202 4 635.46 581.48 8 463.18 631.59
R209 8 700.04 750.02 17 346.58 1023.29 RC203 4 501.52 507.82 8 405.58 602.79
R210 9 757.94 828.97 17 363.70 1031.85 RC204 4 397.42 363.34 7 302.74 501.37
R211 8 711.84 755.92 17 347.08 1023.54 RC205 5 554.12 517.18 8 420.44 610.22
RC206 4 528.28 484.68 7 410.08 555.04
TABLE VI RC207 4 467.96 456.04 7 300.22 500.11
THE RESULTS OF C TYPE INSTANCES BETWEEN URP-RC AND URP
RC208 4 383.68 338.62 6 248.86 424.43
URP-RC URP
Inst.
m TT Obj m TT Obj
C101 16 1265.20 1432.60 34 590.26 1995.13 From Fig. 6(a), it can be observed that the number of UAVs
C102 16 1185.14 1392.57 34 498.62 1949.31 decreases sharply with the increase of battery capacity in URP
C103 15 1196.60 1348.30 33 469.40 1884.70 and comparatively decreases gently in URP-RC. When the
C104 15 1032.52 1266.26 33 460.42 1880.21 battery capacity is 120, the deviation of the number of UAVs
C105 15 1089.52 1294.76 34 504.06 1952.03 between URP-RC and URP reaches 30 which verifies that
C106 16 1049.12 1324.56 34 509.76 1954.88 URP-RC can significantly reduce the fixed cost of UAVs
C107 15 1100.66 1300.33 34 468.62 1934.31 especially for the small UAVs with short endurance range. With
C108 14 1013.96 1206.98 34 481.62 1940.81 the increase of battery capacity, the deviation between URP-RC
C109 14 1040.26 1220.13 33 460.00 1880.00 and URP becomes small and reaches 0 when the capacity is 300.
C201 6 285.66 442.83 10 126.58 563.29 That is because the UAVs can complete the task without
C202 6 233.06 416.53 10 97.76 548.88 recharging when the battery capacity is large enough. Similarly,
C203 5 255.76 377.88 10 78.18 539.09 the results in Fig.6(b) showed that the overall mission time
C204 5 257.16 378.58 10 77.50 538.75 decreases as the battery capacity increases, and becomes the
C205 5 271.46 385.73 10 91.24 545.62 same for both URP-RC and URP when the battery capacity is
C206 5 241.04 370.52 10 70.80 535.40 large enough. Since the targets have specific time windows in
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 10

both URP-RC and URP, when the UAV arrives earlier than the meaningful and valuable extension in the model development.
earliest reconnaissance start time, it has to wait for some time. Another meaningful extension is studying new algorithms to
Therefore, the relatively deviation of the overall mission time solve this problem more efficiently and quickly.
between URP-RC and URP is smaller than that for the number
of UAVs in Fig. 6(a). REFERENCES
The results in Fig. 6 confirm that the battery capacity does [1] Otto A, Agatz N, Campbell J, et al. Optimization approaches for civil
has an important impact on the routing of UAVs, and indicate applications of unmanned aerial vehicles (UAVs) or aerial drones: A
that recharging is efficient to improve small UAVs’ routing survey[J]. Networks, 2018, 72(4):411-458.
[2] Kastrenakes, J. (2017). UPS has a delivery truck that can launch a drone.
performance when the battery capacity is not large enough.
http://www.theverage.com/2017/2/21/14691062/ups-drone-delivery-truck-
test-completed-video/. [Online; accessed 19-July-2018].
[3] Aufgebauer, K. (2016). The future has landed, thanks to delivery drones.
http://goglobal.dhl-usa.com/blog/shipping/the-future-has-landed-thanks-
to-delivery-drones/. [Online; accessed 20-July-2018].
[4] Lin. J. (2018). Meet China’s growing fleet of automated delivery drones.
http://www.popsci.com/china-drone-deliveries/. [Online; accessed 19-
August-2018].
[5] Johnson. L. (2017). 9 things you need to know about the Amazon Prime Air
drone delivery service.
http://www.digitalspy.com/tech/feature/a820748/amazon-prime-air-drone-
delivery-service/. [Online; last accessed 18-Nov-2020].
[6] Yao Liu, Zhihao Luo, Zhong Liu, Jianmai Shi, Guangquan Chen.
Cooperative Routing Problem for Ground Vehicle and Unmanned Aerial
Vehicle: The Application on Intelligence, Surveillance and
(a) Reconnaissance Missions[J]. IEEE Access, 2019, 7 (1): 63504-63518.
[7] Scott Morton, Ruben D'Sa, Nikolaos Papanikolopoulos. Solar powered
UAV: Design and experiments[C]// IEEE/RSJ International Conference on
Intelligent Robots & Systems. IEEE, 2015.
[8] Toksoz T, Redding J, Michini M, et al. Automated Battery Swap and
Recharge to Enable Persistent UAV Missions[C]// AIAA
Infotech@Aerospace Conference. 2011.
[9] Hosseini S, Dai R, Mesbahi M. Optimal path planning and power allocation
for a long endurance solar-powered UAV[C]// American Control
Conference (ACC), IEEE, 2013, pp:2588–2593.
[10] Illhoe H,Young J J , Young D K , et al. System Optimization for Dynamic
Wireless Charging Electric Vehicles Operating in a Multiple-Route
Environment[J]. IEEE Transactions on Intelligent Transportation Systems,
2018,19(6): 1709-1726.
(b) [11] Erdelić, Tomislav; Carić, Tonči. A Survey on the Electric Vehicle Routing
Fig. 6. The results for R101 instance under different battery capacities. (a) The Problem: Variants and Solution Approaches[J]. Journal of Advanced
number of UAVs under different battery capacities. (b) Total mission time Transportation, 2019(54):1-48.
under different battery capacities. [12] Schneider, M., Stenger, A., & Goeke, D. The electric vehicle-routing
problem with time windows and recharging stations[J]. Transportation
Science, 48(4) (2014) 500-520.
[13] Shetty V K, Sudit M, Nagi R. Priority-based assignment and routing of a
VI. CONCLUSION fleet of unmanned combat aerial vehicles [J]. Computers & Operations
Research, 2008, 35 (6): 1813-1828.
To promote the utilization of small UAVs, we investigated a [14] Ceccarelli N, Enright J J, Frazzoli E, et al. Micro UAV Path Planning for
UAV routing problem with recharging to extend the endurance Reconnaissance in Wind[C]// American Control Conference. IEEE, 2007.
range of small UAVs, where the recharging platforms are fixed [15] Mufalli F, Batta R, Nagi R. Simultaneous sensor selection and routing of
unmanned aerial vehicles for complex mission plans [J]. Computers &
and UAV can fly to these recharging platforms to recharge its Operations Research, 2012, 39 (11): 2787-2799.
battery in the route. To solve this problem, a mixed integer [16] Avellar Gustavo, Pereira Guilherme, Pimenta Luciano et. al. Multi-UAV
nonlinear programming model is established and an improved Routing for Area Coverage and Remote Sensing with Minimum Time[J].
ALNS algorithm embedded with a recharging platform Sensors, 2015, 15(11):27783-27803.
[17] Evers L, Dollevoet T, Barros A I, Monsuur H. Robust UAV mission
insertion heuristic is designed. Furthermore, we create a set of planning [J]. Annals of Operations Research, 2014, 222 (1): 293-315.
benchmark instances based on the well-known Solomon dataset [18] Mahmud I, Cho Y Z. Detection Avoidance and Priority-Aware Target
and the experiment results showed that the proposed ALNS Tracking for UAV Group Reconnaissance Operations[J]. Journal of
performs significantly better than the ACO and VNS algorithm. intelligent & robotic systems: Theory & applications, 2018, 92: pp. 381-
392.
Besides, the advantage of recharging strategy is verified and the [19] Vanegas, F.; Gonzalez, F. Enabling uav navigation with sensor and
sensitivity analysis on the battery capacity shows that the environmental uncertainty in cluttered and gps-denied environments[J].
battery capacity effect both the number of UAVs and the Sensors 2016, 16(5):666.
objective values in URP-RC and URP. [20] Zhihao Luo, Zhong Liu, Jianmai Shi. A two-echelon cooperated routing
problem for a ground vehicle and its carried unmanned aerial vehicle[J].
To extend the proposed study, future research directions can Sensors, 2017, 17(5):1144.
be taken into consideration for the problem in a dynamic [21] J.E. Scott and C.H. Scott. Models for drone delivery of medications and
environment where the recharging platforms are mobile and has other healthcare items. International Journal of Healthcare Information
time windows as well. In many practical applications, the Systems and Informatics (IJHISI),2018, 13(3):20-34.
[22] Zhou H, Kong H, Wei L, et al. Efficient Road Detection and Tracking for
recharging platforms are mobile, such as public transport, Unmanned Aerial Vehicle[J]. IEEE Transactions on Intelligent
which has recharging capacity and time window. Thus, it is a Transportation Systems, 2015, 16(1):297-309.
> REPLACE THIS LINE WITH YOUR PAPER IDENTIFICATION NUMBER (DOUBLE-CLICK HERE TO EDIT) < 11

[23] B. Rabta, C. Wankmuller, and G. Reiner. A drone fleet model for last-mile [45] Hiermann, Gerhard, Puchinger, Jakob, Ropke, Stefan, et al. The Electric
distribution in disaster relief operations[J]. International Journal of Fleet Size and Mix Vehicle Routing Problem with Time Windows and
Disaster Risk Reduction, 2018, 28:107-112. Recharging Stations[J]. European Journal of Operational Research, 2016,
[24] K. Dorling, J. Heinrichs, G. G. Messier and S. Magierowski, "Vehicle 252 (3):995-1018.
Routing Problems for Drone Delivery[J]," IEEE Transactions on Systems, [46] Dorigo, M., Maniezzo, V., Colorni, A., Ant system: optimization by a
Man, and Cybernetics: Systems, vol. 47, no. 1, pp. 70-85, Jan. 2017. DOI: colony of cooperating agents. IEEE Transactions on Systems, Mans, and
10.1109/TSMC.2016.2582745 Cybernetics,1996, vol. 1, no. 26, pp. 29–41.
[25] Sawadsitang S, Niyato D, Tan P S, et al. Joint Ground and Aerial Package [47] Yu B, Yang Z Z, Yao B. An improved ant colony optimization for vehicle
Delivery Services: A Stochastic Optimization Approach[J]. IEEE routing problem[J]. European Journal of Operational Research,2009, vol.
Transactions on Intelligent Transportation Systems, 2018, PP:1-14. 196, no. 1, pp. 171-176.
[26] Pham H X, La H M, Feil-Seifer D, et al. A Distributed Control Framework [48] Ding Q, Hu X, Sun L, et al. An improved ant colony optimization and its
of Multiple Unmanned Aerial Vehicles for Dynamic Wildfire Tracking[J]. application to vehicle routing problem with time windows[J].
IEEE Transactions on Systems Man & Cybernetics Systems, 2018:1-12. Neurocomputing, 2012, vol. 98, pp. 101-107.
[27] Chiang W C, Li Y, Shang J, et al. Impact of drone delivery on sustainability [49] Zhang S, Gajpal Y, Appadoo S S, et al. Electric vehicle routing problem
and cost: Realizing the UAV potential through vehicle routing with recharging stations for minimizing energy consumption[J].
optimization[J]. Applied Energy, 2019, 242(PT.1-1284):1164-1175. International journal of production economics, 2018, 203:404-413.
[28] S. Kim and I. Moon, "Traveling Salesman Problem With a Drone [50] D. C. Paraskevopoulos, P. P. Repoussis,C. D. Tarantilis,G. Ioannou,G. P.
Station[J]," IEEE Transactions on Systems, Man, and Cybernetics: Prastacos. A reactive variable neighborhood tabu search for the
Systems, vol. 49, no. 1, pp. 42-52, Jan. 2019. DOI: heterogeneous fleet vehicle routing problem with time windows[J].
10.1109/TSMC.2018.2867496 Journal of Heuristics,2008, vol.14, no. 5, pp. 425-455.
[29] Yao. Liu, Zhong. Liu, Jinamai. Shi, G. Wu and W. Pedrycz, "Two-Echelon [51] M. Bruglieri, F. Pezzell, O. Pisacane, and S. Suraci, ‘‘A variable
Routing Problem for Parcel Delivery by Cooperated Truck and Drone[J]," neighborhood search branching for the electric vehicle routing problem
in IEEE Transactions on Systems, Man, and Cybernetics: Systems, doi: with time windows[J],’’ Electron. Notes Discrete Math., 2015, vol. 47, no.
10.1109/TSMC.2020.2968839. 15, pp. 221–228.
[30] Coelho B N, Coelho V N, Coelho I M, et al. A multi-objective green UAV [52] Huiting Mao, Jianmai Shi, Yuzhen Zhou, et al. The electric vehicle routing
routing problem[J]. Computers & Operations Research, 2017,88:306-315. problem with time windows and multiple recharging options[J]. IEEE
[31] Li B, Patankar S, Moridian B, et al., "Planning Large-Scale Search and Access, 2020, PP (99):1-1.
Rescue using Team of UAVs and Charging Stations*", 2018 IEEE [53] Huiting Mao, Jianmai Shi. Experimental data set for UAV routing with
International Symposium on Safety, Security, and Rescue Robotics recharging.
(SSRR), Philadelphia, PA, 2018, pp. 1-8. https://www.researchgate.net/publication/346048168_Experimental_data
[32] Ribeiro R G, Junior J R C, Cota L P, et al. Unmanned Aerial Vehicle _set_for_UAV_routing_with_recharging
Location Routing Problem with Charging Stations for Belt Conveyor
Inspection System in the Mining Industry[J]. IEEE Transactions on
Intelligent Transportation Systems, 2019, PP (99):1-10.
[33] N. Lasla, H. Ghazzai, H. Menouar and Y. Massoud, "Exploiting Land
Transport to Improve the UAV's Performances for Longer Mission
Coverage in Smart Cities," 2019 IEEE 89th Vehicular Technology
Conference (VTC2019-Spring), Kuala Lumpur, Malaysia, 2019, pp. 1-7.
[34] Yu K, Budhiraja A K, Tokekar P. Algorithms for Routing of Unmanned
Aerial Vehicles with Mobile Recharging Stations[J]. Proceedings-IEEE
International Conference on Robotics and Automation, 2018: 5720-5725.
[35] Ding N, Batta R, Kwon C. Conflict-free electric vehicle routing problem
with capacitated charging stations and partial recharge[M]//Technical
Report. Department of Industrial and Systems Engineering, University at
Buffalo, US and Department of Industrial and Management Systems
Engineering, University of South Florida, US, 2015.
[36] Keskin M, Çatay B. Partial recharge strategies for the electric vehicle
routing problem with time windows. Transportation Research Part C,
2016,65:111-127.
[37] Erdelić, Tomislav; Carić, Tonči. A Survey on the Electric Vehicle Routing
Problem: Variants and Solution Approaches[J]. Journal of Advanced
Transportation, 2019.
[38] Pisinger, D., Ropke, S., 2005. A General Heuristic for Vehicle Routing
Problems. Technical Report, DIKU - Department of Computer Science,
University of Copenhagen.
http://www.diku.dk/hjemmesider/ansatte/sropke/Papers/GeneralVRP_Te
chRep.pdf (04.11.12).
[39] Pisinger, D., Ropke, S., 2007. A general heuristic for vehicle routing
problems[J]. Computers& Operations Research 34 (8), 2403–2435.
[40] Ropke, S., Pisinger, D., 2006a. An adaptive large neighborhood search
heuristic for the pickup and delivery problem with time windows[J].
Transportation Science 40(4), 455–472.
[41] Demir E, Bekta T, Laporte G. An adaptive large neighborhood search
heuristic for the Pollution-Routing Problem[J]. European Journal of
Operational Research, 2012, 223(2):346-359.
[42] Emeç Uğur, Çatay, Bülent, Bozkaya Burcin. An Adaptive Large
Neighborhood Search for an E-grocery Delivery Routing Problem[J].
Computers & Operations Research, 2015: S0305054815002683.
[43] Sacramento D, Pisinger D, Ropke S. An adaptive large neighborhood
search metaheuristic for the vehicle routing problem with drones[J].
Transportation Research, 2019, 102(MAY):289-315.
[44] Keskin M, Laporte G, Çatay B. Electric vehicle routing problem with time-
dependent waiting times at recharging stations[J]. Computers &
Operations Research, 2019, 107: 77-94.

View publication stats