Speak to a Friendly Routing Expert Now:

What is the Traveling Salesman Problem (TSP)?

Traveling Salesman Problem also known as travelling salesman problem explained
Featured image credit: yuoak/iStockphoto.com

The traveling salesman problem (also called the travelling salesperson problem or TSP)  is the problem of figuring out the shortest route for your delivery drivers, field sales, and service reps to take given a list of specific destinations.

Let’s understand the problem with an example.

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 travelling salesperson problem.

An extension of the Hamiltonian Circuit Problem, the TSP is an old problem in computer science that has implications in complexity theory and the P versus NP problem.

The vehicle routing problem and traveling purchaser problem are both generalizations of TSP.

We explain the travelling salesman problem in detail below.

ALSO READ: Shortest vs. Fastest Route: When You May Need Different Types

The Background of the Traveling Salesman Problem

The travelling salesman problem (TSP) 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 is a class of combinatorial optimization problems.

This means the TSP was NP-hard and the complexity of calculating the best route will increase exponentially when more destinations 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, many towns and cities in a US State 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 the Traveling Salesman Problem 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 salesman problem in a reasonable amount of time.

However, while scientists have made progress with specific scenarios, there was no efficient travelling salesman problem solver available.

A one-size-fits-all algorithm might not even be possible.

Applications of the Traveling Salesman Problem

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 traveling salesman problem 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!

Start Free 7 Day Trial

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 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, and here comes route optimization.

What is route optimization, you’d ask!

Route optimization is all about finding the fastest, shortest, and most fuel-efficient route for a set of stops.

ALSO READ: What is Route Optimization?

How to Solve the Traveling Salesman Problem with A Route Planner?

As your team grows, route planning will inevitably become too complex to manage using pen and paper or standard tools like Google Maps or Waze.

Adhering to schedules might be difficult- if not impossible- if route planning is done manually.

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.

Unforeseen situations such as traffic congestion or construction can make it challenging to keep your field reps on schedule and meet customers on time.

You would also risk increasing your operational costs, often in the form of wasted fuel and salaries due to longer driving time.

Furthermore, your customers will not have a great first impression if your salespeople are late for meetings or your delivery drivers do not show up on time.

ALSO READ: Why On-Time Delivery Is Important for Your Business

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

A route planner will help ensure timely customer meetings and cost savings and keep the field workers 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 field service reps’ drive time so that they are spending productive time with customers and positively impacting your bottom line.

ALSO READ: How to Plan a Route a Route with Multiple Stops in 30 Seconds

Conclusion about the Traveling Salesman Problem

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

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!

Start Free 7 Day Trial


About Route4Me

Route4Me has over 34,000 customers globally. Route4Me's Android and iPhone mobile apps have been downloaded over 2 million times since 2009. Extremely easy-to-use, Route4Me's apps create optimized routes, synchronize routes to mobile devices, enable communication with drivers and customers, offer turn-by-turn directions, delivery confirmation, and more. Behind the scenes, Route4Me's operational optimization platform combines high-performance algorithms with data science, machine learning, and big data to plan, optimize, and analyze routes of almost any size in real-time.