Traveling Salesman Problem: What is it? How to Solve It?

Salespersons are required to travel frequently as a part of their job, with the aim of maximizing their business opportunities. However, their daily schedules are often subject to sudden changes due to scheduled and last-minute customer appointments, making it difficult for them to plan optimal travel routes. As a result, salespersons are forced to take longer routes to reach their destinations, which can result in missed appointments and lost business opportunities.

What is the Traveling Salesman Problem (TSP)? 

The Traveling Salesman Problem (TSP) involves finding the shortest possible route to multiple destinations and returning to the starting point. However, this is a complex task due to various constraints such as traffic, last-minute customer requests, and strict delivery windows. Successfully solving the TSP challenge can optimize supply chains and reduce logistics costs, making it an important problem to tackle.

Despite its seemingly simple definition, the TSP becomes increasingly difficult as more cities are added to the itinerary. For example, when delivering to six cities, there could be up to 360 possible routes to consider. Finding the most efficient and feasible path requires evaluating every possible route, which is a computationally challenging task. This has been an ongoing problem since the 1990s.

The TSP has relevance in various industries, such as astronomy, computer science, car navigation, agri-business, airline crew scheduling, computer-generated art, internet planning, logistics planning and scheduling, and microchip production.

What is the objective of TSP?

The problem statement for the Traveling Salesman Problem (TSP) has remained the same over the years: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” This was one of the most well-formulated optimizations in 1930 and remains a powerful solution for logistics-related problems. Variations in TSP problems have since made a disruptive difference in many other areas, including DNA sequencing.

TSP is no longer just about the problem of a salesman traveling to multiple cities in the least amount of time, using the least amount of money, while traveling the shortest distance. It now involves the world gearing towards the Fourth Industrial Revolution.

As cutting-edge technology is being integrated into manufacturing, TSP provides access to a wide variety of operations. For instance, a TSP variation could help design an efficient microchip. Similarly, an asymmetric version of TSP can optimize the set-up cost of a paint manufacturing plant by rearranging the vicinity of colors.

Is the Traveling Salesman Problem solvable?

Considering the basic problem itself, optimizing the logistics of a traveling salesman is under more monetary pressure than ever in history. Even if the problem is kept within city limits, it would be significant enough to become news. This is a real problem at a time when convenience is preferred over everything. A country’s GDP depends on its e-commerce purchases, which is something TSP enthusiasts didn’t foresee five decades ago.

India’s e-commerce industry is expected to contribute $300 billion by 2030, and the entire burden of it rests on the backseat of a delivery bike or transport. There are significant costs associated with this, particularly with return logistics being a pain point. What complicates the TSP logic further is the ground reality where the whole market is dependent upon cash-on-delivery, making it impossible to determine if a delivery will earn its cost back at times.

The problem also manifests itself in ride-sharing. Those who carpool to work heavily depend on affordable and comfortable transportation, and the twice-a-day practice that occurs during rush hour is not easy on anyone. There is added time and pressure for picking up each passenger, constant deviation from the main route to drop off others, and stress associated with it cannot be optimized.

Why is the Traveling Salesman Problem crucial to solve?

The Traveling Salesman Problem is a serious challenge for the logistics and supply chain industry because it involves optimizing the delivery routes for multiple destinations while considering various constraints such as traffic, delivery windows, and customer requests.

With multiple vehicles, more cities and multiple sales professionals, TSP becomes more challenging to solve. Not solving the TSP makes it difficult for sales professionals to efficiently reach their customers, and lead to a fall in business revenues.

Solving traveling salesman problems benefit businesses in numerous ways:

• Saves fuel and reduces the hours traveled by the sales and field professionals 
• Minimizes the distance traveled, thereby reducing the carbon footprint considerably
• Timely meetings with clients and on-time delivery of goods 
• Elevate last-mile customer experience for delivery and field service businesses

Why is the Traveling Salesman Problem challenging to solve? 

