Deploy a serverless application to optimize vehicle routing with Amazon Location Service

Managing vehicle fleets and delivery routes is a challenge faced by businesses and modern applications across industries, including food and parcel delivery, wholesaling, and repair services. Route optimization involves planning efficient routes for vehicles to travel so that various costs, such as fuel consumption or labor hours, are minimized.

For example, a grocery delivery application, flower shop, or industrial repair services company needs to assign drivers each day to service routes. Manually assigning these routes is time-consuming, inefficient in terms of distance traveled or fuel used, and does not scale well to a large number of driver deliveries. By implementing a solution to optimize vehicle routing, customers who manage vehicle fleets can save time and money while improving customer experiences.

This blog shows how to use Amazon Location Service, AWS Lambda, Amazon API Gateway, and AWS Amplify to build out a full stack and serverless application that optimizes delivery routes for a fleet of vehicles, providing a solution for the vehicle routing problem (VRP). The simple web-application is open-sourced on GitHub and deployable within an AWS account in a few easy steps. Because the solution is fully serverless, you only pay for the resources when you use them.

Application overview

The objective of the VRP is to optimize routes for a fleet of vehicles visiting a given set of positions (nodes). Without any additional constraints added, the shortest path is always achieved by sending a single vehicle to each node. In other words, without any additional constraints, the VRP reduces down to the classic traveling salesperson problem (TSP).

A more helpful definition of the VRP is to minimize the length of the longest route among all the vehicles in a fleet. This is the correct definition in order to visit every node in the shortest amount of time possible, and is the constraint solved for in the application.

The above illustration of a VRP shows that each node is visited exactly once by a single vehicle, which begins and ends its travel from a central depot station.

Optimizing routes with Amazon Location Service and AWS Lambda

Amazon Location Service sources high-quality geospatial data from data providers to support routing using a route index. A route calculator resource allows you to estimate travel time and distance and plot routes on a map based on departure time, different modes of transportation (car, truck, walking), and traffic and road network data from your chosen data provider. Route calculators support two API operations: calculate route and calculate route matrix.

Route planning with a route matrix

The first step in finding the shortest path between a set of locations is to create a route matrix. A route matrix has rows and columns of origin and destination points. Each data point in the matrix is the travel time or distance between the origin and destination. The size of a route matrix response is determined by the number of departure positions multiplied by the number of destination positions in the request. The results of a route matrix is visually represented by an asymmetrical weighted graph:

Using an Amazon Location Service route matrix, users receives route results, including travel time and travel distance, for routes between a set of departure positions and a set of destination positions. Below is an example call and response of the calculate_route_matrix method using the AWS SDK for Python (boto3):

response = location.calculate_route_matrix(
     CalculatorName = ‘example_route_calculator’ 
     DeparturePositions = [[-122.3412, 47.6218], [-122.3371, 
     47.62187], [-122.3379, 47.6233]],
     DestinationPositions = [[-122.3412, 47.6218], [-122.3371, 
     47.62187], [-122.3379, 47.6233]],
     DistanceUnit = “Miles”, 
     TravelMode = “Car” 
     )
print(response[“RouteMatrix”])

Computational complexity and optimization solvers

As additional nodes are added to a TSP/VRP problem, the size of the distance matrix grows exponentially, and the number of route permutations grows by n!.  This means that a TSP with 4 nodes has 24 route permutations, but a TSP with 12 nodes has over 479,001,600.

Due to the computational complexity of solving larger vehicle routing problems, it is common for route optimization solutions to use optimization solvers. These programs approximate the best solution using linear algebra and known heuristics. Optimization solvers allow you to find approximate solutions in a reasonable amount of time for larger vehicle routing problems.

For this solution, the performance of the solver is critical as a design criterion because a user expects a response for each request via API Gateway. There exists a large number of commercially available solvers (e.g., CPLEX or Gurobi) and open-source libraries (e.g., Pyomo or APMonitor). While our example leverages an open-source solver, the solution is designed to be compatible with different solvers by modifying the route optimizer function code.

Calculating the optimal route

