Optimal Holiday Shopping

This year I’ve been running behind with my holiday shopping and need to make one last visit to a bunch of stores and pick up my last minute gifts.  I feel pretty good at mentally planning the most efficient route to visit locations, but with more than 3-4 locations to visit I start  second guessing the order I’ve come up with. With lots of stores to visit, I fired up the Google Maps APIs to figure out the optimal order for my shopping spree.

Locating

First, I just need to figure out where I’m going.  I’m going to use the Places API Places API Icon and lookup the place id for each of the stores I need to visit.  The Places API includes a Text Search method I can use to search for places using a human-readable string, in this case, the name and approximate city/town of the place.  Since I don’t know the exact name of the pet store (it’s either a PetSmart or a Petco), I’ll generically search for “Pet Store” and let the Google Maps magic figure it out for me.  To do this, I can just make HTTP requests in my browser to the following URL:

https://maps.googleapis.com/maps/api/place/textsearch/json?query=CVS,%20Secaucus&key=API_KEY_HERE

An HTTP call like that spits out a long JSON response, we’re only interested in the place_id field I previously mentioned. Here’s an example of the output I got.  Finding those fields, I extracted the following Place IDs.

  • CVS, Secaucus => ChIJn5ui2MNXwokRSD3-7K014GI
  • Pet Store, Secaucus => ChIJh6CBAelXwokRJtEap8f2bAw (turns out this is a PetSmart)
  • FedEx, East Rutherford => ChIJdf-POpP4wokRB644UH322Cw
  • Dollar Tree, East Rutherford => ChIJ-562O5P4wokRWcLXUc1mADc
  • Target, North Bergen => ChIJFziVmP33wokRRu0dx8XBfUE

Optimal Order

Now that I can accurately describe where I need to go, it’s time to figure out the most optimal order to visit all those locations.  Enter the Directions API Directions API Icon.  The Directions API accepts not just a start and end point (or origin and destination to be getting technical), but also an array of waypoints to visit along the route.  Using the optimize:true flag we can ask these waypoints to be optimized and re-ordered in the most efficient manner.

Since my last minute shopping spree will be a round trip back to my apartment, the origin and destination will be the same.  The meat of the query is the waypoints listing where I list the Place ID’s separated with the | character. They also need to be prefixed with place_id: so the Directions API knows these are Place IDs and doesn’t try to geocode them.

You can list the waypoints in any order you want, just remember what order they are in.  To keep it simple, I’m using the same order as the list of places above.

https://maps.googleapis.com/maps/api/directions/json?origin=40.7619,-74.0818&destination=40.7619,-74.0818&waypoints=optimize:true|place_id:ChIJn5ui2MNXwokRSD3-7K014GI|place_id:ChIJh6CBAelXwokRJtEap8f2bAw|place_id:ChIJdf-POpP4wokRB644UH322Cw|place_id:ChIJ-562O5P4wokRWcLXUc1mADc|place_id:ChIJFziVmP33wokRRu0dx8XBfUE&key=API_KEY_HERE

This HTTP call will return a very long response with all the directions I need to navigate from my home to each of these stores, and back home.  To understand the order to visit these places I’m looking for the waypoint_order field, here’s an example of the output I got.

"waypoint_order" : [ 4, 1, 2, 3, 0 ]

This array is telling us we should visit waypoint 4 (o-indexed) first and visit waypoint 0 last. Based on the order of the waypoints I supplied, this mean I should run my errands in this order:

  1. Target
  2. Pet Store
  3. FedEx
  4. Dollar Tree
  5. CVS

Results

By adding up the duration associated with each leg in the JSON response, I can tell this trip will take a total of 3414 seconds which is 273 seconds faster than the trip I would have taken visiting the stores in the order I initially listed them in.  I saved 4.5 minutes optimizing the order of these errands!

If you’re looking for a one-liner JavaScript function to add uo the duration, try this:
data.routes[0].legs.reduce((sum, leg) => { return sum + leg.duration.value; }, 0);
Thanks to the Directions API and my optimized shopping order I’ll have an extra 5 minutes I can spend wrapping these of these gifts up. Happy Holidays!