Acta Polytechnica CTU Proceedings


doi:10.14311/APP.2015.1.0057
Acta Polytechnica CTU Proceedings 2:57–61, 2015 © Czech Technical University in Prague, 2015

available online at http://ojs.cvut.cz/ojs/index.php/app

ON SAMPLING BASED METHODS FOR THE DUBINS
TRAVELING SALESMAN PROBLEM WITH NEIGHBORHOODS

Petr Váňa∗, Jan Faigl

Dept. of Computer Science, Czech Technical University in Prague, Technická 2, 166 27 Prague, Czech Republic
∗ corresponding author: vanapet1@fel.cvut.cz

Abstract. In this paper, we address the problem of path planning to visit a set of regions by Dubins
vehicle, which is also known as the Dubins Traveling Salesman Problem Neighborhoods (DTSPN). We
propose a modification of the existing sampling-based approach to determine increasing number of
samples per goal region and thus improve the solution quality if a more computational time is available.
The proposed modification of the sampling-based algorithm has been compared with performance of
existing approaches for the DTSPN and results of the quality of the found solutions and the required
computational time are presented in the paper.

Keywords: dubins vehicle, dubins maneuver, DTSP, DTSPN.

1. Introduction
Path planning for a non-holonomic vehicle is a fun-
damental problem of surveillance mission where an
unmanned aerial vehicle (such as a fixed-wing) is re-
quested to visit a given set of locations. The basic
model of such a vehicle with the limited turning radius
is called the Dubins vehicle [1] for which the combi-
natorial problem of finding optimal sequence of visits
to the locations is known as the Dubins Traveling
Salesman Problem (DTSP) [2].

In this paper, we consider a generalized problem
of the DTSP where the particular waypoints to be
visited can be selected from a set of possible locations.
Due to the similarity of this problem with the so-called
Traveling Salesman Problem with Neighborhoods [3],
the problem is called as the Dubins Traveling Salesman
Problem with Neighborhoods (DTSPN) [4].

The DTSPN is a suitable problem formulation to
address surveillance missions with unmanned aerial
vehicles, where it is required to take a camera snapshot
(or other type of measurement) of each target location.
Such a snapshot can be acquired from some distance
of the target location and thus it is not necessary to
visit the location exactly. It is rather a more suitable
to select the waypoints in such a way that all locations
are covered while the total cost of the final path is
minimal.

There are several approaches to address the DTSP
and also the DTSPN in the literature [2, 4–6] includ-
ing our work [7]. Therefore, in this paper, we provide
an overview of the existing approaches to address the
DTSPN and compare their performance according to
the trade-off between the solution quality and compu-
tational requirements. In particular, we focus on the
sampling-based algorithm [4] which is able to provide
high quality solutions for very high number of samples.
However, more samples increase the computational
burden, and therefore, the algorithm is not directly
suitable for real-time applications. On the other hand,

we can get a quick estimation of the solution quality
using only few samples. This has motivated us to mod-
ify the original algorithm [4] to provide a first solution
quickly that is then improved if a computational time
is left.
The paper is organized as follows. A brief intro-

duction to the problem background is presented in
the next section. The addressed problem is formally
introduced in Section 3. A brief overview of the ex-
isting approaches to solve the DTSPN is provided in
Section 4. The proposed modification of the sampling-
based approach is presented in Section 5 together with
the analysis of its computational complexity. Eval-
uation results of the comparison of the existing ap-
proaches with the proposed modification are reported
in Section 6. Finally concluding remarks are denoted
to Section 7.

2. Related Work
The problem of curvature-constrained path planning
has been studied years ago and the fundamental work
has been published in 1957 by Dubins. In [1], he
proved that the optimal path between two configu-
rations q1,q2 ∈ SE(2) consists of only straight line
segments and segments with the minimum turning
radius. He also showed that only 6 maneuvers can be
optimal, which can be further divided into two main
types:
• CCC type: LRL, RLR;
• CSC type: LSL, LSR, RSL, RSR;
where C stands for a circle turn (R – right, L – left)
and S for a straight segment.
Even though the optimal path for Dubins vehicle

