# Coordinating drones with mothership vehicles: The mothership and multiple
drones routing problem with Graphs

Lavinia Amorosi<EMAIL_ADDRESS>Justo Puerto<EMAIL_ADDRESS>Carlos
Valverde<EMAIL_ADDRESS>Department of Statistical Sciences, Sapienza
University of Rome, Italy  Department of Statistical Sciences and Operational
Research, University of Seville, Spain

###### Abstract

This paper considers the optimization problems that arise to coordinate a
tandem between a mothership vehicle and a fleet of drones. Each drone can be
launched from the mothership to perform an operation. After completing the
operations the drones return to the mothership to recharge batteries and to be
ready for a new operation. Operations consist on (partially) visiting graphs
with given lengths to deliver some service or to perform some
surveillance/inspection activity. The goal is to minimize the overall weighted
distance traveled by the mothership while satisfying some requirements in
terms of percentages of visits to the target graphs. In all cases, we develop
exact formulations resorting to mixed integer second order cone programs that
are compared on a testbed of instances to assess their performance. We also
develop a matheuristic algorithm that provides reasonable solutions.
Computational experiments show the usefulness of our methods in different
scenarios.

###### keywords:

Arc Routing Problems , Networks , Drones , Conic Programming

##  1 Introduction

In recent years the grow of the potential business opportunities related to
the use of drone technology has motivated the appearance of an interesting
body of methodological literature on optimizing of the use of such technology.
We can find examples of that in many different sectors, like telecommunication
where drones can be adopted in place of traditional infrastructures to provide
connectivity (see for example [1], [2], [3], [4], and [5]), or to temporary
deal with the damages caused by a disaster ([6]), deliveries (see for example
[7] , [8], [9] and [10]), also in emergency contexts ([11]), inspection ([12])
and others. The reader is referred to the recent surveys [13] and [14] for
further details.
Among the different aspects that can be considered we want to focus, for its
relationship to the development in this paper, to the design, coordination and
optimization of the combined routes of drones with a base vehicle. After the
initial paper [15] by Murray and Chu, where a combined model of truck and
drone is considered, the work of Ulmer and Thomas [16] also considers another
model where trucks and drones are dispatched as order are placed and analyze
the effect of different policies for either the truck or the drone. Other
papers, as for instance, [17], [18] and [19], have also considered hybrid
truck-and-drone models in order to mitigate the limited delivery range of
drones. Poikonen and Golden, in [20], advance on the coordination problem
considering the Mothership and drone routing problem where these two vehicles
are used to design a route that visits a number of points allowing the truck
to launch and recover the drone in a continuous space. More recently in [9]
the authors consider the $k$-Multi-Visit drone routing problem where a truck
that acts as a mobile depot only allowed to stop in a predefined set of
points, launches drones that can deliver more than one package to their
designated destination points. Many of these papers make the assumptions that
the set of allowable locations to launch/retrieve a drone are fixed and known
a priori, the operations performed by the drone consist of delivering to a
single point and the coordination is between a truck and a single drone. These
assumptions may be appropriate in some frameworks but in other cases it may be
better to relax them.
In particular, only few papers in literature focus on drones operations
consisting in traversing graphs rather than visiting single points. Campbell
et al. [21] introduce the Drone Rural Postman Problem (DRPP). The authors
present a solution algorithm based on the approximation of curves in the plane
by polygonal chains and that iteratively increases the number of points in the
polygonal chain where the UAV can enter or leave. Thus, they solve the problem
as a discrete optimization problem trying to better define the curve by
increasing the number of points. The authors consider also the case in which
the drone has limited capacity and thus it cannot serve all the lines. To deal
with this latter case, they assume to have a fleet of drones and the problem
consists in finding a set of routes, each of limited length.
In [22] this problem has been defined as the Length Constrained K-drones Rural
Postman Problem, a continuous optimization problem where a fleet of
homogeneous drones have to jointly service (traverse) a set of (curved or
straight) lines of a network. The authors design and implement a branch-and-
cut algorithm for its solution and a matheuristic algorithm capable of
providing good solutions for large scale instances of the problem.
Scanning the literature of arc routing problems involving hybrid systems
consisting in one vehicle and one or multiple drones, the number of
contributions is rather limited.
In [23] the authors study the path planning problem of a system composed of a
ground robot and one drone in precision agriculture and solve it by applying
orienteering algorithms. Also the paper [24] studies the problem of paths
planning for systems consisting in a carrier vehicle and a carried one to
visit a set of target points and assuming that the carrier vehicle moves in
the continuous space.
To the best of our knowledge, only the paper [25], deals with the coordination
of a mothership with one drone to visit targets represented by graphs. The
authors made different assumptions on the route followed by the mothership: it
can move on a continuous framework (the Euclidean plane), ii) on a connected
piecewise linear polygonal chain or iii) on a general graph. In all cases, the
authors develop exact formulations resorting to mixed integer second order
cone programs and propose a matheuristic algorithm capable to obtain high
quality solutions in short computing time.
In this paper we deal with an extension of the problem studied in [25] for
which we propose a novel truck-and-multi-drones coordination model. We
consider a system where a base vehicle (mothership) can stop anywhere in a
continuous space and has to support the launch/retrieve of a number of drones
that must visit graphs. The contribution on the existing literature is to
extend the coordination beyond a single drone to the more cumbersome case of
several drones and the operations to traversing graphs rather than visiting
single points. In particular, we focus on a synchronous version in which every
drone is launched and retrieved in the same stage. We present a mathematical
programming formulation, valid inequalities to reinforce it and a matheuristic
to deal with large instances of this problem. Moreover, we discuss and show
how to extend further the former case to the asynchronous situation where one
assumes that the mothership can retrieve one drone in a different stage from
the one in which it has been launched.
The work is structured as follows: Section 2 provides a detailed description
of the problem under consideration and develops a valid mixed integer non
linear programming formulations for it. Section 3 provides some valid
inequalities that strengthen the formulation and also derives upper and lower
bounds on the big-M constants introduced in the proposed formulation. Section
4 presents details of the matheuristic algorithm designed to handle large
instances. In Section 5 we report the results obtained testing the formulation
and the matheuristic algorithm on different classes of planar graphs in order
to assess its effectiveness. Finally, Section 6 concludes the paper.

##  2 Problem description and valid formulation

###  2.1 Problem description

In the All terrain Mothership and Multiple Drones Routing Problem with Graphs
(AMMDRPG), there is one mothership (the base vehicle) and a fleet of
homogeneous drones $\mathcal{D}$ that have to coordinate among them and with
the mothership to perform a number of operations consisting in visiting given
percentages of the length of a set of graphs $\mathcal{G}$. The mothership and
the drones travel at constant velocities $v_{M}$ and $v_{D}$, respectively.
Moreover, it is assumed that each drone has a limited flying autonomy
(endurance) $N^{d}$, so that once it is launched it must complete the
operation and return back to the base vehicle to recharge batteries before the
time limit. The base vehicle can move freely on a continuous space and starts
at a known location, denoted $orig$ where the mothership and the fleet of
drones are ready to depart. Once all the operations are finished the
mothership and the drones must return together to a final location, called
$dest$. The set of target graphs $\mathcal{G}$ to be visited permits to model
real situations like monitoring and inspection activities on portions of
networks (roads or wires) where traditional vehicles cannot arrive, due to,
for example, the presence of narrow streets, or because of a natural disaster
or a terrorist attack that caused damages on the network. In all these cases,
the inspection or monitoring of the drone consists in traversing edges of the
network to perform a reconnaissance activity. For this reason we model the
targets, to be visited by the drone, as graphs. The operation of visiting a
graph can be of two different types: 1) traversing a given percentage of the
length of each one of its edges or 2) visiting a percentage of the total
length of the network.

In this problem, it is assumed that each graph must be visited by one drone:
once the drone assigned to the operation enters the graph, it has to complete
the entire operation of traversing this target before to be able to leave the
graph to return to the base. Moreover, at each stage the drones must be
launched from the mothership at the same point (the launching points have to
be determined) and they also must be retrieved at the same point (the
rendezvous points also have to be determined). However, this does not mean
that the mothership and all drones must arrive at a rendezvous location at the
same time: the fastest arriving vehicle may wait for the others at the
rendezvous location. Note also that every drone of the fleet does not have to
be launched from the current base vehicle location in all the stages because
of the capacity constraint. In addition, it is supposed that the cost induced
by the drones’ trips are negligible as compared to those incurred by the base
vehicle. Therefore, the goal is to minimize the overall distance traveled by
the mothership. In spite of that, the reader may note that from a theoretical
point of view the extension to include in the objective function also the
distances traveled by the drones is straightforward and does not increase the
complexity of the models and formulations. The goal of the AMMDRPG is to find
the launching and rendezvous points of the fleet of drones $\mathcal{D}$
satisfying the visit requirements for the graphs in $\mathcal{G}$ and
minimizing the length of the path traveled by the mothership.

###  2.2 Mixed Integer Non Linear Programming Formulations

In this section we present a MINLP mathematical programming formulation for
the AMMDRPGthat can be used to solve medium size instances of this problem. As
mentioned in Section 2, we assume that the mothership is allowed to move
freely in a continuous space that for the sake of presentation we assume to be
$\mathbb{R}^{2}$. Here, distances are measured by the Euclidean norm,
$\|\cdot\|_{2}$, although this assumption can be extended to any $l_{p}$ norm,
$1\leq p\leq\infty$ (see [26]). In the following, we introduce the parameters
or input data that formally describe the problem and that are summarized in
Table 1.

