The Traveling Saleman problem can be solved better by a neural network approach than by traditional methods - is this important?

The Traveling Salesman Problem (TSP) is NP Hard and so there is no point even trying to find an efficient algorithm for it. Wrong. Just because a problem is difficult to solve exactly it doesn't mean that we can't find a good solution very quickly. As long as you don't demand an exact solution, there are heuristics that provide solutions that are good enough for most purposes. However "good enough" doesn't mean that we don't want, or even need, a better solution. The main problem with creating heuristic algorithms is spotting what features might be related to the outcome. For example, I could propose an algorithm where we should visit towns according to the first letter of their names - clearly not a good heuristic because town names have nothing to do with the order that you should visit them to minimize the distance traveled. But what should you use - what features are related to the quantity you are trying to optimize?

Finding good features is something that neural networks do well and a research team from the University of Cambridge has just announced that using a neural network to help a guided local search. The idea is that if you knew the optimal solution you could work out the cost of including a different selection of route to give you a sub-optimal solution - the cost is generally called the global regret. If you knew the regret of each part of the route you could solve the problem completely by greedily selecting each part of the route to minimize the regret. Of course, you can't do this because it is equivalent to trying every possible route and this is what makes the problem NP hard. 

The solution adopted is to use a neural network to estimate the regret of each part of the path to perform a local search by varying the current solution by accepting modifications that have a lower cost.

The results are that the method outperforms other methods based on machine learning, but hand-crafted methods are still better by a large margin. It is argued that the neural network approach is more flexible in that it can take additional constraints into account, which makes it more suitable for real world real time route planning.

This research is really just another step towards an improved TSP algorithm using machine learning. We know that better algorithms exist - surely a neural network can find them? The problem is probably one of finding a good representation that the network can digest.

More Information

Graph Neural Network Guided Local Search for the Traveling Salesperson Problem

Benjamin Hudson, Qingbiao Li, Matthew Malencia, Amanda Prorok

Related Articles

Amoeba Solves Traveling Salesman Problem

The Physical Travelling Salesman Challenge

Programmer's Guide To Theory - NP & Co-NP

NP-Complete - Why So Hard?

Minimum Spanning Tree

Computational Complexity

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

Comments

Make a Comment or View Existing Comments Using Disqus

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