In theory, solving the Traveling Salesman Problem (TSP) is relatively simple as it involves finding the shortest route for every trip within a city. However, as the number of cities increases, manually solving TSP becomes increasingly difficult. With just 10 cities, the permutations and combinations are already numerous. Adding just five more cities can exponentially increase the number of possible solutions.

It’s impossible to find an algorithm that solves every single TSP problem. There are also some constraints that make TSP more challenging to solve:

• No automated records of scheduled and last-minute business appointments 
• Traffic congestion
• Sudden change of routes 
• Increasing number of last-minute business appointments 
• Stricter customer time windows 
• Rising operational fleet costs

All these constraints give a clear insight that TSP is a real-world problem. It is impossible to solve this challenge with even the best of your manual efforts. Thus, it is necessary to harness the power of technology to manage the TSP problem efficiently.

Using the Hungarian method to solve the Traveling Salesman Problem

To feel the intensity of the problem closely, one can try solving it using the Hungarian method. If one assumes that a delivery executive makes 15 stops in a day, it would still be too large to optimize by hand. In the ride-sharing example where the car has to make four stops—picking up three passengers and returning to the point of origin—costs need to be allocated between rides. It is important not to repeat the same route twice and to solve the TSP to arrive at the minimum cost.

The calculation may seem quite simple at the moment, but scaling the execution of such optimized routes to handle deliveries worth $300 billion is a huge challenge. It would not only overwhelm one’s mind but quite possibly the RAM of one’s computer too. It seems unfair that such a large computational problem, which has taken decades to solve, has suddenly become so large that only a few have the power to tackle it.

Three popular Travelling Salesman Problem Algorithms

Common algorithms in Travelling Salesman Problem include the brute-force approach, the branch and bound method, and the nearest neighbor heuristic. The Hungarian method is also applied in certain assignment-based variations. The following sections explain these approaches in detail.

1. The Brute-Force Approach

The brute-force approach, also known as the naïve method, works by checking every possible route and then choosing the shortest one. This guarantees the best solution but is only practical when the number of cities is very small.

How the routes are calculated:

• If there are n cities and the starting city is fixed, the total number of possible routes is calculated as (n-1)!.
• In a symmetric problem, where a route and its reverse are the same, the number of unique routes is (n-1)! / 2.

For example:

• With 6 cities in a symmetric TSP, the total is (6-1)! / 2 = 120 / 2 = 60 unique routes.
• With 10 cities, the total becomes (10-1)! / 2 = 362,880 / 2 = 181,440 unique routes.

Because the number of routes grows so quickly, brute force is only useful for very small problems or theoretical examples.

2. The Branch and Bound Method

Similar to the brute force method, the branch and bound method also guarantees the best solution, but it avoids wasting time on options that cannot lead to shorter routes. The algorithm builds a route step by step and cuts off paths that are already longer than the best one found so far.

• If a sales representative plans visits to 8 clients and one partial route already exceeds the best distance, that route is dropped.
• This pruning reduces the total number of routes to check, making the process faster than brute force.

Branch and bound is more efficient than brute force, but it still becomes slow as the number of cities increases.

3. The Nearest Neighbor Method

The nearest neighbor method is a heuristic that builds a route quickly but does not always give the best one. It works by starting at one city, then always moving to the nearest unvisited city until all are covered, and finally returning to the start.

• A technician might leave the office, go to the nearest customer, then to the next closest, and continue until all are visited.
• The route is built quickly, but it can be longer than necessary because it only looks at the next closest step.

Companies often use nearest neighbours to create a starting route, which can then be improved with refinement methods such as 2-opt or 3-opt.

Where the Hungarian Method Fits

The Hungarian method does not solve the full Travelling Salesman Problem but is valuable for assignment-based variations where resources must be matched to tasks at the lowest cost.

• In ride-sharing, it can assign the right driver to each passenger.
• In delivery, it can match drivers to orders in the cheapest way.

It is useful for these assignment problems but cannot create complete multi-stop tours on its own. In practice, it is combined with routing algorithms when both assignment and routing need to be solved together.

