Path Planning for Multiple Heterogeneous Unmanned Vehicles with
Uncertain Service Times
Kaarthik Sundar†, Saravanan Venkatachalam∗, Satyanarayana G. Manyam‡
Abstract— This article presents a framework and develops
a formulation to solve a path planning problem for multiple
heterogeneous Unmanned Vehicles (UVs) with uncertain service
times for each vehicle–target pair. The vehicles incur a penalty
proportional to the duration of their total service time in
excess of a preset constant. The vehicles differ in their motion
constraints and are located at distinct depots at the start of
the mission. The vehicles may also be equipped with disparate
sensors. The objective is to find a tour for each vehicle that
starts and ends at its respective depot such that every target
is visited and serviced by some vehicle while minimizing the
sum of the total travel distance and the expected penalty
incurred by all the vehicles. We formulate the problem as
a two-stage stochastic program with recourse, present the
theoretical properties of the formulation and advantages of
using such a formulation, as opposed to a deterministic expected
value formulation, to solve the problem. Extensive numerical
simulations also corroborate the effectiveness of the proposed
approach.
Index Terms— heterogeneity; unmanned vehicles; stochastic
optimization; two-stage problem; simple recourse; uncertain
service times
I. INTRODUCTION
Advances in sensing, robotics, and wireless networks have
enabled the use of teams of Unmanned Vehicles (UVs) for
environmental sensing applications including crop monitor-
ing [1], ocean bathymetry [2], forest fire monitoring [3],
ecosystem management [4], civil security applications such
as border surveillance, and military applications such as
reconnaissance and data collection missions. These appli-
cations frequently require vehicles to collect data such as
visible/infra-red/thermal images, videos of specified target
sites, and environmental data such as temperature, moisture,
humidity using on-board sensors, and deliver them to a
base station. Typically, in these applications, path planning
for the UVs has to be performed a priori before the start
† Center for Non-Linear Studies, Los Alamos National Laboratory, Los
Alamos, NM. kaarthik01sundar@gmail.com
∗Assistant Professor, Dept. of Industrial Engg., Wayne State University,
Detroit, MI.
‡ National Research Council Fellow, Air Force Research Laboratory,
WPAFB, OH.
of the mission in the presence of uncertainty in travel
times, service times, communication delays etc. This paper
considers a stochastic generalization of a fundamental path
planning problem involving a fleet of multiple heterogeneous
vehicles. We classify the heterogeneity of these vehicles
into two categories: structural and functional heterogeneity.
Vehicles are said to be structurally heterogeneous if they
differ in design and dynamics. This can lead to differences in
maximum speed at which they can travel, payload capacity,
fuel consumption, etc [5]–[9]. This is a rational assumption
as some structural differences are always present between
any pair of vehicles. A collection of vehicles is said to be
functionally heterogeneous if not all vehicles may be able to
service a target. The vehicles may be equipped with disparate
sensors due to payload restrictions, and it leads to functional
heterogeneity. In this case, we partition the set of targets into
disjoint subsets: (a) targets to be visited by specific vehicles,
and (b) common targets that can be visited by any of the
vehicles.
The problem we consider in this article is motivated by a
mission scenario, where a collection of UVs have to visit
a set of target locations and collect data. The UVs have
to establish a communication link with sensors located at
the target locations and transfer the sensor data. The time
required to establish the communication link and complete
the data transfer is uncertain, and is modeled as a random
variable with a known distribution. To address any such
routing problem with uncertain service times, we pose the
following heterogeneous, multiple depot, multiple unmanned
vehicle path planning problem with random service times
(HMDMVPP-RST). We are given (i) a set of targets, which
are locations of ground sensors collecting data, (ii) a fleet
of heterogeneous vehicles located at distinct depots, a head-
ing angle for visiting each target and each depot, (iii) an
uncertain service time for every vehicle–target pair, and (iv)
a preset limit for every combination of vehicle–target that
could be indicative of the maximum time the vehicle takes
to service the target. The objective is to find a tour for each
vehicle that starts and ends at its depot such that each target is
arXiv:1702.07647v1  [cs.RO]  24 Feb 2017
visited by at least one vehicle, the vehicle–target constraints
are satisfied, the paths satisfy the motion constraints of the
respective vehicles, and sum of the travel cost by all the
vehicles and the total expected penalty is minimized. The
penalty incurred for a vehicle is proportional to the duration
of its total service time in excess of a preset limit; this
limit may be considered as a budget on the total service
time for each vehicle. Typically, the time taken for a vehicle
to establish a reliable communication link with the ground
sensor at a given target and collecting the data from it varies
based on a plenty of natural factors like wind, obstacles etc.
The vehicle is assumed to loiter at a target until a reliable
communication link is established with the ground sensor
and the data transfer is completed; this loitering time (service
time) at a target is uncertain.
To formulate the HMDMVPP-RST, we make the following
assumptions: each vehicle in the heterogeneous fleet of UVs
is modeled as a Dubins vehicle with distinct value for its
minimum turn radius and all the vehicles are assumed to
travel at a constant velocity. The paths for all the vehicle are
determined before knowing the realizations of the random
service times. The UVs must follow their a priori paths;
no path re-optimizations are permitted. The uncertainty in
the service time for each vehicle–target pair is available in
the form of samples or scenarios from a known distribution.
In the presence of uncertainty, it is often practical to have
recourse decisions. The optimal paths for all the vehicles are
determined while hedging against the uncertainty before the
realization of randomness in service time.
Following are the contributions of this paper: we develop
a two-stage stochastic formulation for the HMDMVPP-RST
which explicitly incorporates the modeling of the uncertainty
in service times for each vehicle–target pair. We develop a
branch-and-cut algorithm which an algorithm that can pro-
vide an optimal solution to any instance of the problem. We
present the conditions under which the two-stage formulation
and a deterministic expected value based formulation that
uses the expected values for the uncertainty in service times
are equivalent for a particular class of instances. Finally, ex-
tensive computational experiments are presented illustrating
the advantages of a two-stage stochastic formulation over the
deterministic expected value counterpart.
A. Related Work
The deterministic variant of the HMDMVPP-RST is a gen-
eralization of the asymmetric multiple vehicle heterogeneous
traveling salesmen problem [10] which is NP-hard. The au-
thors in [10], [11] formulate and develop algorithms that can
compute an optimal solution for the symmetric and asymmet-
ric multiple vehicle heterogeneous traveling salesmen prob-
lems, respectively. Another variant of the HMDMVPP-RST
where the vehicles are homogeneous and modeled as point
masses is the stochastic multiple vehicle routing problem
with random travel times [12]. Authors in [13], [14] consider
a vehicle routing problem with uncertainties in both service
times and travel times; in particular [14] also includes time
windows during which the vehicle should visit the targets.
In [13], the authors consider multiple homogeneous vehicles,
whereas, this paper considers a heterogeneous version of the
problem with motion constraints. A number of variants of the
deterministic version of the HMDMVPP-RST involving one
or more vehicles have been addressed in the literature and
a plethora of heuristics and algorithms to obtain an optimal
solution to the respective problems have been developed. An
interested reader is referred to an excellent survey article [15]
on all the deterministic variants.
The stochastic variants of the HMDMVPP-RST are also
plenty in number; interested readers are referred to a very
recent literature survey on the models and techniques used
to formulate and solve such variants [16]. To the best
of our knowledge, none of the stochastic variants in the
literature consider a heterogeneous fleet of UVs differing
in their motion constraints; this is the first work in the
literature to address such a stochastic variant. But there are
many homogeneous variants that consider more complicated
recourse actions which involve route re-planning. The focus
of this paper is to describe a framework to formulate and
solve problems concerning path planning for multiple het-
erogeneous UVs in the presence of uncertainty in service
times and illustrate the advantages of such a framework.
Furthermore, developing algorithms to solve a such two-
stage stochastic formulation with recourse is considered as
a stand-alone area in the optimization literature [17]–[22].
We also remark that this framework presented here for
the HMDMVPP-RST is not new and has been extensively
studied in the optimization literature for problems concerning
decision making under uncertainty [23] in supply chain
management, revenue management, vehicle routing etc.
The rest of the paper is organized as follows: the Sec.
II presents detailed notations that are used to formulate
the HMDMVPP-RST, followed by the two-stage stochastic
formulation in Sec. III. Sec. IV develops a branch-and-cut
algorithm to solve the formulation in Sec. III to optimality
and finally, Sec. V presents extensive computational results
followed by conclusions and possible extensions in Sec. VI.
II. NOTATIONS AND UNCERTAINTY MODEL
This section introduces the required notation to develop
the two-stage stochastic formulation for the HMDMVPP-
RST. To that end, let T denote the set of targets and D =
{d1, . . . ,dn} the set of depots; we have a heterogeneous fleet
of n vehicles initially stationed at distinct depots. We shall
refer to V := D ∪T as the set of vertices. Associated with
each vertex i ∈V is an orientation angle θi. θi is the angle at
which any vehicle has to arrive and depart from the vertex.
Furthermore, we also assume that there are vehicle–target
constraints where each vehicle k is required to visit a subset
of targets Rk ⊆T with ∩iRi = ∅; Rk denotes the functional
heterogeneous targets that the vehicle k has to visit. The sets
R1, . . . ,Rn are assumed to be known a priori, and targets in
the set T \ (∪iRi) are referred as common targets, and they
can be visited by any vehicle.
Each vehicle in the heterogeneous fleet of UVs is modeled
as Dubins vehicle with a distinct value for its minimum turn
radius. The kinematic constraints of the vehicle stationed at
depot dk is given by: vx = v cosθ,vy = v sinθ, Ûθ ⩽uk,
where vx and vy are the x and y components of the velocities,
respectively, and Ûθ and uk are the angular velocity and the
maximum yaw-rate of the vehicle. uk is different among
vehicles and |v| is assumed to be the same for every vehicle.
Since |v| is the same for all of the vehicles, the uk’s can
be mapped bijectively to the vehicles’ minimum turn radius
values.
Given these vehicles, the problem is formulated on a
directed graph G = (V, E) where E is the set of directed edges
joining any two vertices in V . We assume that the graph
G does not have any self-loops. For each edge (i, j) ∈E
and each vehicle k, let ck
ij be the length of the minimum
distance path for the vehicle k to traverse the edge from
target i to target j with angles of departure and arrival δi
and δj, respectively. This length can be computed using the
well-known result of Dubins [24].
Also, associated with target–vehicle pair [i,k] is a stochas-
tic service time that denotes the time to establish a commu-
nication link for the vehicle k with target i when the vehicle
visits the target i. Let ˜τ = (˜τik) for every i ∈T and vehicle k
denote the non-negative random vector of service times. We
use τ to denote a realization of the random vector ˜τ. The
number of possible realizations of the service time random
variable vector τ (support of τ) is assumed to be finite; this
is a very reasonable assumption as this is usually the only
kind of data available based on past runs of the mission. Let
the realizations of ˜τ be indexed by ω ∈Ωso that they can
be enumerated τ ω, ω ∈Ω, with probability mass function
pω = Pr(˜τ = τ ω), ω ∈Ω. We use boldface notation here
and throughout the rest of the paper to denote vectors, e.g.
pω = (pω
ik). Also, associated with each vehicle–target pair is
a preset constant, ¯τik, which denotes the maximum time the
vehicle k can service at target i. Finally, we let γk denote
a non-negative penalty per unit time of the excess duration
spent on servicing any of the targets visited by vehicle k.
III. A TWO-STAGE STOCHASTIC FORMULATION
In this section, we develop a two-stage stochastic for-
mulation with simple recourse for the HMDMVPP-RST.
We now define the decision variables required for the two-
stage stochastic formulation of the HMDMVPP-RST. For
each vehicle k ∈{1, . . . ,n}, we associate with each edge
(i, j) ∈E, a binary variable xk
ij which takes a value 1 if
the vehicle k traverses the edge (i, j) and 0 otherwise. From
here on, throughout the rest of the article, we denote the set
of vehicles {1, . . . ,n} using K. Similarly for each vehicle
k ∈K and each target i ∈T, yk
i denotes a binary assignment
variable that takes a value 1 if the target i is visited by vehicle
k and 0 otherwise. For each vehicle k ∈K, let zω
k denote the
excess duration in the total service time spent by the vehicle
k on all the targets it visits, for the realization ω ∈Ωof the
random service times. Using the above notations and those
introduced in Sec. II, the two-stage stochastic formulation
for the HMDMVPP-RST is as follows:
A. Objective:
S(x, y, zω) : min
Õ
k ∈K
©­
«
Õ
(i,j)∈E
ck
ijxk
ij
ª®
¬
+ Eτ
 Õ
