How can I produce a distance matrix for large datasets using Google Script?

[BU.I]

0

I am currently producing a script that will compare a the time taken to travel between 90 addresses to each other. The result of the script should be a list that contains the time taken to travel to each address from each other.

I've run into a series of issues whilst trying to resolve this. The main issue is that resulting distance matrix will have around 8100 elements. Google script's max execution time is 30 minutes and thus the script keeps timing out.

Any ways that I can improve the script to make it run faster?

The aim of this script is to produce a list with StartID, EndID and Time. I would then be able to filter the list to find addresses within an hour of each other.

I've hit my daily quota of 3 hours execution time already so any help would be much appreciated. Thanks!

function maps(origin, destination) {
  var driving = Maps.DirectionFinder.Mode.DRIVING
  var transit = Maps.DirectionFinder.Mode.TRANSIT
  var modeSet = driving
  var directions = Maps.newDirectionFinder()
  .setOrigin(origin)
  .setDestination(destination)
  .setMode(modeSet)
  .setOptimizeWaypoints(true)
  .getDirections()
  var result = directions
  return result;  
}


function GoogleMaps() {
 //get distance
  var sheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("ABC");
  var outputSheet = SpreadsheetApp.getActiveSpreadsheet().getSheetByName("EFG");
  var lastrow = sheet.getLastRow();
  var lastcolumn = sheet.getLastColumn();
  var range = sheet.getRange(2, 3, lastrow-1, 3);
  //var range = sheet.getRange(2, 3, 3, 3);
     //Origin is in row 2, column 3
  var values = range.getValues();
  var output = []
  for (var i = 0; i < values.length; ++i)
  {
    var loop1 = values[i]
    var start = values[i][1]
    var startId = values[i][0]
    for (var j = 0; j < values.length; j++) {
      var loop2 = values[j]
      var end = values[j][1]
      var endId = values[j][0]
      var result = maps(start, end)
      var status = result.status
      try{
        var time = result.routes[0].legs[0].duration.value / 60;
        var row = [startId, endId, time]
        output.push(row)
      } catch(err){
        Logger.log(err);
      }
    }
   }    
  var outputLength = output.length
  var outputRange = outputSheet.getRange(1,1,outputLength,3);
  outputRange.setValues(output);

}

[Jacopo Rumi]

Hi.

You can optimize your software as much as you want but, at a certain point, you will find a problem that hits the execution time limits.

Much better to learn how to suspend / resume execution.

I will give you an example that you should place at a suitable spot in your critical loops:

    var currTime = (new Date()).getTime();
    var elapsedTimeInMS = currTime - startTime;
    var timeLimitExceeded = elapsedTimeInMS >= MAX_RUNNING_TIME_MS;

    if (timeLimitExceeded) {

do something to save the state

Use the script service to set up a trigger and relaunch the script in 5 minutes or so.

}

Max execution of a script by means of triggers is 6 hours per day,

If you want to go over that, there are ways but probably that will be good in your case.

Have you mesasured the performance of your actual script? How many distances calculated per minute?

This will be a useful information for further planning.

You could also have a scheduling script which triggers the start of mutiple copies of an operating script, each running on a subset of data.

I hope the above will give you some inspiration :)

Good luck!

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.
To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-c...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/google-apps-script-community/b6ecb94b-ef6c-4ff3-a81e-9fe467759b77%40googlegroups.com.

[Steven Bazyl]

While it's not in the Apps Script API, the maps platform has a dedicated service for doing just this and you can call it via URL fetch -- https://developers.google.com/maps/documentation/distance-matrix/intro

That would likely have the most dramatic impact on performance as you'd be replacing ~8100 calls to find directions with a single all to calculate the matrix (assuming you can pass that many locations in the first place, not sure what the limits are...)

Otherwise, piggybacking on Jacopo's advice, try to make that code resumable (check to see if matrix already exists, skip previously calculated combinations) so it can be incrementally calculated. Any pair only needs to be calculated once unless you're changing assumptions (time of day, commute method, etc.) so take advantage of that.

To view this discussion on the web visit https://groups.google.com/d/msgid/google-apps-script-community/CAHpDaihx2jxD_6UUDdsCHuwXHs3Q6bj2c8kjZUpEbHQoHcieAQ%40mail.gmail.com.

[Andrew Roberts]

Take a look at CBL for continuous batch operation.

To view this discussion on the web visit https://groups.google.com/d/msgid/google-apps-script-community/CADJ_Tyb1vL_hv9oQPrVZy5%3DjjhzntcYG0O-_wY3z40T36aua8A%40mail.gmail.com.

[--Hyde]

The aim of this script is to produce a list with StartID, EndID and Time. I would then be able to filter the list to find addresses within an hour of each other.

Hi BU.I,

With 90 nodes in your graph, a 30-minute runtime sounds excessive. The search should not take more than a few seconds. You may want to follow Steven's advise and use something like the Distance Matrix API, or in the event you need to implement the path search yourself, explore the A* algorithm or some other efficient path finding method that would allow you to bail out as soon as it is clear that the path is going to exceed your limit of one hour of travel time. You can then use Maps.DirectionFinder to get the necessary details for the remaining start/end candidates.

I am not familiar with A* JavaScript implementations but PathFinding.js could be one starting point. It is old Node.js code which suggests that is should be fairly easy to adapt to Apps Script.

Cheers --Hyde

To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-community+unsub...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/google-apps-script-community/b6ecb94b-ef6c-4ff3-a81e-9fe467759b77%40googlegroups.com.

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.

To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-community+unsub...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/google-apps-script-community/CAHpDaihx2jxD_6UUDdsCHuwXHs3Q6bj2c8kjZUpEbHQoHcieAQ%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "Google Apps Script Community" group.

To unsubscribe from this group and stop receiving emails from it, send an email to google-apps-script-community+unsub...@googlegroups.com.