Metraipolis › archive › dc_7a7fd9d034de

Travelling salesman problem — Wikipedia (en)

Source: Wikipedia (en)
Original: https://en.wikipedia.org/wiki/Travelling_salesman_problem
License (as archived): CC-BY-SA-4.0
Archived: 2026-10-31T08:04:34.855Z
SHA-256 of the archived text: 64f3e62a727ed268d5af984a89b92b511ba3b5c13a58d34168eea277e2e45d80
Stable URL of this page: https://metraipolis.com/documento/dc_7a7fd9d034de

How to cite

Travelling salesman problem — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Travelling_salesman_problem (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_7a7fd9d034de (Metraipolis archive dc_7a7fd9d034de, sha256 64f3e62a727ed268d5af984a89b92b511ba3b5c13a58d34168eea277e2e45d80)

BibTeX

@misc{dc7a7fd9d034de,
  title = {Travelling salesman problem — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Travelling_salesman_problem},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_7a7fd9d034de; sha256 64f3e62a727ed268d5af984a89b92b511ba3b5c13a58d34168eea277e2e45d80},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Travelling_salesman_problem. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In the theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research. The travelling purchaser problem, the vehicle routing problem and the ring star problem are three generalizations of TSP. The decision version of the TSP (where given a length L, the task is to decide whether the graph has a tour whose length is at most L) belongs to the class of NP-complete problems. Thus, it is possible that the worst-case running time for any algorithm for the TSP increases superpolynomially (but no more than exponentially) with the number of cities. The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, many heuristics and exact algorithms are known, so that some instances with tens of thousands of cities can be solved completely, and even problems with millions of cities can be approximated within a small fraction of 1%. The TSP has several applications even in its purest formulation, such as planning, logistics, and the manufacture of microchips. In warehouse operations, order picking routes are often modelled as variants of the travelling salesman problem, where a picker must visit multiple storage locations and return to a start or drop-off point while minimizing travel distance or time. Slightly modified, it appears as a sub-problem in many areas, such as DNA sequencing. In these applications, the concept city represents, for example, customers, soldering points, or DNA fragments, and the concept distance represents travelling times or cost, or a similarity measure between DNA fragments. The TSP also appears in astronomy, as astronomers observing many sources want to minimize the time spent moving the telescope between the sources; in such problems, the TSP can be embedded inside an optimal control problem. In many applications, additional constraints such as limited resources or time windows may be imposed.

Tema degli esploratori: governance digitale e beni comuni (deposito sistematico; ricerca «collective intelligence»).
Fonte: Wikipedia in inglese, voce «Travelling salesman problem» — https://en.wikipedia.org/wiki/Travelling_salesman_problem
Wikidata Q322212: «problema di instradamento e di gestione dei processi» (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q322212
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Travelling_salesman_problem?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1374921782, consultata il 2026-10-31T07:50:24.885Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 77e5984536d05c3a3bc3a36b83958ffba3f64963d8346eaeb40dea34a03befab