Understanding the Travelling Salesman Problem (TSP)

January 2, 2020
traveling salesman problem map

The Travelling Salesman Problem (TSP) is the challenge of finding the shortest yet most efficient route for a person to take given a list of specific destinations. It is a well-known algorithmic problem in the fields of computer science and operations research.

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 for.

A set of dots representing cities in the Travelling Salesman Problem.

TSP has commanded so much attention because it’s so easy to describe yet so difficult to solve. In fact, TSP belongs to the class of combinatorial optimization problems known as NP-complete. This means that TSP is classified as NP-hard because it has no “quick” solution and the complexity of calculating the best route will increase when you add more destinations to the problem. 

A solution to the Travelling Salesman Problem

The problem can be solved by analyzing every round-trip route to determine the shortest one. However, as the number of destinations increases, the corresponding number of roundtrips surpasses the capabilities of even the fastest computers. With 10 destinations, there can be more than 300,000 roundtrip permutations and combinations. With 15 destinations, the number of possible routes could exceed 87 billion. 

Popular Travelling Salesman Problem Solutions

Here are some of the most popular solutions to the Traveling Salesman Problem:

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. 

The Branch and Bound Method

This method breaks a problem to be solved into several sub-problems. It’s a system for solving a series of sub-problems, each of which may have several possible solutions and where the solution selected for one problem may have an effect on the possible solutions of subsequent sub-problems. To solve the TSP using the Branch and Bound method, you must choose a start node and then set bound to a very large value (let’s say infinity). Select the cheapest arch between the unvisited and current node and then add the distance to the current distance. Repeat the process while the current distance is less then the bound. If the current distance is less than the bound, you’re done. You may now add up the distance so that the bound will be equal to the current distance. Repeat this process until all the arcs have been covered.

The Nearest Neighbor Method

This is perhaps the simplest TSP heuristic. The key to this method is to always visit the nearest destination and then go back to the first city when all other cities are visited. To solve the TSP using this method, choose a random city and then look for the closest unvisited city and go there. Once you have visited all cities, you must return to the first city.  

Link to Routific's Route Optimization API

Academic Solutions to TSP

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

 

Real-world TSP Applications

Despite the complexity of solving the Travelling Salesman Problem, it still finds applications in all verticals. 

For instance, efficient solutions found through the TSP are being used in the last mile delivery. Last mile delivery refers to the movement of goods from a transportation hub, such as a depot or a warehouse, to the end customer’s choice of delivery. Last mile delivery is the leading cost driver in the supply chain. Companies usually shoulder some of the costs to better compete in the market. In fact, a last mile delivery costs the company an average of $10.1, but the customer only pays an average of $8.08. This is the reason why businesses strive to minimize the cost of last mile delivery. 


An illustration of a simple Vehicle Routing Problem (VRP).

The minimization of costs in last mile delivery is essentially a Vehicle Routing Problem (VRP). VRP is a generalized version of the TSP and is one of the most widely studied problems in mathematical optimization. It deals with finding a set of routes or paths to reduce delivery costs. The problem domain may involve a set of depot locations, hundreds of delivery locations, and several vehicles. As with TSP, determining the best solution to VRP is NP-hard, so the number of problems that can be solved, optimally, using combinatorial optimization or mathematical programming may be limited. Thus, commercial solvers usually use heuristics—these are like shortcuts for our brain, eliminating a lot of math or calculations for a quick and easy solution—due to the frequency and size of real world VRPs they need to solve. 

 

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 those route solutions so they can get their drivers and their goods out the door as soon as possible.

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're a developer and want to know more about real-life TSP and VRP solvers, check out the resources below:

Route Optimization API - TSP Solver

Route Optiization API - VRP Solver

Link to Routific's Route Optimization API