stephen-monroe-85429-smaller

Solving the Traveling Salesman Problem—Finding the Best Route with Google

Imagine this: It’s 1800, and a two mathematicians by the names of W.R. Hamilton and Thomas Kirkman start discussing a problem that questions how to most efficiently route the best path between points (stops).

Experts coined this challenge as the Traveling Salesman Problem (TSP). Originally this included straight-line calculations, but we don’t live in a straight-line world. And over 200 years later, we are still talking about “best” routes.

Looking at an extreme example of this problem, the University of Waterloo took a mathematical approach to getting drunk. Researchers documented every pub in the U.K–all 24,727 of them–and asked the classic TSP question every pub goer wants to know: What is the best route to every pub in the UK?

Crazy, we know.

This situation is detailed in depth on Waterloo’s math department website, but we’ll summarize and tell you that it is immensely complicated. Not only did the researchers need to route from pub to pub, they needed to know street directions, lengths of the individual legs and street speeds.

You may have guessed that this is where Google comes into play. Google Maps can take this enormously complicated algorithm and make it easy to plug in and calculate stop efficiency. Now, with Google’s Traffic layer, we can take traffic conditions into consideration as well.

How do businesses use this tool? Many companies use Google’s Directions API (TSP solver) to calculate routes throughout a day. As a director, what if you didn’t want onedriver to go the shortest route, but wanted multiple drivers to go these shortest route? Or what if you wanted the drivers to go the shortest time route and disregard distance? Google has the tools to accomplish this through use of their Distance Matrix API’s and Directions API.

I am starting to see people navigate away from the utilitarian TSP and picking it apart to customize it to their own needs. Clients are asking questions like; how do I route my foot traffic through a campus a certain way as a tour? How can I route my deliveries to avoid rush hour traffic? How can I take 10 drivers and route them to cover 150 stops without overlapping?

Now, with Google, businesses can create custom solutions to the TSP without needing to retain an on-call mathematician. And hopefully after reading this blog, you know the best route to solving your business’ TSP.

Send this to friend