Bottleneck traveling salesman problem

Bottleneck traveling salesman problem

The Bottleneck traveling salesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization.

It is stated as follows: Find the Hamiltonian cycle in a weighted graph with the minimal weight of the most weighty edge of the cycle.

The problem is known to be NP-hard. The decision problem version of this, "for a given length "x", is there a Hamiltonian cycle in a graph "g" with no edge longer than "x"?", is NP-complete.

In an asymmetric bottleneck TSP, there are cases where the weight from node "A" to "B" is different from the weight from B to A (e. g. travel time between two cities with a traffic jam in one direction).

Euclidean bottleneck TSP, or planar bottleneck TSP, is the bottleneck TSP with the distance being the ordinary Euclidean distance. The problem still remains NP-hard, however many heuristics work better.

An example would be a salesperson traveling by train with a special ticket that is valid for any number of trips between two cities up to a certain distance. The longer the maximum distance the salesperson wants to travel, the more the ticket will cost. Like in the original Travelling salesman problem (TSP), all cities are connected with each other. Our salesperson now tries to "minimize the ticket price" by finding the route that touches all cities once (as with the original TSP, visiting the same city twice implies an imperfect route) and has the shortest maximum distance trip (the bottleneck, as you "only pay for this trip" and get the others for free). Notice that if the salesperson wanted to minimize travel "distance" instead of "price", we would have the original TSP.

From the NP properties mentioned above follows that a small increase in number of graph nodes (cities) to consider results in a massive increase in computation time needed to solve the problem. This is why heuristics are used if a route is searched - they yield a route with a high probability of being very close to the optimum in much less time.

References

* A2.3: ND24, pg.212.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Traveling Salesman Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Euklidisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Metrisches Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein… …   Deutsch Wikipedia

  • Rectilinieares Traveling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Traveling-Salesman-Tour — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Traveling-Salesperson-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Traveling Salesperson Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

  • Travelling salesman problem — The travelling salesman problem (TSP) is an NP hard problem in combinatorial optimization studied in operations research and theoretical computer science. Given a list of cities and their pairwise distances, the task is to find a shortest… …   Wikipedia

  • Travelling-Salesman-Problem — Optimaler Reiseweg eines Handlungsreisenden durch die 15 größten Städte Deutschlands. Die angegebene Route ist die kürzeste von 43.589.145.600 möglichen. Das Problem des Handlungsreisenden (engl. Traveling Salesman Problem, kurz TSP) ist ein …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”