Problem Parameters
---
$orig$: coordinates of the point defining the origin of the mothership path
(or tour).
$dest$: coordinates of the point defining the destination of the mothership
path (or tour).
$\mathcal{G}$: set of the target graphs.
$g=(V_{g},E_{g})$: set of nodes and edges of each target graph
$g\in\mathcal{G}$.
$\mathcal{L}(e_{g})$: length of edge $e$ of graph $g\in\mathcal{G}$.
$\mathcal{L}(g)=\sum_{e_{g}\in E_{g}}\mathcal{L}(e_{g})$: total length of the
graph $g\in\mathcal{G}$.
$B^{e_{g}},C^{e_{g}}$: coordinates of the endpoints of edge $e$ of graph
$g\in\mathcal{G}$.
$\alpha^{e_{g}}$: percentage of edge $e$ of graph $g\in\mathcal{G}$ that must
be visited.
$\alpha^{g}$: percentage of graph $g\in\mathcal{G}$ that must be visited.
$v_{D}$: drone speed.
$v_{M}$: mothership speed.
$N^{d}$: drone endurance.
$M$: big-M constant.
Table 1: Nomenclature for AMMDRPG Binary and Integer Decision Variables
---
$\mu^{e_{g}}\in\\{0,1\\}\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$): equal
to 1 if edge $e$ of graph $g$ (or a portion of it) is visited by the drone,
and 0 otherwise.
$\text{entry}^{e_{g}}\in\\{0,1\\}\>\>\forall e_{g}\in E_{g}$
($g\in\mathcal{G}$): auxiliary binary variable used for linearizing
expressions.
$u^{e_{g}td}\in\\{0,1\\}\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$)
$\>\forall t\in\mathcal{T}\>\forall d\in\mathcal{D}$: equal to 1 if the drone
$d$ enters in graph $g$ by the edge $e_{g}$ at stage $t$,
0 otherwise.
$z^{e_{g}e^{{}^{\prime}}_{g}}\in\\{0,1\\}\>\>\forall e_{g},e_{g}^{\prime}\in
E_{g}$ ($g\in\mathcal{G}$): equal to 1 if the drone goes from $e_{g}$ to
$e^{{}^{\prime}}_{g}$, 0 otherwise.
$v^{e_{g}td}\in\\{0,1\\}\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$)
$\>\forall t\in\mathcal{T}\>\forall d\in\mathcal{D}$: equal to 1 if the drone
$d$ exits from graph $g$ by $e_{g}$ at stage $t$,
0 otherwise.
$s^{e_{g}},\;\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$): integer non negative
variable representing the order of visit of the edge $e$ of graph $g$.
Continuous Decision Variables
$\rho^{e_{g}}\in[0,1]$ and $\lambda^{e_{g}}\in[0,1]\>\>\forall e_{g}\in E_{g}$
($g\in\mathcal{G}$): defining the entry and exit points on $e_{g}$.
$\nu_{\text{min}}^{e_{g}}$ and $\nu_{\text{max}}^{e_{g}}\in[0,1]\forall
e_{g}\in E_{g}$ ($g\in\mathcal{G}$): auxiliary variables used for linearizing
expressions.
$x_{L}^{t}\>\>\forall t\in\mathcal{T}$: coordinates representing the point
where the mothership launches the drone at stage $t$.
$x_{R}^{t}\>\>\forall t\in\mathcal{T}$: coordinates representing the point
where the mothership retrieves the drone at stage $t$.
$R^{e_{g}}\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$): coordinates
representing the entry point on edge $e$ of graph $g$.
$L^{e_{g}}\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G})$: coordinates
representing the exit point on edge $e$ of graph $g$.
$d_{L}^{e_{g}td}\geq 0,\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$)
$\forall t\in\mathcal{T}\>\forall d\in\mathcal{D}$: representing the distance
travelled by the drone $d$ from the launching
point $x_{L}^{t}$ on the mothership at stage $t$ to the first visiting point
$R^{e_{g}}$ on $e_{g}$.
$d^{e_{g}e^{\prime}_{g}}\geq 0,\>\>\forall e_{g},e^{\prime}_{g}\in E_{g}$
($g\in\mathcal{G}$): representing the distance travelled by the drone from the
launching
point $L^{e_{g}}$ on $e_{g}$ to the rendezvous point $R^{e^{\prime}_{g}}$ on
$e^{\prime}_{g}$.
$d^{e_{g}}\geq 0,\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$): representing
the distance travelled by the drone from the rendezvous
point $R^{e_{g}}$ to the launching point $L^{e_{g}}$ on $e_{g}$.
$d_{R}^{e_{g}td}\geq 0\>\>\forall e_{g}\in E_{g}$ ($g\in\mathcal{G}$) $\forall
t\in\mathcal{T}\>\forall d\in\mathcal{D}$: representing the distance travelled
by the drone $d$ from the last
visiting point $L^{e_{g}}$ on $e_{g}$ to the rendezvous point $x_{R}^{t}$ on
the mothership at stage $t$.
$d_{LR}^{t}\geq 0\>\>\forall t\in\mathcal{T}$: representing the distance
travelled by the mothership from the
launching point $x_{L}^{t}$ to the rendezvous point $x_{R}^{t}$ at stage $t$.
$d_{RL}^{t}\geq 0\>\>\forall t\in\mathcal{T}$: representing the distance
travelled by the mothership from the
rendezvous point $x_{R}^{t}$ at stage $t$ to the launching point
$x_{L}^{(t+1)}$ at the stage $t+1$.
Table 2: Decision Variables for AMMDRPG

To represent the movement of the drone within a graph $g\in\mathcal{G}$, we
proceed to introduce some notation related to $g$. Let $g=(V_{g},E_{g})$ be a
graph in $\mathcal{G}$ whose total length is denoted by $\mathcal{L}(g)$.
Here, $V_{g}$ denotes the set of nodes and $E_{g}$ denotes the set of edges
connecting pairs of nodes. Let $e_{g}$ be the edge $e$ of the graph $g\in G$
and let $\mathcal{L}(e_{g})$ be its length. Each edge $e_{g}$ is parameterized
by its endpoints $B^{e_{g}}=(B^{e_{g}}(x_{1}),B^{e_{g}}(x_{2}))$ and
$C^{e_{g}}=(C^{e_{g}}(x_{1}),C^{e_{g}}(x_{2}))$ and we can compute its length
$\mathcal{L}(e_{g})=\|C^{e_{g}}-B^{e_{g}}\|$.

As discussed in Section 2, we consider two modes of visit to the target graphs
$g\in\mathcal{G}$:

  * 1.

Visiting a percentage $\alpha^{e_{g}}$ of each edge $e_{g}$ which can be
modeled by using the following constraints:

$|\lambda^{e_{g}}-\rho^{e_{g}}|\mu^{e_{g}}\geq\alpha^{e_{g}},\quad\forall
e_{g}\in E_{g}.$ ($\alpha$-E)

  * 2.

Visiting a percentage $\alpha^{g}$ of the total length of the graph:

$\sum_{e_{g}\in
E_{g}}\mu^{e_{g}}|\lambda^{e_{g}}-\rho^{e_{g}}|\mathcal{L}(e_{g})\geq\alpha^{g}\mathcal{L}(g).$
($\alpha$-G)

In both cases the corresponding constraints are nonlinear. In order to
linearize them, we need to introduce a binary variable $\text{entry}^{e_{g}}$
that determines the traveling direction on the edge $e_{g}$ as well as the
definition of the parameter values $\nu_{\text{min}}^{e_{g}}$ and
$\nu_{\text{max}}^{e_{g}}$ of the access and exit points to that segment.
Then, for each edge $e_{g}$, the absolute value constraint ($\alpha$-E) can be
represented by:

