The Traveling Salesman Problem and Other Classical Algorithmic Tales…

October 25, 2016

The first time I heard about the Traveling Salesman Problem (TSP, for short) was when my husband sat me down to explain what he was working so tirelessly to solve. At that time, he was a grad student working on his thesis.

He took out a piece of paper and used a pen to mark it up with many, many dots.

1_Wc33TJMNbbiIvP2g0-UtHw

Here’s the breakdown:

You’re a salesman and you have to visit a number of cities in one go. Let’s say 100 — because you are a very ambitious salesman. Now how would you go about doing that? What is the shortest possible route you can take between those 100 cities before returning home?

1_vbBApYYcowq3yv_wNQxhYQ

It’s actually a really difficult problem to solve — almost impossibly hard. Computer scientists call it a NP-hard problem. The Traveling Salesman Problem gets exponentially more difficult to solve the more dots, or cities, the salesman has to visit.

Now if you thought the TSP was difficult, consider this: What if it wasn’t just one salesman you needed to plan routes for? What if you had multiple salesmen — a whole team of them? That’s an even more challenging conundrum known as the vehicle routing problem or VRP: the subject of my husband’s thesis.

He was working an algorithm to solve the vehicle routing problem, and man, did he have his work cut out for him.

1_W1ODGVmXDt8VXfdQ1CAGyw

Why the Traveling Salesman Matters

While we’re nerding out on this whole Traveling Salesman / Vehicle Routing Problem, you might be thinking — why in the world should I care? Well, because TSPs and VRPs are all around you. The problem actually manifests itself quite clearly in everyday life.

The couriers that deliver packages to your office?

The delivery trucks that bring you fresh produce from the store?

The school buses that pick up and drop off your children?

Walk around your city and you’ll see people and vehicles grappling with a TSP or VRP kind of situation. What’s fascinating about all this is how critical solving the TSP and VRP is to the movement of goods and services from one place to another, and another, and another.

This gets especially critical in dense urban areas, where space is tight and time even tighter. Businesses that invest in route optimization algorithms have reported up to 40% savings when it comes to driving time and fuel costs.

It’s no wonder mathematicians have worked to solve the Traveling Salesman and Vehicle Routing Problem for centuries.

The Traveling Salesman is an old, old man

The Traveling Salesman Problem was first mathematically formulated some time in the 1800s, by Irish mathematician Sir William Rowan Hamilton and by the British mathematician Thomas Penyngton Kirkman. Later, in the 1930s, TSP was notably studied by mathematician Karl Menger in Vienna and Harvard, and later promoted by Hassler Whitney and Merrill Flood at Princeton University.

Over the years, computer scientists and programmers have tackled the TSP and VRP, leading to new and improved solutions.

If you’re digging the history, the University of Waterloo has a fantastic websitethat goes deeper into the history of TSP and hosts a great collection of modern TSP use-cases, including TSP world records and TSP-inspired games.

The Traveling Salesman is Everywhere

The TSP and VRP may seem applicable to only transportation and logistics, but I challenge you to look around your city and find more examples.

In my experience, the Traveling Salesman Problem has come up when I’ve least expected it to. There’s room for optimization in many situations: from finding beauty in TSP art; to busy people with lots of errands to run; to crazed Pokémon fans who need a smart way to get to every Pokéstop in town.

The Traveling Salesman is everywhere, folks. And with delivery businesses becoming more and more popular, it looks like he’s here to stay.