Papalocal
Loading…
Papalocal · Things
Work

travelling salesperson problem

Travelling salesperson problem is a NP-hard problem in combinatorial optimization.

All 3 facts, and where they come from

Facts

3 facts · 0 confirmed by two sources · 0 cited · 3 from one source

What it is
optimization problem One source
Named after
peddler One source
door-to-door One source

Where this comes from

Papalocal keeps its own record. It started from these sources; what each one said is kept here as it was copied, so a change on their side never changes this page by itself. Tap one to read its version.

What Wikidata says · copied November 17, 2026 · revision 2536546914
Described as
NP-hard problem in combinatorial optimization
Other names
traveling salesman problem, travelling salesman problem, traveling salesperson problem, round-trip problem, traveling saleswoman problem, travelling saleswoman problem, travelling salespersons problem, traveling salespersons problem, travelling salespeople problem, traveling salespeople problem, traveling saleswomen problem, travelling saleswomen problem
What it is
optimization problem
Named after
peddler; door-to-door
Wikipedias with a page
42

Wikidata item Q322212 (wikidata.org/wiki/Q322212), public domain (CC0). Copied 2026-11-17.

What Wikipedia says · copied November 17, 2026 · revision 1374921782

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.

From the Wikipedia article “Travelling salesman problem” (en.wikipedia.org/wiki/Travelling_salesman_problem), by its contributors, under CC BY-SA 4.0 (creativecommons.org/licenses/by-sa/4.0/). Copied 2026-11-17; not changed.

Confirmed Two sources agree. Cited One source, and it names where it got it. One source One source, without a reference of its own. Sources disagree The sources disagree. We show the best-supported value and keep theirs below.

Picture: Wikimedia Commons: TSP Deutschland 3.png · See Commons file page

People connected 1

Known for it