The traveling salesman problem with multi-visit drone
Journal of Computer Science and Cybernetics, V.37, N.4 (2021), 465–493
DOI 10.15625/1813-9663/37/4/16180
THE TRAVELING SALESMAN PROBLEM WITH
MULTI-VISIT DRONE
1
1
2
1,∗
`
QUANG MINH HA , DUY MANH VU , XUAN THANH LE , MINH HOANG HA
`
1ORLab, Faculty of Computer Science, Phenikaa University, Hanoi, Vietnam
2Institute of Mathematics, Vietnam Academy of Science and Technology, Hanoi, Vietnam
Abstract. This paper deals with the Traveling Salesman Problem with Multi-Visit Drone (TSP-
MVD) in which a truck works in collaboration with a drone that can serve up to q ≥ 1 customers
consecutively during each sortie. We propose a Mixed Integer Linear Programming (MILP) formu-
lation and a metaheuristic based on Iterated Local Search (ILS) to solve the problem. Benchmark
instances collected from the literature of the special case with q = 1 are used to test the performance
of our algorithms. The obtained results show that our MILP model can solve a number of instances to
optimality. This is the first time optimal solutions for these instances are reported. Our ILS performs
better than other algorithms in terms of both solution quality and running time on several instance
classes. The numerical results obtained by testing the methods on new randomly generated instances
show again the effectiveness of the methods as well as the positive impact of using the multi-visit
drone.
Keywords. Traveling salesman problem; Multi-visit drone; Mixed Integer Linear Programming;
Iterated Local Search.
1. INTRODUCTION
Recently, routing problems using the combination of trucks and drones to deliver services
have received much attention. In the notable work of [10], the authors introduced a new
transportation system in which a truck and a drone (an unmanned aerial vehicle – UAV
– used for commercial purposes) are coupled to deliver parcels to customers. Being able
to be launched from the truck, the drone then flies to a single customer location for the
delivery before returning to the rendezvous point where it will be retrieved by the truck and
being prepared for the next launches. The objective function considered in the problem is
to minimize the completion time of both vehicles, i.e. the latest time both vehicles return
to a depot. The problem was named as “Flying Sidekick Traveling Salesman Problem with
Drone” (FSTSP) and has opened a new research direction on routing problems with trucks
and drones.
Dedicated to Professor Phan Dinh Dieu on the occasion of his 85th birth anniversary.
*Corresponding author.
2021 Vietnam Academy of Science & Technology
466
QUANG MINH HA, et al.
A different variant of the problem was introduced in [1]. Although the objective function
of both variants is to minimize the completion time of two vehicles, the problem in the latter
work assumed a different hypothesis where the launch and rendezvous points could be at the
same location (meaning that the truck could launch the drone and then stay to wait for its
return). In [6], the authors presented a similar problem but considered a different objective
function which minimizes the total transportation cost. They called the problem as min-cost
Traveling Salesman Problem with Drone (TSP-D) and the original variant FSTSP as min-
time TSP-D. This paper also proposed a metaheuristic based on the Greedy Randomized
Adaptive Search Procedure (GRASP) to efficiently solve both variants.
Shortly after, Carlsson and Song [2] delivered a research in which the authors also eval-
uated the efficiency of the TSP-D by providing numerous theoretical analysis as well as the
computational results. The authors also named the problem the “horsefly routing problem”
with the objective to minimize the completion time of the vehicles, which is similar to the
variant proposed by [10] except that the number of drones is not strictly limited to one, but
is generalized to become a parameter of the problem. Additionally, the study of the upper
and lower bounds for the completion time of the TSP-D is also conducted. For the solution
approach, a metaheuristic is proposed in which TSP-D solutions are iteratively built starting
from an optimal TSP solution. From this work, the authors concluded that the improvement
in completion time due to the use of drone is proportional to the square root of the ratio of
the speeds of the truck and the drone.
In [3], the authors proposed a hybrid heuristic named HGVNS to solve two TSP-D vari-
ants proposed in [1, 10] with the min-time objective. In detail, HGVNS first creates an initial
solution which is the optimal TSP tour by using a MILP solver and then applies a heuristic
in which some customers on the truck tours are removed and reinserted as drone customers.
Next, the initial solution is used as the input for a general variable neighbourhood search
in which eight neighbourhoods are shuffled and chosen randomly. The authors conducted
the experiments on three instance sets from [1, 15] and TSPLIB. The computational results
show that the proposed approach can decrease delivery time by up to 67.79%.
In [7], a hybrid genetic algorithm (HGA) was proposed to solve the TSP-D problems with
both min-time and min-cost objectives. The authors proposed a hybrid genetic search with
dynamic population management and adaptive diversity control based on a split algorithm,
problem-tailored crossover and local search operators, a new restore method to advance the
convergence and an adaptive penalization mechanism to dynamically balance the search
between feasible/infeasible solutions. The computational results showed that the new algo-
rithm outperforms two existing heuristic methods of [6, 10] in terms of solution quality and
improves many best known solutions found in the literature. Recent exact methods to solve
the FSTSP can be found in [20, 21, 22].
Apart from the works that investigate the original TSP-D variant where one truck and
one drone are used for delivery, there exists many other variants of the TSP-D as well as
its generalization – the Vehicle Routing Problem with Drone (VRP-D) – that have been
studied in many other researches. In [11], the authors extended the original work [10] –
the FSTSP – to introduce a new problem called “The multiple Flying Sidekick Traveling
Salesman Problem” (mFSTSP) where multiple drones are used with a truck to make the
deliveries. Again, the authors formulated the problem with a mixed integer programming
formulation and proposed a three-phase heuristic to solve the problem with various size
THE TRAVELING SALESMAN PROBLEM
467
up to 100 customers. The computational results showed that this variant can improve the
truck-only delivery problem (the TSP) by up to 23%.
The extension of TSP-D to the mTSP-D was introduced in the work of [8] where a fleet
of trucks and drones are used for delivery. However, instead of fixing the pair of truck and
drone (i.e. a truck only carries and works with one identical drone, not others), the problem
allows the drones to return to any available trucks. The authors presented a mixed integer
programming model for the mTSP-D and developed a heuristic called “Adaptive Insertion
Heuristic” (ADI) to solve the problem. The computational results showed that there is a
potential gain for the mTSP-D comparing to the original TSP-D.
In [17], the authors introduced a more general problem that copes with multiple trucks
and drones under the objective function of minimizing the completion time. The authors
named the problem “The vehicle routing problem with drone” (VRP-D) and conducted
the analysis on several worst-case scenarios, from which they proposed bounds on the best
possible savings in time when using drones and trucks instead of trucks alone. A further
development of this research was studied in [14] where the authors extended the worst-case
bounds to more generic distance/cost metrics as well as explicitly considered the limitation
of battery life and cost objectives.
More recently, the authors of [18] introduced a further work of the VRP-D by proposing
a mixed integer programming model for the problem (an arc-based model) to develop a
branch-and-price algorithm. The experiment was run and conducted on 10 and 15-customer
instances. The results showed that by using MILP solver with the proposed branch-and-price
algorithm, the authors can deliver the optimal solutions of these instances in the average of
7 minutes and 4 hours for two types of instances above. Furthermore, it was reported that
a VRP-D solution could save up to 20% of the cost comparing to the traditional VRP.
In all the studies mentioned above, a drone is supposed to visit a single customer during
a flight. This limitation would be broken in very near future as shown in [13] where the
authors studied a new variant of the TSP-D called the “Multi-visit drone routing problem”.
In this work, instead of being limited to carry one parcel at a time, the drone is able to carry
and visit multiple customer locations before returning to the truck for recharging/taking new
parcels. Additionally, the authors also considered that the drone has a fixed energy capacity
instead of a fixed flight time to cope with the variety of parcels’ weight. A descriptive model
and various theoretical analysis were proposed. For solving the problem more effectively, a
local search method was introduced using a Swap-based operator. Extensive computational
results have been conducted to analyse the performance and sensitivity of the factors (i.e.
drone speed and battery). Finally, the authors also extended this model to cope with more
than one drone, which leads to a more general problem.
A recent work [9] proposed a similar variant of the min-cost TSP-D where a drone is
able to service multiple customers before returning to the truck. It was assumed that the
truck must reach the rendezvous point before the drone for security reasons. In addition,
as the problem considered in [13], the authors considered the effect of varying payload on
energy consumption and required that the truck cannot visit multiple customers while the
drone performs its flight. They proposed a two-stage, route-based modeling approach to
optimize both truck’s main route and the drone’s flying schedule. To construct the initial
solution, a hybrid heuristic combining a nearest-neighbor and cost-saving strategies was
used. To improve this initial solution, the author applied the Simulated Annealing (SA)
468
QUANG MINH HA, et al.
metaheuristic. Moreover, an experiment was conducted using randomly generated customer
locations as well as a practical road network of in Changsha, China. The computational
results analysed the overall performance of the SA as well as the sensitivity of different
factors such as the ratio of light parcels, the drone’s capacity, and drone endurance.
In this research, we study a more general variant of the FSTSP in [10] in which the drone
can deliver several parcels in a flight. We call the problem as the Traveling Salesman Problem
with Multi-Visit Drone (TSP-MVD). Compared with the problems considered in [9, 13], our
problem are more general when we allow the truck can visit multiple customers when the
drone flies in the air. We also consider that the launching and retrieving times of the drone
are significant, leading to more complex synchronization operations. However, to simplify
the model, we do not take into account the effect of parcels’ load on energy consumption of
the drone. Our contributions in this paper are as follows:
We propose a new MILP model for a TSP-D variant in which the drone can deliver sev-
eral parcels during a flight, from which small-size instances can be solved to optimality.
We propose an Iterated Local Search (ILS) that could effectively solve the TSP-MVD.
Our algorithm include several problem-tailored components such as: (i) a solution
representation based on a new split method to transform a TSP tour to a TSP-MVD
solution optimally (given the relative orders of the nodes are fixed), (ii) four new local
search operators to specifically handle the “multi-visit” characteristic of the drone, and
(iii) adapted perturbation operators.
We conduct several experiments to test the performance of our proposed methods. Our
MILP model can find optimal solutions for a number of open benchmark instances in
the literature while our ILS can perform better when compared with existing algorithms
on several class of instances in terms of solution quality and running time. The impact
of the limit of drone-visits on the TSP-MVD solutions is also conducted to investigate
the benefit of using the multi-visit drone.
This paper is organized as follows. After this introduction, Section 2 gives the precise
description of the TSP-MVD. In Section 3, we construct a mixed integer linear programming
(MILP) formulation for the TSP-MVD. Section 4 discusses our Iterated Local Search (ILS)
algorithm to solve this problem. Numerical experiments are presented in Section 5. Finally,
Section 6 closes this paper with some conclusions.
2. PROBLEM DESCRIPTION
In this section we give a precise description of the TSP-MVD. We are given n different
customer locations, each one must be served exactly once by either a truck (driver-operated
vehicle) or a drone (unmanned aerial vehicle) operating in coordination with the truck. The
truck and the drone must depart from a single depot (distribution center), and return to
that depot only when all the customers are served. Although the physical location of the
depot exists uniquely, for the sake of distinguishing the departure and arrival events of the
vehicles at the depot, we assign to it two node numbers 0 and n+1. The two vehicles depart
from the depot at node 0 and return to the depot at node n+1. Let V = {0, 1, . . . , n+1} be
the set of nodes representing the customer locations (numbered from 1 to n) and the depot
together with its duplication (numbered by 0 and n + 1).
THE TRAVELING SALESMAN PROBLEM
469
At the depot, the two vehicles can depart or return either independently or in tandem.
The drone may make multiple sorties during the delivery service. A drone sortie starts by
launching the drone either at the depot or from a customer location. During a drone sortie,
both the truck and the drone can visit multiple nodes to deliver parcels to corresponding
customers. However, due to some technical characteristics, the drone payload and flight
endurance are restricted, hence the number of drone visits in each sortie is limited. We
assume that the maximum number of customer locations that can be served by the drone
in each sortie is q (q ≥ 1). We assume furthermore that the drone cannot reconnect with
the truck at some intermediate location, hence a drone sortie must end at either the depot
or a customer location where the drone is retrieved by the truck. We can represent a drone
sortie as a 3-tuple ⟨i, J, k⟩ in which i is the launch node where the truck releases the drone
for delivering, J is a sequence of at most q nodes corresponding to the customers served by
the drone in the sortie, and k is the rendezvous node where the drone returns to the truck.
Since the truck also visits the launch node and the rendezvous node in each sortie of the
drone, the customers at these nodes are better served by the truck driver. Therefore, for a
drone sortie ⟨i, J, k⟩ we have i ∉ J, k ̸∈ J, i ̸= k, |J| ≤ q, the nodes in J are served by the
drone, while the nodes i and k are served by truck if they are not depot nodes.
Before each sortie, the drone is loaded with parcels corresponding to some customers,
and its battery is changed if needed. If the drone is transported by the truck between two
consecutive sorties, these actions can be done on the truck to save time. In that case, the
drone can be launched right after its travel to the new launch node. However, if at the
rendezvous node of a sortie the drone is launched again for a new sortie, then it requires a
service time sL before launching to load parcels and to change battery. A service time sR
is required for the truck driver to retrieve the drone in the end of each drone sortie. At the
rendezvous nodes of the drone sorties, two vehicles are required to wait for each other. While
waiting for the truck before being retrieved, the drone is assumed to be in a constant flight.
Furthermore, due to the limited battery capacity, the drone has an endurance e which is its
maximum operating time without charging. The drone endurance must be enough for each
drone sortie ⟨i, J, k⟩, i.e., the total travel time of the drone from the launch node i through
the customer nodes in J to the rendezvous node k and the time of retrieving the drone at
node k cannot exceed e. The drone must be retrieved before it runs out of battery, therefore
the total travel time of the truck during each drone sortie ⟨i, J, k⟩ and its time to retrieve
the drone at node k cannot exceed the drone endurance e.
Due to some technical reasons, not all customer requests can be fulfilled by the drone. For
examples, some parcels exceed the drone payload capacity, some large-size parcels cannot be
handled by the drone, some parcels require customer signature, or some customer locations
are not safe for landing the drone. Therefore, not all customer nodes can be visited by the
drone. We denote VD ⊆ {1, . . . , n} the set of customer nodes that can be served by the
drone.
While not in a sortie, the drone is carried and recharged by the truck. If the drone is
retrieved by the truck at some customer node k, it may be re-launched from that node.
However, once the drone is launched from a customer node i, it must not return to that node
to be retrieved by the truck. Moreover, the truck may not revisit any customer nodes to
retrieve the drone. In this context, neither the truck nor the drone may revisit any customers.
The objective of the TSP-MVD is to minimize the completion time of both vehicles
470
QUANG MINH HA, et al.
(i.e., the time required to serve all customers and return both vehicles to the depot at node
n + 1). It is worth noting that the TSP-MVD can be considered as an extension of the
TSP-D studied in [10]. In the TSP-D, the drone is restricted to serve exactly one customer
in each of its sorties, which corresponds to the case q = 1 in our setting. In our TSP-MVD,
we allow the drone to deliver parcels to multiple customers before returning to the truck.
In the next section we propose a mixed integer programming formulation for the TSP-
MVD. For the mathematical formulation of the problem, we introduce some more notations
and concepts. Let V0 be the set of nodes from which the vehicles may depart, i.e., V0 =
{0, 1, . . . , n}. Let V+ be the set of nodes to which the vehicles may arrive, i.e., V+
=
{1, . . . , n + 1}. Let τij (resp., τi′j) be the time required for the truck (resp., the drone) to
travel from node i ∈ V0 to node j ∈ V+ if the vehicle can visit these nodes. The drone is
active at a node if the node belongs to some sortie of the drone, otherwise it is called inactive
at that node. A node is called an operation node if it is a launch node or an rendezvous node
of the drone. Under this setting, for a drone sortie ⟨i, J, k⟩, the nodes i and k are operation
nodes, and the drone is active at all nodes in J ∪ {i, k}.
3. MIXED INTEGER LINEAR PROGRAMMING FORMULATION
We represent a feasible TSP-MVD solution as the union of its components. Each compo-
nent consists of either the path of the truck together with the path of the drone in a drone
sortie, or the path of the truck carrying the drone on when the drone is not in a sortie. For
simplicity, we label each component by the name of its starting node. In Example 1 we give
a detail description of a solution to a TSP-MVD instance and its components.
Example 1.
Figure 1 illustrates a solution to a TSP-MVD with 10 customer nodes (labeled from 1
to 10) and a depot (represented by node 0 and node 11). In this solution, the truck follows
the paths represented by continuous arrows, while the drone follows the paths represented
by dashed arrows. The solution is composed of five components labeled by their starting
nodes (0, 2, 6, 7, 9). In component 0, the truck starts from the depot node 0 and comes to
serve customers at nodes 1 and 2 while carrying the drone. In component 2, both vehicles
start at node 2 which is the starting node of this component. The drone is launched from
node 2, then comes to serve nodes 4 and 5 before flying to node 6 to be retrieved there. The
truck starts at node 2, then come to serve nodes 3 and 6, and retrieves the drone at node 6.
Node 6 in turn is the starting node of component 6, which consists of only one continuous
arrow from node 6 to node 7. That means in component 6 the truck carries the drone and
comes directly from node 6 to node 7 to serve the customer there. From node 7, which is
the starting node of component 7, the truck goes directly to serve customer 9, while the
drone is launched to serve node 8 before coming to be retrieved at node 9. At this node, the
drone is launched again to join component 9. It flies to serve the customer at node 10 before
returning to the depot at node 11. In this component, the truck goes directly from node 9 to
the depot. In total, the drone makes three sorties during the delivery service. Its first sortie
belongs to component 2 and consists of the drone path 2–4–5–6. The second sortie belongs
to component 7 and consists of the drone path 7–8–9. The last drone sortie is in component
9, in which the drone starts from node 9, then coming to serve customer 10 before returning
THE TRAVELING SALESMAN PROBLEM
471
to the depot. In the solution, the operation nodes are 2, 6, 7, 9, 11, while the drone is active
at nodes 2, 4, 5, 6, 7, 8, 9, 10, 11.
4
5
8
10
0
1
2
3
6
7
9
11
Component 0
Component 2
Component 6
Component 7 Component 9
Figure 1: A solution to a TSP-MVD with its components
3.1. Determining components’ nodes
To determine the components of a solution to TSP-MVD, we introduce binary variables
zk(k ∈ V0) in which
(
1
0
if node k ∈ V0 is the starting node of a component,
otherwise.
zk =
Since the truck must start from the depot for its first departure, node 0 must be the starting
node of a component, hence by the variable definition we have
z0 = 1.
(1)
Apart from the depot node 0, if a node starts a component, then it is also the last node of
the previous component. To unify this structure on the whole solution, we impose
zn+1 = 1
(2)
to indicate that the depot node n + 1 is the last node of the last component.
To determine which node belongs to which component and is served by which vehicle,
we introduce two sets of binary variables xki and x′ki (k ∈ V0, i ∈ V ) in which
(
1
if node i ∈ V belongs to component k and is served by the truck,
otherwise,
xki
=
0
(
1
if node i ∈ V belongs to component k and the drone is active at i,
otherwise.
x′ki
=
0
Note that, by definition, the drone may be active at the starting node and the last node
of a component but inactive at the other nodes of the component. This corresponds to the
situation in which this component is between two consecutive drone sorties. In spirit of the
component concept, each node must belong to at least one component to guarantee that it
is served. A node can belong up to two components when it is a customer node at which
the drone is launched or retrieved. Since the depot node 0 cannot belong to any component
other than component 0, we have
xk0 = 0
x′k0 = 0
∀k ∈ V0\{0}
∀k ∈ V0\{0}
(3)
(4)
Since the delivery service stops at the depot node n+1, this last node must belong to exactly
one component. This fact can be represented by
X
xk,n+1 = 1.
(5)
k∈V0
472
QUANG MINH HA, et al.
By definition of solution components, a component starts at the node of the same label.
Furthermore, if the node is not the depot, then it must be an operation node. Therefore we
have
xkk = zk ∀k ∈ V0,
(6)
(7)
x′kk = zk ∀k ∈ V0\{0}.
For the customer nodes we impose
zi + xki − x′ki ≤ 1 ∀i ∈ V0\{0}, k ∈ V0\{i},
(8)
(9)
zi + x′ki − xki ≤ 1 ∀i ∈ V0\{0}, k ∈ V0\{i},
X
xki ≤ 1 ∀i ∈ V0\{0},
(10)
(11)
(12)
k∈V0\{i}
X
x′ki ≤ 1 ∀i ∈ V0\{0},
k∈V0\{i}
X
X
xki
+
x′ki − zi = 1 ∀i ∈ V0\{0}.
k∈V0\{i}
k∈V0\{i}
These constraints cover the following requirements on the customer nodes.
If the customer node i ∈ V0\{0} is not an operation node (i.e., zi = 0), then it must
belong to exactly one component. This is guaranteed by (10)–(12), since they imply
xki = 1 or k∈V \{i} xk′ i = 1, that respectively means that the
P
P
that either
node is served by either the truck or the drone in some component k
k∈V0\{i}
0
̸= i.
If the customer node i ∈ V0\{0} is an operation node, then it must be the starting
node of component label i (i.e., zi = 1). This node must also be the last node of
some component k∗
̸
̸
∈ {i, k∗}. This
′
′
∗
Since the drone can only serve the customer nodes within the set VD, the other customer
nodes must be served by the truck. Keeping in mind that each node belongs to at least one
component, this is ensured by imposing
X
xki ≥ 1 ∀i ∈ V \VD.
(13)
k∈V0
To completely determine the node members of components, we have the following additional
constraints
X
x′ki ≤ (q + 2)zk ∀k ∈ V0,
xki ≤ (n + 2)zk ∀k ∈ V0.
(14)
(15)
i∈V
X
i∈V
These constraints ensure that if k is not the starting node of a component, then no node
belongs to a component starting from node k. Note that the constraints (14) guarantee
furthermore that the drone can serve at most q customer locations during a sortie.
THE TRAVELING SALESMAN PROBLEM
473
3.2. Determining vehicles’ paths in components
After determining the node members of components, our next step is to determine the
order of each node in the vehicles’ paths constituting the components. We say that an arc
(i, j) is a truck arc if the truck travels from node i to node j. Similarly, we say that (i, j) is
a drone arc if the d′rone flies from node i to node j. We introduce two more sets of binary
variables ykij and ykij (k ∈ V0, i ∈ V0, j ∈ V+, i
̸
(
1
ykij
yk′ ij
=
0
otherwise,
(
1
0
if (i, j) is a drone arc in component k,
=
otherwise.
To eliminate sub-tours in the paths of the two vehicles, we introduce non-negative continuous
variables ui(i ∈ V ). Using these variables, we can determine the vehicles’ paths in the
components as follows. Each component contains exactly one truck path. The structure of
the truck path in each component is satisfied by imposing the following constraints.
X
ykij = xkj ∀k ∈ V0, j ∈ V+\{k},
(16)
(17)
(18)
(19)
(20)
i∈V0\{j}
X
ykij ≥ xki − zi ∀k ∈ V0, i ∈ V0\{0, k},
j∈V+\{i,k}
X
2
ykij ≤ xki − zi + 1 ∀k ∈ V0, i ∈ V0\{0, k},
j∈V+\{i,k}
X
ykik = 0 ∀k ∈ V0,
i∈V0\{k}
X
ykki = zk ∀k ∈ V0,
i∈V+\{k}
ui − uj + (n + 1)ykij ≤ n ∀k ∈ V0, i ∈ V0, j ∈ V+, i
ui − uj + (n + 1)yk′ ij ≤ n ∀k ∈ V0, i ∈ V0, j ∈ V+, i
ui ≥ 0 ∀i ∈ V,
̸
̸
(21)
(22)
(23)
(24)
ui ≤ n + 1 ∀i ∈ V.
More precisely, by constraints (16), if node j is served by the truck in component k but
is not the starting node of the component, then there must be exactly one truck arc from
another node in the component going to this node. Otherwise, if node j is not in component
k, then there is no arc in this component going to j. By constraints (17) and (18), if node
i is served by the truck in component k but is not the first or the last node (i.e., zi = 0
P
and xki = 1), then we have
truck arc going out node i. If i is the last node of component k
ykij = 1, or equivalently, there must be exactly one
j∈V+\{i,k}
= i (i.e., xki = 1 and
zi = 1), then it follows from (18) that there is no truck arc in the component going out this
node. Constraints (19) imply that within each component there is no truck arc going to the
starting node. By constraints (20), if k is the starting node of a component (i.e., zk = 1),
then there must be exactly one truck arc in this component going out this node. Otherwise,
if there is no component with label k (i.e., zk = 0), then there is no truck arc in such empty
474
QUANG MINH HA, et al.
component. Constraints (21)-(24) eliminate sub-tours of the truck and the drone since they
imply that no node is revisited by the vehicles.
Unlike the truck, in each component there are two different situations for the drone: either
there exists exactly one drone path, or there is no drone path at all. In the former situation,
the drone flies in one path from the starting node to the last node of the component. In
the latter situation, the drone is active only at the operation nodes of the component: it is
retrieved at the starting node, then inactive when carried by the truck, and launched again
at the last node of the component. To cover these cases and the structure of the drone path
(if exists) in each component, the following conditions must be satisfied.
(D1) If j is not a node in component k, then no drone arc in component k comes to j. This
also ensures that for each node there is at most one drone arc going to.
(D2) If the drone is not active at node j, then there is no drone arc going to j.
(D3) If the drone serves node j, then there must be exactly one drone arc going to j and
one drone arc going out of j. Furthermore, these two drone arcs must be in the same
component.
(D4) If the drone is launched at node k, then there must be one drone arc in component k
going out of k, and no drone arc in this component going to k.
(D5) If the drone is retrieved at node j of component k, then this must be the last node of
the component (i.e., no drone arc in this component going out of j).
(D6) In each sortie, the drone must serve at least one customer.
(D7) The drone must be launched right after a component without drone sortie.
To ensure the above conditions, we impose the following constraints.
yk′ ij ≤ x′kj ∀k ∈ V0, j ∈ V+\{k},
X
(25)
(26)
(27)
(28)
(29)
(30)
(31)
i∈V0\{j}
X
yk′ ij ≥ x′kj − zj ∀k ∈ V0, j ∈ V+\{k},
i∈V0\{j}
X
yk′ ji ≥ x′kj − zj ∀k ∈ V0, j ∈ V0\{k},
i∈V+\{j,k}
X
2
yk′ ji ≤ x′kj − zj + 1 ∀k ∈ V0, j ∈ V0\{k},
i∈V+\{j,k}
X
yk′ jk = 0 ∀k ∈ V0,
j∈V0\{k}
X
X
x′ki ≥ 3
yk′ kj ∀k ∈ V0,
i∈V
j∈V+\{k}
X
X
x′ik
−
yi′jk
≤
yk′ kj ∀k ∈ V0\{0}, i ∈ V0\{k}.
j∈V0\{k}
j∈V+\{k}
Conditions (D1) and (D2) are guaranteed by constrai′nts (25). Constraints (25) and (26)
together imply that, if the drone serves node j (i.e., xkj = 1 for some k ∈ V0 and zj = 0),
there must be one drone arc in component k going to j. In this setting, constraints (27)
and (28) imply furthermore that there must be one drone arc in the same component k
going out of j. Therefore condition (D3) is satisfied. The latter requirement of condition
THE TRAVELING SALESMAN PROBLEM
475
(D4) is ensured by constraints (29). Note that, by definition of the variables, the drone is
launched at node k if and only if
P
\{k} yk′ kj = 1, and this is already satisfied by (25)
j∈V+
and (26). Constraints (28) imply furthermore that when the drone is retrieved at node j
of component k (i.e., when xkj = 1 and zj = 1), then there is no drone arc in component
k going out of j. Hence (28) ensure condition (D5). Constraints (30) guarantee that if the
drone is launched at node k, then it is active at the first and the last nodes of the component
k and at least one customer node in this component, hence condition (D6) is ensured. By
constraints (31), if k is the last node of a component i with no drone arc going to (i.e.,
P
P
x′ik = 1 and j∈V \{k} yi′jk = 0), then it implies that
\{k} yk′ kj = 1, or equivalently,
j∈V+
0
the drone must be launched at node k. So the condition (D7) is also satisfied.
3.3. Drone endurance and completion time
To model the objective of the TSP-MVD and to satisfy the constraints related to the
drone endurance, we introduce non-negative continuous variables tk (k ∈ V0) in which tk is
the total time amount to complete service for component k. Since we aim to minimize the
completion time of both vehicles, or equivalently, the total time amount to complete services
for all components, the objective can be represented as follows.
X
min
tk.
(A)
k∈V0
As the drone can be launched from the depot at any time, the truck drive does not
need to spend the service time sL to launch the drone at node 0. Therefore, the endurance
constraint for the drone in the first component is ensured by
X
X
τi′jy0′ ij + sR
y0′ 0j ≤ e.
(32)
i∈V0
j∈V+
j∈V+\{0,i}
Indeed, the first sum in the left hand side of (32) is the total service time of the drone in
component 0 (starting from the depot node 0). If the drone is launched at the depot node 0
P
(which means
y0′ 0j = 1), it must be used in component 0, hence the second sum in the
j∈V+
left hand side of (32) is the service time to retrieve the drone at the last node of component
0. So the left hand side of (32) represents the total active time of the drone in component
0, which must not exceed the drone endurance e.
The endurance constraints for the drone in the other components are satisfied by
X
tk ≤ e + M(1 −
yk′ kj
)
∀k ∈ V0\{0},
(33)
j∈V+\{k}
in which M is a large real number (M = (n + 1) max{τij, τi′j | i ∈ V0, j ∈ V+} is sufficient).
P
If the drone is launched at the first node of component k (i.e.,
(33) we have tk ≤ e, which means that the total service time for component k is within the
\{k} yk′ kj = 1), then by
j∈V+
drone endurance.
The total time amount to complete service for component k is computed by
tk = max{ttk, tdk},
(B)
in which ttk (resp., tdk) is the total time amount for the truck (resp., the drone) to complete its
service for component k. By similar arguments for the left hand side of (32), the completion
time for the drone in component k is computed by
476
QUANG MINH HA, et al.
X
X
tdk =
τi′jyk′ ij + sR
yk′ kj
.
(C)
i∈V0
j∈V+
j∈V+\{k,i}
For the truck, we need to take into account the service time for the driver to launch the
drone if it is launched at the rendezvous node of some component to start a new sortie. To
recognize this situation, we use the binary variables lk(k ∈ V0) in which
(
1
if the drone is launch again at the last node of component k,
lk =
0
otherwise.
The concordance of variables lk with their meaning is ensured by imposing
X
yi′ij + xki − 1 ≤ lk
∀k ∈ V0, i ∈ V+\{k}.
(34)
j∈V+
These constraints guarantee that lk is set to 1 if and only if there is a launching action at
P
the last node i of component k (i.e.,
the truck in component k is given by
yi′ij = xki = 1). Then, the completion time for
j∈V+
X
X
ttk =
τijykij + sR
yk′ kj + sLlk.
(D)
i∈V0
j∈V+
j∈V+\{k,i}
In cooperation of (A) with (B), (C), (D), we come up with the following constraints to
compute the completion time in components.
X
X
τi′jyk′ ij + sR
yk′ kj ≤ tk ∀k ∈ V0,
(35)
(36)
i∈V0
j∈V+
j∈V+\{k,i}
X
X
τijykij + sR
yk′ kj + sLlk ≤ tk ∀k ∈ V0.
i∈V0
j∈V+
j∈V+\{k,i}
To the end, we come up with the following MILP for the TSP-MVD
X
min
tk,
k∈V0
s.t. (1) − (36),
zk ∈ {0, 1} ∀k ∈ V,
xki ∈ {0, 1} ∀k ∈ V0, i ∈ V,
x′ki ∈ {0, 1} ∀k ∈ V0, i ∈ V,
ykij ∈ {0, 1} ∀k ∈ V0, i ∈ V0, j ∈ V+\{i},
yk′ ij ∈ {0, 1} ∀k ∈ V0, i ∈ V0, j ∈ V+\{i},
lk ∈ {0, 1} ∀k ∈ V0,
tk ≥ 0 ∀k ∈ V0.
4. AN ITERATED LOCAL SEARCH FOR TSP-MVD
In this section, following the paradigm of Iterated Local Search (ILS, see e.g., [4]), we
propose a metaheuristic for solving the TSP-MVD problem. The key idea is to focus our
search on a smaller set of the solution space instead of the whole solution space by using
an implicit solution representation called giant tours. We define a giant tour as any TSP
THE TRAVELING SALESMAN PROBLEM
477
tour that starts from the depot at node 0, goes through all customer nodes and returns to
the depot at node n + 1. After applying the split procedure described in Section 4.1. on
a giant tour, we obtain a feasible TSP-MVD solution. Such TSP-MVD solution associated
with giant tour T is denoted by sT . The value of T , also called the completion time of sT is
denoted as f(T ). The overall framework of our ILS algorithm for the TSP-MVD is described
in Algorithm 1.
Algorithm 1: Iterated local search for TSP-MVD.
Data: A TSP-MVD instance.
Result: Best found giant tour T ∗ and its corresponding TSP-MVD solution s
.
∗
T
1
Initialization: Set values for parameters nNI, n , r, y, acceptProb, ;
H
2 nIter = 0;
3 T0 = InitialTour();
4 s = Split(T0);
T0
5 s = LocalSearch(s );
6 TT00= Restore(s );
T0
T0
7 T ′ = T0, T ∗ = T0, H = {T0};
8 while nIter < nNI do
9
10
11
12
13
14
15
nIter = nIter + 1;
T = Perturb(T ′);
s
s
= Split(T );
T
= LocalSearch(s );
T
TT = Restore(s );
T
if f(T ) < f(T ∗) then
T ∗ = T ;
16
17
if f(T ) < f(T ′) then
H = H ∪ {T };
18
19
if |H| > nHmax then
Sort elements of H in the increasing order of f(T ), T ∈ H;
20
Remove the worst elements in H until |H| = nmHin
;
21
22
23
24
if AcceptanceCriterion(T , T ′, acceptProb) then
T ′ = T ;
else
T ′ = the giant tour of index ⌊ry|H|⌋ in H;
= Split(T ∗);
∗
25 s
T
Our ILS algorithm starts with a giant tour T0 obtained by InitialTour procedure. The
giant tour T0 is used as the input for the splitting algorithm to get a TSP-MVD solution
sT . This solution is then educated by using LocalSearch procedure and then restored by
0
using Restore procedure to have an updated giant tour. The solution corresponding to this
giant tour becomes a local optimum to be used as the input for the first iteration. We
initialize the history list H by pushing this updated giant tour into the list. Then, in each
iteration, we first save a copy T ′ of the current giant tour T , and then “shake” T ′ by using
Perturb procedure. The perturbed giant tour T is then split by using the splitting algorithm
described in Section 4.1. to obtain its corresponding TSP-MVD solution. This solution is
then passed to LocalSearch procedure to improve its quality (i.e., to reduce its value). After
being educated, the giant tour T is updated by using Restore procedure. We then update
the best giant tour and its value. In the next step, if the updated giant tour T is better than
478
QUANG MINH HA, et al.
the previous one T ′ (in sense of its value), then we add the giant tour T to a history list H.
This list of the past giant tours is then sorted in the ascending order of the tours’ values, so
that we can remove the worst tours in H to keep the number of giant tours in the list varying
from nHmin to nHmax. Then, by using AcceptanceCriterion procedure, we decide which giant
tour in the list H will be chosen for the next iteration. If giant tour T we are considering is
accepted, we use it as the current giant tour for the next iteration. Otherwise, we choose a
random giant tour in H. We terminate the algorithm when the number of iterations reaches
a fixed limit. For the algorithm execution, we use the following parameters:
nNI: maximum number of iterations,
nHmin, nHmax: minimum and maximum numbers of the best tours kept in the history list
H,
acceptProb: probability of accepting bad moves in AcceptanceCriterion,
r: a random number in (0, 1],
y: degree of randomness.
In the following subsections, we discuss in detail the procedures used in our ILS algorithm,
that are Split, InitialTour, Perturb, LocalSearch, Restore, and AcceptanceCriterion.
4.1. Splitting algorithm
In this section, we introduce the splitting algorithm for decoding a giant tour into a
feasible TSP-MVS solution. This splitting algorithm is an adaption of the one introduced in
[6], which was used for the TSP-D, to the context of our TSP-MVD.
Roughly speaking, the algorithm starts with a TSP tour from the depot through all
customer nodes, then optimally selects the nodes that could be served by the drone while
respecting the relative order of these nodes in the tour. More precisely, we are given a TSP
tour, denoted T , from the depot node 0 through all customer nodes and then return to the
depot at node n + 1. If we denote by T [i] the ith node on the tour T , then T [0] = 0 and
T [n + 1] = n + 1 are the depot and its duplication. We construct an auxiliary directed
graph HT = (VT , AT ) associated with the tour T as follows. The node set VT consists of
the indices of the nodes on tour T , i.e., VT = {0, 1, . . . , n + 1}. Each arc in AT has form
(i, j) with i < j, that corresponds to the situation in which both vehicles start from T [i]
and consecutively travel to serve customers at the subsequent nodes T [i + 1], . . . , T [j]. If
in such a situation we allow the drone to make at most one sortie in coordination with the
truck, then the smallest completion time for the path from T [i] to T [j] is considered as a
cost cij assigned to arc (i, j). Additionally, to speed up the splitting algorithm, we only
reduce the number of arcs in AT by using a threshold λ, which is the maximum number
of nodes between nodes i and j in tour T , i.e., we only allow arc (i, j) satisfying condition
|{T [i], . . . T [j]}| ≤ λ. This threshold helps the algorithm to avoid computing the arcs that
are too long and might not be used in good TSP-MVD solutions.
The computation of the arc costs is precisely described in Algorithm 2. For the algorithm
initialization, we assume that only truck is available to serve the customers, hence the cost
of each arc (i, j) ∈ AT is set by the truck travel time along the path from T [i] to T [j] of the
tour T . If the coordination of the truck with a drone sortie can reduce the completion time
for such a path, then we update the arc cost by the better completion time. Since the drone
cannot make a sortie between two adjacent nodes on the tour, we only need to update the
THE TRAVELING SALESMAN PROBLEM
479
cost cij when T [i] and T [j] are non-adjacent nodes on tour T . As such, we use variable cost
to save the best computed value for cij after checking all feasible options for drone sortie.
Such a sortie has the form ⟨T [i], {T [k], . . . , T [k + m − 1]}, T [j]⟩ in which the drone serves
m ≤ q nodes T [k], . . . , T [k+m−1] in this order on the path from T [i] to T [j]. In the context
of such sortie, the nodes T [k], . . . , T [k + m − 1] served by the drone are excluded from the
truck path. For each of such drone sorties, the total time amount we really use on the path
from T [i] to T [j] is the maximum completion time between the drone and the truck for this
path. The completion time must be checked to ensure that it is within the drone endurance.
To incorporate the fact that the truck needs to prepare for the drone before each launch, we
also add the drone launch time sL to the completion time if the launch node T [i] is not the
depot.
Algorithm 2: Cost calculation in TSP-MVD splitting algorithm.
Data: A TSP tour T from node 0 through all customer nodes.
Result: Cost cij associated to each arc (i, j) in H .
T
1
Initialization: ∀(i, j) ∈ A : cij = truck travel time along the path from T [i] to T [j].
T
2 for i = 0 → n − 1 do
3
4
5
6
7
8
for j = i + 2 → min(i + λ, n + 1) do
cost = cij;
for m = 1 → min{q, j − i − 1} do
for k = i + 1 → j − m do
if T [h] ∈ VD for all h = k, . . . , k + m − 1 then
droneTime = sR plus drone travel time during its sortie
⟨T [i], {T [k], . . . , T [k + m − 1]}, T [j]⟩;
9
truckTime = sR plus truck travel time along the path
(T [i], T [i + 1], . . . , T [k − 1], T [k + m], T [k + m + 1], . . . , T [j]);
if droneTime ≤ e and truckTime ≤ e then
usedTime = max{droneTime, truckTime};
10
11
12
13
if i
̸
usedTime = usedTime + sL;
14
15
if usedTime < cost then
cost = usedTime;
16
cij = cost;
Having assigned the corresponding cost to each arc in HT , we can compute a cheapest
path from node 0 to node n + 1 in this auxiliary graph. Such cheapest path can be found
by applying the well-known Dijkstra algorithm [19]. If there is any arc of form (i, i + 1) in
the cheapest path, then we convert the arc to a truck path from node T [i] directly to node
T [i + 1]. For any arc (i, j) in the cheapest path with j ≥ i + 2, we convert the arc to the
truck path together with the drone sortie (if exists) constituting the cost cij computed in
Algorithm 2. After converting all arcs of the cheapest path, we have spit the given TSP tour
T into a feasible solution to the TSP-MVD.
4.2. Getting an initial giant tour
To generate an initial solution for the ILS algorithm, we first construct a TSP tour based
on a constructive heuristic so-called k-cheapest insertion, with k ∈ Z+. This construction is
480
QUANG MINH HA, et al.
the same as the one in [6] used for the TSP-D. For the sake of completeness, we present here
the construction details.
We start with a subtour consisting of only the depot and a customer node. Then, step
by step, we extend the subtour by inserting an unvisited node. We define an insertion by an
ordered set (i, k, j) in which k is an unvisited node while i and j are two consecutive nodes
on the current subtour. The cost of such insertion is defined by τik + τkj − τij. This cost
is the increment of time amount when the truck travels along the path i − k − j instead of
going directly from i to j. In each step, we randomly choose an insertion (i, k, j) among
the ninsert insertions of the least costs, and insert node k into the location between i and j,
then mark k as a visited node. Here, ninsert is a pre-defined parameter and is set to 3 in our
experiments. When all customer nodes are visited and added, the tour construction stops
and we obtain a giant tour T0. We return it as the output of InitialTour procedure.
4.3. Local search operators
The LocalSearch procedure is to educate a TSP-MVD solution obtained by splitting a
giant tour. For this procedure, we use the following move operators.
Truck Swap 1-1: exchanging two random positions on the truck tour.
Truck Swap 2-1: swapping two consecutive nodes i, i + 1 with another random node j
on the truck tour.
Truck Swap 2-2: swapping two pairs of consecutive nodes {i, i + 1} and {j, j + 1} on
the truck tour.
Truck-only Relocation 1-1: relocating a random truck-only node i after a random node
j. For a truck-only node we mean a node that does not belong to any drone sortie.
Truck-only Relocation 2-1: relocating a random pair of truck-only nodes {i, j} after a
random node k. We also consider the moves where {i, j} are reversed to {j, i} when
being relocated to k.
2-opt: swapping two pairs of consecutive nodes {i, j} and {u, v} in the truck tour to
have {i, u} and {j, v}.
Drone delivery creation: changing a path i − j − k on the truck tour, in which j is a
truck-only node, into a drone sortie in which i is the launch node, j becomes a drone
node, and k is the rendezvous node.
Drone delivery relocation: relocating the sequence of drone visited nodes J in a drone
sortie ⟨i, J, k⟩ to have another drone sortie ⟨i′, J, k′⟩ with new launch and rendezvous
nodes i′ and k′ in the truck tour.
Drone delivery removal: removing a drone sortie ⟨i, J, k⟩ by reinserting the sequence
of nodes J into the position right after a random node j in the truck tour.
Inter drone-truck swap 1-1: swapping the launch or rendezvous node of a drone sortie
with a drone node of another drone sortie.
Inter truck-rdv swap 1-1: swapping the launch and rendezvous nodes of a drone sortie.
Drone sequence insertion: inserting a truck-only node i to a random position in a
sequence of drone visited nodes J of a drone sortie.
Drone sequence removal: removing a drone node j ∈ J in a drone sortie ⟨i, J, k⟩ by
reinserting it to the position right after a node j′ in the truck tour.
THE TRAVELING SALESMAN PROBLEM
481
Drone sequence swap: swapping two drone nodes belonging to two different drone
sorties.
Drone sequence permuting: replacing the sequence of nodes J of a drone sortie ⟨i, J, k⟩
by a random permutation of its nodes.
The last four operators are the new ones that we propose to solve the TSP-MVD, while
the other operators are adapted from the ones proposed in [6, 7], that were used for the TSP-
D. In each call of LocalSearch procedure in Algorithm 1, we use all but in a random order
of the above move operators. Furthermore, to speed up the performance of LocalSearch
procedure, we apply the idea of a concept so-called granular threshold (see [16]). That is, in
each call of the operators, we avoid scanning all the neighborhoods of the considering nodes,
and only scan the neighborhoods consisting of 10% of nodes that are closest to each of the
considering nodes.
4.4. Perturbation technique
The aim of Perturb procedure in Algorithm 1 is to have a new starting point for the
ILS by shaking a giant tour. It is observed from [10] that the quality of the giant tour has
a clear impact on the value of its associated TSP-D solution. Based on this observation,
our perturbation technique is designed for the TSP-MVD in such a way that it keeps the
positions of the nodes in the truck tour, and only “shake” a subset of the drone nodes to
avoid too much different (and possibly bad) new giant tours. Algorithm 3 describes more
precisely the Perturb procedure used in our ILS. The procedure takes the current giant tour
T as its input and returns a perturbed giant tour T ′. We initialize T ′ by a tour of the same
structure as T but all nodes have label −1. At first, we compute the TSP-MVD solution
sT associated with T by applying the splitting algorithm. This TSP-MVD solution sT is
extracted into two parts: the truck tour T ∗ and the list of drone sorties droneSorties. We
copy all nodes on the truck tour T ∗ to T ′, keeping their position indices as in the giant tour
T . Then, we go through each node in the drone sorties and decide with probability of 0.5
whether to copy this node to the T ′ or not, keeping its position index as in T . Finally, we
randomly locate each of the uncopied nodes in the drone sorties to the unassigned positions
in T ′, the ones with label -1.
In addition to the specifically designed perturbation for TSP-MVD described above, two
more standard perturbation methods are also used to add more diversification to this process,
as follows:
Random reinsertion: we randomly select p nodes and remove them from the giant tour
T of the current TSP-MVD solution. These nodes are then shuffled and reinserted to
the giant tour following the k-cheapest-insertion strategy that is described in [6]. In this
paper, the number of nodes p is randomly selected in the set {0.1|V |, 0.2|V |, . . . 0.6|V |},
k is randomly chosen between {3, 4, 5} for each node waiting to be re-inserted.
PMX-style operator: This perturbation follows the PMX operator [5] with the two
chromosomes are the giant tour T of the current TSP-MVD solution and a random
giant-tour selected in the history H of ILS.
In each iteration of the ILS, a perturbation strategy is chosen randomly among these three
alternative operators.
482
QUANG MINH HA, et al.
Algorithm 3: Perturb procedure for TSP-MVD.
Data: A giant tour T and its associated solution s
Result: A giant tour T ′ perturbed from T .
T
1
Initialization: T ′ = T and then replace node labels in T ′ by −1;
2 s = Split(T );
3 TT∗ = the truck tour in s ;
T
4 droneSorties = the list of nodes served by drone in s ;
T
5 foreach node i in T ∗ do
6
7
indi = index of i in T ;
T ′[indi] = i;
8 foreach node j in droneSorties do
9
10
11
r = random number between (0, 1];
if r ≤ 0.5 then
indj = index of j in T ;
12
T ′ [indj] = j;
13 I = {i ∈ {0, . . . , n + 1} | T ′ [i] = −1} = array of unassigned positions in T ′;
14 U = {T [i] | i ∈ I} = array of uncopied nodes in s ;
T
15 Randomly reshuffle U;
16 for k = 1 to |I| do
17
T ′ [I[k]] = U[k];
18 return T ′ ;
4.5. Restore method
The splitting method described in Section 4.1. converts some nodes of a giant tour to
drone nodes in order to obtain a feasible TSP-MVD solution. Conversely, Restore method
reinserts the drone nodes in a given feasible TSP-MVD solution to the truck tour in order to
obtain a new giant tour. The purpose of Restore method is to speed up the convergence speed
of the search since the giant tour is updated with the “educated” sequences. In Algorithm 4
we describe Restore procedure for the TSP-MVD more precisely. Given a TSP-MVD solution
composed of a truck tour and set of drone sorties, a giant tour T is initialized with nodes
from the truck tour. Then, for each drone sortie ⟨i, J, k⟩, we insert the whole set J of drone
nodes to a random position between launch node i and rendezvous node k in T .
Algorithm 4: Restore procedure for TSP-MVD.
Data: A TSP-MVD solution s.
Result: A giant tour T .
1
Initialization: truckTour = truck tour in s, droneSorties = set of drone sorties in s,
T = truckTour;
2 foreach drone sortie ⟨i, J, k⟩ do
3
4
5
6
7
if k − i = 1 then
insert J right before k in T , respecting order of nodes in J;
else
randNode = random node between i and k (including k) in T ;
Insert J right before randNode in T , respecting order of nodes in J;
THE TRAVELING SALESMAN PROBLEM
483
4.6. Acceptance criterion
The procedure AcceptanceCriterion used in Algorithm 1 decides whether we should accept
a new generated giant tour T based on the previously perturbed one T ′. If the new giant
tour T is better than the previous one T ′ in sense of its value, we immediately accept
it. Otherwise, we only accept this new giant tour with a probability of acceptProb which
decreases gradually. That is, we set acceptProb = acceptProb/rac after each time a worse
giant tour is allowed. Here, rac > 1 is a given value set to 1.0002 defined by experiments.
By doing this, we allow the search to explore wider regions at the early iterations to find
diversified solutions for the history list H. Moreover, when approaching the final iterations
of the procedure, the probability of accepting bad solutions would be very small, making
Algorithm 1 to focus on finding better solutions.
Algorithm 5: AcceptanceCriterion
Data: New generated giant tour T , previously perturbed giant tour T ′, value of acceptProb.
Result: true if T is accepted, false if T is not accepted.
1 if f(T ) < f(T ′) then
2
return true;
3 else
4
5
6
7
randProb = random value between (0, 1] ;
if randProb ≤ acceptProb then
acceptProb = acceptProb/rac
return true;
;
8
9
else
return false;
5. NUMERICAL EXPERIMENTS
In this section, we present the computational results of the MILP formulation in Section
3. and ILS algorithm in Section 4.. Our main aim is to validate the MILP model and
show the efficiency of the ILS algorithm in comparison with the existing methods for solving
TSP-MVD. We also analyze the impact of drone capacity on the performance of the ILS
algorithm as well as the quality of obtained solutions.
5.1. Experimental setup
We used CPLEX 12.9 as MILP solver and run the MILP formulation on a computer
with an Intel Xeon E5620 2.4 GHz processor and 16 GB of RAM. The ILS algorithm was
implemented in C++ and all experiments of the metaheuristic were conducted on a computer
with Intel i7-6700 3.4 GHz and 16 GB of RAM.
To generate TSP-MVD instances, we use the same set of TSP-D instances proposed in
[6] but allow the drone can serve up to q ≥ 1 customers in each of its sortie. For the sake
of completeness, we present here the construction of the tested instances. Each TSP-MVD
instance is characterized by the locations of the depot as well as the customers, the subset
of customers that cannot be served by the drone, traveling time of each vehicle between
484
QUANG MINH HA, et al.
Table 1: Information of groups of instances for the TSP-MVD
Instance label
A1 to A5
Number of customers Area (km2) Average distance
10
50
100
100
7.43
7.13
B1 to B10
C1 to C10
D1 to D10
E1 to E10
F1 to F10
G1 to G10
50
500
15.45
22.19
7.14
50
1000
100
100
100
100
500
15.21
21.59
1000
the nodes, drone launch time, drone retrieve time, and drone endurance. For each tested
instance, we randomly generated locations for a number of customers within a square in a
plane. We generated 65 such instances and classified them into 7 groups according to the
number of customers and the area of the square, as shown in Table 1.
The fourth column in Table 1 indicates the average Euclidean distance between customer
locations. Similarly to the settings in [10], for all generated instances, we set the speed of the
truck and the drone to 40 km per hour, the default drone endurance e was set to 20 minutes,
both the launch time sL and and retrieve time sR were set to 1 minute, and 20% of customers
chosen randomly could not be served by the drone. Furthermore, the depot location was
set to the bottom left vertex of the square in each tested instance. The maximum number
of drone visits per sortie was set to q = 2 by default. In addition, we also use the TSP-D
instances proposed in [10] to test the performance of our approaches.
We selected values for parameters used in Algorithm 1 by experiments. The maximum
number of iterations nNI was set to 5000. To manage the history list H, we set the maximum
number nHmax of the best tours keeping in the history list to 25, the minimum number nHmin
to 10. The degree of randomness y was set to 2. The value for acceptProb was fixed to 0.5.
For the splitting algorithm, the threshold λ was set to 0.2|V |.
5.2. Results on the small instances of [10]
The aim of this experiment is to validate the MILP model and assess the performance of
our ILS algorithm on the set of 72 TSP-D instances of 10-customer size from [10]). For each
instance, we consider two settings for the drone endurance: e = 20 (minutes) and e = 40
(minutes). On each tested instance, our MILP model is run in a time limit of 16 hours
while our ILS algorithm is run 10 times and the best objective value as well as the average
objective value are reported. We compare the quality of obtained solutions to the ones found
by existing methods for the TSP-D: Hybrid Genetic Search Algorithm (HGA, see [7]), the
MILP model of [10], the best solutions obtained from a set of methods in [10] including the
MILP model. HGA was run 10 times and the best result was reported. The detailed results
are reported in Table 9 in Appendix. In that table, column “Instance” gives the name of
each tested TSP-D instance, column e gives the corresponding values of drone endurance
(in minutes). Columns MILPo, BEST, and HGA respectively report the objective values
of: solutions obtained by the MILP model of [10], the best solutions found by the set of
methods in [10], and the best solutions provided by HGA. The objective values, gap values,
and running time in seconds of our MILP model are presented in Columns MILPn, GapM
Tải về để xem bản đầy đủ
29 trang
16940
Free
Bạn đang xem 20 trang mẫu của tài liệu "The traveling salesman problem with multi-visit drone", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- the_traveling_salesman_problem_with_multi_visit_drone.pdf
