Traveling Salesman Problem

Traveling Salesman Problem
Featured image credit: yuoak/iStockphoto.com

A salesman wants to visit a few locations to sell goods. He knows the names of the locations and the distances between each one. What is the shortest route the salesman should follow so that he only visits each location once before returning to the starting point?

The problem you just read is the famous traveling salesperson problem (TSP). An extension of the Hamiltonian Circuit Problem, the traveling salesperson problem is an old problem in computer science that has implications in complexity theory and the P versus NP problem.

The TSP problem was formulated in 1930, but it is one of the most studied combinatorial optimization problems even today. In 1972, Richard Karp proved that the Hamiltonian cycle problem was NP-complete, which meant that the TSP was NP-hard; this means that the complexity of calculating a correct route will increase exponentially when more cities are added to the problem.

For example, there are three possible routes if there are four cities, but there are 360 possible routes if there are six cities. This is because scientists do not only compute the most efficient path— but the one that works. This computation uses the brute-force approach-solving the problem by figuring out every single possibility and then picking the best one. In other words, look for every unique path the salesman could possibly take.

Even though computational difficulties increase with each city added to the itinerary, computer scientists have been able to calculate the optimal solution to this problem for thousands of cities since the early 90s.

For instance, there are that many towns and cities in a US State that could be a part of the delivery area of the large logistics provider. Figuring out the shortest route between all the stops the vehicle needs to make on a day-to-day basis would save a lot of time and money.

Why is TSP So Difficult To Solve?

In theory, the TSP is easy to state and can be solved by checking every round-trip route to find the shortest one. However, as the number of cities grows, the corresponding number of round-trips outstrips the capabilities of the fastest computers.

With 10 cities, there can be more than 300,000 round-trip permutations and combinations. With 15 cities, the number of possible routes might be more than 87 billion.

In the early days of computers, computer scientists hoped that someone would come up with an improved algorithm or approach for solving the traveling salesmen problem in a reasonable amount of time. However, while scientists have made progress with specific scenarios, there’s no algorithm to solve every traveling salesman problem efficiently. A one-size-fits-all algorithm might not even be possible.

Applications of TSP

The TSP still finds applications in all verticals. Efficient solutions found through the TSP are being used in astronomy, computer science, and even vehicle routing.

The TSP can also be used to find out how a laser should move when boring points into a printed circuit board. Astronomers use the concepts of TSP to determine the movement of a telescope for the shortest distance between different stars in a constellation.

Other uses for TSP include internet planning, agriculture, microchip production, and computer-generated art.

Want To See For Yourself How Route4Me Can Boost Your Profits?

Whether you want to slash the time it takes you to plan routes for your drivers, increase the number of stops they can make, or keep your customers satisfied knowing that your drivers show up on time… Route4Me helps you achieve that!

Challenges Faced by Traveling Salesmen

Almost every salesperson wakes up in the morning with the thought of making the best use of their day. They have many confirmed appointments with their customers and many more last-minute ones. Salespeople do not always have a confirmed schedule. Due to this shortcoming, salespeople often have to backtrack and take longer routes to reach customer addresses. This lack of route planning results in missed appointments and lost opportunities.

The modern-day salesman faces the additional problems of traffic congestion, last-minute customer requests, and specific delivery window timings, in addition to the route woes faced by the yesteryear’s salesperson.

If you thought the TSP from the mathematical puzzle was difficult, consider this: What if it wasn’t just one salesperson you had to plan routes for? What if you had a team of sales representatives? What if you had to split up the visits and assign them to your team? What if sales guys had different appointment slots, and your target was to keep their routes the shortest, fastest, and most effective?

Consider this: If you have a total of 100 customer addresses and there are eight salespeople in your team, there could be more than a million possible route combinations. A basic algorithm that weighs every possible combination and selects the best one will take you days, if not months.

Now, that’s a real-world challenge!

What is a route optimization, you’d ask!

Route optimization is all about finding the fastest, shortest, and most fuel-efficient route for a set of stops. It is used when you want to plan the best path while considering complexities such as salesperson schedules, customer time windows, road conditions, weather updates, and more.

How Will Route Optimization Software Address TSP?

As your sales team grows, route planning will inevitably become too complex to manage using standard tools like Google Maps or Waze. You will not be able to manually factor in things like customer time windows and weather conditions without some heavy-duty tools, and, as a result, will end up spending a lot of time planning routes. You also risk increasing your operational costs, often in the form of wasted fuel and salaries due to longer driving time.

A reliable route optimization software will help you reduce driving time and fuel consumption by finding the most efficient route for your sales team in a matter of minutes.

Your potential customers will not have a great first impression if your salespeople are late for meetings. However, adhering to schedules might be difficult- if not impossible- if route planning is done manually. Unforeseen situations such as traffic congestion or construction can make it challenging to keep salespeople on schedule and meet customers on time.

A route planner will not only help ensure timely customer meetings and cost savings but also keep salespeople safe. This is because we all tend to drive fast to “make up” for lost time, increasing the risk of an accident. A route optimizer will reduce your sales team’s drive time so that they are spending productive time with customers and positively impacting your bottom line.

Conclusion

If you look around, there will be many more TSP-like instances with people and vehicles grappling with inaccurate routes and delays.

The courier guys delivering packages to your office?

The delivery guys bringing you fresh groceries the same day you ordered?

The school buses that never miss the mark, and pick up and drop off your children at the same time every day?

Scientists have been trying to address problems like TSP for decades. The closest we’ve come- through imperfectly- are complex algorithms via easy-to-use route planner apps.

Want To See For Yourself How Route4Me Can Boost Your Profits?

Whether you want to slash the time it takes you to plan routes for your drivers, increase the number of stops they can make, or keep your customers satisfied knowing that your drivers show up on time… Route4Me helps you achieve that!

Leave a Reply

Your email address will not be published. Required fields are marked *