On the dubins traveling salesman problem

Jerome Ny; Eric Feron; Emilio Frazzoli

doi:10.1109/TAC.2011.2166311

On the dubins traveling salesman problem

Jerome Ny, Eric Feron, Emilio Frazzoli

Research output: Contribution to journal › Article › peer-review

129 Scopus citations

Abstract

We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. © 2006 IEEE.

Original language	English (US)
Pages (from-to)	265-270
Number of pages	6
Journal	IEEE Transactions on Automatic Control
Volume	57
Issue number	1
DOIs	https://doi.org/10.1109/TAC.2011.2166311
State	Published - Jan 1 2012
Externally published	Yes

Bibliographical note

Generated from Scopus record by KAUST IRTS on 2021-02-18

Access to Document

10.1109/TAC.2011.2166311

Cite this

@article{7897b1a3e7f045f0b1c408785cd77572,

title = "On the dubins traveling salesman problem",

abstract = "We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. {\textcopyright} 2006 IEEE.",

author = "Jerome Ny and Eric Feron and Emilio Frazzoli",

note = "Generated from Scopus record by KAUST IRTS on 2021-02-18",

year = "2012",

month = jan,

day = "1",

doi = "10.1109/TAC.2011.2166311",

language = "English (US)",

volume = "57",

pages = "265--270",

journal = "IEEE Transactions on Automatic Control",

issn = "0018-9286",

publisher = "Institute of Electrical and Electronics Engineers",

number = "1",

}

TY - JOUR

T1 - On the dubins traveling salesman problem

AU - Ny, Jerome

AU - Feron, Eric

AU - Frazzoli, Emilio

N1 - Generated from Scopus record by KAUST IRTS on 2021-02-18

PY - 2012/1/1

Y1 - 2012/1/1

N2 - We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. © 2006 IEEE.

AB - We study the traveling salesman problem for a Dubins vehicle. We prove that this problem is NP-hard, and provide lower bounds on the approximation ratio achievable by some recently proposed heuristics. We also describe new algorithms for this problem based on heading discretization, and evaluate their performance numerically. © 2006 IEEE.

UR - http://ieeexplore.ieee.org/document/6004813/

UR - http://www.scopus.com/inward/record.url?scp=84855399736&partnerID=8YFLogxK

U2 - 10.1109/TAC.2011.2166311

DO - 10.1109/TAC.2011.2166311

M3 - Article

SN - 0018-9286

VL - 57

SP - 265

EP - 270

JO - IEEE Transactions on Automatic Control

JF - IEEE Transactions on Automatic Control

IS - 1

ER -

On the dubins traveling salesman problem

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this