The travelling salesman problem [and how to solve it]

The travelling salesman problem is a huge challenge for last mile delivery teams and can be the difference between profitability or not.

The travelling salesman problem [and how to solve it]
The travelling salesman problem

The travelling salesman problem and our supply chain

The travelling salesman problem (TSP) sounds like a simple conundrum to wrestle with and then solve but it is actually one of the biggest challenges to our supply chain and mathematics has been unable to come close to solving it. Put simply, it refers to the efforts of a door-to-door salesman trying to find the shortest and/or quickest way to serve all of the stops on his list of visits in a given time period (usually a working day).

Although it was once the problem of a salesperson, today there’s far more workers that are faced with it. In recent years, the explosion of eCommerce and online shopping has seen more and more deliveries made directly to consumers' homes than ever before. For the delivery drivers responsible for these ‘drops’, it can mean delivering to over 100 individual locations on any given day.

So, getting the travelling salesman problem solved is mission critical!
In this article, we’ll define the problem in a bit more detail, as well as discuss the importance of it for various industries including couriers and last mile carriers. We’ll also take a look at some of the solutions to the problem and discuss what computational programmes or route planning softwares are most suited to solving your own TSP problem.

In this article you will learn:

  • What is the travelling salesman problem?
  • Why the travelling salesman problem is important
  • Has the travelling salesperson problem been solved?
  • Possible solutions to the Travelling Salesman Problem
  • How to practically address the TSP
  • How SmartRoutes helps to solve the TSP
  • How to address your vehicle routing optimization

What is the travelling salesman problem?

The Travelling Salesman Problem (TSP) refers to the challenge of finding the shortest route between any multiple of locations or waypoints on a map. It takes its name from the historical challenge faced by door-to-door salespeople who needed to visit as many potential customers in the shortest time possible to increase their sales numbers.

The TSP has become a renowned algorithmic problem in the fields of study such as physics, computer sciences, and latterly in logistics and operations research.

Why is the travelling salesman problem important?

When it comes to business, time is money and no matter what businesses you're in, if it involves travelling between multiple locations by vehicle, you need to ensure that it’s doing so in the most efficient way possible.

Consider this for a minute:

According to Route Consultant, a FedEx Ground Driver in the United States does an average of 100 miles or less per day, and completes between 150-230 stops a day, which includes pickups.

Believe it or not, there are trillions (yes, trillions) of unique ways that each of these stops could be served. Of course, some of these are most obviously not the most efficient routes, but actually determining which one is can be a challenge that is still beyond practical human capabilities.

What began as a field sales problem many moons ago is now a very real issue in the supply chain logistics industry. For any business that has more than a couple vehicles, ensuring that they are all delivering goods in the most efficient manner can be the difference between a viable and viable business model.

The TSP provides the challenge, but also the answer to the problem of multiple vehicle route optimization. By solving for the TSP, we can find the most efficient routes for delivery drivers to take when out on the road. The better it is solved, the less distance is travelled, thus the more fuel is saved and the less hours are required by the drivers. This means a double-bonus for the balance sheet in any delivery-based business operation.

But the TSP isn’t just important for businesses' financial viability. With the ever-increasing importance of reducing our carbon footprint, reducing the distances travelled directly contributes to the amount of fossil fuels being burned. We all have a part to play, and the ability to effect such important change through problem solving is a bonus for the greater society too. In fact, a recent effort to reduce the time taken for a politician to tour the UK shows how difficult the problem is.

The benefits of solving the TSP also trickle down to the customers who rely on timely and efficient delivery of goods. Whether they need the deliveries for the operations of their own businesses, or whether they rely on on-time delivery of medication for personal illness, the TSP has real-world implications for everyone that relies on it. Believe it or not, customer experience (or as it’s correctly termed in the last mile, ‘delivery experience’) is another big reason why the TSP is so important.

Has the travelling salesperson problem been solved?

A quick Google of the questions will tell you that a group of scientists in Japan have solved the travelling salesman problem. Or at least that they’ve found a way to use a processor to instantly solve for 22 locations, with the previous best being 16 ‘cities’.

But like we already discovered, delivery drivers can make over 100 stops per day, so we can’t really say that finding a way for 22 stops is really ‘solved’ definitively.

Here are a few examples of academic responses to the problem:

NSGA-II The chromosome algorithm

The multi-agent system

The zero suffix model

At SmartRoutes, our many years of work have revolved around solving the TSP. Actually, to be precise, we’ve been focussed on solving what’s known in our industry as the ‘Vehicle Routing Problem’, but in the grand scheme of things, the two problems are pretty much identical at the most basic level.

The aim of this blog isn’t to teach you how to solve the TSP using the most modern of computer algorithms, and we certainly aren;t insisting that you embark on your own mission to solve it (but we’re not discouraging it either!). Rather, we’re going to take a look at some of the ways in which it has been approached by modern means. We also take a further look at how the team at SmartRoutes have brought a real-life solution to the table and how it has proved its efficacy in the field of work.

Possible solutions to the Travelling Salesman Problem

There are literally entire books dedicated to trying to solve the TSP, so it is important to note that what we list below are ‘possible’ solutions rather than ‘actual solutions’. The TSP is what is referred to as a ‘NP-hard’ problem, which means that there literally is no known solution to it.

