The Travelling Salesman Problem [And How To Solve It]
The Travelling Salesman Problem (TSP) refers to the challenge of finding the shortest route between any multiple stops on a map.
![The travelling salesman problem [and how to solve it]](/blogs/content/images/size/w2000/2023/03/The-travelling-salesman-problem--and-how-to-solve-it-.png.webp)
The travelling salesman problem (TSP) 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 are 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, 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 look at the problem in a bit more detail, as well as discuss the importance of it for various industries including couriers and last mile carriers. If you are struggling with routing salespeople or delivery teams then we have the solution for you. We’ll also take a look at some of the solutions to the problem and discuss which route optimization software is the 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
- Possible solutions to the travelling salesman problem
- How to practically address the TSP
- How SmartRoutes helps to solve the TSP
What is the Travelling Salesman Problem?
The Travelling Salesman Problem (TSP) refers to the challenge of finding the shortest route between any multiple stops 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 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 of vehicles, ensuring that they are all delivering goods in the most efficient manner can be the difference between having a viable business model, or not.
By attempting to solve the TSP, we can find the most efficient routes for delivery drivers to take when out on the road. This results in less distance being travelled, less fuel being used and fewer hours driven. This means a double bonus for the balance sheet in any delivery-based business operation.
But the travelling salesman problem (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 this problem (TSP) also trickles 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, it 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.
SmartRoutes Route Planning Software
Streamline your entire delivery process, all from one platform
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:
1. The ‘Brute-Force’ check
The trouble with the travelling salesman problem (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 and then selects the route that is actually the shortest.
2. The branch and bound approach
The branch and bound approach 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 to the one nearest to the depot. By using nodes, and attaching ‘costs’ to each node, the algorithm estimates how likely a given choice is to lead to a solution to the problem.
3. 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.
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 Travelling Salesman 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!
While 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 become more powerful than ever, route planning and optimization can be done in a matter of seconds. There are 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:
To create the quickest and most efficient routes for delivering goods by road as quickly as is technically possible.
Now as we’ve discussed, there isn't a cut-and-dry solution to the travelling salesman problem. 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.
If you're looking to create a great delivery experience for your customers then look no further than SmartRoutes. You can try it out with our 7-day free trial!
Frequently asked questions
1. What is the traveling salesman problem (TSP), and why is it important?
The traveling salesman problem (TSP) is a classic optimization problem in which a salesperson must find the shortest possible route that visits a set of given cities exactly once and returns to the starting city. It's important because it has applications in various fields like logistics, transportation, and manufacturing, where efficient routing and cost-saving are crucial.
2. Are there practical applications of TSP-solving algorithms?
Yes, TSP-solving algorithms have numerous practical applications. For instance, they are used in optimizing delivery routes for couriers and delivery services, planning circuit design on computer chips, and even in DNA sequencing.
3. What are some common algorithms to solve the traveling salesman problem?
There are several algorithms to solve the TSP, including:
- Brute-Force Method: Exhaustively explores all possible routes.
- Nearest Neighbour: Select the nearest unvisited city at each step.
- The Branch and Bound Approach: This pays attention to finding the lowest possible cost for the remaining pathways.
4. What are the limitations and challenges associated with solving the traveling salesman problem?
Solving the TSP can be challenging due to its computational complexity. As the number of cities increases, the problem becomes exponentially harder to solve. Additionally, approximating an optimal solution for large datasets can be time-consuming. Researchers are continually working on algorithms to address these challenges and find efficient solutions for real-world TSP instances.
If you enjoyed this blog, you might also be interested in:
Michael Santry