Academic TSP solutions

Academic research on the Travelling Salesman Problem has produced a variety of methods, including machine learning models, the Zero Suffix Method, Biogeography-Based Optimization, MRSILS, Multi-Objective Evolutionary Algorithms, and Multi-Agent Systems. The following are some of the most notable solutions:

• Machine Learning for Vehicle Routing

Researchers at MIT have applied machine learning to break large NP-complete problems like TSP into smaller sub-problems. By solving the smaller parts first and combining them, machine learning models can speed up the overall routing process for large networks.

• Zero Suffix Method

This method focuses on solving the classical symmetric TSP. It simplifies the complexity of evaluating routes and aims to reduce the calculation load compared to traditional exact methods.

• Biogeography-Based Optimization (BBO)

Inspired by the migration strategies of animals, BBO treats potential solutions like “habitats” and improves them by exchanging features, much like species adapt in nature. It is used to tackle optimization problems, including TSP.

• Meta-Heuristic Multi Restart Iterated Local Search (MRSILS)

This method repeatedly restarts local searches from different points to escape poor-quality solutions. MRSILS can outperform Genetic Algorithms, especially when cities are grouped into clusters.

• Multi-Objective Evolutionary Algorithm (MOEA)

Based on NSGA-II, this approach solves multiple TSPs at once. It is designed for cases where there are several objectives to balance, such as minimizing distance while also minimizing travel time or cost.

• Multi-Agent System

This approach uses multiple agents that work together to plan routes across a set of cities with fixed resources. Each agent explores part of the solution space, and their combined results help in finding efficient routes.

Real-world TSP Examples

The Travelling Salesman Problem is more than a mathematical puzzle. Its approximate solutions, powered today by artificial intelligence and machine learning, are used directly in logistics to improve efficiency, cut costs, and increase service reliability.

• Last-Mile Delivery

Last mile is the most expensive stage of logistics. According to a Capgemini report, last-mile delivery accounts for 41% of total supply chain costs. By applying TSP-based optimization, logistics companies can reduce travel distances, group deliveries more efficiently, and complete more stops per route, directly lowering costs.

• UPS and ORION

UPS developed ORION (On-Road Integrated Optimization and Navigation), an advanced route optimization platform that solves routing problems similar to TSP at massive scale. ORION saves UPS an estimated 100 million miles per year, reducing fuel consumption and improving delivery efficiency.

• Amazon’s Last-Mile Routing Challenge

Amazon partnered with MIT and released operational routing data covering over 9,000 routes across U.S. cities to push innovation in solving large-scale last-mile problems. The initiative highlights how e-commerce leaders rely on TSP-inspired models to manage complex real-world deliveries.

• Grocery and On-Demand Delivery

In grocery and e-grocery logistics, routing systems based on TSP are used to balance delivery density and service speed. A study showed that dynamic routing could improve delivery times in on-demand delivery settings.

These examples show that TSP-inspired optimization is not only academic but also central to how global logistics leaders manage the rising demands of delivery, fuel costs, and customer expectations.

How does Artificial Intelligence technology help in solving the Traveling Salesman Problem? 

Modern enterprises want to attract customers by providing superior service. A customer that interacts with an enterprise for a business opportunity wants the business to value their needs. 

Most customers make business decisions based on how salespeople from an enterprise respond to their requirements. The crucial aspect that they look out for in a salesperson is whether they are able to be on time for business appointments. A salesperson that travels to multiple locations should ensure they attend business appointments on time.

The Traveling Salesman Problem makes it way more difficult for salespersons to make their business appointments on time and reach their sales targets. With a lot of complexities involved in routes traveled, it is necessary for them to employ the right technology to counter them. Artificial Intelligence (AI) plays an active role in helping businesses counter route inefficiencies and solve TSP.

AI combines human intuition with complex mathematics in real-time. It analyzes a massive amount of data clearly and quickly. It mainly helps a modern enterprise to make operational, strategic and tactical decisions.

Here’s how AI solved TSP in many modern enterprises.