k ∈K
γkzω
k
!
.
(1)
The objective (1) minimizes the sum of the total travel
distance and the expected sum of the penalties incurred by
all the vehicles for the excess duration spent on servicing
all the targets. Here, E is the expectation operator over the
random variable τ. We refer to the total travel distance and
the expected penalty as the first-stage cost and the second-
stage/recourse cost, respectively.
B. Degree constraints:
Õ
j ∈V
xk
ij = yk
i
∀i ∈T,k ∈K and
(2)
Õ
j ∈V
xk
ji = yk
i
∀i ∈T,k ∈K.
(3)
The constraints (2) and (3) ensure that the out-degree and
in-degree of a target that is visited by vehicle k ∈K is 1,
respectively.
C. Sub-tour elimination constraints:
Õ
(i,j)∈E
i ∈S,j<S
xk
ij ≥yk
i
∀i ∈S,S ⊆T,k ∈K.
(4)
The constraints in (4) eliminate sub-tours of any subset
of targets for each vehicle; they also ensure that for each
vehicle, its path remains connected. They are also referred
to as connectivity constraints.
D. Vehicle–target assignment constraints:
Õ
k ∈K
yk
i = 1
∀i ∈T and
(5)
yk
i = 1
∀k ∈K,i ∈Rk
(6)
The constraints in (5) ensure that each target is visited by
some vehicle and the constraints (6) are the vehicle–target
assignments for the functional heterogeneous targets.
E. Service time constraints:
Õ
i ∈T
¯τik −τ ω
ik

 yk
