skip to content

Department of Computer Science and Technology

Image: Wiktor Karkocha on Unsplash.com

Researchers here will tell a major conference today that through using a new approach to solving the 'Travelling Salesman Problem' – one of the most famously difficult questions in computer science – they have produced results that significantly outperform some current best-in-class approaches.

As postgraduate student Ben Hudson (right) will show at The International Conference on Learning Representations today, he and his colleagues here have developed a hybrid, data-driven approach to the problem that is not only producing very high-quality solutions, but doing so at a faster rate than other state-of-the-art approaches.

And this is significant because as well as being a notorious theoretical question that has puzzled researchers for 90 years, the Travelling Salesman Problem also has very real relevance to industry today. Essentially a question about how best to combine a set of tasks so that they can be performed in the fastest and most efficient way, finding good solutions to the problem can greatly help improve sectors such as transport and logistics.

As Ben's supervisor Professor Amanda Prorok says: "The importance of global logistics system was really brought home to us during the pandemic. We're very reliant on this kind of infrastructure to be more efficient – and our solution could help with that as it targets both in-warehouse logistics (e.g. the routing of robots around a warehouse to collect goods for delivery) and those outside it, e.g. the routing of goods to people."

The Travelling Salesman Problem involves a notional delivery driver who must call at a set number of cities – say, 20, 50 or 100 – that are connected by highways all in one journey. The challenge is to find the shortest possible route that calls at each destination once, and to find it quickly.

Our goal is to improve routing methods so they produce solutions that result in lower distances being travelled and therefore lower carbon emissions and reduced impact on the environment.

Ben Hudson

As Amanda Prorok (below right) explains, "There are two key components to the problem. We want to order the stops, and we also want to know the cost (in time or distance) of going from one stop to another in that order."

Dynamically changing routes
Twenty years ago the route from the warehouse to the destinations might have been fixed in advance. But with today's availability of real-time traffic information, and the ability send messages to the driver to add or remove delivery locations on-the-fly, the route may now change during the journey. But minimising its length or duration still remains key.

As Ben and his colleagues explain in their paper Graph Neural Network-Guided Local Search for the Travelling Salesperson Problem, "There's often a cost attributed to waiting for an optimal solution or hard deadlines at which decisions must be taken. For example, the driver cannot wait for a new solution to be computed – they may miss their deliveries, or the traffic conditions may change again." And that, they add, is why Wthere is a need for general, anytime combinatorial optimization algorithms that produce high-quality solutions under restricted computation time.W

They argue that their new hybrid approach does this by combining a machine learning model that provides information about what the previous best routes have been, and a ‘metaheuristic’ tool that uses this information to assemble the new route.

Ben adds: "We want to find the good solutions faster. If I'm a driver for a courier firm I have to decide what my next destination is going to be as I'm driving. I can't afford to wait for a better solution. So that's why in our research we focused on the trade-off between the computational time needed and the quality of the solution we got."

The importance of global logistics system was really brought home to us during the pandemic. We're very reliant on this kind of infrastructure to be more efficient – and our solution could help with that.

Professor Amanda Prorok

Guided Local Search algorithm
To do this, Ben came up with a Guided Local Search algorithm that could differentiate routes from one city to another that would be very costly (e.g. in time or distance) from routes that would be less costly to include in the journey. This enabled the researchers to identify high-quality (rather than optimal) solutions very quickly.

They did this by using a measure of what they call the 'global regret' – i.e. the cost of enforcing one decision relative to the cost of an optimal solution – of each city-to-city route in the Guided Local Search algorithm. They used machine learning to come up with an approximation of this 'regret'.

"We already know the correct solution to a set of these problems,” explains Ben. "So we used some machine learning techniques to try and learn from those solutions. Based on that, we try to learn for a new problem – i.e. for a new set of cities in different locations – which paths between the cities are promising.

"And when we have this information, it then feeds into the next part of the algorithm – the part that actually draws the routes. It uses that extra information about what the good paths may be to build a good solution much more quickly than it could have done otherwise."

And the results they came up with were impressive. As the team say in their paper: "Our experiments demonstrate that our hybrid, data-driven approach converges to optimal solutions at a faster rate than three recent learning-based approaches for the Travelling Salesman Problem."

In particular, when trying to solve the problem when it had a 100-city route, "we reduced the mean optimality gap from 1.534% to 0.705%, a two-fold improvement." And when generalizing from the 20-city problem route to the 100-city problem route, "we reduced the optimality gap from 18.845% to 2.622%, a seven-fold improvement."

Environmental benefits
While this research formed part of Ben’s MPhil degree, it is much more than just an academic exercise. The researchers are keenly focused on the real-life applications of their work.

Ben, who is now going on to a PhD, adds: "A lot of logistics companies are using routing methods in real life. Our goal with this research is to improve such methods so that they produce better solutions – i.e. solutions that result in lower distances being travelled and therefore lower carbon emissions and reduced impact on the environment."


Published by Rachel Gardner on Tuesday 26th April 2022