The XY Traveling Salesman Problem Solved
Written by Mike James   
Friday, 14 September 2012

The traveling salesman problem is important because it is NP complete.If you can find a fast way to solve it, you have proved P=NP and changed the face of computation.

The latest result shows that a special type of  traveling salesman (TSP) problem is solvable in polynomial time.

 

tspicon1

 

The TSP problem is easy to state but difficult to solve efficiently . All you have to do is to find the shortest route a salesman would have to travel to visit each of n cities. It turns out that no algorithm that is polynomial (i.e. takes time proportional to nc where c is a constant) has been found.

This form of the TSP is NP Hard and the decision version, which just has to decide if there is a solution better than a supplied sample tour, is NP Complete.

What this means is that solving the decision version in polynomial time would provide a fast solution to all NP problems. This is not only theoretically interesting but of practical importance as public key cryptography depends on there being no such solution as it is based on a problem - factoring large numbers - that is also in NP.

You can think of TSP as being the big computational problem of computer science, but despite a lot of work not a great deal of progress has been made - unless you count special cases.

The Euclidean form of the problem simply places the cities on an xy grid and allows the salesman to travel by the straightest route between each city, i.e. as the bird flies  rather than along roads. You might not think that the Euclidean form is any easier, and you would be correct, but you can add some more constraints. The Euclidean TSP is NP-Complete, so solving it has the same effect as solving the general TSP problem.

For example, if all of the cities lie on the x-axis then you can find a fast solution. In fact you can take this a stage further - if the cities lie on any reasonable curve you can compute a solution in polynomial time. This is interesting, but the restricted problem isn't NP complete and we need to try to loosen the conditions.

The reason that the TSP on a curve is simpler is that the cities are arranged in one dimension. This suggests looking at a restricted 2D problem - the simplest of which is the XY TSP which constrains the cities to sit on the x- or y-axis or on any two straight lines at right angles.

The XY TSP problem has been studied since 1980 without much progress - until Vladimir Deineko (Warwick Business School),  Eranda Cela (University of Technology Graz) and Gerhard Woeginger (Eindhoven University) invented a polynomial algorithm. The new algorithm is about as fast as one could reasonably expect working in time proportional to n2. The algorithm is a dynamic programming approach that makes use of rules that force you to take paths between cities in particular groups.

Is there an algorithm that works faster?

Is there any way to extend the algorithm to more general Euclidean TSP?

For example, suppose you distort the arrangement just a little so that some of the cities aren't quite on the x or y axes? Could a perturbation approach work, or is there some fundamental difference as soon as the cities have a more general arrangement. This says as much about real world geometry as it does combinatorial graph theory.

 

tspicon1

 

The only problem is that the paper describing how it all works is behind a paywall and costs $31.50 to read - which is an ongoing disgrace.

More Information

The x-and-y-axes travelling salesman problem (paywalled)

First three pages of the paper

Related Articles

Travelling Salesman - A Movie About P=NP

The Physical Travelling Salesman Challenge

NP-Complete - Why So Hard?

Minimum Spanning Tree

Computational Complexity

 

raspberry pi books

 

Comments




or email your comment to: comments@i-programmer.info

 

To be informed about new articles on I Programmer, install the I Programmer Toolbar, subscribe to the RSS feed, follow us on, Twitter, Facebook, Google+ or Linkedin,  or sign up for our weekly newsletter.

 

Banner


Generative AI Training For All On Coursera
04/03/2024

Generative AI is on the loose, getting into business and commerce as well as into art, poetry and coding. Already useful, it  will become ever more useful as long as we use it properly. Coursera  [ ... ]



Quantum Company Wins Digital Startup Contest
03/03/2024

Quantum specialists Qilimanjaro is the winner of this year's Four Years From Now competition. The award was made at this year's Mobile World Congress (MWC) in Barcelona.


More News

 

Last Updated ( Saturday, 15 September 2012 )