Solving The Traveling Salesman Problem For Deliveries

The Traveling Salesman Problem (TSP) is the challenge of finding the shortest, 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, 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, or route optimization, increases profitability for delivery businesses, and reduces greenhouse gas emissions because it means less distance traveled.

In computing, the TSP has commanded so much attention because it’s so easy to describe yet so difficult to solve. In fact, it 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 increases as you add more destinations. 

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.

‍

The three most popular TSP solutions

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. 

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

3. 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.  ‍

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

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:

• 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, it still finds applications 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 in last mile delivery is essentially a Vehicle Routing Problem (VRP). VVRP, a generalized version of the TSP, 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 TSP, determining the best solution to VRP is NP-hard.

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 delivery route planning 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 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