The Traveling Salesman Problem (TSP) is the challenge of finding the shortest path or shortest route for a salesperson to take, given a starting point, a number of cities (nodes), and optionally an ending point. It is a well-known algorithmic problem in the fields of computer science and operations research, with important real-world applications for logistics and delivery businesses.
There are obviously a lot of different routes to choose from, but finding the best one—the one that will require the least distance or cost—is what mathematicians and computer scientists have spent decades trying to solve.
It’s much more than just an academic problem. Finding more efficient routes using route optimization algorithms increases profitability for delivery businesses, and reduces greenhouse gas emissions because it means less distance traveled.
In theoretical computer science, the TSP has commanded so much attention because it’s so easy to describe yet so difficult to solve. The TSP is known to be a combinatorial optimization problem that’s an NP-hard problem, which means that the number of possible solution sequences grows exponential with the number of cities. Computer scientists have not found any algorithm that can solve this problem in polynomial time, and therefore rely on approximation algorithms to try numerous permutations and select the shortest route with the minimum cost.
The main problem can be solved by calculating every permutation using a brute force approach and selecting the optimal solution. However, as the number of destinations increases, the corresponding number of roundtrips grows exponentially and surpasses the capabilities of even the fastest computers. With 10 destinations, there can be more than 300,000 roundtrip permutations. With 15 destinations, the number of possible routes could exceed 87 billion.
For larger real-world travelling salesman problems, when manual methods such as Google Maps Route Planner or Excel route planner no longer suffice, businesses rely on approximate solutions that are sufficiently optimized by using fast tsp algorithms that rely on heuristics. Finding the exact optimal solution using dynamic programming is usually not practical for large problems.
Three popular Travelling Salesman Problem Algorithms
Here are some of the most popular solutions to the Travelling Salesman Problem:
1. The brute-force approach
The Brute Force approach, also known as the Naive Approach, calculates and compares all possible permutations of routes or paths to determine the shortest unique solution. To solve the TSP using the Brute-Force approach, you must calculate the total number of routes and then draw and list all the possible routes. Calculate the distance of each route and then choose the shortest one—this is the optimal solution.
This is only feasible for small problems, rarely useful beyond theoretical computer science tutorials.
2. The branch and bound method
The branch and bound algorithm starts by creating an initial route, typically from the starting point to the first node in a set of cities. Then, it systematically explores different permutations to extend the route one node at a time. Each time a new node is added, the algorithm calculates the current path's length and compares it to the optimal route found so far. If the current path is already longer than the optimal route, it "bounds" or prunes that branch of the exploration, as it would not lead to a more optimal solution.
This pruning is the key to making the algorithm efficient. By discarding unpromising paths, the search space is narrowed down, and the algorithm can focus on exploring only the most promising paths. The process continues until all possible routes are explored, and the shortest one is identified as the optimal solution to the traveling salesman problem. Branch and bound is an effective greedy approach for tackling NP-hard optimization problems like the travelling salesman problem.
3. The nearest neighbor method
To implement the Nearest Neighbor algorithm, we begin at a randomly selected starting point. From there, we find the closest unvisited node and add it to the sequencing. Then, we move to the next node and repeat the process of finding the nearest unvisited node until all nodes are included in the tour. Finally, we return to the starting city to complete the cycle.
While the Nearest Neighbor approach is relatively easy to understand and quick to execute, it rarely finds the optimal solution for the traveling salesperson problem. It can be significantly longer than the optimal route, especially for large and complex instances. Nonetheless, the Nearest Neighbor algorithm serves as a good starting point for tackling the travelling salesman problem and can be useful when a quick and reasonably good solution is needed.
This greedy algorithm can be used effectively as a way to generate an initial feasible solution quickly, to then feed into a more sophisticated local search algorithm, which then tweaks the solution until a given stopping condition.
Minimizing costs in last mile delivery is essentially in last mile delivery is essentially a Vehicle Routing Problem (VRP). VRP, a generalized version of the travelling salesman problem, is one of the most widely studied problems in mathematical optimization. Instead of one best path, it deals with finding the most efficient set of routes or paths. The problem may involve multiple depots, hundreds of delivery locations, and several vehicles. As with the travelling salesman problem, determining the best solution to VRP is NP-complete.
Real-life TSP and VRP solvers
While academic solutions to TSP and VRP aim to provide the optimal solution to these NP-hard problems, many of them aren’t practical when solving real world problems, especially when it comes to solving last mile logistical challenges.
That’s because academic solvers strive for perfection and thus take a long time to compute the optimal solutions – hours, days, and sometimes years. If a delivery business needs to plan daily routes, they need a route solution within a matter of minutes. Their business depends on delivery route planning software so they can get their drivers and their goods out the door as soon as possible. Another popular alternative is to use Google maps route planner.
Real-life TSP and VRP solvers use route optimization algorithms that find a near-optimal solutions in a fraction of the time, giving delivery businesses the ability to plan routes quickly and efficiently.
If you want to know more about real-life TSP and VRP solvers, check out the resources below 👇
Marc Kuo is the Founder & CEO of Routific, a route optimization platform for growing delivery businesses. Our mission is to green the planet by reducing the mileage and fuel consumption of delivery fleets. With over a decade of experience in the last-mile industry, he has advised hundreds of delivery businesses on their route planning and delivery operations.
Frequently Asked Questions
No items found.
Liked this article? See below for more recommended reading!