However, some of the more notable or practical answers to the problem are as follows:

The ‘Brute-Force’ check

The trouble with the TSP, is that technically, it is solvable. You just need to work out every possible sequence that a number of stops can be served. Right?
Well, sure, but the number of routes possible grows so rapidly that even the most powerful of modern algorithmic computers fail at the task. The trouble with creating an optimized route for 10 stops isn’t the problem per se, it’s creating the route fast.

Well, this is what the brute-force method attempts, or as it’s also known, the ‘naive approach’. It calculates all the possible permutations, finds the shortest one possible (like you might do it in your head) and then selects the route that is actually the shortest (best of luck doing that in your head!). Despite its name, it's actually a pretty beautiful piece of mathematics and more practical than the brutal or naive title suggests.

The branch and bound approach

The branch and bound approach to the TSP pays attention to finding the lowest possible cost for the remaining pathways that the initial stages of approaches like the brute-force provide.

Sometimes referred to as Parallel TSP, it assumes that we don’t want to try every single ‘possible’ route. Even using common sense, would probably narrow it down somewhat. For example, we’re not going to go to the furthest drop-off point first and then return the one nearest to the depot etc. By using nodes, and attaching ‘costs’ to each node. What the algorithm does, is it estimates how likely a given choice is to lead to a solution to the problem.

It’s quite a technical approach, and beyond the scope of this blog, but Reddit user u/rlabble gives a pretty fantastic explanation of it in his reply to a question about it here.

The Nearest Neighbour Method

With the nearest neighbour approach, the algorithm begins with the start location of the route, and then adds the stop nearest to it. A list of locations visited is already served, and if a stop has been served it is skipped and the next stop is added. Once the final stop is reached, you return to the start location again.

You may want to read that again, but it’s actually pretty practical!

The benefit of the nearest neighbour method is that it is relatively quick to do, and also more practical than the other 2 approaches outlined. The downside, however, is that it isn't always as accurate at providing the optimized route as the other two approaches.


How to practically address the TSP problem

Well, if you’ve managed to read this far, you know that the answer is unsolvable in a literal sense but in a practical sense, it is!

Whilst algorithms might not give you the very quickest or cheapest route every single time, they can do so much more effectively than the human brain can. As we’ve seen with the nearest neighbour method, it is possible to use computational power to automatically eliminate the bulk of routes that would most obviously not be efficient. Furthermore, the same computers can also then select which route is the quickest (or in mathematical terms has the lowest cost) from the remaining options.

As technology advances, and machine learning and automation becomes more powerful than ever, route planning and optimization can be done in a matter of seconds. There is essentially two processes that are complete: the mathematical equation and the automated selection of the best route. This has been a game changer for the road transport industry, particularly with larger volumes of packed goods being distributed in smaller quantities in recent years.

How SmartRoutes solves the Travelling Salesman Problem

SmartRoutes is what is referred to as delivery management software. As a total delivery software solution, it helps businesses to manage everything from order management and fulfilment, to the planning of routes for delivery drivers and the capture of proof-of-delivery for end customers.

At the core of the solution, however, is route optimization. This means that we have developed the solution with on clear overall aim:

Create the quickest and most efficient routes for delivering goods by road, as quick as is technically possible

Now as we’ve discussed, there isn;yt a cut-and-dry solution to the TSP. But here at SmartRoutes, we took what is regarded as the best approach, added the best technology and then set about accounting for every other factor that plays a role in the delivery of goods by delivery vehicles.

Some of the most obvious ones include the size of fleets, the types of roads, real-time driver analytics, and whether time or distance between stops is a better indicator of efficiency based on field-testing.

However, we have also accounted for some less obvious factors in our own algorithm. For example, our algorithm is weighted to prefer routes that have less right turns for users in the US and the UK.

Why? Well, because crossing traffic is actually a time-suck when it comes to delivering large volumes of goods. By turning left, drivers don’t have to wait for oncoming traffic to pass before continuing their route. Of course, this is also much safer for drivers which is another reason why we adopted this within our routing algorithm.

Do we profess to have solved the TSP?

No, we don’t. But what we do know is that we have accounted for a myriad of factors that can be factored into the calculations. These have been learned factors through extensive research and field-testing that we have undertaken with partners and customers over several years. And whilst academia has given us the basis for finding solutions to the problem, by layering the qualitative experience of delivery businesses owners and drivers on top of these algorithms we have brought the world of route optimization to the next level. Problems are made to be solved and the vehicle routing problem is one we’re hell-bent on fixing.


How to address your vehicle routing optimization

The Travelling Salesman Problem will continue to be the subject of much debate amongst mathematics students around the world for many years to come. Although there is regular news of it being solved, the reality is that even the fastest of computers are still some ways from being declared an outright victor.

That being said, technology has brought us closer to an answer than ever before and the technology behind it has a real and immediate benefit to any business that has vehicles delivering to multiple locations.

To learn more about vehicle routing and to stay up to date with the latest developments of SmatRoutes routing algorithm, you can sign up to our newsletter.

If you would like to see the results of our routing algorithm for yourself, you can sign-up for a 7-day free trial and create an optimized route in a matter of seconds.