Combinatorial Traveling Salesman Problem Algorithms

Claudia D'Ambrosio; Andrea Lodi; Silvano Martello

doi:10.1002/9780470400531.eorms0160

Combinatorial Traveling Salesman Problem Algorithms

Claudia D'Ambrosio
, Andrea Lodi
, Silvano Martello

University of Bologna

Résultats de recherche: Le chapitre dans un livre, un rapport, une anthologie ou une collection › Chapitre › Revue par des pairs

Résumé

The traveling salesman problem (TSP) is a fundamental and well-known problem in combinatorial optimization. We start by reviewing some of its ancestors, including the famous Hamiltonian cycle problem of which the TSP is the weighted version. We then introduce the most famous formulations of both the symmetric and the asymmetric TSP, and describe combinatorial approaches for both versions of the problem. We conclude with a brief discussion on the available TSP software.

langue originale	Anglais
titre	Wiley Encyclopedia of Operations Research and Management Science
Editeur	wiley
Pages	1-9
Nombre de pages	9
ISBN (Electronique)	9780470400531
ISBN (imprimé)	9780470400630
Les DOIs	https://doi.org/10.1002/9780470400531.eorms0160
état	Publié - 1 janv. 2010
Modification externe	Oui

Accès au document

10.1002/9780470400531.eorms0160

Autres fichiers et liens

Lien vers la publication dans Scopus

Contient cette citation

@inbook{f2d421ad11d8493a9e276ad7672b3042,

title = "Combinatorial Traveling Salesman Problem Algorithms",

abstract = "The traveling salesman problem (TSP) is a fundamental and well-known problem in combinatorial optimization. We start by reviewing some of its ancestors, including the famous Hamiltonian cycle problem of which the TSP is the weighted version. We then introduce the most famous formulations of both the symmetric and the asymmetric TSP, and describe combinatorial approaches for both versions of the problem. We conclude with a brief discussion on the available TSP software.",

keywords = "Hamiltonian cycle, branch and bound, combinatorial algorithms, graph-theoretic relaxations, heuristic algorithms, software, traveling salesman problem",

author = "Claudia D'Ambrosio and Andrea Lodi and Silvano Martello",

year = "2010",

month = jan,

day = "1",

doi = "10.1002/9780470400531.eorms0160",

language = "English",

isbn = "9780470400630",

pages = "1--9",

booktitle = "Wiley Encyclopedia of Operations Research and Management Science",

publisher = "wiley",

}

TY - CHAP

T1 - Combinatorial Traveling Salesman Problem Algorithms

AU - D'Ambrosio, Claudia

AU - Lodi, Andrea

AU - Martello, Silvano

PY - 2010/1/1

Y1 - 2010/1/1

N2 - The traveling salesman problem (TSP) is a fundamental and well-known problem in combinatorial optimization. We start by reviewing some of its ancestors, including the famous Hamiltonian cycle problem of which the TSP is the weighted version. We then introduce the most famous formulations of both the symmetric and the asymmetric TSP, and describe combinatorial approaches for both versions of the problem. We conclude with a brief discussion on the available TSP software.

AB - The traveling salesman problem (TSP) is a fundamental and well-known problem in combinatorial optimization. We start by reviewing some of its ancestors, including the famous Hamiltonian cycle problem of which the TSP is the weighted version. We then introduce the most famous formulations of both the symmetric and the asymmetric TSP, and describe combinatorial approaches for both versions of the problem. We conclude with a brief discussion on the available TSP software.

KW - Hamiltonian cycle

KW - branch and bound

KW - combinatorial algorithms

KW - graph-theoretic relaxations

KW - heuristic algorithms

KW - software

KW - traveling salesman problem

UR - https://www.scopus.com/pages/publications/105026044692

U2 - 10.1002/9780470400531.eorms0160

DO - 10.1002/9780470400531.eorms0160

M3 - Chapter

AN - SCOPUS:105026044692

SN - 9780470400630

SP - 1

EP - 9

BT - Wiley Encyclopedia of Operations Research and Management Science

PB - wiley

ER -

Combinatorial Traveling Salesman Problem Algorithms

Résumé

Accès au document

Autres fichiers et liens

Empreinte digitale

Contient cette citation