Add real time traffic to your route optimization system with Google Maps

The first in a three-part series, this article shows how to improve the accuracy of your routes using Google Maps. This is particularly important if you operate in cities such as Los Angeles, Seattle or New York that see significant variations in average driving speeds over the course of the day due to rush hour traffic. Not taking real time traffic into account might cause your drivers to miss critical time windows and end their route late, leaving both drivers and customers unhappy.

Part 1: Real-time traffic route optimization with Google Maps (this article)
Part 2: Real-time traffic with the Mapbox Matrix API
Part 3: The best route optimization API for ETA accuracy with real-time traffic data

Before we start, it's important to clarify that when I say "real time traffic", I actually mean the predicted traffic at the time the driver starts his route (this also ignores congestion and delays caused by traffic accidents and ad hoc road closures). Most delivery companies plan their routes the night before, so it would not make any sense to base ETAs (estimated arrival times) on traffic conditions at the time the route was created. Forecasting traffic conditions requires significant computing power and access to data, which is why this series of blog posts will feature three service providers - Google Maps, Mapbox and LogisticsOS, that have delivered real time traffic data to customers at scale. Unlike Google and Mapbox, LogisticsOS is a young startup, but they are able to provide real time traffic together with their route optimization API through licensing deals with established mapping companies such as Tom Tom and HERE Maps.

An introduction to the Google Maps API

Google gets their real time traffic data from the hundreds of millions of people that use the Google Maps app while driving. What we are going to do here is adjust the ETAs from our route optimization system to account for real time traffic. The Google Maps API does not account for time windows, priorities and service time at each stop, so instead of sending the entire sequenced route to Google, we are just going to ask Google to give us the travel times between stops and adjust our route's ETAs accordingly.

If you are already using an existing route optimization API, you probably are receiving the route solution as an array of stops, each with an ETA. Let's use a simple example of a route planned for Thursday 1 Dec, 2022 in Vancouver, Canada. The Afi Routing Engine (docs) returns the route solution in JSON and uses this format (full route solution):

{
  "vehicle_1": [
    {
      "location_id": "driver_start",
      "location_name": "Killarney, East Vancouver",
      "arrival_time": "18:00",
      "finish_time": "18:00",
      "distance": 0,
      "start_time": "17:48"
    },
    {
      "location_id": "ABC-123",
      "location_name": "Brassneck Brewery",
      "arrival_time": "18:00",
      "finish_time": "18:30",
      "distance": 5976,
      "duration": 30,
      "travel_mins": 11.96,
      "waiting_mins": 48.04,
      "working_mins": 41.96
    },
    {
      "location_id": "DEF-456",
      "location_name": "Zakkushi on Denman",
      "arrival_time": "18:37",
      "finish_time": "19:22",
      "distance": 3888,
      "duration": 45,
      "travel_mins": 7.78,
      "waiting_mins": 0,
      "working_mins": 52.78
    },
    {
      "location_id": "GHI-789",
      "location_name": "Granville Island Brewing",
      "arrival_time": "20:00",
      "finish_time": "20:15",
      "distance": 2261,
      "duration": 15,
      "travel_mins": 4.52,
      "waiting_mins": 32.7,
      "working_mins": 19.52
    },
    {
      "location_id": "driver_end",
      "location_name": "VanDusen Botanical Gardens",
      "arrival_time": "20:22",
      "finish_time": "20:22",
      "distance": 3621
    }
  ]
}

The first object in the array, location_id: driver_start , is where the vehicle starts his route. By looking at the arrival_time field of that object, you can see that the driver should leave by 17:48 and arrives at his first stop, location_name: Brassneck Brewery at 18:00. Displayed as a table, here's what his original route looks like:

Schedule without Real Time Traffic

The latitude and longitude values are taken from the network object in the route solution while the travel times are read off the travel_mins field of each stop. With this information on hand, the next step is to ask Google to get the travel time for a driver departing on 1 Dec, 2022 at 17:48 going from Killarney, East Vancouver to Brassneck Brewery, departing at 18:30 from Brassneck Brewery to Zakkushi on Denman and so on.

