Algorithms for the Travelling Salesman Problem

The Traveling Salesman Problem (TSP) is the challenge of finding the shortest path or shortest possible 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 in graph theory. 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 for solving travelling salesman problems 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, soon surpassing 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

TThe 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 beyond the first pair of cities, 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 traveling 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 traveling 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.‍

How route optimization algorithms work to solve the Travelling Salesman Problem.

Academic TSP solutions

Academics have spent years trying to find the best solution to the Travelling Salesman Problem The following solutions were published in recent years:

• Machine learning speeds up vehicle routing: MIT researchers apply Machine Learning methods to solve large np-complete problems by solving sub-problems.
• Zero Suffix Method: Developed by Indian researchers, this method solves the classical symmetric TSP. 
• Biogeography‐based Optimization Algorithm: This method is designed based on the animals’ migration strategy to solve the problem of optimization. 
• Meta-Heuristic Multi Restart Iterated Local Search (MRSILS): The proponents of this research asserted that the meta-heuristic MRSILS is more efficient than the Genetic Algorithms when clusters are used. 
• Multi-Objective Evolutionary Algorithm: This method is designed for solving multiple TSP based on NSGA-II. 
• Multi-Agent System: This system is designed to solve the TSP of N cities with fixed resource. 
   

Real-world TSP applications

Despite the complexity of solving the Travelling Salesman Problem, approximate solutions — often produced using artificial intelligence and machine learning — are useful in all verticals.

For example, TSP solutions can help the logistics sector improve efficiency in the last mile. Last mile delivery is the final link in a supply chain, when goods move from a transportation hub, like a depot or a warehouse, to the end customer. Last mile delivery is also the leading cost driver in the supply chain. It costs an average of $10.1, but the customer only pays an average of $8.08 because companies absorb some of the cost to stay competitive. So bringing that cost down has a direct effect on business profitability.

Minimizing costs 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 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 👇

Route Optimization API - TSP Solver

Route Optimization API - VRP Solver