Faster solutions using graph neural networks

The travelling salesperson problem is a famously hard to solve, yet important computer science problem. A computer must work out the best route for a delivery driver that has to visit a list of locations. The more locations in the list the longer it takes a standard algorithm to solve the most efficient route between them. With 100 locations, finding a fully optimal solution can take a very long time. The number of routes increases exponentially with added destinations, with 10 destinations producing 300,000 roundtrip permutations and combinations. At 15 destinations, potential routes can increase to 87 billion!

Many solutions have been proposed that find good enough solutions in a certain time, and a team at the University of Cambridge have just proposed a new one that is particularly fast.

The solution uses graph neural networks to predict which routes are most likely to be part of a good solution, based on past data on which routes were the best. The solution gives a two-fold improvement for a 100-point route over existing machine learning based solutions. The authors claim the significantly improved approach could improve the efficiency of the logistics and transport sectors.