Minimizing maps directionfinder api calls

If you use the Google APIs, you'll have been hit with the "service invoked too many times in one day" problem. In Backing off on rate limiting I showed how to deal with rate limited APIs, but that doesn't help when your quota applies across a whole day. It's better to try to find a strategy to minimize the calls in the first place. 
You can take a copy of this sheet and the code at https://docs.google.com/spreadsheet/ccc?key=0At2ExLh4POiZdFpHWXF1UGR1NnlhU21Rd0trTW45dFE&usp=sharing

Mileage table

Someone had posted a question on the GAS community, asking how to create one of those mileage matrixes showing the distance between two points. They had tried but hit the rate limit exceeded. Applying Backing off on rate limiting got them a little further, but then they hit the "too many times in one day" problem. The maximum for a free consumer account is 2,500 per day and for a business acccount 100,000 per day. Another couple of annoying quota restrictions are a maximum number of characters per uri encoded direction instructions, and a restriction on the number of waypoints allowed in a direction.

The DirectionFinder

There is another API - the Direction Matrix API - which might  have been good for this problem but the terms of use say - 

Use of the Distance Matrix API must relate to the display of information on a Google Map; for example, to determine origin-destination pairs that fall within a specific driving time from one another, before requesting and displaying those destinations on a map. Use of the service in an application that doesn't display a Google map is prohibited.

Instead though,  we are going to use the Directions API, which also has the same terms of use, but is probably more applicable for creating maps with. I'm also going to include a few extra goodies like lat/long, duration of travel and so on. If using this code, please ensure you follow the terms and create a map with the result. You can read the terms of use here.

Although these functions will work with or without an API key, I recommend you set up a project in the cloud console, get a public Api key and use it. Although the quotas are the same, the main benefit is that you'll be measured per API key rather than ip address for your daily usage.