between two configurations is known and it is straight-
forward to compute, this is not sufficient to directly
solve the DTSP. It is because the orientation of the
vehicle at the waypoints is not known and thus it must
be determined together with the optimal sequence of

57

http://dx.doi.org/10.14311/APP.2015.1.0057
http://ojs.cvut.cz/ojs/index.php/app


Petr Váňa, Jan Faigl Acta Polytechnica CTU Proceedings

visits to the waypoints. Moreover, the optimal orien-
tation depends on the sequence and vice-versa, which
make the problem difficult to address.
Probably the simplest approach to address the

DTSP is the Alternating Algorithm (AA) proposed
in [2]. In this approach, headings are established in
the way that even edges are connected by straight
line segments and odd edges are connected by Du-
bins maneuvers. In addition, the authors show that
the length of the optimal solution of the DTSP can
be bounded by LTSPκdn/2eπρ, where ρ is minimum
turning radius, LTSP is the length of the optimal so-
lution of the Euclidean TSP, n is the number of the
goals, and κ < 2.658.

Based on the similar idea, authors of [5] proposed a
receding horizon algorithm called the look-ahead (LA)
approach. The heading is determined with respect
to the next point in the sequence. This algorithm
investigates each point only once, and therefore, the
LA approach is very fast and suitable for real-time
application while the authors reported better results
than the AA.

The optimal solution of the Dubins planning to visit
a given sequence of waypoints that are at the distance
longer than 4ρ is presented in [8]. The approach is
based on the convex optimization; however, the opti-
mization needs to be solved several times because of
possible alternation of the maneuvers directions. The
authors bound the number of possible combinations
to 2n−2 for n waypoints.

The DTSPN is a generalization of the DTSP, where
each goal is extended by a neighborhood (goal region).
As the DTSP is known to be NP-hard [6], also its
generalization the DTSPN is NP-hard.

3. Problem Definition
The addressed problem is motivated by surveillance
missions with fixed-wing aerial vehicles, which are
nonholonomic vehicles due to their kinodynamic con-
straints. These vehicles are often modeled as the
Dubins vehicle [1], which can go only forward at a
constant speed and has a minimum turning radius ρ.
The configuration space of such a vehicle can be repre-
sented as SE(2), where each configuration q ∈ SE(2)
is a triplet (x,y,θ), where (x,y) is the vehicle position
in a plane and θ ∈ S1 is the orientation of the vehicle.
The mathematical model of the Dubins vehicle can
be formulated as follows:

 ẋẏ
θ̇


 = v


 cos θsin θ

u
ρ


 , |u| ≤ 1, (1)

where v is the vehicle forward velocity, ρ is the mini-
mum turning radius, and u is the control input, u > 0.
Now, we can introduce the DTSPN [9] a more for-

mally. Let R = {R1, . . . Rn} be a set of n regions
Ri ⊂ R2 that are requested to be visited by the Du-
bins vehicle and let Σ = (σ1, . . . ,σn) be an ordered
permutation of {1, . . . ,n}. We define a projection

from SE(2) to R2, i.e., P(q) = (x,y), and let qi be an
element of SE(2) whose projection lies in Ri.
The DTSPN is path planning problem where the

Dubins vehicle has to visits each region Ri while sat-
isfying the kinodynamic constraints of (1). Every
optimal path has to intersect each goal region Ri in
at least one configuration qi. Hence, we can treat the
DTSPN as an optimization problem over all possi-
ble permutations Σ and configurations (q1, . . . ,qn) as
follows:

Problem 3.1 (DTSPN).

minimize Σ,q L(qσn,qσ1 ) +
n−1∑
i=1
L(qσi,qσi+1 )

subject to P(qi) ∈ Ri, i = 1, . . . ,n

where L(qi,qj) is the Dubins distance between qi
and qj.
In this paper, we are focused on the problem with