The result of the solver is an optimal vehicle route plan for each vehicle with node IDs. Because each vehicle completes a round trip beginning and ending at the depot, the first and last node IDs for each is 0. The intermediate node IDs represent the waypoints for each vehicle, and the route distance is the aggregate distance between each of the nodes from along the route.

Using the calculate route API from Amazon Location Service, a user can create a route between two geographic locations (the departure and the destination positions), with up to 23 intermediate waypoints. Within the Route Optimizer function, the optimized nodeIDs are passed as waypoints to the calculate_route API for each vehicle

The route results include line geometry for drawing the route on a map, plus the overall time and distance of the route. Calculate route optionally accounts for traffic conditions if a departure time is specified. Additionally, users can optionally set travel mode options, including car, truck, or walking and preferences to avoid tolls and ferries. This example calls the calculate_route method using the AWS SDK for Python (boto3):

response = location.calculate_route( 
     CalculatorName = ‘example_route_calculator’, 
     DeparturePosition = [-122.3412, 47.6218],
     DestinationPosition = [-122.3412, 47.6218],
     DistanceUnit = ‘Miles’,
     IncludeLegGeometry = True,
     TravelMode = ‘Car’,
     WaypointPositions = [[-122.3371, 47.62187], [-122.3379, 47.6233]] ) print(response[“Summary”]
     )
print(response[“Summary”])

Architecture overview

The example application consists of a static front-end web app using AWS Amplify and Amazon Location Service maps. The backend API uses Amazon API Gateway and an AWS Lambda function. The Lambda function calls the Amazon Location Service Routes APIs and uses OR-Tools.

1. The front-end web app uses Amplify Core, Auth, and Geo libraries for JavaScript to initialize an Amazon Location Service base map.

2. On each map click, an InvokeURL sends updated session information to API Gateway. It includes point coordinates and user-specified constraints such as fleet size and travel mode.

3. Using Lambda proxy for API Gateway, the information is passed to the route optimizer Lambda function.

4. The Lambda function calls the Amazon Location Service Routes using the AWS SDK for Python (Boto3) and OR-Tools to perform the optimization.

Deploying the solution

The following prerequisites are required to deploy the example application:

• An AWS account
• AWS SAM CLI
• Python 3.9
• An AWS Identity and Access Management (IAM) role with appropriate access

Deploy the example application:

1. Clone the repository and download the sample source code to your environment where AWS SAM is installed:

git clone https://github.com/aws-samples/serverless-route-optimization

2. Change into the project directory containing the template.yaml file:

cd ~/environment/serverless-route-optimization

3. Build the application using AWS Serverless Application Model (AWS SAM):

sam build

4. Deploy the application to your account using AWS SAM. Be sure to name your resources deployed by AWS SAM.

sam deploy --guided

Testing the application

To test the application, a user can specify values for departure time and date, travel mode, fleet size, route maximum, and balance routes. By default, routes are optimized with the objective of minimizing the distance of the single longest route in the fleet, in turn minimizing the time for the fleet to visit all of the positions.

A user then begins selecting points on the map, with the first point representing the “depot” and subsequent points representing delivery locations. The application returns optimized routes given the input constraints, as well as the ordered addresses of deliveries per vehicle.

Using this application as a template, you can begin solving for more specific constraints to the VRP, such as capacity constraints or time windows, by modifying the Lambda function code. The solution can also be integrated with Amazon Location Service Places API to add address information for the route of each vehicle.

Conclusion and next steps

This blog post shows how to deploy a full stack serverless application to solve vehicle routing problems using Lambda, API Gateway, AWS Amplify, and Amazon Location Service. Rather than paying for an expensive subscription service to optimize delivery routes for your fleet of vehicles, you can clone the GitHub repository and begin building your own custom route optimization solution today. Because the solution is completely serverless, you only pay for resoruces when they are used.

For further reading and open-source materials about logistics and last-mile delivery, check out the Last Mile Delivery Accelerator for Instant Delivery.

If you are interested in discussing how your business can leverage this solution, please schedule time with your AWS account manager or reach out directly to the blog authors.