$\mu^{e_{g}}|\rho^{e_{g}}-\lambda^{e_{g}}|\geq\alpha^{e_{g}}\Longleftrightarrow\left\\{\begin{array}[]{ccl}\rho^{e_{g}}-\lambda^{e_{g}}&=&\nu_{\text{max}}^{e_{g}}-\nu_{\text{min}}^{e_{g}},\\\
\nu_{\text{max}}^{e_{g}}&\leq&1-{\text{entry}^{e_{g}}},\\\
\nu_{\text{min}}^{e_{g}}&\leq&{\text{entry}^{e_{g}}},\\\
\mu^{e_{g}}(\nu_{\text{max}}^{e_{g}}+\nu_{\text{min}}^{e_{g}})&\geq&\alpha^{e_{g}}.\\\
\end{array}\right.$ ($\alpha$-E)

The linearization of ($\alpha$-G) is similar to ($\alpha$-E) by changing the
last inequality in ($\alpha$-E) by

$\sum_{e_{g}\in
E_{g}}\mu^{e_{g}}(\nu_{\text{max}}^{e_{g}}+\nu_{\text{min}}^{e_{g}})\mathcal{L}(e_{g})\geq\alpha^{g}\mathcal{L}(g).$
($\alpha$-G)

To model this problem, we use stages identified with the order in which the
different elements in the problem are visited. Let us denote by $\mathcal{T}$
the set of stages/tasks that the mothership and the fleet of drones have to
carry out. These stages are visits to the different graphs in $\mathcal{G}$
with the required constraints. A stage $t\in\mathcal{T}$ is referred to as the
operation in which the mothership launches some drones from a taking-off
location, denoted by $x_{L}^{t}$ and later it takes them back on a rendezvous
location $x_{R}^{t}$. Here, it is important to realize that both locations
$x_{L}^{t}$ and $x_{R}^{t}$ must be determined in the continuous space where
the mothership is assumed to move. Note that $|\mathcal{T}|\leq|\mathcal{G}|$,
since it is assumed that, for each stage, at least one drone must be launched.
For each stage $t\in\mathcal{T}$, each one of the drones launched from the
mothership must follow a path starting from and returning to the mothership,
while visiting the required edges of $g$. According to the notation introduced
above, we write this generic path in the following form:

$x_{L}^{t}\rightarrow R^{e_{g}}\rightarrow
L^{e_{g}}\rightarrow\ldots\rightarrow R^{e^{\prime}_{g}}\rightarrow
L^{e^{\prime}_{g}}\rightarrow\ldots\rightarrow
R^{e^{\prime\prime}_{g}}\rightarrow x_{R}^{t}\rightarrow x_{L}^{t+1}.$

Figure 1: Example illustrating the meaning of the launching (L) and retrieving
(R) points.

Figure 1 shows an example of the notation over a configuration with four
target graphs that have four nodes and four edges. Here, it is supposed that
the number of available drones is two. The mothership begins at its starting
point $orig$. Then, it moves to $x_{L}^{1}$ where two drones are launched to
visit two graphs. There, each drone follows a route (represented by the orange
and green paths) that ensures the coverage of $50\%$ of each edge of the
graph. The red dots on the visited graphs are the intermediate points
$R^{e_{g}}$ and $L^{e_{g}}$ used by the drones in their visit to the edges of
the different graphs. After finishing the visit of the first two graphs the
drones return to the point $x_{R}^{1}$ from where they are launched again to
visit the remaining two graphs. Once these graphs are visited, the drones
return to the mothership at the rendezvous point $x_{R}^{2}$ and then the
mothership ends its route at the destination point $dest$.

To include the definition of these paths in our mathematical programming
formulation we need to make decisions to choose:

  * 1.

The optimal assignment of drones for visiting graphs in a given stage $t$.

  * 2.

The optimal order to visit the edges of each graph in its corresponding stage.

We model the route that the drone follows by using the binary variables
$u^{e_{g}td}$, $z^{e_{g}e^{\prime}_{g}}$ and $v^{e_{g}td}$ defined in Table 2.

$\displaystyle\sum_{g\in\mathcal{G}}\sum_{e_{g}\in
E_{g}}\sum_{d\in\mathcal{D}}u^{e_{g}td}$ $\displaystyle\leq 1,$
$\displaystyle\forall t\in\mathcal{T},$ (1)
$\displaystyle\sum_{g\in\mathcal{G}}\sum_{e_{g}\in
E_{g}}\sum_{d\in\mathcal{D}}v^{e_{g}td}$ $\displaystyle\leq 1,$
$\displaystyle\forall t\in\mathcal{T},$ (2) $\displaystyle\sum_{e_{g}\in
E_{g}}\sum_{t\in\mathcal{T}}\sum_{d\in\mathcal{D}}u^{e_{g}td}$
$\displaystyle=1,$ $\displaystyle\forall g\in\mathcal{G},$ (3)
$\displaystyle\sum_{e_{g}\in
E_{g}}\sum_{t\in\mathcal{T}}\sum_{d\in\mathcal{D}}v^{e_{g}td}$
$\displaystyle=1,$ $\displaystyle\forall g\in\mathcal{G},$ (4)
$\displaystyle\sum_{e_{g}\in E_{g}}u^{e_{g}td}$ $\displaystyle=\sum_{e_{g}\in
E_{g}}v^{e_{g}td},$ $\displaystyle\forall g\in\mathcal{G},\forall
t\in\mathcal{T},\forall d\in\mathcal{D},$ (5)
$\displaystyle\sum_{t\in\mathcal{T}}\sum_{d\in\mathcal{D}}u^{e_{g}td}+\sum_{e^{\prime}_{g}\in
E_{g}}z_{g}^{e^{\prime}_{g}e_{g}}$ $\displaystyle=\mu^{e_{g}},$
$\displaystyle\forall e_{g}\in E_{g}:g\in\mathcal{G},$ (6)
$\displaystyle\sum_{t\in\mathcal{T}}\sum_{d\in\mathcal{D}}v^{e_{g}td}+\sum_{e^{\prime}_{g}\in
E_{g}}z_{g}^{e_{g}e^{\prime}_{g}}$ $\displaystyle=\mu^{e_{g}},$
$\displaystyle\forall e_{g}\in E_{g}:g\in\mathcal{G}.$ (7)

Inequalities (1) and (2) state that for each stage at most one drone can be
launched and retrieved for performing an operation. Constraints (3) and (4)
assure that each graph is visited at some stage $t$ by some drone $d$.
Equations (5) ensure that the operation of entering and exiting from the graph
$g$ occurs in the same stage $t$ and is done by the same drone $d$.
Constraints (6) state that if edge $e$ of graph $g$ is visited by the drone
$d$, one of two alternative situations must occur: either $e$ is the first
edge of graph $g$ visited by the drone $d$ at stage $t$, or edge $e$ is
visited by the drone $d$ after visiting another edge $e^{\prime}$ of graph
$g$. Similarly, constraints (7) state that if edge $e$ of graph $g$ is visited
by the drone $d$, either $e$ is the last edge of graph $g$ visited by the
drone at stage $t$, or the drone $d$ must move to another edge $e^{\prime}$ of
graph $g$ after visiting edge $e$.

#### Elimination of subtours

In order to represent actual routes of the drones over the target graphs,
subtours cannot be allowed. Note that subtours would represent fake operations
since they would allow free jumps of the drone between different routes at no
time. To prevent the existence of subtours within each graph $g\in\mathcal{G}$
that the drone must visit, one can include, among others, either the compact
formulation that uses the Miller-Tucker-Zemlin constraints (MTZ) or the
subtour elimination constraints (SEC).
For the MTZ formulation, we use the continuous variables $s^{e_{g}}$, defined
in Table 2, that state the order to visit the edge $e_{g}$ and set the
following constraints for each $g\in\mathcal{G}$:

$\displaystyle s^{e_{g}}-s^{e^{\prime}_{g}}+|E_{g}|z^{e_{g}e^{\prime}_{g}}$
$\displaystyle\leq|E_{g}|-1,$ $\displaystyle\quad\forall e_{g}\neq
e_{g}^{\prime}\in E_{g},$ (MTZ1) $\displaystyle 0$ $\displaystyle\leq
s^{e_{g}}\leq|E_{g}|-1,$ $\displaystyle\quad\forall e_{g}\in E_{g}.$ (MTZ2)

Alternatively, we can also use the family of subtour elimination constraints
for each $g\in\mathcal{G}$:

$\sum_{e_{g},e^{\prime}_{g}\in
S}z_{g}^{e_{g}e^{\prime}_{g}}\leq|S|-1,\quad\forall S\subset E_{g}.$ (SEC)

Since there is an exponential number of SEC constraints, when we implement
this formulation we need to perform a row generation procedure including
constraints whenever they are required by a separation oracle. To find SEC
inequalities, as usual, we search for disconnected components in the current
solution. Among them, we choose the shortest subtour found in the solution to
be added as a lazy constraint to the model.

The goal of the AMMDRPG is to find a feasible solution that minimizes the
total distance traveled by the mothership. To account for the different
distances among the decision variables of the model we need to set the
continuous variables $d_{L}^{e_{g}td}$, $d^{e_{g}}$,
$d^{e_{g}e^{\prime}_{g}}$, $d_{R}^{e_{g}td}$, $d_{RL}^{t}$ and $d_{LR}^{t}$,
defined in Table 2. This can be done by means of the following constraints:

$\displaystyle\|x_{L}^{t}-R^{e_{g}}\|$ $\displaystyle\leq d_{L}^{e_{g}td},$
$\displaystyle\quad\forall e_{g}:g\in\mathcal{G},\forall
t\in\mathcal{T},\forall d\in\mathcal{D},$ (DIST1-t)
$\displaystyle\|R^{e_{g}}-L^{e_{g}}\|$ $\displaystyle\leq d^{e_{g}},$
$\displaystyle\quad\forall e_{g}:g\in\mathcal{G},$ (DIST2-t)
$\displaystyle\|R^{e_{g}}-L^{e^{\prime}_{g}}\|$ $\displaystyle\leq
d^{e_{g}e^{\prime}_{g}},$ $\displaystyle\quad\forall e_{g}\neq
e_{g}^{\prime}\in E_{g}:g\in\mathcal{G},$ (DIST3-t)
$\displaystyle\|L^{e_{g}}-x_{R}^{t}\|$ $\displaystyle\leq d_{R}^{e_{g}td},$
$\displaystyle\quad\forall e_{g}:g\in\mathcal{G},\forall t\in T,\forall
d\in\mathcal{D},$ (DIST4-t) $\displaystyle\|x_{R}^{t}-x_{L}^{t+1}\|$
$\displaystyle\leq d_{RL}^{t},$ $\displaystyle\quad\forall t\in\mathcal{T},$
(DIST5-t) $\displaystyle\|x_{L}^{t}-x_{R}^{t}\|$ $\displaystyle\leq
d_{LR}^{t},$ $\displaystyle\quad\forall t\in\mathcal{T}.$ (DIST6-t)

The coordination between the drones and the mothership must ensure that the
time spent by the drone $d$ to visit the graph $g$ at the stage $t$ is less
than or equal to the time that the mothership needs to move from the launching
point to the retrieving point during the stage $t$. To this end, we need to
define the following coordination constraint for each graph $g\in\mathcal{G}$,
stage $t\in\mathcal{T}$ and drone $d\in\mathcal{D}$:

$\frac{1}{v_{D}}\left(\sum_{e_{g}\in
E_{g}}u^{e_{g}td}d_{L}^{e_{g}td}+\sum_{e_{g},e^{\prime}_{g}\in
E_{g}}z^{e_{g}e^{\prime}_{g}}d^{e_{g}e^{\prime}_{g}}+\sum_{e_{g}\in
E_{g}}\mu^{e_{g}}d^{e_{g}}+\sum_{e_{g}\in
E_{g}}v^{e_{g}td}d_{R}^{e_{g}td}\right)\leq\frac{d_{LR}^{t}}{v_{M}}+M(1-\sum_{e_{g}\in
E_{g}}u^{e_{g}td}).$ (DCW)

Eventually, we have to impose that the tour of the mothership, together with
the drones, starts from the origin $orig$ and ends at the destination $dest$.
To this end, we define the following constraints:

$\displaystyle x_{L}^{0}$ $\displaystyle=orig,$ (ORIG1) $\displaystyle
x_{R}^{0}$ $\displaystyle=orig,$ (ORIG2) $\displaystyle
x_{L}^{|\mathcal{G}|+1}$ $\displaystyle=dest,$ (DEST1) $\displaystyle
x_{R}^{|\mathcal{G}|+1}$ $\displaystyle=dest.$ (DEST2)

Note that, since the objective function of this problem minimizes the right-
hand-side of (DCW), this constraint will become an equality and we can model
the time capacity constraint for a particular stage $t\in\mathcal{T}$ by
limiting the distance traveled by the mothership for this task $t$:

$d_{LR}^{t}\leq N^{d}.$ (Capacity)

Therefore, putting together all the constraints introduced before, the
following formulation minimizes the overall distance traveled by the
mothership ensuring the coordination with the fleet of drones while
guaranteeing the required coverage of the target graphs. |s| ∑_t∈T (d_RL^t +
d_LR^t) (1)-(7) (MTZ1)-(MTZ2)  or  (SEC) ($\alpha$-E)  or  ($\alpha$-G) (DCW)
(Capacity) (DIST1-t)-(DIST6-t) (ORIG1)-(DEST2).

The objective function accounts for the distances traveled by the mothership.
Constraints (1)-(7) models the route followed by the drone $d\in\mathcal{D}$,
(MTZ1) - (MTZ2)  or  (SEC) ensure that the displacement of the drone
$d\in\mathcal{D}$ assigned to the target graph $g\in\mathcal{G}$ is a route,
($\alpha$-E)  or  ($\alpha$-G) defines what is required in each visit to a
target graph. Finally, constraints (DIST1-t)-(DIST6-t) set the variables
$d_{L}^{e_{g}td}$, $d^{e_{g}}$, $d^{e_{g}e^{\prime}_{g}}$, $d_{R}^{e_{g}td}$,
$d_{RL}^{t}$ and $d_{LR}^{t}$, defined in Table 2, which represent Euclidean
distances needed in the model.

Note that, to deal with the bilinear terms of (DCW), we use McCormick’s
envelopes to linearize them by adding variables $p\geq 0$ representing the
products and introducing the following constraints:

$\displaystyle p$ $\displaystyle\leq Mz,$ $\displaystyle p$ $\displaystyle\leq
d,$ $\displaystyle p$ $\displaystyle\geq mz,$ $\displaystyle p$
$\displaystyle\geq d-M(1-z),$

where $m$ and $M$ are, respectively, the lower and upper bounds of the
distance variable $d$. These bounds will be adjusted for each bilinear term in
Section 3.

###  2.3 The AMMDRPG without synchronisation

In the (2.2) formulation, we assume that every drone is launched and retrieved
in the same stage. In this subsection, we show how this assumption can be
relaxed. We consider a variant of the model presented in Section 2.2, in which
we assume that the mothership can retrieve one drone in a stage different from
the one in which it has been launched. That is, the mothership can move to
another point to launch a new drone without having retrieved the one that was
launched before.

To deal with this extension, we do not need to define new variables since it
is possible to use the same variables that were used in the previous model.
First of all, constraint (5) must be changed to:

$\sum_{e_{g}\in E_{g}}u^{e_{g}td}-\sum_{e_{g}\in E_{g}}\sum_{t^{\prime}\geq
t}v^{e_{g}t^{\prime}d}=0,\quad\forall g\in\mathcal{G},\forall
t\in\mathcal{T},\forall d\in\mathcal{D}.$ (8)

This equation states that, if the graph $g$ is assigned to the drone $d$ at
the stage $t$, there is another stage $t^{\prime}\geq t$ in which the drone
must come back to the mothership. In addition, if the drone $d$ is launched at
$t_{1}$ and retrieved at $t_{2}$, this drone cannot be used in any
intermediate stage. Hence, for each graph $g\in\mathcal{G}$ and drone
$d\in\mathcal{D}$ the following constraints must be satisfied:

$\sum_{e_{g}\in E_{g}}\sum_{t=t_{1}+1}^{t_{2}}u^{e_{g}td}\leq
M(2-\sum_{e_{g}\in E_{g}}u^{e_{g}t_{1}d}-\sum_{e_{g}\in
E_{g}}v^{e_{g}t_{2}d}),\quad t_{1}<t_{2},$ (9) $\sum_{e_{g}\in
E_{g}}\sum_{t=t_{1}}^{t_{2}-1}v^{e_{g}td}\leq M(2-\sum_{e_{g}\in
E_{g}}u^{e_{g}t_{1}d}-\sum_{e_{g}\in E_{g}}v^{e_{g}t_{2}d}),\quad
t_{1}<t_{2}.$ (10)

Moreover, the coordination constraint (DCW) must be modified to consider the
general case in which the stages of launching and retrieving can be different.
For each $t_{1}<t_{2}$ and $\forall g\in\mathcal{G},\forall d\in\mathcal{D}$:

$\displaystyle\frac{1}{v_{D}}\left(\sum_{e_{g}\in
E_{g}}u^{e_{g}t_{1}d}d_{L}^{e_{g}t_{1}d}+\sum_{e_{g},e^{\prime}_{g}\in
E_{g}}z^{e_{g}e^{\prime}_{g}}d^{e_{g}e^{\prime}_{g}}+\sum_{e_{g}\in
E_{g}}\mu^{e_{g}}d^{e_{g}}+\sum_{e_{g}\in
E_{g}}v^{e_{g}t_{2}d}d_{R}^{e_{g}t_{2}d}\right)\leq$
$\displaystyle\frac{\sum_{t=t_{1}}^{t_{2}}d_{LR}^{t}}{v_{M}}+\frac{\sum_{t=t_{1}}^{t_{2}-1}d_{RL}^{t}}{v_{M}}$
$\displaystyle+M(2-\sum_{e_{g}\in E_{g}}u^{e_{g}t_{1}d}-\sum_{e_{g}\in
E_{g}}v^{e_{g}t_{2}d}).$

This inequality takes into account the total time the mothership needs to go
from the launching point $x_{L}^{t_{1}}$ to the rendezvous point
$x_{R}^{t_{2}}$ when the drone $d$ is chosen to visit the graph
$g\in\mathcal{G}$ and this operation begins at stage $t_{1}$ and ends at
$t_{2}$. Finally, we present a result that links the two models presented
before. Note that the only difference that solutions can have between these
models is that, for the non-synchronized case, the mothership can launch a
second drone sequentially before retrieving another one that was launched
before. Figure 2 shows a solution that is not possible for the model with
synchronization. Indeed, we can see that a first drone is launched at
$x_{L}^{1}$ to visit $P_{1}$ that is retrieved at $x_{R}^{1}$. However, the
mothership has launched another drone at $x_{L}^{2}$ that goes visiting
$P_{2}$ before having retrieved the first drone. Obviously, this solution does
not satisfy the assumption in the synchronized model.

Figure 2: The mothership launches two drones sequentially

In order to present our next result, wlog, we restrict ourselves to the
degenerate case where graphs reduce to points. The reader may note that we
could reduce the general case to this one reducing the available capacity so
that is possible to traverse the required percentage of these graphs. We
simplify the proof considering a generic solution between two consecutive
target points.

######  Theorem 2.1.

Let $x_{L}^{1}$, $x_{L}^{2}$ (resp. $x_{R}^{1}$, $x_{R}^{2}$) be the launching
(resp. rendezvous) points associated to the visit of the target points $P_{1}$
and $P_{2}$. If there exist two points $x_{L}$ and $x_{R}$ verifying

$\left\\{\begin{array}[]{ccl}\dfrac{\|x_{L}-x_{R}\|}{v_{C}}&\leq&\dfrac{\|x_{L}-P_{1}\|+\|P_{1}-x_{R}\|}{v_{D}},\\\
\dfrac{\|x_{L}-x_{R}\|}{v_{C}}&\leq&\dfrac{\|x_{L}-P_{2}\|+\|P_{2}-x_{R}\|}{v_{D}},\\\
\dfrac{\|x_{L}-x_{R}\|}{v_{C}}&\leq&N^{d},\\\
\|x_{L}-x_{R}\|&\leq&\|x_{L}^{1}-x_{L}^{2}\|+\|x_{L}^{2}-x_{R}^{1}\|+\|x_{R}^{1}-x_{R}^{2}\|,\end{array}\right.$

then the contribution of this partial route to the optimal objective value
will be the same in both models.

###### Proof.

Note that in the considered configuration, the order of visit to the points
$P_{1}$ and $P_{2}$ is fixed and then, the binary variables in the model are
fixed in this case. Thus, the only difference that the two models can have are
the location of the launching and rendezvous points. Hence, the only
constraints that are involved are those related to these points. These are the
conditions in the statement: The first two are the (DCW) inequalities. The
third one is the (Capacity) constraint and the last one ensures that the
distance traveled by the mothership in the synchronized model is smaller than
or equal to the distance assumed in the non-synchronized solution described in
the statement. Therefore, the conclusion follows.

∎

##  3 Strengthening the formulation of AMMDRPG

In this section we present some valid inequalities for AMMDRPG that reinforce
the formulation given in Section 2.2. Moreover, the (DCW) constraint has
products of binary and continuous variables that, when they are linearized,
produce big-M constants that have to be tightened. This section also provides
some bounds for these constants whenever it is possible.

###  3.1 Valid inequalities for the AMMDRPG

In this problem, we assume that the fleet has more than one drone since
otherwise the problem reduces to (AMDRPG) that was already studied in [25].
Therefore, if there exists a stage in which more than one drone is launched,
the mothership does not need to perform $|\mathcal{G}|$ different stages.
Hence, most likely the model does not need to deal with those stages that are
numbered at the end. By exploiting this idea, it is possible to concentrate
all drone operations on the first stages, avoiding empty tasks in
$\mathcal{T}$. Let $\beta^{t}$ be a binary variable that assumes the value one
if all the target graphs are visited when the operation $t$ begins, and zero,
otherwise. Note that, if all the operations are completed before the stage $t$
then they are also completed before the stage $t+1$. Hence, $\beta$ variables
must satisfy the following constraints:

$\beta^{t}\leq\beta^{t+1},\mbox{ for all }t=1,\ldots,|\mathcal{G}|-1.$
(Monotonicity)

Let $k^{t}$ denote the number of graphs that are visited in the stage $t$.
This number can be computed using the $u$ variables since $u^{e_{g}td}$ takes
the value 1 if the graph $g$ is visited in stage $t$ by the drone $d$. Thus:

$k^{t}=\sum_{e_{g}\in g:g\in\mathcal{G}}\sum_{d\in\mathcal{D}}u^{e_{g}td}.$

Hence, if $\beta^{t}$ equals one, the entire set of graphs in $\mathcal{G}$
must have been visited before the stage $t$:

$\sum_{t^{\prime}=1}^{t-1}k^{t^{\prime}}\geq|\mathcal{G}|\beta^{t},$ (VI-1)

where $|\mathcal{G}|$ denotes the number of graphs of $\mathcal{G}$.

To reduce the space of feasible solutions, we can assume without loss of
generality that it is not permitted to have a stage $t$ without any operation
if some graphs are still to be visited. This can be enforced by the following
constraints:

$k^{t}\geq 1-\beta^{t}.$ (VI-2)

In addition, it is also possible to reduce the symmetry. Since we are assuming
that drones are indistinguishable, we can assume that given an arbitrary order
on them, we always assign drones to operations in that given order. This
assumption allows us to assign for an operation at the stage $t$ the first
drone that is available, avoiding to consider the last ones, if they are not
necessary. This consideration can be implemented by means of the following set
of inequalities. For all $t\in\mathcal{T}$:

$\sum_{e_{g}\in\mathcal{G}}u^{e_{g}td}\leq\sum_{e_{g}:g\in\mathcal{G}}u^{e_{g}td-1},\;\forall
d=2,\ldots|\mathcal{D}|,$ (VI-3)
$\sum_{e_{g}\in\mathcal{G}}v^{e_{g}td}\leq\sum_{e_{g}:g\in\mathcal{G}}v^{e_{g}td-1},\;\forall
d=2,\ldots|\mathcal{D}|.$ (VI-4)

Hence, if the drone $d_{1}$ is assigned to the task $t$, every drone $d_{2}$
that is, for the launching order in $\mathcal{D}$, before than $d_{1}$, must
have been also assigned to perform the task $t$.

The model that we have proposed includes big-M constants. We have defined
different big-M constants along this work. In order to strengthen the
formulations we provide tight upper and lower bounds for those constants. In
this section we present some results that adjust them for each one of the
models.

#### Big $M$ constants bounding the distance from the launching / rendezvous
point on the path followed by the mothership to the rendezvous / launching
point on the target graph $g\in\mathcal{G}$

To linearize the first term of the objective function in AMMDRPG, we define
the auxiliar non-negative continuous variables $p_{L}^{e_{g}td}$ (resp.
$p_{R}^{e_{g}td}$) and we model the product by including the following
constraints:

$\displaystyle p_{L}^{e_{g}td}$ $\displaystyle\geq m_{L}^{e_{g}}u^{e_{g}td},$
$\displaystyle p_{L}^{e_{g}td}$ $\displaystyle\leq
d_{L}^{e_{g}}-M_{L}^{e_{g}td}(1-u^{e_{g}t}).$

The best upper bound $M_{L}^{e_{g}td}$ or $M_{R}^{e_{g}td}$ that we can
consider is the full diameter of the data, that is the maximum distance
between every pair of vertices of the graphs $g\in\mathcal{G}$, in the input
data, i.e., every launching or rendezvous point is inside the circle whose
diametrically opposite points are described below.

$M_{R}^{e_{g}td}=\max_{\\{v\in V_{g},v^{\prime}\in
V_{g^{\prime}}:g,g^{\prime}\in\mathcal{G}\\}}\|v-v^{\prime}\|=M_{L}^{e_{g}td}.$

On the other hand, the minimum distance in this case can be zero. This bound
is attainable whenever the launching or the rendezvous points of the
mothership is the same that the rendezvous or launching point on the target
graph $g\in\mathcal{G}$.

#### Bounds on the big $M$ constants for the distance from the launching to
the rendezvous points on the target graph $g\in\mathcal{G}$.

When the drone visits a graph $g$, it has to go from one edge $e_{g}$ to
another edge $e^{\prime}_{g}$ depending on the order given by
$z^{e_{g}e_{g}^{\prime}}$. This fact produces a product of variables
linearized by the following constraints:

$\displaystyle p^{e_{g}e^{\prime}_{g}}$ $\displaystyle\geq
m^{e_{g}e_{g}^{\prime}}d_{RL}^{gg^{\prime}},$ $\displaystyle
p^{e_{g}e_{g}^{\prime}}$ $\displaystyle\leq
d^{e_{g}e_{g}^{\prime}}-M^{e_{g}e_{g}^{\prime}}(1-z^{e_{g}e_{g}^{\prime}}).$

Since we are taking into account the distance between two edges
$e=(B^{e_{g}},C^{e_{g}}),\,e^{\prime}=(B^{e^{\prime}_{g}},C^{e^{\prime}_{g}})\in
E_{g}$, the maximum and minimum distances between their vertices give us the
upper and lower bounds:

$\displaystyle M^{e_{g}e^{\prime}_{g}}=$
$\displaystyle\max\\{\|B^{e_{g}}-C^{e^{\prime}_{g}}\|,\|B^{e_{g}}-B^{e^{\prime}_{g}}\|,\|C^{e_{g}}-B^{e^{\prime}_{g}}\|,\|C^{e_{g}}-C^{j_{g}}\|\\},$
$\displaystyle m^{e_{g}e^{\prime}_{g}}=$
$\displaystyle\min\\{\|B^{e_{g}}-C^{e^{\prime}_{g}}\|,\|B^{e_{g}}-B^{e^{\prime}_{g}}\|,\|C^{e_{g}}-B^{e^{\prime}_{g}}\|,\|C^{e_{g}}-C^{e^{\prime}_{g}}\|\\}.$

#### Bounds on the big $M$ constants for the distance covered by the drone
during an operation for all the models by stages

To link the drone operation with the trip followed by the mothership, we have
defined the constraint $\eqref{DCW}$ that includes another big-M constant:

$\left(\sum_{e_{g}\in
E_{g}}u^{e_{g}td}d_{L}^{e_{g}td}+\sum_{e_{g},e^{\prime}_{g}\in
E_{g}}z^{e_{g}e^{\prime}_{g}}d^{e_{g}e^{\prime}_{g}}+\sum_{e_{g}\in
E_{g}}\mu^{e_{g}}d^{e_{g}}+\sum_{e_{g}\in
E_{g}}v^{e_{g}td}d_{R}^{e_{g}td}\right)/v_{D}\leq
d_{RL}^{t}/v_{M}+M(1-\sum_{e_{g}\in E_{g}}u^{e_{g}td}).$

To obtain an upper bound on $M$ we add to the length of the graph
$\mathcal{L}(g)$ the big-Ms computed for $u^{e_{g}td}$ and $v^{e_{g}td}$,
namely $M_{L}^{e_{g}td}$ and $M_{R}^{e_{g}td}$, respectively, and the maximum
distance that can be traveled by the drone to move from one edge to another
one. This results in a valid value for this $M$ constant:

$M=\mathcal{L}(g)+M_{L}^{e_{g}td}+M_{R}^{e_{g}td}+\sum_{e_{g},e_{g}^{\prime}\in
E_{g}}M^{e_{g}e_{g}^{\prime}}.$

##  4 A Matheuristic for the Mothership-Drone Routing Problem with Graphs

This section is devoted to present our matheuristic approach to address the
solution of the AMMDRPG. Our motivation comes from the fact that the exact
solution of the models presented in Section 2.2 is highly time demanding.
Alternatively, the matheuristic provides good quality solution in limited
computing times.
The basic idea of the algorithm is to determine the route that a drone should
perform for visiting each graph $g\in\mathcal{G}$, and thus the entry and exit
points $L^{e_{g}}$ and $R^{e^{{}^{\prime}}_{g}}$ for each graph. Sequentially,
a clustering procedure on the target graphs is applied in order to compute the
route of the mothership via their reference points and the origin/destination
points. The clustering procedure is based on a random selection of the initial
target graphs and for this reason it is repeated a number of times in order to
consider different cluster structures. At each iteration the new clusters are
evaluated by computing the cost of the route visiting their reference points
and the origin/destination points. The route computed on the reference points
of the best cluster generated by this iterative procedure, is used to set the
values of the binary variables $u^{e_{g}td}$ and $v^{e_{g}td}$, that determine
the order of visits to the graphs. Finally, these variables are provided as an
initial partial solution to the AMMDRPG model to produce a complete feasible
solution.
In the following, we present the pseudo-code of this algorithm:

  * STEP 1

(First entry and last exit points for each target graph)
Compute the route on each target graph $g\in\mathcal{G}$. Let $L^{e_{g}}$ and
$R^{e^{{}^{\prime}}_{g}}$ be the pair of entry and exit points on $g$ closest
to the origin and let $\mathcal{L}(e_{g},e^{{}^{\prime}}_{g})$ be the
associated length computed as the sum of the distances travelled by the drone
to visit the graph $g$, excluding the distance between $L^{e_{g}}$ and
$R^{e^{{}^{\prime}}_{g}}$.

  * STEP 2

(Clustering procedure)
Initialization: set $it=1$, define one cluster for each target graph and set
$nit=1$.
Select randomly two clusters $K_{i}$ and $K_{j}$ (where $i<j$).
Check if the number of graphs belonging to the union of $K_{i}$ and $K_{j}$ is
less than the number of available drones $n_{D}$.
If this condition is satisfied:
search for point $P$ satisfying the following capacity constraint:

$\frac{d(P,R^{e_{g}})+\mathcal{L}(e_{g},e^{{}^{\prime}}_{g})+d(L^{e^{{}^{\prime}}_{g}},P)}{v_{D}}\leq
N^{d},\quad\forall R^{e_{g}},L^{e^{{}^{\prime}}_{g}}\in K_{i},\>\>K_{j}.$

If such a point exists, merge the two clusters and label the new one as
$K_{i}$.
Set $nit=nit+1$.
Repeat the same procedure on the new cluster structure while $nit<maxit$.

  * STEP 3

(Computation of Reference Points) Compute a reference point for each cluster
generated at STEP 2. This computation seeks for the minimization of the
distance between each pair of reference points and the distance between them
and the origin, always imposing that the (Capacity) constraint is satisfied.

  * STEP 4

(Setting the order of visits to the graphs: route via the reference points and
the origin/destination points)
Compute the TSP of the mothership among the reference points of the clusters
and let $\mathcal{L}(TSP)$ be the associated length.
Set $it=it+1$.
if(it< maxseed) go to STEP 2
else go to STEP 5

  * STEP 5

(Solution of the AMMDRPG model fixing an initial partial solution)
Set the values of the binary variables $u^{e_{g}td}$ and $v^{e_{g}td}$ and
solve the model AMMDRPG to obtain a feasible solution.

Figure 3: Illustrative example

Figure 3 shows an illustrative example consisting of four target planar graphs
($g_{1}$, $g_{2}$, $g_{3}$ and $g_{4}$) to be visited. We assume that their
visits must be performed by a fleet of two drones supported by a mothership
which starts from the origin $(0,0)$ and ends on the destination point
$(100,0)$.

(a) a

(b) b

(c) c

(d) d

Figure 4: STEP 1 for the illustrative example

Figure 4 reports a zoom on each single target graph, showing the tour
generated by STEP 1 of the heuristic procedure. A pair of points representing
retrieving and launching points, together with an arrow pointing the direction
followed by the drone according with the order in which the edges are visited,
are depicted on each edge.

(a) a

(b) b

Figure 5: [a] STEP 2, [b] STEP 3 for the illustrative example

By applying STEP 2 to this illustrative example, we obtain three clusters, as
shown in Figure 5[a]. One cluster contains graphs $g_{1}$ and $g_{3}$ (in
red), while graph $g_{2}$ and $g_{4}$ represent distinct clusters. The
computation of the reference points of these clusters, according with STEP 3,
produces the points $P_{1}$ and $P_{2}=P_{3}$, as shown in Figure 5[b]. Note
that in this case the reference points for the two clusters containing
respectively $g_{2}$ and $g_{4}$ coincide, and thus we have only two distinct
reference points for the three clusters.

(a) a

(b) b

Figure 6: [a] STEP 4, [b] STEP 5 for the illustrative example

STEP 4 of the heuristic procedure generates the tour of the mothership along
the origin point, $P_{1}$, $P_{2}$ and the destination point, as shown in
Figure 6[a]. This tour returns also the order in which the clusters are
visited (and thus, also the order of visit to the target graphs) and this
permits to set the values of the variables $u^{e_{g}td}$ and $v^{e_{g}td}$ of
the AMMDRPG model.
By providing the initial partial solution obtained by the values of the
variables $u^{e_{g}td}$ and $v^{e_{g}td}$, STEP 5 solves the AMMDRPG model and
returns the final feasible solution shown in Figure 6[b]. From it we can
observe that the sequence of visit of the target graphs does not change with
respect to the one provided by STEP 4. The fleet of two drones first visits
graphs $g_{1}$ and $g_{3}$ starting from the launching point $x^{1}_{L}$.
Then, both drones are retrieved by the mothership at point $x^{1}_{R}$. The
mothership moves to the point $x^{2}_{L}$ where one drone is launched for
visiting graph $g_{2}$. Then the mothership reaches point $x^{2}_{R}$ to
retrieve the drone and from the same point it launches the other drone for
visiting graph $g_{4}$. Then, this drone is retrieved by the mothership at
point $x^{3}_{R}$ before moving to the final destination point.

(a) a

(b) b

(c) c

Figure 7: Zoom on the tour on each target graph provided by STEP 5

Focusing on each single target graph, Figure 7 shows the zoom on the tours
followed by the drones. For example, Figure 7[a] reports the one performed by
the drone that visits graph $g_{1}$. The drone starts from the mothership at
point $x^{1}_{L}$ and first visits the segment
$\overline{R^{1}_{1}L^{1}_{1}}$. From point $L^{1}_{1}$ the drone moves to the
second visited edge of graph $g_{1}$ visiting the segment
$\overline{R^{2}_{1}L^{2}_{1}}$. Finally, the drone leaves the graph from
point $L^{2}_{1}$ and it is retrieved by the mothership at point $x^{1}_{R}$.
Note that in this example the drones do not visit the full 100% of each graph,
but only a pre-specified percentage of each one of them.

The reader may notice that the above algorithm can be also used to generate
solutions for the model without synchronization commented in Section 2.3 since
any solution of the synchronous model is also feasible for the asynchronous
one.

##  5 Experimental results

In this section we discuss the experimental results obtained testing the
formulations presented in Section 2.2 and the matheuristic procedure proposed
in Section 4 on a testbed of instances. In particular, we consider instances
like the ones used in [25] where the targets, to be visited by the drones, are
represented by grid graphs. This set consists of 5 instances of respectively 5
and 10 target graphs, with different cardinality of the set of nodes. More
precisely, each instance is composed of 20$\%$ graphs with 4 nodes, 20$\%$
graphs of 6 nodes, 20$\%$ graphs of 8 nodes and 20$\%$ graphs of 10 nodes.
Moreover, we assume that the velocity of the drones is twice that of the
mothership and that a random percentage of each target graph, or of each of
its edges, must be visited by the fleet of drones.
We consider in our experiments that the number of drones varies between 1 and
3 and that the drones endurance (expressed as maximum time that the drone can
operate when it is fully recharged) ranges between 20 and 60. Table 3 reports
a summary of the characteristics of our instances.

Table 3: Instances parameter values # Targets | (5,10)
---|---
# Drones | (1,2,3)
# Vertices | (4,6,8,10,12)
Drone endurance | (20,30,40,50,60)
$\%$ target (edge) | random variable

Table 4 reports the results obtained solving the AMMDRPGmodel on the instances
previously described, by adopting the commercial solver Gurobi. We consider
the exact solution both providing and not providing an initial solution
computed by the matheuristic described in Section 4. More precisely, the first
column of Table 4 indicates the number of target graphs to be visited by the
fleet of drones, the second column reports the capacity of the drones, the
third column distinguishes between the visit of a percentage of each edge (e)
and the percentage of each target graph (g). The fourth column reports the
size of the fleet of drones. Thus, for each combination of the listed
parameters, we summarize the average percentage gap of the solution obtained
within the time limit set equal to 2 hours. We report respectively average
percentage gap with initialization by the solution provided by the
matheuristic, solution time, in seconds, of the matheuristic and average gap
without initialization by the solution obtained by the matheuristic.
We can observe that the value of the average percentage gap ranges between a
minimum of 66.9% and a maximum of 97.43%. This shows that the model is hard to
be solved even on small size instances. Moreover, we can see that in most of
the cases, the average percentage gap associated with the variant of the model
consisting in visiting a given percentage of each edge, is higher than the one
associated with the variant imposing to visit a given percentage of each
target graph. Another thing that we can observe is that the average percentage
gap increases with the number of drones and decreases with the drone
endurance.
As regards the number of target graphs, we can see that by increasing it from
5 to 10, the exact method, without initialization by the solution obtained
with the matheursitic, becomes even harder. Indeed, the red entries of the
table mean that some instances could not find a feasible solution within the
time limit (note that in the brackets we indicate the number of these
instances). The number of not solvable instances increases with the number of
drones. Moreover, for the minimum level of endurance, the exact solution of
the model without initialization provided by the matheuristic, does not
provide any solution, within the time limit, for instances with 10 graphs and
2 or 3 drones.
Considering the comparison with the exact method starting from the solution
provided by the matheuristic, we can note that the values of average
percentage gap are very close to the ones related to the exact solution method
without initialization. Thus the initialization does not speed up the
convergence of the solver. However, we can see that the matheuristic is always
able to find a feasible solution of the problem, even for the cases in which
the solver is not.
Moreover, the average solution times of the matheuristic range between a
minimum of 37 seconds to a maximum of 3 minutes. They increase with the drone
capacity for the variant of the model in which a given percentage of each edge
must be visited, while they decrease by increasing the number of drones for
the variant of the model in which a given percentage of each target graph must
visited. By increasing the number of target graphs from 5 to 10, the average
solution times of the matheuristics become more than double for both model
variants. Summing up, the results obtained show that the exact solution method
given by solving the formulation is very challenging even for small size
instances. However, exploiting it, the matheuristic is able to provide
solutions for all instances rather quickly.

Table 4: Comparison between exact solution with and without initialization by
the matheuristic solution

|  |  | # drones
---|---|---|---
|  |  | 1 | 2 | 3
$\bm{|\mathcal{G}|}$ | $\bm{N^{d}}$ | v.t. | % Gap (i) | TimeH | % Gap (wi) | % Gap (i) | TimeH | % Gap (wi) | % Gap (i) | TimeH | % Gap (wi)
|  | e | 82,63 | 61,56 | 81,70 | 91,57 | 63,80 | 90,61 | 93,06 | 60,87 | 90,93
| 20 | g | 79,09 | 44,97 | 79,63 | 89,03 | 37,32 | 91,85 | 94,00 | 39,05 | 95,80
|  | e | 82,70 | 65,21 | 80,17 | 85,14 | 64,41 | 82,21 | 91,9 | 63,34 | 90,12
| 30 | g | 75,80 | 55,77 | 71,19 | 84,36 | 44,36 | 88,27 | 91,02 | 44,59 | 91,39
|  | e | 80,94 | 68,81 | 77,98 | 83,44 | 64,80 | 82,16 | 91,24 | 63,19 | 86,25
| 40 | g | 74,47 | 43,92 | 73,46 | 81,21 | 38,27 | 84,35 | 85,34 | 37,51 | 89,63
|  | e | 76,87 | 66,67 | 74,41 | 81,12 | 63,86 | 79,57 | 85,11 | 63,51 | 86,16
| 50 | g | 70,58 | 43,42 | 66,90 | 80,96 | 43,98 | 88,84 | 80,49 | 44,35 | 82,81
|  | e | 76,39 | 67,78 | 71,61 | 81,63 | 66,08 | 79,84 | 83,82 | 64,40 | 82,06
5 | 60 | g | 78,17 | 44,69 | 72,79 | 79,35 | 40,63 | 86,55 | 81,74 | 50,01 | 84,66
|  | e | 82,56 | 137,93 | 84,91 | 92,30 | 128,53 | - | 94,73 | 124,44 | -
| 20 | g | 81,00 | 119,20 | 84,08 (2) | 89,88 | 83,50 | 96,64 (2) | 96,44 | 70,00 | 97,43 (3)
|  | e | 80,60 | 159,00 | 80,93 | 87,11 | 132,15 | 87,58 (3) | 94,56 | 127,35 | 92,85 (2)
| 30 | g | 79,93 | 132,67 | 82,70 (1) | 86,32 | 80,29 | 86,13 (3) | 91,12 | 76,72 | 89,74 (1)
|  | e | 79,05 | 191,37 | 78,07 | 85,11 | 131,26 | 84,33 | 91,88 | 132,10 | 88,61 (1)
| 40 | g | 80,23 | 115,00 | 79,64 | 87,31 | 68,39 | 84,57 (3) | 96,09 | 69,40 | 91,86 (1)
|  | e | 81,49 | 188,32 | 77,81 | 87,72 | 134,01 | 85,51 (1) | 92,68 | 132,82 | 90,79 (3)
| 50 | g | 79,92 | 87,23 | 80,38 | 82,80 | 66,14 | 84,00 (3) | 92,48 | 64,94 | 91,96 (2)
|  | e | 83,79 | 155,27 | 81,57 | 85,91 | 131,94 | 82,96 (2) | 92,24 | 130,11 | 86,58 (3)
10 | 60 | g | 77,57 | 97,89 | 78,46 | 86,94 | 76,53 | 88,29 (2) | 94,31 | 69,53 | 92,23 (3)

We show in Figure 8 the relationship between the objective function values of
the problem and the number of available drones and their capacity. This figure
reports the average objective values of all the instances with three target
graphs varying the number of drones in $\\{1,2,3\\}$ and their endurance
(capacity) in $\\{10,20,30,40,50,60\\}$. The darker the color intensity the
smaller the objective value. As expected, our experiment confirms that both, a
greater number of drones and larger endurance reduce total length of the
mothership route.

Figure 8: Heatmap of objective function values depending on number of drones
and drone capacities. The darker the color intensity the smaller the objective
value.

##  6 Case Study

In this section we describe a realistic application of the system studied in
this paper to perform surveillance operations. Considering the current
COVID-19 restrictions, we focus on the problem of preventing and identifying
possible concentrations of people during events such as popular or religious
festivals. In particular we consider the Courtyards Festival of Cordoba
(https://patios.cordoba.es/es/). This is a social event that takes place every
year in the city of Cordoba, Spain, during the first two weeks of May.
Courtyard’s owners decorate their houses with many flowers trying to win the
award that is offered by the Town Hall. During this competition a festival
runs in parallel with a number of artistic performances along six different
paths located in different areas in the city as shown in Figure 9. In the
pandemic context, to monitor the situation to avoid concentration of people,
we propose to apply a system consisting of one helicopter and a fleet of three
drones. This kind of system has been proved successfully and has been already
applied in the military field by the US Army in order to leave the helicopter
to the edge of dangerous airspace and release drones, which will then
penetrate enemy territory and send back intelligence, surveillance and
reconnaissance information (see [27]). In our application the reason to adopt
a similar system is the possibility to inspect simultaneously and in real time
different paths also reducing the risk of flying the helicopter over populated
areas and the cost for moving the helicopter by minimizing the total length of
its tour.

Figure 9: Map of the Courtyards Festival in Cordoba.

We run the model presented in Section 2.2 on this scenario starting from the
initial solution provided by the matheuristic, where the 6 coloured paths
reported in the map of Figure 9 represent the 6 target graphs to be visited,
in this case inspected, by the fleet of drones. In addition, we suppose that
the drones’ speed is 100 km/h while that of the helicopter is 50 km/h aiming
to minimize costs. Moreover, we assume that the fleet is composed by three
drones with an endurance equal to 2 hours, and we impose that each target
graph must be fully visited (inspected). As we can see from Figure 10, the
origin of the mothership tour coincides with the destination and it is located
in an area of the city where it is possible to assume the take-off and landing
of an helicopter. Figure 10 reports the tour followed by the helicopter in the
solution obtained within the time limit of 2 hours sets to solve the model and
with a percentage gap equal to 83%. We can observe that the helicopter,
starting from the origin, flies to the point $x_{L}^{1}$ that is the first
launching point and then flies along the edge connecting $x_{L}^{1}$ with
$x_{R}^{1}$, that is the first rendezvous point. Next, the helicopter flies to
$x_{L}^{2}$ for launching the second drones’ mission that are retrieved at
point $x_{R}^{2}$. The third and last mission starts from $x_{L}^{3}$ and ends
at point $x_{R}^{3}$ from where the helicopter goes back to the final
destination.
Figure 11 shows the tour followed by the three drones for inspecting the six
paths. In particular, one drone, in red, starts from $x_{L}^{1}$ for visiting
the path of "Alcazar Viejo". From the same point a second drone, in green,
starts for visiting the path of "Santa Maria-San Agustin". Both drones end
their first mission at point $x_{R}^{1}$, where they are retrieved by the
helicopter. Then, the helicopter flies to point $x_{L}^{2}$ where only one
drone, the red one, starts its second mission to visit the path of "Juderia-
San Francisco". In the meanwhile the helicopter, containing the other two
drones, flies to point $x_{R}^{2}$ where it retrieves the previously launched
drone. The last mission involves all the three drones that are launched from
point $x_{L}^{3}$. The first drone, the red one, visits the path of "San
Lorenzo", the second, the green one, visits the path of "Regina-Realejo" and
the third, the blue one, visits the path of "Santiago-San Pedro". All the
three drones are retrieved by the helicopter at point $x_{R}^{3}$ and after
that the helicopter goes back to the destination. The total distance travelled
by the helicopter is equal to 11.27 km.

All details of this case study, including maps coordinates, .lp models and
solutions can be found in [28].

Figure 10: Mothership tour.  Figure 11: The complete solution.

##  7 Concluding remarks

This papers has analyzed the coordination problem that arises between a
mothership vehicle and a fleet of drones that must coordinate their routes to
minimize the total distance travelled by the mothership while visiting a set
of targets modeled by graphs. We have presented exact formulations of the
problem, for its synchronized and not synchronized versions. They are mixed
integer non-linear programming models. Moreover, we presented valid
inequalities for them.
Our computational results show that the considered problem is very challenging
to solve even on small to medium size instances. For that reason,
additionally, we have proposed a matheuristic algorithm that provides
acceptable feasible solutions in very short computing time; so that it is a
good alternative to the exact method. We report extensive computational
experiments on randomly generated instances. Moreover, we present a case study
related to inspection activities in the context of COVID-19 restrictions. We
show the application of the system described in this paper in the framework of
the Courtyard Festival in the city of Cordoba, by illustrating the solution
obtained by adopting the problem formulation, in its synchronized version, and
its solution by means of the initialization provided by the proposed
matheuristic.
The formulation and algorithms proposed in this paper can be seen a first
building block to handle coordination of systems given by a base vehicle and
drones. Further research in this topic must focus on finding faster and more
accurate algorithms able to solve larger instances. Moreover, it is also
challenging to model more complex operations allowing that drones can visit
more than one target per trip. These problems being very interesting are
beyond the scope of the present paper and will be the focus of a follow up
research line.

## Acknowledgements

This research has been partially supported by Spanish Ministry of Education
and Science/FEDER grant number MTM2016-74983-C02-(01-02), and projects Junta
de Andalucia P18-FR-1422, FEDER-US-1256951, CEI-3-FQM331 and NetmeetData:
Ayudas Fundación BBVA a equipos de investigación científica 2019.

## References

  * Amorosi et al. [2018] L. Amorosi, L. Chiaraviglio, F. D’Andreagiovanni, N. Blefari-Melazzi,  Energy-efficient mission planning of uavs for 5g coverage in rural zones,  in: 2018 IEEE International Conference on Environmental Engineering (EE), 2018, pp. 1–9. doi:10.1109/EE1.2018.8385250.
  * Chiaraviglio et al. [2018] L. Chiaraviglio, L. Amorosi, N. Blefari-Melazzi, P. Dell’Olmo, C. Natalino, P. Monti,  Optimal design of 5g networks in rural zones with uavs, optical rings, solar panels and batteries,  in: 2018 20th International Conference on Transparent Optical Networks (ICTON), 2018, pp. 1–4. doi:10.1109/ICTON.2018.8473712.
  * Jimenez et al. [2018] J. G. Jimenez, L. Chiaraviglio, L. Amorosi, N. Blefari-Melazzi,  Multi-Period Mission Planning of UAVs for 5G Coverage in Rural Areas: A Heuristic Approach,  Proceedings of the 2018 9th International Conference on the Network of the Future, NOF 2018 (2018) 52–59. doi:10.1109/NOF.2018.8598123.
  * Amorosi et al. [2019] L. Amorosi, L. Chiaraviglio, J. Galan-Jimenez,  Optimal energy management of uav-based cellular networks powered by solar panels and batteries: Formulation and solutions,  IEEE Access Vol. 7 (2019) 53698–53717.
  * Chiaraviglio et al. [2019a] L. Chiaraviglio, L. Amorosi, N. Blefari-Melazzi, P. Dell’olmo, A. Lo Mastro, C. Natalino, P. Monti,  Minimum Cost Design of Cellular Networks in Rural Areas with UAVs, Optical Rings, Solar Panels, and Batteries,  IEEE Transactions on Green Communications and Networking 3 (2019a) 901–918. doi:10.1109/TGCN.2019.2936012.
  * Chiaraviglio et al. [2019b] L. Chiaraviglio, L. Amorosi, F. Malandrino, C. F. Chiasserini, P. Dell’Olmo, C. Casetti,  Optimal Throughput Management in UAV-based Networks during Disasters,  INFOCOM 2019 - IEEE Conference on Computer Communications Workshops, INFOCOM WKSHPS 2019 (2019b) 307–312. doi:10.1109/INFCOMW.2019.8845190.
  * Mathew et al. [2015] N. Mathew, S. L. Smith, S. L. Waslander,  Planning Paths for Package Delivery in Heterogeneous Multirobot Teams,  IEEE Transactions on Automation Science and Engineering 12 (2015) 1298–1308. doi:10.1109/TASE.2015.2461213.
  * Mourelo Ferrandez et al. [2016] S. Mourelo Ferrandez, T. Harbison, T. Weber, R. Sturges, R. Rich,  Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm,  Journal of Industrial Engineering and Management; Vol 9, No 2 (2016)DO - 10.3926/jiem.1929 (2016). URL: https://www.jiem.org/index.php/jiem/article/view/1929.
  * Poikonen and Golden [2020] S. Poikonen, B. Golden,  Multi-visit drone routing problem,  Computers and Operations Research 113 (2020) 104802. URL: https://doi.org/10.1016/j.cor.2019.104802. doi:10.1016/j.cor.2019.104802.
  * Amorosi et al. [2020] L. Amorosi, R. Caprari, T. Crainic, P. Dell’Olmo, N. Ricciardi,  CIRRELT-2020-17 An Integrated Routing-Scheduling Model for a Hybrid UAV-Based Delivery System,  CIRRELT, 2020.
  * Wen et al. [2016] T. Wen, Z. Zhang, K. K. L. Wong,  Multi-objective algorithm for blood supply via unmanned aerial vehicles to the wounded in an emergency situation,  PLoS ONE 11 (2016). doi:10.1371/journal.pone.0155176.
  * Trotta et al. [2018] A. Trotta, F. D. Andreagiovanni, M. Di Felice, E. Natalizio, K. R. Chowdhury,  When UAVs Ride A Bus: Towards Energy-efficient City-scale Video Surveillance,  Proceedings - IEEE INFOCOM 2018-April (2018) 1043–1051. doi:10.1109/INFOCOM.2018.8485863.
  * Otto et al. [2018] A. Otto, N. Agatz, J. Campbell, B. Golden, E. Pesch,  Optimization approaches for civil applications of unmanned aerial vehicles (uavs) or aerial drones: A survey. .,  Networks Vol. 72 (2018) 1–48.
  * Chung et al. [2020] S. H. Chung, B. Sah, J. Lee,  Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions,  Computers & Operations Research 123 (2020) 105004. URL: https://www.sciencedirect.com/science/article/pii/S0305054820301210. doi:https://doi.org/10.1016/j.cor.2020.105004.
  * Murray and Chu [2015] C. C. Murray, A. G. Chu,  The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery,  Transportation Research Part C: Emerging Technologies 54 (2015) 86–109. URL: https://www.sciencedirect.com/science/article/pii/S0968090X15000844. doi:https://doi.org/10.1016/j.trc.2015.03.005.
  * Ulmer and Thomas [2018] M. W. Ulmer, B. W. Thomas,  Same-day delivery with heterogeneous fleets of drones and vehicles,  Networks 72 (2018) 475–505. URL: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.21855. doi:https://doi.org/10.1002/net.21855. arXiv:https://onlinelibrary.wiley.com/doi/pdf/10.1002/net.21855.
  * Campbell et al. [2017] J. F. Campbell, D. Sweeney, J. Zhang,  Strategic design for delivery with trucks and drones,  Computer Science (2017).
  * Carlsson and Song [2017] J. G. Carlsson, S. Song,  Coordinated logistics with a truck and a drone,  Management Science Vol. 64 (2017) 4052–4069.
  * Dayarian et al. [2017] I. Dayarian, M. Savelsbergh, J. P. Clarke,  Same-day delivery with drone resupply.,  Optimization Online (2017).
  * Poikonen and Golden [2020] S. Poikonen, B. Golden,  The mothership and drone routing problem,  INFORMS Journal on Computing 32 (2020) 249–262. URL: https://doi.org/10.1287/ijoc.2018.0879. doi:10.1287/ijoc.2018.0879. arXiv:https://doi.org/10.1287/ijoc.2018.0879.
  * Campbell et al. [2018] J. F. Campbell, Á. Corberán, I. Plana, J. M. Sanchis,  Drone arc routing problems,  Networks 72 (2018) 543–559. doi:10.1002/net.21858.
  * Campbell et al. [2021] J. F. Campbell, Ángel Corberán, I. Plana, J. M. Sanchis, P. Segura,  Solving the length constrained k-drones rural postman problem,  European Journal of Operational Research 292 (2021) 60–72. URL: https://www.sciencedirect.com/science/article/pii/S0377221720309115. doi:https://doi.org/10.1016/j.ejor.2020.10.035.
  * Tokekar et al. [2016] P. Tokekar, J. V. Hook, D. Mulla, V. Isler,  Sensor Planning for a Symbiotic UAV and UGV System for Precision Agriculture,  IEEE Transactions on Robotics 32 (2016) 1498–1511. doi:10.1109/TRO.2016.2603528.
  * Garone et al. [2010] E. Garone, R. Naldi, A. Casavola, E. Frazzoli,  Cooperative mission planning for a class of carrier-vehicle systems,  Proceedings of the IEEE Conference on Decision and Control (2010) 1354–1359. doi:10.1109/CDC.2010.5717171.
  * Amorosi et al. [2021] L. Amorosi, J. Puerto, C. Valverde,  Coordinating drones with mothership vehicles: The mothership and drone routing problem with Graphs (2021).
  * Blanco et al. [2017] V. Blanco, E. Fernández, J. Puerto,  Minimum spanning trees with neighborhoods: Mathematical programming formulations and solution methods,  European Journal of Operational Research 262 (2017) 863–878. doi:10.1016/j.ejor.2017.04.023.
  * FG [????] Us army catches "air-launched effect" drones in mid-air using another uav, https://www.flightglobal.com/military-uavs/us-army-catches-air-launched-effect-drones-in-mid-air-using-another-uav/140498.article, ????
  * Puerto and Valverde [2021] J. Puerto, C. Valverde, Project: Instances for the Case Study of the All Terrain Mothership Multiple Drone Routing Problem with Graphs (AMMDRPG). Url: https://github.com/z72vamac/case_study_AMMDRPGST, 2021. URL: https://github.com/z72vamac/case_study_AMMDRPGST.