regions Ri that are mutually exclusive. Hence, we can
define the minimum distance constraint DK such that
for all i,j ∈{1, 2, . . . ,n}, i 6= j,∀pi ∈ Ri,∀pj ∈ Rj:

||pi −pj|| > Kρ. (2)

In particular, we are focused on the problem for
which the minimum distance DK is equal to 4ρ, which
is denoted as the D4 constraint in the rest of this
paper. Problem instances of the DTSPN with the
D4 constraint have special properties that are shown
and used in [7] to find high quality solutions. In this
paper, we also consider D4 problems and compare the
existing solutions with the sampling based methods.
An overview of the existing methods is provided in
the next section.

4. Existing Methods
In literature, we can find several different approaches
to address the DTSPN. The existing approaches can
be divided into three main classes: 1) the decoupled
methods; 2) sampling-based methods; 3) and evolu-
tionary methods. Representatives of each particular
class are briefly described in the following subsections.

4.1. Decoupled Methods
A decoupled method addresses the DTSPN by decom-
position of the problem into two sub-problems. First,
the permutation of the visits to the requested areas
(locations) is found independently on the Dubins path
planning. The second sub-problem is to find a par-
ticular visiting configuration of each location. In this
way, the original DTSPN is transformed to the DTSP
with point locations to visit.

In [10], the authors address the DTSPN by solving
the Euclidean TSP where cities represents centers of
the regions to be visited. Once such a permutation
is found, the final solution is constructed using the
AA [2].

58



vol. 2/2015 The Dubins Traveling Salesman Problem with Neighborhoods

Authors of [7] also consider a solution the ETSP to
estimate the permutation of the visits. But instead of
simple AA, the proposed local iterative optimization
(LIO) is used to find a significantly better solution.

4.2. Sampling-Based Methods
Sampling-based methods [4, 11] are another class of
existing approaches to address the DTSPN. Similarly
to the decoupled methods, also sampling-based meth-
ods are based on existing approaches for the TSP
variants; however, in this case a single representative
of each region is not considered as in [10] but each
region is rather sampled by a particular number of
random samples (including the orientation of the ve-
hicle). The samples can be determined in the whole
region or only on its boundary. Then, the samples of
different regions are connected by the Dubins maneu-
ver to form a roadmap. Such a roadmap is considered
as an instance of the Generalized Asymmetric TSP
(GATSP). If the GATSP is solved to the optimum,
the sampling-based methods are resolution complete
[11].
Since the optimal solution of the GATSP can be

computationally very demanding, existing heuristic
for the TSP can be a more suitable option. The
generated GATSP can be solved by its transformation
to the Asymmetric TSP (ATSP) using the Noon-Bean
transformation [12]. Then, the transformed ATSP
can be solved by existing algorithms, e.g., the Lin-
Kernighan heuristic algorithm [13].

4.3. Evolutionary Methods
The last class of existing approaches are genetic pro-
gramming based algorithms. The general idea of these
methods is to encode a solution by a chromosome in
which the goal permutation and the configurations of
the visits are stored. Similarly to another approaches,
only configurations on the boundary of the regions
are considered in these evolutionary methods.
Probably the first evolutionary approach to the

DTSPN was published in [14]. The authors adapted
the Ordered Crossover operator (OX) and added two
new mutation operators (orientation shift and position
shift) to optimize visiting configurations.

Relatively recently, the genetic approach from [14]
was modified into a memetic algorithm in [15]. The
authors used similar operators and added a local im-
provement of individuals in the population by optimiz-
ing the position of visiting points. The authors used
AA as heuristic algorithm to speed up the algorithm.

5. Modification of Existing
Sampling-Based Algorithm

The main issue of sampling based algorithms for the
DTSPN is that they require a fixed number of sam-
ples, which need to be established in advance. We
propose an iterative schema to avoid this issue and set
the number of samples progressively, which provides
first solutions very quickly. Moreover, if there is some

additional computational time, the algorithm can iter-
atively improve the solution by adding more samples,
which results to obtain a first solution quickly that is
further improved.
In the basic sampling-based algorithm, a roadmap

