Travelling Salesman Problem: Definition, Algorithms & Solutions

The Traveling Salesman Problem (TSP) is all about figuring out the shortest route for a salesperson to visit several cities, starting from one place and possibly ending at another. It's a well-known problem in computer science and operations research, with real-world uses in logistics and delivery.

There are many possible routes, but the goal is to find the one that covers the least distance or costs the least. This is what mathematicians and computer scientists have been working on for decades.

This isn’t just a theory problem. Using route optimization algorithms to find better routes can help delivery businesses make more money. It also helps to lower their greenhouse gas emissions by traveling less.

In theoretical computer science, the Traveling Salesman Problem (TSP) gets a lot of attention because it’s simple to explain but tough to solve. It’s a type of problem called combinatorial optimization and is known as NP-hard. This means the number of possible routes grows very quickly as more cities are added. Since there isn’t an efficient algorithm to solve TSP quickly, computer scientists use approximation algorithms. These methods test many different routes and pick the shortest one that costs the least.

You can solve the main problem by trying every possible route and picking the best one, but this brute-force method gets tricky as you add more destinations. The number of possible routes grows quickly, quickly overwhelming even the fastest computers. For just 10 destinations, there are over 300,000 possible routes. When there are 15 destinations, the number of routes can skyrocket to over 87 billion.

For bigger real-world Traveling Salesman Problems, tools like Google Maps Route Planner or Excel just don’t cut it anymore. Businesses turn to approximate solutions using quick TSP algorithms that use smart shortcuts. Trying to find the exact best route with dynamic programming isn’t usually practical for large problems.

In this post:

• Three Common Algorithms for the Traveling Salesman Problem
• Academic Solutions for the Traveling Salesman Problem
• Real-World Uses of the Traveling Salesman Problem
• Practical Solutions for TSP and VRP
• FAQs About The Travelling Salesman Problem

Three Common Algorithms for the Traveling Salesman Problem

1. Brute-Force Method

The brute-force method, sometimes called the naive approach, tries every possible route to find the shortest one. To use this method, you list all possible routes, calculate the distance for each one, and then pick the shortest route as the best solution.

This method works only for small problems and is mostly used for teaching in theoretical computer science. For larger problems, it's not practical.

2. Branch and Bound Method

The branch and bound method starts with an initial route, usually from the start point to the first city. It then explores different ways to extend the route by adding one city at a time. For each new route, it checks the length and compares it to the best route found so far. If the current route is longer than the best one, the algorithm "prunes" or cuts off that route, since it won’t be the best solution.

This pruning helps make the algorithm more efficient by focusing only on the most promising routes. The process continues until all possible routes have been checked, and the shortest one is chosen as the best solution. Branch and bound is a smart way to handle tough problems like the traveling salesman problem.

3. Nearest Neighbor Method

The nearest neighbor algorithm starts from a random point. From there, it finds the closest city that hasn't been visited yet and adds it to the route. This process is repeated by moving to the next closest unvisited city until all cities are included in the route. Finally, the route loops back to the starting city to complete the tour.

Although the nearest neighbor method is simple and fast, it often doesn't find the best possible route. For large or complex problems, it might end up with a route much longer than the optimal one. Still, it’s a useful starting point for solving the traveling salesman problem and can quickly provide a good enough solution.

This approach can also be used as the first step to create a decent route, which can then be improved with more advanced algorithms to get an even better solution.

Academic Solutions for the Traveling Salesman Problem

Researchers have been working for years to find the best solutions for the Traveling Salesman Problem. Here are some of the recent advancements:

1. Machine Learning for Vehicle Routing. MIT researchers use machine learning to tackle large, complex problems by breaking them into smaller, more manageable ones.
2. Zero Suffix Method. Developed by researchers in India, this technique addresses the classical symmetric Traveling Salesman Problem.
3. Biogeography-Based Optimization Algorithm. Inspired by animal migration patterns, this method uses nature's strategies to find optimization solutions.
4. Meta-Heuristic Multi-Restart Iterated Local Search (MRSILS). This approach claims to be more effective than genetic algorithms when working with clusters.
5. Multi-Objective Evolutionary Algorithm. Based on the NSGA-II framework, this method solves multiple Traveling Salesman Problems simultaneously.
6. Multi-Agent System. This system handles the Traveling Salesman Problem for N cities with fixed resources.

Real-World Uses of the Traveling Salesman Problem

Even though solving the Traveling Salesman Problem is complex, approximate solutions—often using artificial intelligence and machine learning—are valuable across many industries.

For instance, TSP solutions can enhance efficiency in last-mile delivery. Last-mile delivery is the final stage in the supply chain, where goods move from a warehouse or depot to the customer. This step is also the biggest cost factor in the supply chain. It typically costs about $10.10, while customers only pay around $8.08, with companies covering the difference to stay competitive. Reducing these costs can significantly boost business profitability.

Reducing costs in last-mile delivery is a lot like solving a Vehicle Routing Problem (VRP). VRP is a broader version of the Travelling Salesman Problem and is a key topic in mathematical optimization. Instead of finding just one best route, VRP focuses on finding the most efficient set of routes. It might involve multiple depots, many delivery locations, and several vehicles. Like the Travelling Salesman Problem, finding the best solution for VRP is also a tough challenge.

Practical Solutions for TSP and VRP

Academic solutions for the Traveling Salesman Problem (TSP) and Vehicle Routing Problem (VRP) aim to find the perfect answer to these tough problems. However, these solutions often aren't practical for real-world issues, especially when dealing with last-mile logistics.

Academic solvers focus on perfection, which means they can take a long time—sometimes hours, days, or even years—to compute the best solutions. For a delivery business that needs to plan routes every day, waiting that long isn't feasible. They need quick results to get their drivers and goods moving as soon as possible. Many businesses turn to tools like Google Maps Route Planner for a faster option.

In contrast, real-life TSP and VRP solvers use route optimization algorithms that provide near-perfect solutions in much less time. This allows delivery businesses to plan routes efficiently and swiftly, keeping their operations running smoothly.

FAQs About The Travelling Salesman Problem