What is Batch Routing and Matrix Routing?
TomToms Routing API and Batch & Matrix Requests
These days, just being able to get to the destination isn’t enough, customers want to arrive at their location as fast as possible. It makes sense both for the user and for a business that getting a driver to their destination should be done as quickly as possible, so how can we make sure we’re on the right track?
The process of mapping a path from one location to another is called routing. Using TomTom’s Routing API provides us with both a database of useful map and real-time and predictive traffic information and the ability to generate an optimal route to get from our starting place to our destination in the shortest amount of time possible.
TomTom's Routing API also offers batch and matrix request modes that enable advanced routing applications for developers.
In this article we'll:
- Review how routing works
- Review routing options such as rechable range
- Learn about using batch routing to request multiple routes at once
- Learn about using matrix routing to compare routes
How does routing work?
In short, routing is simply providing directions between two or more locations.
Finding the most optimal path from a given starting point to a given endpoint is a graph problem. What is the most optimal path a user can take to reach the endpoint? Before we can even run any algorithms, we first need a dataset of every possible path a user can take!
In a simplified version scenario of a routing problem, we need to know what streets exist and how they are connected. These locations are typically converted into Geocode locations, which are just pairs of coordinate points for easier storage in a database.
Once the arduous work of collecting all the data points is complete, we can now start thinking about using a graph algorithm to most efficiently calculate the optimal path to reach a user’s destination. Shortest path algorithms are a difficult problem, especially because these algorithms need to be able to compute information extremely quickly, so we need to be deliberate instead of applying a brute force strategy of trying every possible pair of routes.
With the two steps above we can now create a theoretical optimal path from A to B. Unfortunately, real life is never this simple. Factors like traffic and construction affect the optimal paths a user can take and the time it may take to get there. Mathematicians might use something called Dijkstra's Shortest Path First algorithm here because it's designed specifically to calculate based on weighted path values — in this case roads — so by assigning each traffic value, we can figure out what the best way to our destination is.
Before assigning weighted values, however, developers need to gather live information about the traffic condition of the routes and then use it to calculate how much weight each road must get, in order to calculate the true optimal path to get the user from point A to point B. Specifically TomTom routing utilizes the A* (A-star) search algorithm to determine optimal paths.
TomTom’s Routing API has all of this information available to it, including path (road) coordinates, traffic data, and the ability to automatically weight routes with consideration for route segment speed and distances. The default modes for the TomTom Routing API provide basic route information. These include:
- Calculate Route, which returns optimized routes between two or more waypoints
- Calculate Reachable Range, which returns the destinations that can be reached given a budget of time, fuel or power (in the case of electric vehicles)
Along with the above individual requests, we can also make batch and matrix routing requests which use a combination of the above requests.
The Calculate Route API requires, at minimum, a pair of longitude and latitude coordinates (which you can find using the Search API). The return response will return a list of routes that can take the user to their destination, and other useful information such as total distance traveled, estimated travel time, and turn by turn directions.
Armed with this API, we have everything needed to create our own map app, or even a customized routing app that fits your specific business’ needs.
CALCULATE REachable range
The second routing API we will cover is Calculate Reachable Range. This API takes in a starting location and a budget parameter, to calculate how far the user can travel. The return response will be a list of routes that we will be able to travel.
Some potential use cases for this scenario include:
- Calculate the boundaries of travel from a starting point within a time range.
- Calculate how far an electric vehicle can travel within an energy budget for an electric vehicle. The energy budget for a trip is measured in kilowatt hours.
- Calculate how far a vehicle can travel within a fuel budget for a combustion engine. The budget is specified in liters of fuel.
The Batch Routing API works much the same as the Routing API. The difference is that batch routing enables you to include requests for many different routes in a single call to the API. In addition, you can make requests that run either synchronously or asynchronously.
Synchronous requests return a result immediately and are used when querying for up to 100 routes.
Asynchronous requests, on the other hand, allow you to request more routes, but the results are not provided immediately in the initial response. Asynchronous requests are more involved, but they allow for processing of up to 10,000 routes in a single request.
Making an asynchronous request requires that we make a batch request as usual, but instead of receiving a response with a list of results, we’ll receive the location from which your application can retrieve the routing results when they're ready. One example scenario that this can come in handy is a business that needs to schedule multiple delivery paths for multiple vehicles. By batching API requests together, the business can generate all the routes for all of the vehicle at once!
Matrix routing is a technique for starting with a matrix of start and destination locations and evaluating all the possible routes to understand which are the fastest or the most efficient. The Matrix Routing API takes at least one origin and destination coordinate to use, and calculates the cost of each route needed for every combination of origin to destination.
The key differences between batch routing and matrix routing are:
- Batch routing returns full route information for requests that can include waypoints between origin and destination.
- Matrix routing evaluates combinations of routes between a matrix of origins and destinations that do not include intervening waypoints.
- Matrix routing returns only travel times and distances for each origin/destination combination in the matrix.
What do we mean by a matrix of origins and destinations? Say we have two origins and four destinations:
- Origins [A, B]
- Destinations [C, D, E, F]
Using the standard Routing API, we'd have to make eight separate calls to the API:
- A -> C
- A -> D
- A -> E
- A -> F
- B -> C
- B -> D
- B -> E
- B -> F
Then we'd need to manually evaluate the different returned routes to determine which was shortest or fastest.
Matrix routing allows us to do this all in one call, with the results returned to us as a list of routes to go from one location to the next, along with the travel time and distance for each route. Just like batch routing, we can also make matrix routing requests synchronously or asynchronously.
Matrix searches fall into three general categories:
- Many-to-Many 1.to-many and many-to-1 searches should be fairly self-explanatory. You start with one origin and a number of destinations, for example, and get back the distances and travel times to each destination. Or perhaps you start with multiple origins and a single destination, a scenario that might be used by a car service determining who is closest to picking up a passenger.
Many-to-many searches get to the key strength of matrix searching and cover a much larger number of possible dispatch and logistics scenarios. For example, with just-in-time delivery, if you're delivering packages from several different warehouses and you can optimize the distances from warehouses to destinations, you could figure out how to most efficiently route those packages to the appropriate warehouses.
Once the packages are at the correct warehouses, you can employ batch routing to determine the actual delivery routes.
After reading through this article, you have all the information you need to get started on building your own app with the Routing API. You now know:
- How routing works and what value companies like TomTom provide.
- What routing APIs are available and examples of what they can be used for.
- How to combine the Routing API with batch and matrix routing to solve more complex scenarios and specific business needs.
It doesn't matter if your app is just a small app that guides a user around a point of interest or a large-scale app where you control a fleet of cars to service an entire city, TomTom provides all the information you need to build a successful app.
To learn more about TomTom's services and solutions for last-mile mobility and transportation services, check out the Mobility and On-Demand page here.