Routing#
The MOIA Fleet API contains a routing service tailored to the specific vehicles managed through the API.
It is accessible in the Fleet API through the RoutingService.
This service allows computing routes between two (or more) waypoints, similar to common public routing products such as Google/Apple/Bing Maps.
It also provides a method for computing matrices of predicted travel times between sets of waypoints.
Further, the service can be used to match paths, i.e. translate a GPS trace or route from a different provider into a MOIA-internal route with metadata like travel time and drivability.
When dispatching missions via the Fleet API, MOIA internally uses this service to compute appropriate routes for the vehicles to drive.
Note that in the current state of Fleet API, routes obtained through the API are purely informative.
They provide an indication of estimated travel times and route feasibility.
However, getting a specific route through the routing service does not guarantee that this exact route will be taken by a successive mission assignment with the same waypoints (due to the volatility of traffic).
Routing Objects#
Compute Route Request#
A ComputeRouteRequest primarily consists of an origin and a destination waypoint (represented by geographical coordinates and an optional heading).
Additionally, the request must contain,
A
VehicleConfigurationspecifying the kind of vehicle to consider for computing metadata such as travel times or segment drivability of the matched routes.A
fleet_id, specifying the fleet of the vehicle for which a route is computed. This ensures the service adheres to adjustments configured by fleet operators.
Further, up to 100 intermediate waypoints may be provided as via points.
{
"origin": {
"latitude": 30.273393,
"longitude": -97.743473
},
"destination": {
"latitude": 30.27268,
"longitude": -97.741016,
"heading": 20.0
},
"via": [
{
"latitude": 30.27308,
"longitude": -97.742339,
"heading": 110
}
],
"vehicle_configuration": {
"self_driving": true
},
"fleet_id": "646f570a-a3b2-44bb-86ee-9c07dd4d8a68"
}
Compute Travel Time Matrix Request#
A ComputeTravelTimeMatrixRequest primarily consists of sets of waypoints for origins and destinations.
Additionally, the request must contain,
A
VehicleConfigurationspecifying the kind of vehicle to consider for computing metadata such as travel times or segment drivability of the matched routes.A
fleet_id, specifying the fleet of the vehicle for which a route is computed. This ensures the service adheres to adjustments configured by fleet operators.
{
"origins": [
{
"latitude": 30.273393,
"longitude": -97.743473
}
],
"destinations": [
{
"latitude": 30.27268,
"longitude": -97.741016,
"heading": 20.0
},
{
"latitude": 30.27308,
"longitude": -97.742339,
"heading": 110
}
],
"vehicle_configuration": {
"self_driving": true
},
"fleet_id": "646f570a-a3b2-44bb-86ee-9c07dd4d8a68"
}
Match Path Request#
A MatchPatchRequest primarily consists of a path, i.e. an ordered list of locations represented by geographical coordinates.
The path must have at least two locations.
Additionally, the request must contain,
A
VehicleConfigurationspecifying the kind of vehicle to consider for computing metadata such as travel times or segment drivability of the matched routes.A
fleet_id, specifying the fleet of the vehicle for which a route is computed. This ensures the service adheres to adjustments configured by fleet operators.
{
"fleet_id": "646f570a-a3b2-44bb-86ee-9c07dd4d8a68",
"path": [
{
"latitude": 53.5563838,
"longitude": 9.963399
},
{
"latitude": 53.55632,
"longitude": 9.9628078
},
{
"latitude": 53.555995,
"longitude": 9.962775
}
],
"vehicle_configuration": {
"self_driving": false
}
}
Route#
A Route is a suggested path to drive.
It goes from the origin of a routing request over all via waypoints (in the specified order) to the destination.
A route consists of a sequence of route legs where each leg contains the route between two successive waypoints.
{
"legs": [
{
"leg": {
"travelTimeSeconds": 15,
"lengthMeters": 111,
"geometry": [
{
"latitude": 30.27339,
"longitude": -97.74348
},
{
"latitude": 30.27328,
"longitude": -97.74308
},
{
"latitude": 30.27321,
"longitude": -97.74283
},
{
"latitude": 30.27309,
"longitude": -97.74238
}
]
}
},
{
"leg": {
"travelTimeSeconds": 124,
"lengthMeters": 571,
"geometry": [
{
"latitude": 30.27309,
"longitude": -97.74238
},
{
"latitude": 30.27291,
"longitude": -97.74245
},
{
"latitude": 30.27271,
"longitude": -97.74104
}
]
}
}
]
}
Leg#
A Leg describes the length, predicted travel time and route geometry of a route section.
For example:
{
"travelTimeSeconds": 15,
"lengthMeters": 111,
"geometry": [
{
"latitude": 30.27339,
"longitude": -97.74348
},
{
"latitude": 30.27328,
"longitude": -97.74308
},
{
"latitude": 30.27321,
"longitude": -97.74283
},
{
"latitude": 30.27309,
"longitude": -97.74238
}
]
}
A leg may be accompanied by so called Violations.
If there are violations, the service was able to compute a route but that route is dangerous, illegal or even impossible to drive.
The service only responds with a leg with violations if no alternative route without violations exists according to the routing data.
However, routing data is never perfect, therefore the route is provided regardless.
Nevertheless, for any use case which involves driving a route, routes with violations should be discarded (for example, mission dispatch will reject routes with violations).
To ensure that callers explicitly handle violations, legs are wrapped in a message of type LegOrLegWithViolations which has different variants for regular legs and legs with violations.
A leg without violations may look like this:
{
"leg": {
"travelTimeSeconds": 15,
"lengthMeters": 111,
"geometry": [
{
"latitude": 30.27339,
"longitude": -97.74348
},
{
"latitude": 30.27328,
"longitude": -97.74308
},
{
"latitude": 30.27321,
"longitude": -97.74283
},
{
"latitude": 30.27309,
"longitude": -97.74238
}
]
}
}
A leg with violations may look like this:
{
"legWithViolation": {
"leg": {
"travelTimeSeconds": 5,
"lengthMeters": 38,
"geometry": [
{
"latitude": 53.55654,
"longitude": 10.002183
},
{
"latitude": 53.5565,
"longitude": 10.0021
},
{
"latitude": 53.55639,
"longitude": 10.0019
},
{
"latitude": 53.55632,
"longitude": 10.00175
}
]
},
"violations": [
{
"violationType": "VIOLATION_TYPE_BLOCKED_ROAD_USED",
"startIndex": 1,
"coordinatesCount": 4
}
]
}
}
Violation#
A violation indicates an issue with a route leg. While a route could be computed, a leg violates a routing restriction. The part of a leg which is affected by the violation is provided as an index into the geometry array of the associated leg. For example:
{
"violationType": "VIOLATION_TYPE_BLOCKED_ROAD_USED",
"startIndex": 1,
"coordinatesCount": 4
}
The service only responds with a leg with violations if no alternative route without violations exists according to the routing data. This may happen for example when the origin or destination of the route request lies on a blocked segment. Consider the specific violation type to assess the severity of a violation.
Compute Travel Time Matrix Response#
The ComputeTravelTimeMatrix responds with a stream of ComputeTravelTimeMatrixResponses.
Combined, they represent a matrix, i.e. a table of travel times between all origins and destinations given in the corresponding request.
With a row for each origin and a column for each destination, the travel times are given in row-major order.
That is, the travel time from the origin with index i to the destination with index j is stored at the travel time entry with index (i*num_destinations + j).
Because matrices can become rather large and waiting for (de)serialisation/transfer (potentially over multiple hops) of the full matrix can be quite expensive, this large array of travel times is split into chunks.
Each chunk becomes ComputeTravelTimeMatrixResponse and is stored in the travelTimesSeconds field.
The chunks may have arbitrary (non-equal) sizes and may arrive in arbitrary order.
Beside the travel times, each chunk contains:
A field
entriesOffset, specifying the global travel time array index where the travel times of this chunk start. Sorting chunks by this field brings them into the correct order.An array
violatingEntriesIndiceswhich lists the local indices of all entries where the corresponding route did contain violations.An array
noRouteFoundEntriesIndiceswhich lists the local indices of all entries where no route could be found. Note that at these indicestravelTimesSecondsstill has a value. However, this value is invalid and must not be used.An array
noRouteFoundEntriesReasonswherenoRouteFoundEntriesReasons[i]contains the reason whytravelTimesSeconds[noRouteFoundEntriesIndices[i]]could not be computed.
The following shows an example response chunk:
{
"entriesOffset": 42,
"travelTimesSeconds": [1, 2, 0, 3],
"violatingEntriesIndices": [1],
"noRouteFoundEntriesIndices": [2],
"noRouteFoundEntriesReasons": ["NO_ROUTE_FOUND_REASON_COULD_NOT_REACH_WAYPOINT"]
}
Routing Functionality#
Point-to-Point Routing#
Point-to-point routing is a straightforward use case for the routing service.
Build a ComputeRouteRequest with your desired origin and destination waypoints and supply an appropriate VehicleConfiguration.
Make sure to provide a heading to achieve good matching quality and to disambiguate the direction in which a vehicle should leave/arrive.
Call the ComputeRoute procedure with the request.
Given a ComputeRouteRequest, the procedure will produce a ComputeRouteResponse.
In the case of successful computation, the response will consist of a route which you can then use for your purposes.
If the requested waypoints necessarily lead into an impossible or illegal situation (according to the routing data), you will get back a route with violations.
In this case you have to carefully consider if the route is usable in the context of your use case.
Route computation may also fail entirely if the service could not match any of the waypoints to the MOIA map data, or if the map data contains no route between a pair of waypoints.
This should only happen if you request routes for locations outside the area covered by MOIAs service.
Matrix Routing#
Matrix routing becomes relevant when larger volumes of travel time predictions are required.
Consider a fleet of 100 vehicles and 100 requests with locations of customers to pick up.
To optimally assign vehicles to requests, reliable estimates of how long each potential route might take are essential.
While it would be possible to issue 100*100=10000 individual point-to-point routing requests, this quickly becomes prohibitively resource-intensive.
When only travel times but no routes are required, it is possible to instead compute a matrix of travel times.
Through smart batching and specialized algorithms, such a matrix can be computed much more efficiently.
To use matrix routing, build a ComputeTravelTimeMatrixRequest with your desired origin and destination waypoints and supply an appropriate VehicleConfiguration.
Make sure to provide a heading to achieve good matching quality and to disambiguate the direction in which a vehicle should leave/arrive.
Call the ComputeTravelTimeMatrix procedure with the request.
Given a ComputeTravelTimeMatrixRequest, the procedure will produce a stream of ComputeTravelTimeMatrixResponses.
These represent chunks of the travel time matrix.
The stream will be terminated once the result matrix was fully transmitted.
To obtain the combined matrix, first sort the chunks by their entriesOffset.
Appending all the travelTimesSeconds arrays yields the entire matrix as a linear array with first the travel times from the first origin to all destinations, then from the second origin to all destinations, and so on.
Some travel times may correspond to routes with violations.
The indices of these travel times are given in each chunk’s violatingEntriesIndices array.
Some route computations may even have failed.
In such a case, a value will still be present but it is invalid and must not be used.
The indices of such invalid values will be listed in each chunk’s noRouteFoundEntriesIndices, while the noRouteFoundEntriesReasons array will at the same index contain the reason for the failure.
Note that by default the API enforces a strict limit of at most 1000 matrix cells per second per account. Requests for matrices larger than 1000 cells will be rejected. While our services are potentially able to compute many millions of travel time values per second, we need to provision appropriate resources. Please reach out to the routing team if you want to use the matrix routing API with larger loads.
Path Matching#
The purpose of path matching is to translate arbitrary path geometry (for example a GPS trace or a route from a different provider) into a corresponding route in the MOIA map.
From the matched route metadata such as the travel time or drivability of the included roads can be derived.
The path matching service tries to find a route which geometrically resembles the input as close possible.
In contrast to the routing service, it does not optimize for a good, i.e. fast, violation free route but only tries to reproduce the given geometry.
To use it, build a MatchPathRequest with your desired polyline denoted by a sequence of locations and supply an appropriate VehicleConfiguration.
Call the MatchPath procedure with the request.
The service will respond with a MatchPathResponse which contains a route in the MOIA map that best matches the given polyline.
The matching route is given by either a Leg, or a LegWithViolation if the route contains violations.
If the polyline does not match any route in reasonable distance, a PathNotMatchedReason will be returned.