Optimizing a route with the Google Maps Directions API

In my last post, I explained how to create a simple route using the Google Maps Directions API. In this tutorial, I'll build on what we did last time and show you how to add delivery stops optimally, so that you are guaranteed to take the shortest route possible.

Part 1: Build your own route optimization API with Google Maps
Part 2: Creating a route with the Google Maps Directions API
Part 3: Optimizing a route with the Google Maps Directions API (this article)
Part 4: Route optimization web service basics
Part 5: Let's build a route optimization web service
Part 6: Putting it all together - testing your route optimization API (coming soon)

Just a recap from my last post, Creating a Route with the Google Maps Directions API, we are trying to create a route from:

(start) 1337 India St, San Diego, CA 92101, United States

for delivery to:

(A) 1200 Third Ave, San Diego, CA 92101, United States
(B) 707 Tenth Ave, San Diego, CA 92101, United States
(C) 180 Broadway Suite 101, San Diego, CA 92101, United States
(D) 945 Broadway, San Diego, CA 92101, United States

ending at:

(end) 1485 E St, San Diego, CA 92101.

Here's what the API call from (start) to (end) looks like:

Method: GET

https://maps.googleapis.com/maps/api/directions/json?origin=1337%20India%20St%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States&destination=1485%20E%20St%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States&key=GOOGLE_API_KEY

To add the delivery stops to this route, we need to include the waypoints parameter to the API call like this:

Method: GET

https://maps.googleapis.com/maps/api/directions/json?
origin={origin}
&destination={destination}
&waypoints={first_waypoint}|{second_waypoint|...|{last_waypoint}
&key=GOOGLE_API_KEY

where {first_waypoint}|{second_waypoint}|...|{last_waypoint} are the URL encoded addresses of the delivery stops you'll be making, separated by a "|" (vertical bar ASCII character). Now, let's see what the full API call looks like when we add stops (A), (B), (C) and (D) to it.

Method: GET

https://maps.googleapis.com/maps/api/directions/json?origin=1337%20India%20St%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States&destination=1485%20E%20St%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States&waypoints=1200%20Third%20Ave%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States%7C707%20Tenth%20Ave%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States%7C180%20Broadway%20Suite%20101%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States%7C945%20Broadway%2C%20San%20Diego%2C%20CA%2092101%2C%20United%20States&key=GOOGLE_API_KEY

And here's what's returned (protip - copy your json response and paste it into a web based json viewer for readability):

If you expand the routes array of the returned json, the legs array inside it has 5 entries for each leg of the journey, (start) to (A), (A) to (B), ..., (D) to (end). The start_address field in each leg shows you where the leg starts while the start_location object contains the the start_address's coordinates. If we connect each start_location to the corresponding end_location for each leg in the order returned (alternatively, use overview_polyline to do this), this is what our route looks like.

You can quickly see that the route is far from optimal. A and B are at opposite ends of the map, as are C and D, so it would be extremely inefficient to do the route this way. Let's fix it.

By default, the Google Maps Directions API calculates a route through the provided waypoints in their given order. To optimize the route, we need to add optimize:true to the waypoints parameter like so:

Method: GET

https://maps.googleapis.com/maps/api/directions/json?
origin={origin}
&destination={destination}
&waypoints=optimize:true|{first_waypoint}|{second_waypoint}|...|{last_waypoint}
&key=GOOGLE_API_KEY

And here's the new sequence returned:

We now go from (start) to (C), (A), (D), (B) and finish at (end), which you can see from the map is far more efficient.

So far so good. We sent over our start and end locations as well as the addresses of all the stops we wanted to deliver to along the way and got back an optimized route (but there are limitations - for example you can only optimize up to 25 stops / 1 driver in a single call). Why then should we bother building a web service that does exactly the same thing?

The first reason is readability. As you may have noticed, the API call we are making to Google is rather long and hard to understand, and will get even more so when additional stops are added. Instead, wouldn't it be great if our API call looked something like this:

{
	"visits": {
		"A": {
			"location": {
				"name": "A",
				"address": "1200 Third Ave, San Diego, CA 92101, United States"
			}
		},
		"B": {
			"location": {
				"name": "B",
				"address": "707 Tenth Ave, San Diego, CA 92101, United States"
			}
		},
		"C": {
			"location": {
				"name": "C",
				"address": "180 Broadway Suite 101, San Diego, CA 92101, United States"
			}
		},
		"D": {
			"location": {
				"name": "D",
				"address": "945 Broadway, San Diego, CA 92101, United States"
			}
		}
	},
	"fleet": {
		"Afian": {
			"shift_start": "08:00",
			"start_location": {
				"id": "loc-start",
				"name": "START",
				"address": "1337 India St, San Diego, CA 92101, United States"
			},
			"end_location": {
				"id": "loc-end",
				"name": "END",
				"address": "1485 E St, San Diego, CA 92101"
			}
		}
	},
	"options": {
		"polylines": true
	}
}

This way you can clearly see that for the optimization task, I have one driver, "Afian" starting his shift at 8 am from 1337 India St, San Diego, CA 92101 who has to visit stops A, B, C and D before ending at 1485 E St, San Diego, CA 92101.

The second is persistence - storing the route solution returned so that it can be used later on. If a route optimization job is particularly complex, it is possible that the request will take longer than 20 seconds and trigger a HTTP time out error. Instead of expecting an immediate json response and having to deal with timeout issues, it is best practice for the API to return an optimization job id such as:

{
  "job_id": "604a2928-7f6e-4556-994a-4c1114a6d55b"
}

that can be queried using a separate GET endpoint once the optimization result has been computed.

The third is authentication. If your route optimization web service gets popular, you will eventually want to restrict access to authorized (perhaps paying!) users. The proper way to do authentication is for the client application making a request to send over credentials using the Authorization request header.

My next post will show you the basics of building a route optimization web service that does all this, and more.

👋 As always, if you have any questions or suggestions for me, please reach out or say hello on LinkedIn.

Next: Part 4: Route Optimization Web Service Basics