Makes optimized decisions for each vehicle and route

With increasing business appointments, it would be difficult for enterprise businesses to control operational fleet costs. It is highly challenging to manage crucial business appointments without the help of technology, especially when the business handles multiple vehicles and multiple salespersons.

AI technology helps operation managers in a business to prepare and assign optimal sales schedules for their workforce. By taking into account vicinity, vehicle capacity, customer time window, skills of sales professionals, driver skills and so on, it generates optimal appointment schedules. These optimal schedules help the businesses strictly adhere to the Service Line of Agreement (SLA).

Read about: The Definitive Guide to Logistics Route Optimization

According to the “An Analysis of the Operational Costs of Trucking: 2022 Update”, the average fuel cost per mile decreased further from $0.308 in 2020 to $0.296 in 2021.

Since the outbreak of the Covid-19 pandemic in 2020, fuel costs have been at record low levels. However, as the world moves towards a post-pandemic stage in 2023, fuel costs have started to rise steadily. The Ukraine-Russia war in 2022 and its trade shocks have had a significant impact on fuel prices, resulting in a sharp increase. As a result, fuel costs have become a larger proportion of operational costs for carriers in 2023.

The increasing number of appointments on a daily basis for salespersons makes it difficult for businesses to minimize fuel costs.

Employing the right technology like AI will help salespersons complete the maximum number of customer appointments by traveling a minimal distance. Its optimally allocated route plans reduce the traveling time and help businesses avoid wastage of fuel and labor costs.

Recognize the right addresses

When you are in a rush to complete your sales visits, unclear addresses can induce delays. If the driver is going to ride in an unfamiliar area, delays will increase. These delays can even cause missed appointments.

By using an AI application like route optimization software, enterprise businesses can avoid delays caused due to incorrect addresses. Its competent geocoding capabilities convert unclear or incomplete text addresses into geographical coordinates, thereby reducing the chances of reaching wrong customer locations.

Reduces cost per mile

According to the “An Analysis of the Operational Costs of Trucking: 2022 Update” by the American Transport Research Institute, the average cost per mile of trucks continued to decrease from $1.646 in 2020 to $1.585 in 2021.

As fuel costs continue to rise and the world moves towards a post-pandemic period, there is a potential for an increase in the average cost per mile for trucks. This poses a challenge for modern enterprise businesses who want their salespersons to reach their targets without increasing operational fleet costs. To achieve their sales targets, salespersons need to attend more business appointments.

AI technology with its algorithms factors business goals and delivery constraints to come up with efficient routes. Its optimal route recommendations enable salespersons to take the cost-minimizing route, thereby attending a maximum number of business appointments in a day and minimizing cost per mile. 

Improves productivity

What happens when salespersons attend business appointments in locations where they may not have many opportunities? It results in deadhead or empty miles. Empty miles kill the productivity of the fleet, and drive up operational costs considerably. 

AI technology coupled with data insights helps modern enterprise businesses analyze their past performance of sales appointments. It helps them identify business opportunities that incur huge costs and work out new ways to counter them. Based on historical data, it assists stakeholders of a business to rightsize their fleet requirements and direct them to locations where higher demand is expected. The past data records and predictive capabilities of AI help them implement strategies that improve productivity of their sales professionals.

Conclusion

With modern enterprise businesses struggling from incorrect routes and delays, it has become highly-crucial to solve TSP situations. Scientists have been working on solving the TSP problem for decades. But the modern AI-backed routing software has gone closer towards solving traveling salesman problems with their complex algorithms and enhanced route planning capabilities.

The Locus Dispatch Management Platform is the best-in-class tool that has helped many enterprise businesses solve their traveling salesman problems. Its algorithms help sales professionals generate the most efficient schedules for any complicated routes without any manual interference. By employing its AI capabilities, you can increase the number of appointments with your customers by traveling a minimal distance, thereby making sales visits more optimal.

To build the most efficient routes for your sales schedules and counter TSP effectively, try a demo with Locus now!