with (n·m)2 edges is created where n is the number of
regions to be visited and m is the number of samples
per region. For each edge one Dubins maneuver is
constructed. Since the Noon-Been transformation
does not change the number of vertices, the overall
time complexity of generating an instance of the ATSP
can be bounded by O((n ·m)2).
A solution of the generated ATSP can be found

by the available LKH solver. According to the au-
thor of the LKH, the time complexity of the LKH is
approximately O(n2.2ATSP ) [16]. Hence, the expected
total time complexity is O((n ·m)2.2). The time com-
plexity to solve the ATSP is greater than a roadmap
generation, and therefore, we do not need to explic-
itly consider the construction of the roadmap in the
estimation of the required computational time based
on the number of samples.
Based on the relation of the required number of

operations on the number of samples, we can establish
a sequence of the increasing numbers of the samples
needed to find an initial solution quickly and improve
its quality later. The sampling-based algorithm works
with the constant number of samples given a priory,
we can run the sampling based algorithm repeatedly
with an increasing number of samples. Since the
time complexity of the algorithm is nearly quadratic,
an inverse function for the number of samples mk
according to the number k of the particular iteration
can be defined as:

mk ≈
√

2k. (3)

After rounding the mk to an integer value, it gives us
the following series of the numbers:

M = {1, 2, 3, 4, 6, 8, 11, 16, 23, 32, 45, 64, . . .}. (4)

Figure 1 provides influence of the required computa-

Number of samples per region

0 100 200 300 400 500 600 700 800

T
im

e
 [

s]

10
-2

10
-1

10
0

10
1

10
2

10
3

ETSP + LIO

Sample + ATSP

Figure 1. The average required computational time
(from 20 trials) for the instance of the DTSPN with 4
circle regions and D4 constraint.

tional time on the number of samples per each region

59



Petr Váňa, Jan Faigl Acta Polytechnica CTU Proceedings

to visit. We plot the required computational time on
the number of samples per each region to visit. In
this case, a simple problem with 4 regions and D4
constraint is considered and the computational time
is compared with the ETSP+LIO algorithm proposed
in [7].

6. Results
The performance of the proposed modification of the
sampling based algorithm has been evaluated in a
series of scenarios. The evaluated instances of the
DTSPN were generated randomly for convex regions
satisfying the D4 constraint. Several shapes of the
regions have been considered: points, disks with the
radius equal to ρ, ellipses with the semi-axis 2ρ and
0.5ρ, and convex polygons with up to 6 vertices cre-
ated from a circle with the radius ρ. A relatively
high and uniform density of the regions for the D4
constraint has been considered by generating centers
of the regions inside a bounding box with the side
6
√
nρ, where n is the number of the regions to be

visited by the Dubins vehicles. An example of the
examined problems is depicted in Figure 2.

(a) . D4 convex regions (b) . D1 convex regions

Figure 2. Examples of the randomly generated in-
stances of the DTSPN.

The examined algorithms are denoted as follows.
The newly proposed modification of the sampling-
based algorithm is denoted Sample+ATSP. The al-
gorithm is compared it with the evolutionary ap-
proaches [14] and [15] denoted as Genetic and
Memetic, respectively. In addition, we implemented
three variants of the decoupled approach based on the
solution of the ETSP utilized as the heuristic estima-
tion of the permutation of the visits to the regions.
The first decoupled approach is denoted as ETSPN+AA
and it is based on the Alternating Algorithm (AA) [2].
The second method is denoted as the ETSP+LIO [7] and
is based on local optimization of position and heading
of the waypoints. The last method is derived from
the ETSP+LIO, but only local iterative optimization of
the heading is considered, this method is denoted as
the ETSPN+HoLIO.
The quality of found solutions has been evaluated

regarding a dedicated computational time for prob-
lems with n = 20 and n = 40 regions with the D4

constraint. The quality is measured as the ratio of the
path length found by the particular algorithm to the
solution provided by the ETSP+LIO algorithm, simi-
larly as in [7]. All instances were generated randomly,
and therefore, 50 trials have been solved for each prob-
lem and the algorithm variants. The achieved results
are depicted in Figure 3 for the 20 regions and in
Figure 4 for the 40 goal regions.

