Traveling Salesman Problem (TSP) and How Tech Can Solve It

Updated: Mar 9, 2023

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

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:     The Definitive Guide to Logistics Route Optimization

Saves fuel and labor costs

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!

---