The API we'll use is called the Google Maps Directions API (we've written a short tutorial to get you started). It takes as input an {origin}, {destination} and {departure_time} as parameters in the URL. The format for {departure_time} is unix time, which uses the number of seconds since since 00:00:00 UTC on 1 January 1970 to represent the to represent a valid date-time pair.

Method: GET

https://maps.googleapis.com/maps/api/directions/json?
origin={origin}
&destination={destination}
&departure_time={departure_time}
&key=GOOGLE_API_KEY

Let's go ahead and retrieve the predicted travel time between stops ABC-123 (Brassneck Brewery) and DEF-456 (Zakkushi on Denman) leaving at 18:30 PST (Vancouver is on the west coast of Canada and runs on Pacific Time) on 1 Dec 2022. The first step is to determine the value of {departure_time}. Using a unix epoch converter, we obtain 1669948200 as the unix time stamp for the above date time. For the {origin} and {destination} parameters, we'll use the GPS coordinates for Brassneck Brewery (49.265, -123.101) and Zakkushi on Denman (49.291, -123.138) to avoid any address mismatch issues that could come up if we use location names. Now we are ready to call the Google Maps Directions API.

Method: GET

https://maps.googleapis.com/maps/api/directions/json?origin=49.265,-123.101&destination=49.291,-123.138&departure_time=1669948200&key=GOOGLE_API_KEY

Adjusting Travel Times to Account for Real Time Traffic

The information we want can be found in the legs object of the response (example response).

{
  "duration": {
    "text": "15 mins",
    "value": 873
  },
  "duration_in_traffic": {
    "text": "17 mins",
    "value": 1030
  }
}

Note: The duration_in_traffic field is only returned if you ask for the travel time between two points i.e. if you don't use the waypoints array.