Time [s]

10
-2

10
-1

10
0

10
1

10
2

R
e
la

ti
v
e
 l

e
n
g
th

 o
f 

th
e
 s

o
lu

ti
o
n

1

1.1

1.2

1.3

1.4

1.5

ETSP + LIO

ETSPN + HoLIO

ETSPN + AA

Memetic

Genetic

Sample + ATSP

Figure 3. Average ratio of the tour length (from 50
trials) according to the ETSP+LIO solution for the
DTSPN with n=20 convex regions. Plots start from
the time when the first solution is available.

Time [s]

10
-2

10
-1

10
0

10
1

10
2

R
e
la

ti
v
e
 l

e
n
g
th

 o
f 

th
e
 s

o
lu

ti
o
n

1

1.1

1.2

1.3

1.4

1.5

ETSP + LIO

ETSPN + HoLIO

ETSPN + AA

Memetic

Genetic

Sample + ATSP

Figure 4. Average ratio of the tour length (from 50
trials) according to the ETSP+LIO solution for the
DTSPN with n=40 convex regions. Plots start from
the time when the first solution is available.

All the algorithms have been implemented in C++
and tested on a single core of the Intel Core i5-M480
CPU running at 2.67 GHz. The processor was accom-
panied with 4 GB RAM.

6.1. Discussion
The presented results show that the proposed modifi-
cation of the sampling-based algorithm can be consid-
ered as a meaningful alternative to the evolutionary
based algorithms. In the case of the high number
of regions to visit (n = 40), the modified sampling-
based algorithm has even superior results to the both
Genetic and Memetic algorithms, while it is less com-
putationally demanding.
In the results depicted in Figures 3 and 4, the

ETSP+LIO algorithm achieved the best results among

60



vol. 2/2015 The Dubins Traveling Salesman Problem with Neighborhoods

the evaluated algorithms. This is caused by the fact,
that all instances of the DTSPN were generated with
non-overlapping regions with the D4 constraint and
the ETSP+LIO has been designed on top of the prop-
erties of the optimal solution of such a problem and
thus it directly searches for good solutions [7].

7. Conclusions
In this paper, we proposed a modification of the
sampling-based algorithm for the DTSPN. The pro-
posed algorithm repeatably executes the original
sampling-based algorithm with an increasing number
of the samples per each region. By this modification,
the newly developed algorithm provides the first solu-
tion very quickly that can be further improve if more
time is available. This makes the algorithm suitable
in situations where a solution has to be found quickly
and where the maximum time that can be dedicated
for the computation is not known in advance.

We also compared the modified algorithm with other
existing approaches on the randomly generated in-
stances of the DTSPN with the D4 constraint. The
modified algorithm provides better results than the
implemented evolutionary algorithms while it is less
computationally demanding.
A further comparison of the algorithms’ perfor-

mance in the instances of the DTSPN where regions
to visit are closer or overlapping is a subject of our
future work.

Acknowledgements
The presented work has been supported by the Czech
Science Foundation (GAČR) under research project No.
GP13-18316P.

References
[1] 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 pp. 497–516, 1957.
doi:10.2307/2372560.

[2] K. Savla, E. Frazzoli, F. Bullo. On the point-to-point
and traveling salesperson problems for Dubins’ vehicle.
In Proceedings of the American Control Conference, pp.
786–791. IEEE, 2005. doi:10.1109/ACC.2005.1470055.

[3] A. Dumitrescu, J. Mitchell. Approximation algorithms
for TSP with neighborhoods in the plane. J Algorithms
48(1):135–159, 2003.

[4] J. T. Isaacs, D. J. Klein, J. P. Hespanha. Algorithms
for the traveling salesman problem with neighborhoods
involving a dubins vehicle. In American Control
Conference (ACC), 2011, pp. 1704–1709. IEEE, 2011.
doi:10.1109/ACC.2011.5991501.

