Bottleneck traveling salesman problem
From Wikipedia, the free encyclopedia
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.
[edit] References
- Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A2.3: ND24, pg.212.
