Amazon Location Service enables Matrix Routing to optimize route planning

Amazon Location Service introduces Matrix Routing as a new feature to Routes that lets you calculate routes between one or more departure and destination positions. Matrix Routing will return the shortest time and distance between each departure and destination point in your Matrix. With Amazon Location Matrix Routing, you can specify additional routing parameters for more accurate results, including departure time, which uses predictive traffic data when calculating a route, mode of transportation (car or truck), and any avoidances (tolls, ferries).

This blog provides a tutorial for you to get started with Matrix Routing using Amazon Location Service today.

What is a Route Matrix?

Route planning is not always as simple as planning a route from point A to point B. Routes may have multiple points of departure, such as point A and B, and multiple destinations positions such as X and Y.

To plan and optimize your routes from A and B to X and Y, you need the travel time and travel distance for all of the potential routes within the matrix, including A to X, A to Y, B to X, and B to Y. The calculation of time and distance between each combination of points makes up a route matrix. Matrix routing is an important part of route planning and optimization in GIS applications that rely on routing.

A basic example of this is common crowd source delivery applications. Matrix routing is used to plan not only the most efficient route from your food pick-up to your destination, but also, many times a delivery driver will be carrying multiple deliveries, and therefor needs to calculate the most efficient route from pick-up to each of the delivery destinations to make sure the food is still hot on arrival.

Given three delivery destinations, B, C, and D, from the same pick-up A, the delivery application must find the most optimal route from A to B, C, and D according to the travel time between each point. This makes sure that each customer receives their food in the least amount of time from leaving the restaurant.

Using a weighted graph, as seen in the following figure, we can plot out the matrix route calculations based on the travel time for A to B, A to C, A to D, B to C, B to D, and C to D.

Figure 1: Weighted Graph

A weighted graph demonstrates the weight between connecting vertices. In this example, the vertices are our destination points and the weight is the travel time between each point.

By knowing the travel time calculation between each point, the travel application can calculate a minimal cost path according to the least amount of travel time between each point, as seen in the following figure.

Figure 2: Minimal cost path

By planning the route from A to B to C to D, the total travel time is the least amount of travel time according to all route variations, with the least amount of travel time between each delivery. This ensures that each customer receives their delivery in the least amount of time considering all destinations.

Matrix Routing with Amazon Location Service Routes

Set up an Amazon Location Service Route calculator

Step 1: To set up a Route Calculator in the Amazon Location Service console, select Route calculators from the list of available features.

Figure 3: Location service console

Step 2: From the Route Calculators Screen, select the orange Create route calculator to add a route calculator to the list of My route calculators.

Figure 4: Route calculator console

Step 3: Give the calculator a “Name”, and select the Data provider that you want to use. Providing a description is optional. Note that for differences between data providers when using Route Calculators, see the Amazon Location Service Developer Guide

Figure 5: create route calculator

Invoke the Routes API Using AWS Command Line Interface (CLI)

Next, you will test calculating a route matrix using the Amazon Location Routes API. In this example, you will use nine large cities in Michigan. The following list shows the cities with their respective longitude and latitude positions.

Detroit -83.045833, 42.331389
Warren -83.023889, 42.491944
Sterling Heights -83.028056, 42.579722
Lansing -84.546667, 42.733611 
Ann Arbor -83.748333, 42.281389
Flint -83.693333, 43.018889 
Dearborn -83.213333, 42.314444 
Livonia -83.373611, 42.397222 
Troy -83.143056,42.580278

In this example you will use the AWS Command Line Interface (CLI). For instruction on setting up the AWS CLI, read the AWS Command Line Interface instruction documentation.

You can utilize the following AWS CLI command to send your departure and destination positions to the route calculator, as well as additional optional parameters for the mode of transportation, car or truck, and avoidances, avoid ferries, avoid tolls.

For this example, you will only send the required departure positions and destination positions parameters:

