What Is the Traveling Salesman Problem?

The traveling salesman problem (TSP) asks a simple question. 

If you’re given a list of cities to visit, what’s the shortest possible route you can take that lets you visit each city once and then return to the city where you started?

You might also see the TSP called the traveling salesperson problem, vehicle routing problem, or traveling purchase problem.

The problem goes back to the 1930s when mathematician Karl Menger started studying the problem at Harvard University and then in his native Vienna, Austria.

Since then, many math whizzes have come up with ways to answer the problem.

This list of “milestones” in TSP solutions from Waterloo University has mathematicians and computer science experts solving problems covering 49 cities to 24,978 cities and even 85,900 cities.

Some computer scientists even achieved a record-breaking TSP solution more recently.

I don’t know about you, but I wouldn’t want to do that math!

That said, if you run a delivery company or eCommerce store that delivers goods to customers, the TSP impacts you.

How? I mean, you probably aren’t messing around with mathematical algorithms and equations in your day-to-day life.

The thing is, the problem is all about route optimization — which does affect you.

Route optimization is the process of finding the most efficient sequence of delivery stops. 

And that’s basically what the TSP tries to figure out.

I will talk about some of the ways the TSP is solved and give you an example of how the problem might look in practice.

How to solve the traveling salesman problem

At first glance, the TSP might not seem THAT complicated.

Again: You want to figure out the fastest routes between cities, hit each city once, and then return to your original starting point.

Logically, you might think that all you have to do is pull up a map and plot a route.

But remember, the theory makes you take a so-called Hamiltonian approach — where each vertex on the plot graph is visited only once.

Say you have ten cities to visit. You want to visit each city only once. 

