A related problem is the bottlenecktravelingsalesman problem (bottleneck TSP): Find the Hamiltonian cycle in a weighted graph with the minimal length of the longest edge.

In May 2004, the travelingsalesman problem of visiting all 24,978 cities in Sweden was solved: a tour of length approximately 72,500 kilometers was found and it was proven that no shorter tour exists.

In March 2005, the travelingsalesman problem of visiting all 33,810 points in a circuit board was solved using CONCORDE: a tour of length 66,048,945 units was found and it was proven that no shorter tour exists, the computation took approximately 15.7 CPU years.

The Bottlenecktravelingsalesman problem (bottleneck TSP) is a problem in discrete or combinatorial optimization.

Euclidean bottleneck TSP, or planar bottleneck TSP, is the bottleneck TSP with the distance being the ordinary Euclidean distance.

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.

Share your thoughts, questions and commentary here

Want to know more? Search encyclopedia, statistics and forums:

Press Releases |
Feeds |
Contact
The Wikipedia article included on this page is licensed under the
GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m