[5] X. Ma, D. A. Castanon. Receding horizon planning
for Dubins traveling salesman problems. In 45th IEEE
Conference on Decision and Control, pp. 5453–5458.
2006. doi:10.1109/CDC.2006.376928.

[6] J. Le Ny, E. Feron, E. Frazzoli. On the Dubins
Traveling Salesman Problem. IEEE Transactions on
Automatic Control 57(1):265–270, 2012.
doi:10.1109/TAC.2011.2166311.

[7] P. Váňa, J. Faigl. On the Dubins Traveling Salesman
Problem with Neighborhoods. International Conference
on Intelligent Robots and Systems (IROS) pp.
4029–4034, 2015.

[8] X. Goaoc, H.-S. Kim, S. Lazard. Bounded-curvature
shortest paths through a sequence of points using
convex optimization. SIAM Journal on Computing
42(2):662–684, 2013. doi:10.1137/100816079.

[9] J. T. Isaacs, J. P. Hespanha. Dubins traveling salesman
problem with neighborhoods: a graph-based approach.
Algorithms 6(1):84–99, 2013. doi:10.3390/a6010084.

[10] X. Yu, J. Hung. Optimal path planning for an
autonomous robot-trailer system. In 38th Annual
Conference on IEEE Industrial Electronics Society
(IECON), pp. 2762–2767. 2012.
doi:10.1109/IECON.2012.6389140.

[11] K. J. Obermeyer, P. Oberlin, S. Darbha. Sampling-
based path planning for a visual reconnaissance
unmanned air vehicle. Journal of Guidance, Control, and
Dynamics 35(2):619–631, 2012. doi:10.2514/1.48949.

[12] C. E. Noon, J. C. Bean. A lagrangian based
approach for the asymmetric generalized traveling
salesman problem. Operations Research 39(4):623–632,
1991. doi:10.1287/opre.39.4.623.

[13] S. Lin, B. W. Kernighan. An effective heuristic
algorithm for the traveling-salesman problem. Operations
research 21(2):498–516, 1973. doi:10.1287/opre.21.2.498.

[14] K. J. Obermeyer. Path planning for a uav
performing reconnaissance of static ground targets in
terrain. In AIAA Guidance, Navigation, and Control
Conference, pp. 10–13. 2009. doi:10.2514/6.2009-5888.

[15] X. Zhang, J. Chen, B. Xin, Z. Peng. A memetic
algorithm for path planning of curvature-constrained
uavs performing surveillance of multiple ground targets.
Chinese Journal of Aeronautics 27(3):622–633, 2014.
doi:10.1016/j.cja.2014.04.024.

[16] K. Helsgaun. LKH solver 2.0.7.
http://www.akira.ruc.dk/~keld/research/LKH.
[cited 31 Mar 2015].

61

http://dx.doi.org/10.2307/2372560
http://dx.doi.org/10.1109/ACC.2005.1470055
http://dx.doi.org/10.1109/ACC.2011.5991501
http://dx.doi.org/10.1109/CDC.2006.376928
http://dx.doi.org/10.1109/TAC.2011.2166311
http://dx.doi.org/10.1137/100816079
http://dx.doi.org/10.3390/a6010084
http://dx.doi.org/10.1109/IECON.2012.6389140
http://dx.doi.org/10.2514/1.48949
http://dx.doi.org/10.1287/opre.39.4.623
http://dx.doi.org/10.1287/opre.21.2.498
http://dx.doi.org/10.2514/6.2009-5888
http://dx.doi.org/10.1016/j.cja.2014.04.024
http://www.akira.ruc.dk/~keld/research/LKH

	Acta Polytechnica CTU Proceedings 2:57–61, 2015
	1 Introduction
	2 Related Work
	3 Problem Definition 
	4 Existing Methods 
	4.1 Decoupled Methods
	4.2 Sampling-Based Methods
	4.3 Evolutionary Methods

	5 Modification of Existing Sampling-Based Algorithm 
	6 Results 
	6.1 Discussion

	7 Conclusions 
	Acknowledgements
	References