If you were to create a visual, you would have ten dots (one dot = one city = one “vertex”) on the page (your "”plot graph”). 

You’d want the line connecting those dots to hit each city only once. 

Plus, as a dispatcher, you know that a map alone doesn’t necessarily give you the fastest, most efficient route for hitting all your stops.

For example, there are factors to consider, like traffic patterns, speed limits, and construction.

On top of that, narrowing down all the possible routes to the single BEST route is a big job. 

If you plot your cities on a map, there are a LOT of different routes to choose from. 

A TSP covering only ten cities, for example, can have upward of 300,000 different permutations (variations of combinations).

Long story short, the traveling salesman problem can get VERY complicated VERY fast.

Hey, there’s a reason all these math geniuses have been puzzling about this equation for decades!

The TSP is considered difficult even by the pros.

As a type of combinatorial optimization problem known as NP-complete, it’s considered an NP-hard problem exactly because there is no fast and easy answer to it.

A combinatorial optimization problem is a type of math or logic problem.

It involves figuring out what combination of variables will give you the best (optimal) outcome. 

So, in this case, the optimal outcome is the fastest route between cities.

An NP problem is a term used in computer science to describe an unsolved problem. 

An NP-complete problem is one where scientists or mathematicians haven’t yet figured out a fast and easy algorithm to solve it. 

These problems can be categorized based on complexity — such as NP-hard, which means it’s a tough one!

You can solve it and determine the shortest path by researching EVERY round-trip route.

But every time you add just one more stop, the number of cities grows — and the problem becomes even harder!

Traveling salesman problem algorithms

Real talk: If you’re in charge of planning delivery routes (for example, as an online retail shop owner or delivery manager), you’re probably not going to use these algorithms.

(Don’t worry — there are easier ways to optimize your routes, which I mention at the end.)

Still, understanding the basics of these algorithms can be useful.

Why?

It’s handy to understand the different possible “optimal solutions.” 

(Don’t worry, I discuss these in more detail below).

For example, the nearest neighbor algorithm prioritizes going to the closest next city, while the brand-and-bound algorithm prioritizes the cheapest arc between cities.

Here’s a quick breakdown of some of the more popular graph theory algorithms and how they’re structured.

(Note: As I describe each of these, I’m going to stick to the TSP language and use the term “cities.”

That said, you could also think in terms of the “stops” — for example, each city as a stop on a delivery route.)

Let’s get to it.

Nearest neighbor (NN) algorithm 

The nearest neighbor algorithm is probably the simplest and easiest to understand of the TSP solutions.

With this method, you simply go to the geographically closest city or destination at every step.

Once you designate your starting city, find the nearest unvisited city. 

That’s your next stop.

Then, from there, find the nearest unvisited city. That’s your next stop.

And so on.

After you’ve hit all your cities, go back to the starting city.

Branch-and-bound algorithm 

The branch-and-bound algorithm breaks one larger TSP problem into several smaller problems. 

Each of the smaller problems may have several possible solutions.

With this method, you start by designating a starting city.

Then, determine the cheapest arc between that starting city and an unvisited city (any unvisited city — unlike the “nearest neighbor” option, it doesn’t have to be the closest city with the shortest route).

Calculate the distance between the pair of cities. That’s one small subproblem.

The distance between those two cities is then added to an overall tally of all distances traveled between all cities.

You continue until every city has been touched — always adding the distance traveled between two cities to the larger tally of distance traveled.

In the end, the overall tally of distance traveled (a combination of all the subset problems) will vary based on the sequence of cities visited.

The algorithm of Christofides and Serdyukov 

The algorithm of Christofides and Serdyukov — sometimes simply called the Christofides algorithm — is an approximation algorithm that offers an approximate solution to the TSP.

It may not give the optimal solution but a near-optimal solution.

It’s used to create a minimum “spanning tree” (a connected graph of all cities that touches all cities).

Start by finding the shortest distance between two cities in the entire network and highlighting the connecting arc and the cities it connects.

Then, pick the next shortest connection in the network and highlight the connecting arc and the cities it connects.

Once all arcs are connected, you’re done.

Brute force algorithm 

The brute force algorithm looks at all possible variations of a route to figure out which one is the shortest.

To use it, you have to calculate, draw, and list all potential paths. 

Then, figure out the distance of each route — the shortest one is the best.

Held–Karp algorithm 

The Held–Karp algorithm — sometimes called the Bellman–Held–Karp algorithm — measures the distances between all cities listed.

The output is the shortest overall distance covered when each city is visited once (and you then return to the starting city).

An example of the traveling salesman problem

A visual example can make it easier to understand the TSP and its complexities.

Say you’ve got eight cities to choose from. 

Using a map, you plot out the set of cities like this (the green node is your starting and ending city):

Now, you could chart a path like this:

Or like this:

OR like this:

Those aren’t your only options. And this is only covering eight cities!

Imagine trying to figure out the most efficient route for, say, 20 stops.

Or 100.

Or 1,000.

The complete graph is going to look pretty crazy (and require A LOT of operations research).

The algorithms described above might help you find the shortest, fastest distance between all the cities (or, on a smaller scale, delivery stops) you have to hit.

But, again, there are real-world factors that aren’t represented in this simple chart of dots and arrows — like speed limits and traffic obstructions.

Math equations won’t get you far there. The solution?

A route optimization software like Circuit for Teams. 

Circuit can help with your territory planning by charting the fastest sequence of delivery stops for all your delivery drivers’ routes.

Circuit doesn’t just take geography into account. 

It also considers local search data, from traffic patterns to construction sites.

Circuit for Teams makes determining optimal driver routes fast and easy

The TSP is a decades-old math problem that asks one question: 

If you’re given a list of cities to visit, what’s the shortest possible route you can take that lets you visit each city once — and then return to the city where you started?

Many problem-solvers have come up with ways to solve the TSP. 

Approaches range from the brute force approach to the nearest neighbor algorithm.

If you manage delivery routes, a general understanding of the various algorithms used to solve the TSP can help you with your own route planning.

For example, you might prioritize the routes with minimum cost or that cover the shortest distances.

But you don’t need complicated algorithms to optimize your routes. 

Routing software like Circuit for Teams can do the job for you quickly.

Circuit also has other perks to make delivery route planning and delivery driving more efficient. 

For example, you can set delivery time windows and offer proof of delivery to customers.

Thanks to driver GPS tracking, you can also send customers real-time updates about the estimated times of arrival (ETAs) and set delivery time windows. 

Learn more about the benefits of driver GPS tracking.

Drivers can also benefit from a package finder feature, which can help minimize the risk of lost packages (a worst-case scenario).

When you’re planning efficient routes, you can also save money — for example, by reducing idle engine running time in traffic jams and cutting gas costs. 

This is just one of the many ways route planners help save money.