While our route optimization system told us that the trip between these two locations would take just 7 minutes (leaving at 18:30 and arriving at 18:37), the duration_in_traffic field returned by Google indicates that it would take 17 minutes instead - big difference! Repeating this process for each of the stop pairs results in a more realistic schedule below (some of the timings don't line up exactly due to hard time window constraints e.g. GHI-789 Granville Island Brewing could only be visited from 20:00 onwards).

Schedule with Real Time Traffic

With this new schedule, we've also taken care to move the service periods at each stop back to account for the traffic adjusted arrival times e.g. Killarney, East Vancouver to Brassneck Brewery now takes 20 minutes instead of 12, so the driver can only start his delivery at 17:48 + 00:20 = 18:08, which means he ends the delivery at 18:08 + 00:30 = 18:38. A visual representation of this driver's schedule with and without real time traffic is shown at the start of this post.

The code that does this is included below:

if (etas === "google" && googleKey) {
  for (const driverId of _.keys(jsonSolution)) {
    const driverSolution = jsonSolution[driverId];

    // Init visits
    const visits = [];
    for (let i = 0; i < driverSolution.length; i++) {
      const visit = driverSolution[i];
      const isVisit = visit.location_id in jsonInput.visits;
      let location,
        start = "00:00";
      if (!isVisit) {
        let fleet = _.get(jsonInput, `fleet.${driverId}`);
        if (i === 0) {
          location = fleet.start_location;
        } else {
          location = fleet.end_location;
        }
      } else {
        let stop = _.get(jsonInput, `visits.${visit.location_id}`);
        stop = visit.type === "pickup" ? stop.pickup : stop.dropoff;
        location = stop.location;
        start = stop.start;
      }
      // Push to visits
      visits.push({
        location,
        visit,
        start,
      });
    }

    // Skip it
    if (visits.length < 2) {
      continue;
    }

    // Call API service
    let visitCurrent = 1;
    let origin = visits.splice(0, 1);
    origin = origin.pop();
    let visitFinishTime = origin.visit.arrival_time;

    while (visits.length) {
      let waypoints = visits.splice(0, 8);
      let cloneWaypoints = [...waypoints];
      let destination = waypoints.pop();
      visitFinishTime = hhmmToMinutes(visitFinishTime);

      // Call google api
      const strWaypoints = waypoints.map(
        (point) => `${point.location.lat},${point.location.lng}`
      );
      const response = await apiGoogleDirection(
        `${origin.location.lat},${origin.location.lng}`,
        `${destination.location.lat},${destination.location.lng}`,
        strWaypoints,
        departure_time,
        googleKey
      );
      if (response.status === "OK") {
        _.forEach(response.routes[0].legs, (step) => {
          let seconds = parseInt(step.duration.value);
          let minutes = Math.floor(seconds / 60);
          let stop = driverSolution[visitCurrent];
          let duration = stop["duration"] ? stop["duration"] : 0;
          stop["travel_mins"] = minutes;
          stop["distance"] = parseInt(step.distance.value);
          stop["working_mins"] = duration + stop["travel_mins"];

          let visit = cloneWaypoints.splice(0, 1)[0];
          let visitStartMins = hhmmToMinutes(visit.start);

          let newArrivalTime = visitFinishTime + minutes;
          let waitingMins = 0;
          if (newArrivalTime < visitStartMins) {
            waitingMins = visitStartMins - newArrivalTime;
            newArrivalTime = visitStartMins;
          }
          stop["arrival_time"] = minutesToHHmm(newArrivalTime);
          stop["finish_time"] = minutesToHHmm(newArrivalTime + duration);
          stop["waiting_mins"] = waitingMins;

          // Reset finish time of driver
          if (visitCurrent === 1) {
            driverSolution[0]["finish_time"] = minutesToHHmm(
              visitFinishTime + minutes
            );
          }

          // Reset vars
          visitCurrent++;
          visitFinishTime = hhmmToMinutes(stop["finish_time"]);
        });
      }

      // Reset origin
      origin = destination;
      visitFinishTime = destination.visit.finish_time;
    }

    // Add new solution
    jsonSolution[driverId] = driverSolution;
    body.output.solution = jsonSolution;

    values.jsonView = JSON.stringify(body);
    values.jsonSolution = JSON.stringify(body.output.solution);
  }
}

const apiGoogleDirection = async (origin, destination, points, departure_time, googleKey) => {
  let endpoint = ` https://maps.googleapis.com/maps/api/directions/json?origin={origin}&destination={destination}&waypoints=optimize:false%7C{waypoints}&departure_time={departure_time}&key={key} `;
  endpoint = endpoint.replace("{origin}", origin);
  endpoint = endpoint.replace("{destination}", destination);
  if (points.length) {
    endpoint = endpoint.replace("{waypoints}", points.join("|"));
  } else {
    endpoint = endpoint.replace("&waypoints=optimize:false|{waypoints}", "");
  }

  endpoint = endpoint.replace("{key}", googleKey);
  endpoint = encodeURI(endpoint);
  const response = await rp(endpoint);
  return JSON.parse(response);
};

Just in case you were wondering, the time window constraints are maintained by checking to see if the traffic aware arrival time at a stop (newArrivalTime) comes before the start time (visitStartMins), and if so, keeping the original arrival time.

if (newArrivalTime < visitStartMins) {
  waitingMins = visitStartMins - newArrivalTime;
  newArrivalTime = visitStartMins;
}

Of course, if real time traffic delays the driver's arrival time at the stop past the originally scheduled start time, there's a risk that the original time windows at the stop will no longer be respected.

Parting Thoughts

This is a good start, but using adjusting our ETAs in a post-processing step only after our route has been optimized means that we might break one or more hard constraints e.g. the slower travel times could push a delivery outside its given time window or cause the driver to exceed his shift time.

It also means that we could end up with a suboptimal solution because our routing engine was not using accurate travel times to begin with. In my next post, I'll show you how to fix these issues by incorporating real time traffic at the route optimization stage using something called a distance matrix.

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

Next: Part 2: Real Time Traffic with the Mapbox Matrix API