i + zω
k ⩾0
∀k ∈K,ω ∈Ωand
(7)
zω
k ⩾0
∀k ∈K,ω ∈Ω.
(8)
The term

τ ω
ik −¯τik

yk
i in constraint (7) represents the excess
service time spent by vehicle k at target i. The constraints
(7) together with (8) imply that a penalty would be incurred
by the vehicle only if the total duration of service time spent
by the vehicle on all the targets it visits exceeds the sum
of the maximum allowed service times at all of the visited
targets.
F. Variable restrictions:
xk
ij ∈{0, 1}
∀e ∈E,k ∈K and
(9)
yk
i ∈{0, 1}
∀i ∈T,k ∈K.
(10)
The constraints in (9) and (10) denote the binary restrictions
on the decision variables.
We now present some interesting properties of the two-
stage stochastic formulation for a single vehicle variant of
the HMDMVPP-RST.
Proposition
1.
For
a
single
vehicle
variant
of
the
HMDMVPP-RST, the optimal path for the UV is given by
an instance of the deterministic traveling salesman problem.
Proof. For a single vehicle problem, K = {1} and the
assignment constraints in (5) reduce to y1
i = 1 for every
target i ∈T. Hence, the yk
i variables in the the two-stage
stochastic formulation can be eliminated. Then, the service
time constraints in (7) reduces to
Õ
i ∈T
¯τi1 −τ ω
i1

 + zω