aws location \
    calculate-route-matrix \
        --calculator-name MyRouteCalculator \
        --departure-positions "[[-83.045833,42.331389],[-83.023889,42.491944],[-83.028056,42.579722],[-84.546667,42.733611],[-83.748333,42.281389],[-83.693333,43.018889],[-83.213333,42.314444],[-83.373611,42.397222],[-83.143056,42.580278]]" \
        --destination-positions "[[-83.045833,42.331389],[-83.023889,42.491944],[-83.028056,42.579722],[-84.546667,42.733611],[-83.748333,42.281389],[-83.693333,43.018889],[-83.213333,42.314444],[-83.373611,42.397222],[-83.143056,42.580278]]"

Invoke the Routes API using AWS Lambda

Similarly, you can use the following code (utilizing Boto3 client) with AWS Lambda to invoke the calculate_route_matrix method. Set an environment variable CALCULATOR_NAME for the function to the name of the route calculator that you previously created (in our example, it’s ‘MyRouteCalculator’). Then, replace the content of lambda_function.py with the following Python code:

import os
import boto3
import json

CALCULATOR_NAME = os.environ['CALCULATOR_NAME']

location = boto3.client('location')

def lambda_handler(event, context):
    return {
        'status': 200,
        'body': json.dumps(location.calculate_route_matrix(
                CalculatorName=CALCULATOR_NAME,
                DeparturePositions=event['departure_positions'],
                DestinationPositions=event['destination_positions'])['RouteMatrix'])
    }

Additionally, you must update the default execution role of the Lambda function with the ability to invoke the method.

Figure 6: Lambda permissions

You can add the following inline policy to the role to allow the calculate_route_matrix method to be used with your route calculator resource, MyRouteCalculator.

{
    "Version": "2012-10-17",
    "Statement": [
        {
            "Effect": "Allow",
            "Action": "geo:CalculateRouteMatrix",
            "Resource": "arn:aws:geo:*:*:route-calculator/MyRouteCalculator"
        }
    ]
}

From the Lambda Test tab, create a test event with the following JSON:

{
  "destination_positions": <destination_position_array>,
  "departure_positions": <departure_position_array>
}

See the following image for an example in the AWS Lambda console. Make sure to replace <destination_position_array> and <departure_position_array> with your test data for destination and departure positions.

Figure 7: Lambda test console

Executing the Lambda test will send the test data to the Lambda function’s handler as the event parameter. Then, the handler will send the test data to Amazon Location Service’s CalculateRouteMatrix API.

Testing this by using the Michigan city departure and destination position data above, we are returned a 9 x 9 matrix of Distance in the specified DistanceUnits (kilometers by default) and DurationSeconds.

