Google Maps and the Traveling Salesman Problem
Known and loved as the de facto standard for finding directions from point A to point B, the Google Maps Platform Directions API can do so much more than just find simple directions. It also can tackle what’s known as the traveling salesman problem (TSP)—the need to determine the most cost-efficient route across multiple destinations.
The simplest form of TSP is referred to as a single vehicle routing problem. Directions API finds the most efficient path by rearranging the destinations (waypoints) and comparing the differences in distance and drive time.
But what if you need to generate optimal routes across a fleet of vehicles responsible for traveling to many locations? This more complicated TSP is called a multiple vehicle routing problem (VRP). VRPs exist across a wide variety of industries, including these common examples:
- Food bank collections and deliveries
- School bus student pick-ups and drop-offs
- Long-haul freight shipping
- Bike courier services
So, what is the simple answer to a complex VRP?
Surprise, it’s still Google! Well, it’s not really that surprising at all. Google services and libraries can come together to transform this mind-bending math problem into a set of simple routes in just a few easy-to-implement steps, turning a problem into a plan.
Using the Directions API to handle your VRP offers a host of benefits. First, there is a significant increase in fleet efficiency. Better routing saves time, and we all know that time is money. Additionally, because Directions API is a tool already available to Google Maps Platform users, access to the desired solution is no more than a few clicks away.
So what are you waiting for? Take Directions API for a VRP test drive.