1 ⩾0
∀ω ∈Ω.
The above constraint does not contain any edge decision vari-
ables xk
ij, effectively decomposing the problem to a traveling
salesman problem and an expected penalty minimization
problem which is given by the following linear program:
min Eτ
γ1zω
1

 subject to:
Õ
i ∈T
¯τi1 −τ ω
i1

 + zω
1 ⩾0
∀ω ∈Ωand
zω
1 ⩾0
∀ω ∈Ω.
Hence, the optimal path for the single UV can be computed
independently by solving a traveling salesman problem.
□
G. Value of Stochastic Solution (VSS)
We now present a measure to compare the significance
of the solution obtained by solving the two-stage stochas-
tic problem for the HMDMVPP-RST with respect to the
deterministic version of the problem, referred to as the
Expected Value Problem (EVP) in the literature [23]. Given
the HMDMVPP-RST, a natural predisposition is to take
expectation over the service time for each vehicle–target pair
and solve the following deterministic problem to obtain paths
for each vehicle.
D(x, y, z) : ©­
«
min
Õ
k ∈K
Õ
(i,j)∈E
ck
ijxk
ij
ª®
¬
+
 Õ
k ∈K
γkzk
!
s.t.
constraints (2), (3), (4), (5), (6), (9), (10),
Õ
i ∈T
¯τik −Eτ(τ ω
ik)
 yk
