# 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)

 Detroit Warren Sterling Heights Lansing Ann Arbor Flint Dearborn Livonia Troy Detroit 0 30.06 36.566 145.379 69.402 111.075 18.537 33.697 34.818 Warren 27.472 0 13.785 139.284 79.351 100.196 36.477 42.804 23.939 Sterling Heights 37.658 13.384 0 149.47 89.537 89.332 46.663 52.99 11.171 Lansing 145.164 142.603 149.109 0 103.699 82.276 139.35 116.993 147.187 Ann Arbor 68.542 82.896 89.402 104.067 0 87.273 61.811 39.22 87.48 Flint 112.687 104.829 91.261 82.755 88.18 0 111.501 101.403 81.639 Dearborn 14.731 38.241 44.747 140.184 58.039 109.562 0 22.334 42.825 Livonia 33.166 45.855 52.361 117.696 39.151 100.667 22.291 0 51.453 Troy 35.306 27.448 11.052 146.947 87.014 82.793 44.311 39.646 0

Duration Array (Seconds)

 Detroit Warren Sterling Heights Lansing Ann Arbor Flint Dearborn Livonia Troy Detroit 0 1233 1661 5052 2512 3902 1019 1342 1479 Warren 1105 0 730 4564 2682 3396 1560 1753 973 Sterling Heights 1745 796 0 5204 3322 3244 2200 2393 797 Lansing 5053 4719 5147 0 3523 3044 4805 3975 5002 Ann Arbor 2464 2860 Flint 3929 3579 3244 3056 3165 0 4291 3643 2907 Dearborn 1135 1639 2067 4757 2142 4135 0 972 1922 Livonia 1330 1941 2369 4039 1424 3626 1079 0 2141 Troy 1539 1189 829 5033 3151 2946 1994 2245 0

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.

 Detroit Warren Sterling Heights Lansing Ann Arbor Flint Dearborn Livonia Troy Detroit 0 30.06 36.566 145.379 69.402 111.075 18.537 33.697 34.818 Warren 27.472 0 13.785 139.284 79.351 100.196 36.477 42.804 23.939 Sterling Heights 37.658 13.384 0 149.47 89.537 89.332 46.663 52.99 11.171 Lansing 145.164 142.603 149.109 0 103.699 82.276 139.35 116.993 147.187 Ann Arbor 68.542 82.896 89.402 104.067 0 87.273 61.811 39.22 87.48 Flint 112.687 104.829 91.261 82.755 88.18 0 111.501 101.403 81.639 Dearborn 14.731 38.241 44.747 140.184 58.039 109.562 0 22.334 42.825 Livonia 33.166 45.855 52.361 117.696 39.151 100.667 22.291 0 51.453 Troy 35.306 27.448 11.052 146.947 87.014 82.793 44.311 39.646 0

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).