Home > Research > Publications & Outputs > Good triangulations yield good tours

Research

Electronic data

Links

Text available via DOI:

Keywords

View graph of relations

Good triangulations yield good tours

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Published

Standard

Good triangulations yield good tours. / Letchford, A N; Pearson, N.
In: Computers and Operations Research, Vol. 35, No. 2, 2008, p. 638-647.

Research output: Contribution to Journal/Magazine › Journal article › peer-review

Harvard

Letchford, AN & Pearson, N 2008, 'Good triangulations yield good tours', Computers and Operations Research, vol. 35, no. 2, pp. 638-647. https://doi.org/10.1016/j.cor.2006.03.025

APA

Letchford, A. N., & Pearson, N. (2008). Good triangulations yield good tours. Computers and Operations Research, 35(2), 638-647. https://doi.org/10.1016/j.cor.2006.03.025

Vancouver

Letchford AN, Pearson N. Good triangulations yield good tours. Computers and Operations Research. 2008;35(2):638-647. doi: 10.1016/j.cor.2006.03.025

Author

Letchford, A N ; Pearson, N. / Good triangulations yield good tours. In: Computers and Operations Research. 2008 ; Vol. 35, No. 2. pp. 638-647.

Bibtex

@article{4be1262115eb4092a87500f5a005ec65,
title = "Good triangulations yield good tours",
abstract = "Consider the following heuristic for planar Euclidean instances of the Traveling Salesman Problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.",
keywords = "Delaunay triangulation, traveling salesman problem",
author = "Letchford, {A N} and N Pearson",
year = "2008",
doi = "10.1016/j.cor.2006.03.025",
language = "English",
volume = "35",
pages = "638--647",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Ltd",
number = "2",

}

RIS

TY - JOUR

T1 - Good triangulations yield good tours

AU - Letchford, A N

AU - Pearson, N

PY - 2008

Y1 - 2008

N2 - Consider the following heuristic for planar Euclidean instances of the Traveling Salesman Problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.

AB - Consider the following heuristic for planar Euclidean instances of the Traveling Salesman Problem (TSP): select a subset of the edges which induces a planar graph, and solve either the TSP or its graphical relaxation on that graph. In this paper, we give several motivations for considering this heuristic, along with extensive computational results. It turns out that the Delaunay and greedy triangulations make effective choices for the induced planar graph. Indeed, our experiments show that the resulting tours are on average within 0.1% of optimality.

KW - Delaunay triangulation

KW - traveling salesman problem

U2 - 10.1016/j.cor.2006.03.025

DO - 10.1016/j.cor.2006.03.025

M3 - Journal article

VL - 35

SP - 638

EP - 647

JO - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - 2

ER -