i + zk ⩾0, and zk ⩾0
∀k ∈K.
The problem D is analogous to a single scenario, two-
stage stochastic version of the HMDMVPP-RST that utilizes
the expected service time for each vehicle–target pair. We
remark that in the above formulation, the variable vector z
is not a function of the realizations, ω ∈Ω. Let (x∗, y∗)
denote the vector of optimal first stage decisions for the EVP
that represents the optimal paths for each vehicle with the
vehicle–target assignment. The VSS is a measure of how
good (or more frequently, how bad) a decision (x∗, y∗) is in
terms of the two-stage stochastic problem. To that end, let S∗
denote the optimal objective value to the two-stage stochastic
problem in 1, and let D∗= S(x∗, y∗, zω); D∗is the optimal
objective value of the two-stage stochastic problem obtained
by fixing the first stage solution (x∗, y∗) obtained from the
EVP. Then the Value of the Stochastic Solution (VSS) is
given by
VSS = D∗−S∗.
VSS provides the cost of ignoring uncertainty in choosing
a decision. For any stochastic program, it is known in the
literature that VSS ⩾0 [23], [25]. We also note that the
Prop. 1 can be equivalently stated as: VSS = 0 for the single
vehicle case of the HMDMVPP-RST.
IV. ALGORITHM
In this section, we briefly present the main ingredients of
a branch-and-cut algorithm that is used to solve the formu-
lation in the Sec. III to optimality. The two-stage stochastic
formulation developed in the Sec. III for the HMDMVPP-
RST can be provided to off-the-shelf commercial branch-
and-cut solvers to obtain an optimal solution. But, the
formulation contains the sub-tour elimination constraints (4)
for each vehicle which enforce any feasible solution to the
problem to not contain any sub-tours of the targets. The
number of such constraints is exponential and it may not be
computationally efficient to enumerate all these constraints
and provide them to these solvers. To address this issue, we
use the following approach: we relax these constraints from
the formulation, and whenever the solver obtains an integer
feasible solution to this relaxed problem (or a fractional solu-
tion with integrality constraints dropped), we check if any of
these constraints are violated by the feasible solution, integer
or fractional. If so, we add the constraint dynamically and
continue solving the original problem. This process of adding
constraints to the problem sequentially has been observed to
be computationally efficient for the deterministic traveling
salesman problem and some of its variants [8], [26]–[28].
The algorithms used to identify violated constraints are
referred to as separation algorithms.
We shall now detail the separation algorithm used to
dynamically identify violated sub-tour elimination constraint
(4) given a fractional solution. For every vehicle k ∈K,
G∗
k = (V ∗
k , E∗
k) denotes the support graph associated with a
given fractional solution (x∗, y∗), i.e., V ∗
k := {i ∈T : yk∗
i
>
0} ∪{dk} and E∗
k := {(i, j) ∈E : xk∗
ij > 0}. Here, x and y are
the vectors of the decision variable values in HMDMVPP-
RST. To check if any of the sub-tour elimination constraints
in (4) are violated given an integer (fractional) solution, we
first examine the strongly connected components in G∗
k. Each
strongly connected component C that does not contain the
depot dk generates a violated sub-tour elimination constraint
for S = C and for each i ∈S. We now define δ+(S) := {(i, j) ∈
E : i ∈S, j < S}. If a connected component C contains the
depot dk the following procedure is used to find the largest
violated sub-tour elimination constraint in xk(δ+(S)) ⩾yk
i .
Given a strongly connected component C that contains a
depot dk, i ∈C \ {dk}, and a fractional solution (x∗, y∗),
the most violated constraint of the form xk(δ+(S)) ≥yk
i
can be obtained by computing a minimum s −t cut on a
capacitated directed graph ¯Gk = ( ¯Vk, ¯Ek), with ¯Vk = V ∗
k . The
vertex s denotes the source vertex and s = dk. The vertex t
denotes the sink vertex and t = i, and the edge set is given
by ¯Ek = E∗
k. Every edge (i, j) ∈¯Ek is assigned a capacity
xk∗
ij . We now compute the minimum s −t cut (S, ¯Vk \S) with
t ∈¯Vk \S. The vertex set S′ = ¯Vk \S defines the most violated
inequality if the capacity of the cut is strictly less than yk∗
i .
Clearly, the targets i with yk∗
i
= 0 need not be considered.
This algorithm can be repeated for every vehicle to generate
the violated sub-tour elimination constraints. Once the set
S′ that defines a violated sub-tour elimination constraint is
obtained, this constraint is added to the formulation and the
branch-and-cut algorithm is continued.
V. COMPUTATIONAL RESULTS
We now present detailed computational results to corrob-
orate the effectiveness of the two-stage stochastic approach
to deal with uncertainty in service times, by comparing its
solution with the deterministic EVP. All the simulation ex-
periments were performed on a MacBook Pro with a 2.9 GHz
Intel Core i5 processor and 16 GB RAM using CPLEX 12.7
as a mixed-integer linear programming solver. The branch-
and-cut algorithm with the dynamic cut-generation routine
presented in Sec. IV was implemented in C++ using the
callback functionality of CPLEX. The internal cut-generation
routines of CPLEX were switched off and CPLEX was used
only to manage the enumeration tree in the branch-and-cut
algorithm. All computation times are reported in seconds and
an upper limit of 3600 seconds was imposed on each run of
the algorithm. The performance of the algorithm was tested
on instances generated from the traveling salesman problem
library (TSPLIB) [29].
A. Instance Generation
We generated 13 instances containing 29 targets from
one TSPLIB instance named bays29. Since the objective of
this paper is to present a two-stage framework to address
stochasticity in path planning problems for heterogeneous
UVs, we restrict the total number of instances to a small
value and concentrate on its merits over the deterministic
EVP. The number of vehicles, n, and the number of func-
tional heterogeneous targets for every vehicle, Rk, in the
single TSPLIB instance with 29 targets is varied in the
sets {1, 2, 3, 4, 5} and {1, 3, 5}, respectively. For the instance
with just one vehicle, no functional heterogeneous targets are
present; this instance is merely used to illustrate the result in
Prop. 1. The depot locations for the vehicles and their desired
heading angles at the vertices were uniformly randomly
generated. The minimum turn radius of the vehicles were
generated according to the following procedure: for each
instance, the grid size д was computed to be the maximum
of the coordinates of all the vertices; now the minimum turn
radius was computed using the formula 3 · k · д/100 where
k = 1, · · · ,n. The minimum length path for each pair of
vertices was computed using the results of and Dubins [24].
We assign a name to each of the 13 instances and the names
conform to the format “bays29-n-f ”, where n and f are the
number of vehicles and number of functional heterogeneous
targets per vehicle, respectively. 100 scenarios for the service
times for each vehicle–target pair, τ ω
ik, are generated ran-
domly from a uniform distribution; each scenario is assumed
to be equally likely and hence pω
ik =
1
|Ω|, where |Ω| = 100.
The maximum allowable service time for each vehicle–target
pair, ¯τik is set to the average of τ ω
ij , ω ∈Ω, offset by a
random value from [−3, 3] and the penalties γk is set to 1000
for every k.
B. Computation times
The computation times for the algorithm to compute the
optimal solution with 100 scenarios for each of the 13
instances is shown in Table I. For instances with around 30
targets and 100 scenarios, the branch-and-cut algorithm is
observed to be reasonably fast and can compute the optimal
solution within half a minute. We remark that no simulation
experiments have been performed to test the scalability of
the algorithm with increasing number of targets or number
of scenarios. As elaborated in the Sec. I-A, developing
decomposition algorithms to solve the formulation in Sec.
III for large instances of the problem with approximately
100 targets and greater than 1000 scenarios is a separate
research topic; we delegate this algorithmic development for
future work.
TABLE I
COMPUTATION TIME IN SECONDS WITH 100 SCENARIOS
instance name
computation time (sec)
bays29-1-0
0.16
bays29-2-1
5.10
bays29-2-3
1.13
bays29-2-5
1.54
bays29-3-1
7.88
bays29-3-3
1.01
bays29-3-5
0.28
bays29-4-1
8.22
bays29-4-3
2.72
bays29-4-5
0.13
bays29-5-1
17.88
bays29-5-3
1.79
bays29-5-5
0.11
C. Branch-and-cut algorithm performance
The main advantage of the branch-and-cut algorithm is
that it can deal with the exponential number of sub-tour
elimination or connectivity constraints (in Eq. (4)) by dy-
namically generating them as and when they are violated
by the current feasible solution in the enumeration tree. This
procedure of dynamically generating the constraints is found
to be very effective since only a fraction of the total number
of connectivity constraints are required for convergence to
the optimal solution; this is corroborated by the results in
Fig. 1.
0
100
200
300
400
500
600
bays29-1-0
bays29-2-1
bays29-2-3
bays29-2-5
bays29-3-1
bays29-3-3
bays29-3-5
bays29-4-1
bays29-4-3
bays29-4-5
bays29-5-1
bays29-5-3
bays29-5-5
# of constraints (4) added
Fig. 1. Number of connectivity constraints (4) added by the branch-and-cut
algorithm
D. Comparison to the EVP
In this section, we explicitly compute the VSS, defined in
Sec. III-G, for all the instances. The Table II shows the cost
of the solution obtained via the two-stage stochastic program
(S∗) and the cost obtained by using the solution of the EVP
in the two-stage stochastic program (D∗), respectively. The
first entry in Table II has a VSS value of zero, since it is a
single vehicle variant of the problem (see Prop. 1). The Fig.
2 shows the extra computation time in seconds to solve the
EVP when compared to the two stage stochastic formulation.
This is not surprising because, the two-stage problem is a
much more difficult problem as it accounts for uncertainty
in the service times whereas the deterministic EVP accounts
for the uncertainty only using the expectation. Nevertheless,
efficient decomposition techniques can be utilized to reduce
the gap within a stipulated runtime.
TABLE II
VALUE OF STOCHASTIC SOLUTION (VSS)
instance name
D∗
S∗
VSS
bays29-1-0
16,574.10
16,574.1
0.00
bays29-2-1
17,996.70
15,830.6
2,166.10
bays29-2-3
16,195.50
15,720.0
475.50
bays29-2-5
18,993.20
18,475.5
517.70
bays29-3-1
17,918.80
16,391.4
1,527.40
bays29-3-3
22,345.60
20,319.6
2,026.00
bays29-3-5
23,869.50
23,199.3
670.20
bays29-4-1
20,226.40
19,194.1
1,032.30
bays29-4-3
30,235.30
26,952.0
3,283.30
bays29-4-5
32,883.50
32,769.1
114.40
bays29-5-1
24,817.10
23,389.1
1,428.00
bays29-5-3
35,212.50
33,167.3
2,045.20
bays29-5-5
46,496.20
46,062.2
434.00
0
2
4
6
8
10
12
14
bays29-1-0
bays29-2-1
bays29-2-3
bays29-2-5
bays29-3-1
bays29-3-3
bays29-3-5
bays29-4-1
bays29-4-3
bays29-4-5
bays29-5-1
bays29-5-3
bays29-5-5
Excess computation time (seconds)
Fig. 2.
Additional computation time to solve the two-stage stochastic
formulation when compared to the EVP
Fig. 3 and 4 show the optimal paths obtained from the
two-stage stochastic program and the EVP for the instance
0
200
400
600
800
1000
1200
1400
1600
1800
2000
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
Functional Heterogeneous targets
Depots
Targets
Vehicle 1
Vehicle 2
Fig. 3.
Optimal paths computed by the two-stage stochastic formulation
for the instance bays29-2-1
0
200
400
600
800
1000
1200
1400
1600
1800
2000
400
600
800
1000
1200
1400
1600
1800
2000
2200
2400
Functional Heterogeneous targets
Depots
Targets
Vehicle 1
Vehicle 2
Fig. 4.
Optimal paths computed by the EVP for the instance bays29-2-1
bays29-2-1, respectively; the instance has two vehicles and
one functional heterogeneous target per vehicle. The travel-
ing cost for the vehicles (the first-stage costs) are 14, 975.4
and 14, 004.7 for the two-stage stochastic program and the
EVP for the instance bays29-2-1, respectively. Though the
EVP produces paths for the vehicles whose total cost is less
than the two-stage stochastic program, the expected penalty
incurred by the EVP solution would be much higher than
that produced the two-stage stochastic program (see row 2
in Table II).
VI. CONCLUSION
This paper formulates the multiple depot heterogeneous
multiple vehicle problem with random service times for
each vehicle–target pair as a two-stage stochastic problem
with recourse. The formulation is compared with the deter-
ministic expected value problem formulation and theoretical
conditions under which both the formulations are equivalent
are derived. The two formulations are compared using the
value of the stochastic solution (VSS), which measures
the cost of including uncertainty in the decision making
process. A branch-and-cut algorithm to solve the two-stage
stochastic formulation to optimality is then developed fol-
lowed by extensive computational results. Future work can
include developing computationally efficient algorithms us-
ing decomposition–based techniques and scale the algorithm
both in terms of the number of targets and in terms of the
number of scenarios.
REFERENCES
[1] J. F. Shanahan, J. S. Schepers, D. D. Francis, G. E. Varvel, W. W.
Wilhelm, J. M. Tringe, M. R. Schlemmer, and D. J. Major, “Use
of remote-sensing imagery to estimate corn grain yield,” Agronomy
Journal, vol. 93, no. 3, pp. 583–589, 2001.
[2] H. Ferreira, C. Almeida, A. Martins, J. Almeida, N. Dias, A. Dias,
and E. Silva, “Autonomous bathymetry for risk assessment with roaz
robotic surface vehicle,” in Oceans 2009-Europe.
IEEE, 2009, pp.
1–6.
[3] D. W. Casbeer, R. W. Beard, T. W. McLain, S.-M. Li, and R. K.
Mehra, “Forest fire monitoring with multiple small uavs,” in American
Control Conference, 2005. Proceedings of the 2005.
IEEE, 2005, pp.
3530–3535.
[4] C. Corrigan, G. Roberts, M. Ramana, D. Kim, and V. Ramanathan,
“Capturing vertical profiles of aerosols and black carbon over the in-
dian ocean using autonomous unmanned aerial vehicles,” Atmospheric
Chemistry and Physics Discussions, vol. 7, no. 4, pp. 11 429–11 463,
2007.
[5] K. Sundar and S. Rathinam, “Route planning algorithms for unmanned
aerial vehicles with refueling constraints,” in American Control Con-
ference (ACC), 2012.
IEEE, 2012, pp. 3266–3271.
[6] ——, “Algorithms for routing an unmanned aerial vehicle in the
presence of refueling depots,” IEEE Transactions on Automation
Science and Engineering, vol. 11, no. 1, pp. 287–294, 2014.
[7] D. Levy, K. Sundar, and S. Rathinam, “Heuristics for routing het-
erogeneous unmanned vehicles with fuel constraints,” Mathematical
Problems in Engineering, vol. 2014, 2014.
[8] K. Sundar, S. Venkatachalam, and S. Rathinam, “Formulations and
algorithms for the multiple depot, fuel-constrained, multiple vehicle
routing problem,” in IEEE American Control Conference (ACC), 2016,
pp. 6489–6494.
[9] ——, “An exact algorithm for a fuel-constrained autonomous vehicle
path planning problem,” arXiv preprint arXiv:1604.08464, 2016.
[10] K. Sundar and S. Rathinam, “Algorithms for heterogeneous, multiple
depot, multiple unmanned vehicle path planning problems,” Journal
of Intelligent & Robotic Systems, pp. 1–14, 2016.
[11] ——, “An exact algorithm for a heterogeneous, multiple depot,
multiple traveling salesman problem,” in Unmanned Aircraft Systems
(ICUAS), 2015 International Conference on.
IEEE, 2015, pp. 366–
371.
[12] A. S. Kenyon and D. P. Morton, “Stochastic vehicle routing with
random travel times,” Transportation Science, vol. 37, no. 1, pp. 69–
82, 2003.
[13] G. Laporte, F. Louveaux, and H. Mercure, “The vehicle routing
problem with stochastic travel times,” Transportation science, vol. 26,
no. 3, pp. 161–170, 1992.
[14] X. Li, P. Tian, and S. C. Leung, “Vehicle routing problems with
time windows and stochastic travel and service times: Models and
algorithm,” International Journal of Production Economics, vol. 125,
no. 1, pp. 137–145, 2010.
[15] G. Laporte, “The vehicle routing problem: An overview of exact and
approximate algorithms,” European journal of operational research,
vol. 59, no. 3, pp. 345–358, 1992.
[16] J. Oyola, H. Arntzen, and D. L. Woodruff, “The stochastic vehicle
routing problem, a literature review,” 2016.
[17] J. F. Benders, “Partitioning procedures for solving mixed-variables
programming problems,” Numerische mathematik, vol. 4, no. 1, pp.
238–252, 1962.
[18] R. D. Wollmer, “Two stage linear programming under uncertainty with
0–1 integer first stage variables,” Mathematical Programming, vol. 19,
no. 1, pp. 279–288, 1980.
[19] M. Gendreau, G. Laporte, and R. Séguin, “Stochastic vehicle routing,”
European Journal of Operational Research, vol. 88, no. 1, pp. 3–12,
1996.
[20] P. Toth and D. Vigo, Vehicle routing: problems, methods, and appli-
cations.
SIAM, 2014.
[21] E. Beier, S. Venkatachalam, L. Corolli, and L. Ntaimo, “Stage-
and scenario-wise fenchel decomposition for stochastic mixed 0-1
programs with special structure,” Computers & Operations Research,
vol. 59, pp. 94–103, 2015.
[22] S. Venkatachalam, “Algorithms for stochastic integer programs using
fenchel cutting planes,” Ph.D. dissertation, Texas A&M University,
2014.
[23] J. R. Birge and F. Louveaux, Introduction to stochastic programming.
Springer Science & Business Media, 2011.
[24] L. E. Dubins, “On curves of minimal length with a constraint on
average curvature, and with prescribed initial and terminal positions
and tangents,” American Journal of mathematics, vol. 79, no. 3, pp.
497–516, 1957.
[25] A. Madansky, “Inequalities for stochastic linear programming prob-
lems,” Management science, vol. 6, no. 2, pp. 197–204, 1960.
[26] K. Sundar and S. Rathinam, “Multiple depot ring star problem: a poly-
hedral study and an exact algorithm,” Journal of Global Optimization,
pp. 1–25, 2016.
[27] ——, “Generalized multiple depot traveling salesmen problem–
polyhedral study and exact algorithm,” Computers & Operations
Research, vol. 70, pp. 39–55, 2016.
[28] S. G. Manyam, D. W. Casbeer, and K. Sundar, “Path planning for
cooperative routing of air-ground vehicles,” in American Control
Conference (ACC), 2016.
IEEE, 2016, pp. 4630–4635.
[29] G. Reinelt, “Tsplib-a traveling salesman problem library,” ORSA
journal on computing, vol. 3, no. 4, pp. 376–384, 1991.