One of the things I noticed about the DirectionFinder of the Directions API, is that it allows waypoints. So let's say you wanted to create a mileage matrix of points a,b,c,d,e The simple approach would be to calculate each combination of AB, AC , AD, AE, BC, BD, BE, CD, CE ,DE , which would take 20 calls. That could be halved to 10 if you assume that AB is the same as BA (in other words we have a symmetrical table). However you can do all that in 6 calls using waypoints.  A-B-C-D-E , A-C-E, A-D, A-E, BD, or in 1 call if you add dummy waypoints. As it turns out there is a quota on the number of waypoints too, which makes calculating the calls a little complex.  The algorithm tries to make as long a route as possible with linked waypoints, and doesn't need the mileage chart to have symmetrical from and to points. What's left over is then joined up with dummy waypoints to minimize the number of calls. I'm sure it can be optimized further, but the table below shows the call saving that could be made using waypoints depending on whether you are using the free API or a business account - although this is complicated by the quota on url direction length (which I can't see from within GAS)


 Points  No of routes   Assume AB = BA, but dont use waypoints  Use waypoints - free api max 8  Use waypoints - business account max 23
 5  20  10  5  5
 7  42  21  7  7
 10  90  45  15  15
 50  2450  1225  141  85

Whether to use the GAS API?

When I started this, I used the built in Maps service of GAS. However, it failed inexplicable with "server error" from time to time and seemed very fragile, so instead this uses the Directions JSON API directly, which is more robust and allows more control. For example. one thing I found is that certain routes would generate a server error 500 for no apparent reason. Splitting the routes in two on such a failure (although no quota was exceeded), would make it work again. 

The waypoint code

It takes two arrays, one of sources and one of destinations and returns a set of route plans.


/**generate a key to index a to/from pair
 * @param {string} a placename
 * @param {string} a placename
 * @return {string} a key for the 2 place names
 */

function getABKey( a,b) {
  return 'x' + [a.toString() ,b.toString()].sort().join('_');
}
/**create an object of all required to from pairs
 * @param {Array.string} from array of placenames
 * @param {Array.string} to array of placenames
 * @return {object} an object of all required to from pairs
 */

function getAllRoutes (from, to ) {
  // in summary, this creates an object containg all required route combinations
  return from.reduce (function (p,c) {
    return to.reduce(function (tp,tc) {
      var k = getABKey (c,tc);
      if (!tp.hasOwnProperty(k) && c !== tc) {
        tp[k] = {a:c,b:tc,distance:'',placed:false,key:k, start:c, end:tc,duration:''};
      } 
      return tp;
    },p);
    return p;
  }, {});
}

/* optimize routes so that waypoints are contigous and maximized
 * @param {object} active an object for which I need a successor waypoint
 * @param {object} routeOb a object describing required routes, created by getAllRoutes
 * @param {Array.object} chunk the array  of from to pairs so far in this chunk
 * @return {object} the successor to/from pair
 */

function nextGoodPoint ( active, routeOb,chunk) {

  for (k in routeOb) {
    var r = routeOb[k];
    if (!r.placed && ( !active || ( active.key !== r.key && (r.a === active.b || r.b === active.b))) &&
      (!chunk.some(function(d) { return d.a === r.a || d.a === r.b || d.b === r.a || d.b === r.b }) ) ) { 
      return r;
    }
  }
  return null;


/* optimize routes so that waypoints are contigous and maximized
 * @param {object} active an object for which I need a successor waypoint
 * @param {object} routeOb a object describing required routes, created by getAllRoutes
 * @param {number} maxChunk maximium number points to allow in a chunk
 * @param {number} maxCharacters maximium number of characters to allow (URL length restriction)
 * @return {Array.object} an array  of from to pairs
 */

function goodPoints ( active, routeOb, maxChunk , maxCharacters) {

  var r, chunk=[];
  while ((r = nextGoodPoint( active, routeOb,chunk)) && chunk.length < maxChunk ) {
    var chunkChars = chunk.reduce(function(p,c) {
      return p + c;
    },0);

    // may need to swap and b to maintain continuity of route
    if (r.a !== active.b) {
      // swap ends
      var t = r.b;
      r.b = r.a;
      r.a = t;
      r.swapped = true;
    }
    
    // check we're not blowing url limit

    if ( (chunk.reduce(function(p,c) {return p + c.a.length;},0) + r.b.length) > maxCharacters)  {
      if (!chunk.length) throw ("place name " + r.b + " too big for directions API");
      return chunk;
    }
    else {  
      chunk.push(active);
      active.placed = true;
      active = r;
    }
  }
  return chunk;
}

/* optimize routes so that waypoints are contigous and maximized
 * @param {object} routeOb a object describing required routes, created by getAllRoutes
 * @param {number} maxWayPoints maximium number of waypoints to allow
 * @param {number} maxCharacters maximium number of characters to allow (URL length restriction)
 * @return {Array.object} an array of arrays of from to pairs
 */
function optimizeRoutes (routeOb, maxWayPoints, maxCharacters) {

  var chunks=[], active;

  while ( active= nextGoodPoint ( null , routeOb,[])) {
    var chunk = goodPoints(active,routeOb, maxWayPoints,maxCharacters);
    if (!chunk.length) {
      chunk.push(active);
      active.placed = true;
    }
    chunks.push(chunk);
  };
  
  return chunks;
}



Applying the routes


Now we can apply the routes to the direction finder, using the waypoints to minimize api calls as follows

/** use directions API to create dstances, time and other information between places
 * @param {Array.string} from an array of from place names
 * @param {Array.string} to and array of to place names
 * @param {object} options see below for what
 * @return {object} a single object containing all the route results
 */
function routeDistanceWaypointsFetch(from,to,options) {

  // default options
  options = options || {};
  options.useMiles = (typeof (options.useMiles) === 'undefined') ? true: options.useMiles;
  options.mode = (typeof (options.mode) === 'undefined') ? 'driving': options.mode;
  options.endPoint = options.endPoint || "https://maps.googleapis.com/maps/api/directions/json?";
  options.apiKey = (typeof (options.apiKey) === 'undefined') ? "AIzaSyCLxPQffPPKNun-Axawxc2vrJoqYtNF7yQ" : options.apiKey;
  
  
  // these are quotas are described in https://developers.google.com/maps/documentation/directions/
  options.maxWayPoints = options.maxWayPoints || 8;
  options.maxCharaters = options.maxCharacters || 1700;
  
  
  // this will leverage the use of waypoints to minimize map service calls, and will also eliminate duplicate routes
  // note that a -> b is assumed to be be the same as b -> a
  var routeOb = getAllRoutes(from,to);
  var chunks = optimizeRoutes(routeOb,options.maxWayPoints,options.maxCharacters);

  // by now we'll have number of routes where other routes have been chunked in as waypoints
  for (var n=0;n<chunks.length;n++) {
    var w = chunks[n];
    var params = [
      "mode="+options.mode,
      "units="+ (options.useMiles ? "imperial" : "metric")
    ];
      
    // add the key if there is one
    if (options.apiKey) {
      params.push("key=" + options.apiKey);
    }
    
    // transit mode can take arrival and departure times parameters
    if (options.departureTime)params.push("departureTime="+encodeURIComponent(options.departureTime));
    if (options.departureTime)params.push("arrivalTime="+encodeURIComponent(options.arrivalTime));
    
    var urlBase = options.endPoint + params.join("&");

    // add the waypoints
    var way = w.slice(1).map(function(p) { 
      return p.a;
    });

    // get the whole route, backing off if necessary
    var route,r2,url= urlBase + makeWayUrl ( w[0].a, w[w.length-1].b , way) ;
    try {
       // try getting the whole route
        route = getDirectionData(url);
        if (route.status==="OK") {
      
          if (route.routes[0].legs.length !== w.length ) { 
            throw ('no of legs ' + route.routes[0].legs.length + ' incorrect for ' +w.length + ' waypoints');
          }
      
        // each leg will show the distance between each place
          route.routes[0].legs.forEach( function(r,j) {
            var p = routeOb[w[j].key];
            p.distance = r.distance.value / (options.useMiles ? 1609.344 : 1000 );
            p.duration = r.duration.value;
            p.start = r.start_location;
            p.end = r.end_location;
          });
      }
      else {
        w.forEach (function(f) {  
            var p = routeOb[getABKey(f.a ,f.b)];
            p.distance  = 'route or waypoints failed - maybe be an unreachable item in ' + url;
        });
      }
    }
    catch (err) {
      if (way.length > 1 && err.toString().indexOf('"status" : "UNKNOWN_ERROR"') !== -1) {
        // another annoying hack workaround around here - can get an error 500(server error) for particulat routes
        // no reason I can see, except that if the overall route is too long (no published quota problems) 
        // so we'll cut the waypoints in half and try again
        
        //split the waypoints in 2 and try again
  
        var wp1 = w.slice(0,Math.floor(w.length/2)-1);
        var wp2 = w.slice(wp1.length,w.length);

        chunks.push(wp1);
        chunks.push(wp2);  

      }
      else {
        throw(err);
      }
    }
  }

  return routeOb;

}

/**create starts/fins/waypoints url
 * @param {string} origin
 * @param {string} destination
 * @param {Array.string} wayPoints
 * return {string} url fragment
 */
function makeWayUrl (origin, destination, wayPoints) {
  
  var t = "&origin=" + encodeURIComponent (origin) + 
    "&destination=" + encodeURIComponent (destination) ;
  if(wayPoints.length) { 
    t += "&waypoints=" + encodeURIComponent( wayPoints.join("|") );
  }
  return t;
}
    
/**given a url, get the direction object, backing off if necessary
 * @param {string} url the constructed url
 * @return {object} a directions response object
 */
 
function getDirectionData (u) {
  return JSON.parse(rateLimitExpBackoff(function () { 
      return UrlFetchApp.fetch (u, {muteExceptions:true, method:"GET"} ) ;
    }).getContentText());
}


And we can get the input from and to cities for this from a sheet like this, and populate the results

function executeRoutes () {
  var ss = SpreadsheetApp.getActiveSpreadsheet ();
  var distanceSheet = ss.getSheetByName("distances");
  
  // headings are side and top.
  var fromRange = distanceSheet.getRange("b1:1");
  var toRange = distanceSheet.getRange("a2:a");
  var fromData = fromRange.getValues()[0].map(function(d) { return d.trim().toLowerCase();});
  var toData = toRange.getValues().map(function(d) { return d[0].trim().toLowerCase() });
  
  // calculate info about routes between
  var result = routeDistanceWaypointsFetch(
    fromData,
    toData,
    {mode:'driving',apiKey:'', useMiles:true, maxWayPoints:8}
  );
 
  // extract the distances
  var distances =  fromData.map(function (top,i) {    
    return toData.map ( function (side,j) {
      var r = result[getABKey(top,side)];
      return r ?  r.distance : '';
    });
  });
  
  // output to the sheet
  var outRange = distanceSheet.getRange(fromRange.getRow() + 1, fromRange.getColumn(), toRange.getNumRows(), fromRange.getNumColumns());
  outRange.setValues(distances);
  
  // extra stuff ---we can do other kinds of info - for example travel time
  // extract the travel times
  var durations =  fromData.map(function (top,i) {    
    return toData.map ( function (side,j) {
      var r =  result[getABKey(top,side)];
      return r ? r.duration/60/60 : '';
    });
  });
  
  // write that to a travel time sheet
  // output to the sheet, first clearing it and dumping the headings
  var durationSheet = ss.getSheetByName("durations");
  durationSheet.clearContents();
  durationSheet.getRange(fromRange.getRow(),fromRange.getColumn(),1,fromRange.getNumColumns()).setValues(fromRange.getValues());
  durationSheet.getRange(toRange.getRow(),toRange.getColumn(),toRange.getNumRows(),1).setValues(toRange.getValues());
  
  
  var outRange = durationSheet.getRange(fromRange.getRow() + 1, fromRange.getColumn(), toRange.getNumRows(), fromRange.getNumColumns());
  outRange.setValues(durations);
  
}


Finally I am using exponential backoff to deal with invoking the API too quickly.
 /**
   * rateLimitExpBackoff()
   * @param {function} callBack some function to call that might return rate limit exception
   * @param {number} sleepFor optional amount of time to sleep for on the first failure in missliseconds
   * @param {number} maxAttempts optional maximum number of amounts to try
   * @param {number} attempts optional the attempt number of this instance - usually only used recursively and not user supplied
   * @return {object} results of the callback 
   **/
  
  var rateLimitExpBackoff = function ( callBack, sleepFor ,  maxAttempts, attempts  ) {

    // can handle multiple error conditions by expanding this list
    function errorQualifies (errorText) {
      return ["Exception: Service invoked too many times",
              "Exception: Rate Limit Exceeded"].some(function(e){
                return errorText.toString().slice(0,e.length) == e;
              });
    }
    
    
    // sleep start default is  2 seconds
    sleepFor = Math.abs(sleepFor || 2000);
    
    // attempt number
    attempts = Math.abs(attempts || 1);
    
    // maximum tries before giving up
    maxAttempts = Math.abs(maxAttempts || 5);

    // check properly constructed
    if (!callBack || typeof(callBack) !== "function") {
      throw ("you need to specify a function for rateLimitBackoff to execute");
    }
    
    // try to execute it
    else {

      try {
        return callBack();
      }
      catch(err) {
        // failed due to rate limiting
        if (errorQualifies(err)) {
          
          //give up?
          if (attempts > maxAttempts) {
            throw (err + " (tried backing off " + (attempts-1) + " times");
          }
          else {
            
            // wait for some amount of time based on how many times we've tried plus a small random bit to avoid races
            Utilities.sleep (Math.pow(2,attempts)*sleepFor) + (Math.round(Math.random() * sleepFor));

            // try again
            return rateLimitExpBackoff ( callBack, sleepFor ,  maxAttempts , attempts+1);
          }
        }
        else {
          // some other error
          throw (err);
        }
      }
    }
  };

And a snip of the result looks like this - but remember that you need to use these results to generate a Google Map as per the terms of use

See  Google Apps Scripts snippets for more like this

For help and more information join our forum,follow the blog or follow me on twitter .

Comments