Mobility On-Demand Technical Solution Paper

Determining Optimal Delivery Sequence

A user running a delivery service most likely wants to optimize the routes of the drivers so that they can make their deliveries in the fastest and most efficient way. To do so, make use of the Waypoints Sequence Extension API. This API allows you to get the optimal sequence of delivery locations, optimized for either time or distance.

The related request specifies the following:
  • the start location as start parameter,
  • the delivery locations as destinationN parameters,
  • the routing mode (for example fastest;car;traffic:enabled) as mode parameter,
  • and the expected start time as departure parameter.
You can set the optional improveFor parameter to either time or distance in order to define which aspect to optimize the delivery sequence for. The response contains the array of waypoints in the optimal order. To get the full route details, use the Routing API, which allows you to calculate separate sections of the sequence, or multiple sections at once by passing multiple waypoints in the calculateroute request.
Table 1. Request Summary
Parameter Name Value
start Starting Position of the Journey
start=52.2,8.1
destinationN Intermediate destinations, at least one. If no end parameter is provided, one of these values is selected as end of the sequence. Waypoints of destination parameters can have appointment or access hour constraints.
mode Specifies the routing mode.
mode=fastest;car;traffic:enabled
departure Time when travel is expected to start. Traffic speed and incidents are taken into account when calculating the route. departure is required, if traffic:enabled is set or if properties are added to waypoints.
departure=2014-11-11T16:52:00+02:00
departure=2014-11-11T16:52:00Z
improveFor The parameter to optimize the sequence for (time or distance)
improveFor=time
const https = require('https');
const _ = require('lodash');

/**
 * Builds a GET request for the Waypoint Sequence Extension API.
 * 
 * mode      The routing mode (e.g. 'fastest;car;traffic:enabled')
 * optimizeFor   The parameter to optimize the sequence for ('time' or 'distance')
 * start     The start waypoint
 * end       The end waypoint
 * destinations  Array of intermediate waypoints to find optimal sequence for
 */
function buildFindSequenceRequestOptions(mode, optimizeFor, start, end, destinations) {
  var destinationParams = _(destinations).map((value, index) => {
    var key = 'destination' + (index + 1);
    var val = value.lat + ',' + value.lon;
    return [key, val];
  }).fromPairs();
  var requestParams = _({
              'start': [start.lat, start.lon].join(','),
              'end': [end.lat, end.lon].join(','),
              'mode': mode,
              'improveFor': optimizeFor,
              'departure': 'now',
              'app_id': {YOUR_APP_ID},
              'app_code': {YOUR_APP_CODE}
            }).assign(destinationParams.value())
              .map((value, key) => {
              return key + '=' + encodeURIComponent(value);
            }).join('&');
  return {
    method: 'GET',
    hostname: 'wse.cit.api.here.com',
    path: ['/2/findsequence.json', requestParams].join('?')
  };
}

/**
 * Calls the Waypoint Sequence Extension (WSE) API to find the optimal sequence of waypoints
 * See buildFindSequenceRequestOptions for an explanation of the parameters 
 */
function findOptimalSequence(mode, optimizeFor, start, end, destinations) {
  return new Promise((fulfill, reject) => {
    var options = buildFindSequenceRequestOptions(mode, optimizeFor, start, end, destinations);
    var req = https.request(options, (res) => {
      var data = "";
      res.on('data', (d) => {
        data += d;
      });
      res.on('end', () => {
        if(res.statusCode >= 400) {
          reject(new Error(data));
        }
        else
        {
          var json = JSON.parse(data);
          if(json.results && json.results.length > 0) {
            var result = json.results[0];
            // First and last items in waypoints array are start and end waypoints, we're only interested in the order of the destinations in between
            var destinations = result.waypoints.slice(1, -1);
            // Subtract 1 from index as WSE indexes destinations starting from 1
            fulfill(destinations.map(waypoint => Number(waypoint.id.substr('destination'.length)) - 1));
          }
          else {
            fulfill(null);
          }
        }
      })
    });
    req.on('error', (err) => {
      reject(err);
    });
    
    req.end();
  });
}

// Example delivery locations
var exampleDeliveryLocations = [ { lat: 37.93815, lon: -122.34044 },
  { lat: 37.89103, lon: -122.16065 },
  { lat: 37.80399, lon: -122.26692 },
  { lat: 37.77562, lon: -122.44025 },
  { lat: 37.8356103, lon: -122.2898201 },
  { lat: 37.76375, lon: -122.24955 },
  { lat: 37.76469, lon: -122.42562 }
];

// Example depot location (location to both start from and end at)
var exampleDepotLocation = { lat: 37.870242, lon: -122.268234 };

// Routing mode (fastest car route accounting for traffic)
var mode = 'fastest;car;traffic:enabled';

// Optimize waypoint sequence for time
var optimizeFor = 'time';

findOptimalSequence(mode, optimizeFor, exampleDepotLocation, exampleDepotLocation, exampleDeliveryLocations)
  .then(console.log)
  .catch(console.error);
/** Output:
  [ 1, 5, 2, 4, 3, 6, 0 ]
 */
For more information, see the Waypoints Sequence Extension API and Routing API Developer's Guides on http://developer.here.com.