[[{"Distance":0,"DurationSeconds":0},{"Distance":30.06,"DurationSeconds":1233},{"Distance":36.566,"DurationSeconds":1661},{"Distance":145.379,"DurationSeconds":5052},{"Distance":69.402,"DurationSeconds":2512},{"Distance":111.075,"DurationSeconds":3902},{"Distance":18.537,"DurationSeconds":1019},{"Distance":33.697,"DurationSeconds":1342},{"Distance":34.818,"DurationSeconds":1479}],
[{"Distance":27.472,"DurationSeconds":1105},{"Distance":0,"DurationSeconds":0},{"Distance":13.785,"DurationSeconds":730},{"Distance":139.284,"DurationSeconds":4564},{"Distance":79.351,"DurationSeconds":2682},{"Distance":100.196,"DurationSeconds":3396},{"Distance":36.477,"DurationSeconds":1560},{"Distance":42.804,"DurationSeconds":1753},{"Distance":23.939,"DurationSeconds":973}],
[{"Distance":37.658,"DurationSeconds":1745},{"Distance":13.384,"DurationSeconds":796},{"Distance":0,"DurationSeconds":0},{"Distance":149.47,"DurationSeconds":5204},{"Distance":89.537,"DurationSeconds":3322},{"Distance":89.332,"DurationSeconds":3244},{"Distance":46.663,"DurationSeconds":2200},{"Distance":52.99,"DurationSeconds":2393},{"Distance":11.171,"DurationSeconds":797}],
[{"Distance":145.164,"DurationSeconds":5053},{"Distance":142.603,"DurationSeconds":4719},{"Distance":149.109,"DurationSeconds":5147},{"Distance":0,"DurationSeconds":0},{"Distance":103.699,"DurationSeconds":3523},{"Distance":82.276,"DurationSeconds":3044},{"Distance":139.35,"DurationSeconds":4805},{"Distance":116.993,"DurationSeconds":3975},{"Distance":147.187,"DurationSeconds":5002}],
[{"Distance":68.542,"DurationSeconds":2464},{"Distance":82.896,"DurationSeconds":2860},{"Distance":89.402,"DurationSeconds":3288},{"Distance":104.067,"DurationSeconds":3561},{"Distance":0,"DurationSeconds":0},{"Distance":87.273,"DurationSeconds":3127},{"Distance":61.811,"DurationSeconds":2267},{"Distance":39.22,"DurationSeconds":1452},{"Distance":87.48,"DurationSeconds":3143}],
[{"Distance":112.687,"DurationSeconds":3929},{"Distance":104.829,"DurationSeconds":3579},{"Distance":91.261,"DurationSeconds":3244},{"Distance":82.755,"DurationSeconds":3056},{"Distance":88.18,"DurationSeconds":3165},{"Distance":0,"DurationSeconds":0},{"Distance":111.501,"DurationSeconds":4291},{"Distance":101.403,"DurationSeconds":3643},{"Distance":81.639,"DurationSeconds":2907}],
[{"Distance":14.731,"DurationSeconds":1135},{"Distance":38.241,"DurationSeconds":1639},{"Distance":44.747,"DurationSeconds":2067},{"Distance":140.184,"DurationSeconds":4757},{"Distance":58.039,"DurationSeconds":2142},{"Distance":109.562,"DurationSeconds":4135},{"Distance":0,"DurationSeconds":0},{"Distance":22.334,"DurationSeconds":972},{"Distance":42.825,"DurationSeconds":1922}],
[{"Distance":33.166,"DurationSeconds":1330},{"Distance":45.855,"DurationSeconds":1941},{"Distance":52.361,"DurationSeconds":2369},{"Distance":117.696,"DurationSeconds":4039},{"Distance":39.151,"DurationSeconds":1424},{"Distance":100.667,"DurationSeconds":3626},{"Distance":22.291,"DurationSeconds":1079},{"Distance":0,"DurationSeconds":0},{"Distance":51.453,"DurationSeconds":2141}],
[{"Distance":35.306,"DurationSeconds":1539},{"Distance":27.448,"DurationSeconds":1189},{"Distance":11.052,"DurationSeconds":829},{"Distance":146.947,"DurationSeconds":5033},{"Distance":87.014,"DurationSeconds":3151},{"Distance":82.793,"DurationSeconds":2946},{"Distance":44.311,"DurationSeconds":1994},{"Distance":39.646,"DurationSeconds":2245},{"Distance":0,"DurationSeconds":0}]]

Distance Array (Kilometers)

Duration Array (Seconds)

Additionally, you can then utilize this data to optimize your route based on distance, duration, or whatever business logic is needed. In the below example, you have optimized for shortest distance traveled.

Overall, the result path is: Detroit → Dearborn → Livonia → Ann Arbor → Warren → Sterling Heights → Troy → Flint.

Figure 8: Minimal cost path

Get started with Matrix Routing today

Matrix routing functionality is now available in all of the regions where Amazon Location Service is supported.

Evaluate Amazon Location Service by using the free tier during your first three months of request-based usage. During that time, you won’t be billed for monthly request-based usage of up to 10,000 Routes calculated (note: a N x M matrix is N * M routes, i.e., three departure positions and two destination positions are calculated as six routes).

Learn more about this new capability by reading the Amazon Location Service Developer Guide.

About the authors