User Tools

Site Tools

Please register and/or login to edit and create pages


start:mathematics:travelling_salesman

Wikenigma - an Encyclopedia of Unknowns Wikenigma - an Encyclopedia of the Unknown Wikenigma - an Encyclopaedia of Unknowns Wikenigma - an Encyclopaedia of the Unknown

Travelling salesman problem

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?

Computing algorithms can now tackle the Travelling Salesman Problem with thousands of destinations and give an almost exact answer.

“For many other instances with millions of cities, solutions can be found that are guaranteed to be within 1% of an optimal tour.” [source: Wikipedia, above]

These estimations are sufficiently accurately for logistics and transport companies to plot highly efficient delivery/pickup routes. (Note that similar algorithms are used in the electronics industry to find efficient routing schemes for complex printed-circuit boards and chip layout.)

However, there is no formal proof providing a 100% reliable mathematical method to solve any and every situation. (The 'brute force' computing algorithms merely iteratively test a variety of pseudo-random solutions at very high speed, and then choose the best answer.)

    Share this page


DOKUWIKI IMPLEMENTATION DESIGN BY UNIV.ORG.UK