Resource: Solution
The solution contains planned routes and related metadata resulted from an optimization run.
JSON representation |
---|
{ "name": string, "displayName": string, "optimizationResponse": { object ( |
Fields | |
---|---|
name |
The resource name of the solution. Format: |
displayName |
The display name of the solution. |
optimizationResponse |
The core solution in the form of an |
metadata |
The metadata for this solution. |
OptimizeToursResponse
Response after solving a tour optimization problem containing the routes followed by each vehicle, the shipments which have been skipped and the overall cost of the solution.
JSON representation |
---|
{ "routes": [ { object ( |
Fields | |
---|---|
routes[] |
Routes computed for each vehicle; the i-th route corresponds to the i-th vehicle in the model. |
requestLabel |
Copy of the |
skippedShipments[] |
The list of all shipments skipped. |
validationErrors[] |
List of all the validation errors that we were able to detect independently. See the "MULTIPLE ERRORS" explanation for the |
metrics |
Duration, distance and usage metrics for this solution. |
totalCost |
Deprecated: Use |
ShipmentRoute
A vehicle's route can be decomposed, along the time axis, like this (we assume there are n visits):
| | | | | T[2], | | |
| Transition | Visit #0 | | | V[2], | | |
| #0 | aka | T[1] | V[1] | ... | V[n-1] | T[n] |
| aka T[0] | V[0] | | | V[n-2],| | |
| | | | | T[n-1] | | |
^ ^ ^ ^ ^ ^ ^ ^
vehicle V[0].start V[0].end V[1]. V[1]. V[n]. V[n]. vehicle
start (arrival) (departure) start end start end end
Note that we make a difference between:
- "punctual events", such as the vehicle start and end and each visit's start and end (aka arrival and departure). They happen at a given second.
- "time intervals", such as the visits themselves, and the transition between visits. Though time intervals can sometimes have zero duration, i.e. start and end at the same second, they often have a positive duration.
Invariants:
- If there are n visits, there are n+1 transitions.
- A visit is always surrounded by a transition before it (same index) and a transition after it (index + 1).
- The vehicle start is always followed by transition #0.
- The vehicle end is always preceded by transition #n.
Zooming in, here is what happens during a Transition
and a Visit
:
---+-------------------------------------+-----------------------------+-->
| TRANSITION[i] | VISIT[i] |
| | |
| * TRAVEL: the vehicle moves from | PERFORM the visit: |
| VISIT[i-1].departure_location to | |
| VISIT[i].arrival_location, which | * Spend some time: |
| takes a given travel duration | the "visit duration". |
| and distance | |
| | * Load or unload |
| * BREAKS: the driver may have | some quantities from the |
| breaks (e.g. lunch break). | vehicle: the "demand". |
| | |
| * WAIT: the driver/vehicle does | |
| nothing. This can happen for | |
| many reasons, for example when | |
| the vehicle reaches the next | |
| event's destination before the | |
| start of its time window | |
| | |
| * DELAY: *right before* the next | |
| arrival. E.g. the vehicle and/or | |
| driver spends time unloading. | |
| | |
---+-------------------------------------+-----------------------------+-->
^ ^ ^
V[i-1].end V[i].start V[i].end
Lastly, here is how the TRAVEL, BREAKS, DELAY and WAIT can be arranged during a transition.
- They don't overlap.
- The DELAY is unique and must be a contiguous period of time right before the next visit (or vehicle end). Thus, it suffice to know the delay duration to know its start and end time.
- The BREAKS are contiguous, non-overlapping periods of time. The response specifies the start time and duration of each break.
- TRAVEL and WAIT are "preemptable": they can be interrupted several times during this transition. Clients can assume that travel happens "as soon as possible" and that "wait" fills the remaining time.
A (complex) example:
TRANSITION[i]
--++-----+-----------------------------------------------------------++-->
|| | | | | | | ||
|| T | B | T | | B | | D ||
|| r | r | r | W | r | W | e ||
|| a | e | a | a | e | a | l ||
|| v | a | v | i | a | i | a ||
|| e | k | e | t | k | t | y ||
|| l | | l | | | | ||
|| | | | | | | ||
--++-----------------------------------------------------------------++-->
JSON representation |
---|
{ "vehicleIndex": integer, "vehicleLabel": string, "vehicleName": string, "vehicleStartTime": string, "vehicleEndTime": string, "visits": [ { object ( |
Fields | |
---|---|
vehicleIndex |
Vehicle performing the route, identified by its index in the source |
vehicleLabel |
Label of the vehicle performing this route, equal to |
vehicleName |
Name of the vehicle performing this route. It is used in the stateful service only. |
vehicleStartTime |
Time at which the vehicle starts its route. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
vehicleEndTime |
Time at which the vehicle finishes its route. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
visits[] |
Ordered sequence of visits representing a route. visits[i] is the i-th visit in the route. If this field is empty, the vehicle is considered as unused. |
transitions[] |
Ordered list of transitions for the route. |
hasTrafficInfeasibilities |
When
Arrival at next_visit will likely happen later than its current time window due the increased estimate of travel time |
routePolyline |
The encoded polyline representation of the route. This field is only populated if |
breaks[] |
Breaks scheduled for the vehicle performing this route. The |
metrics |
Duration, distance and load metrics for this route. The fields of |
routeCosts |
Cost of the route, broken down by cost-related request fields. The keys are proto paths, relative to the input OptimizeToursRequest, e.g. "model.shipments.pickups.cost", and the values are the total cost generated by the corresponding cost field, aggregated over the whole route. In other words, costs["model.shipments.pickups.cost"] is the sum of all pickup costs over the route. All costs defined in the model are reported in detail here with the exception of costs related to TransitionAttributes that are only reported in an aggregated way as of 2022/01. |
routeTotalCost |
Total cost of the route. The sum of all costs in the cost map. |
endLoads[] |
Deprecated: Use |
travelSteps[] |
Deprecated: Use |
vehicleDetour |
Deprecated: No longer used. This field will only be populated at the This field is the extra detour time due to the shipments visited on the route. It is equal to A duration in seconds with up to nine fractional digits, ending with ' |
delayBeforeVehicleEnd |
Deprecated: Delay occurring before the vehicle end. See |
Visit
A visit performed during a route. This visit corresponds to a pickup or a delivery of a Shipment
.
JSON representation |
---|
{ "shipmentIndex": integer, "shipmentName": string, "isPickup": boolean, "visitRequestIndex": integer, "startTime": string, "loadDemands": { string: { object ( |
Fields | |
---|---|
shipmentIndex |
Index of the |
shipmentName |
Name of the |
isPickup |
If true the visit corresponds to a pickup of a |
visitRequestIndex |
Index of |
startTime |
Time at which the visit starts. Note that the vehicle may arrive earlier than this at the visit location. Times are consistent with the A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
loadDemands |
Total visit load demand as the sum of the shipment and the visit request |
detour |
Extra detour time due to the shipments visited on the route before the visit and to the potential waiting time induced by time windows. If the visit is a delivery, the detour is computed from the corresponding pickup visit and is equal to:
Otherwise, it is computed from the vehicle
A duration in seconds with up to nine fractional digits, ending with ' |
shipmentLabel |
Copy of the corresponding |
visitLabel |
Copy of the corresponding |
arrivalLoads[] |
Deprecated: Use Exception: we omit loads for quantity types unconstrained by intervals and that don't have any non-zero demand on the route. |
delayBeforeStart |
Deprecated: Use |
demands[] |
Deprecated: Use |
Delay
Deprecated: Use ShipmentRoute.Transition.delay_duration
instead. Time interval spent on the route resulting from a TransitionAttributes.delay
.
JSON representation |
---|
{ "startTime": string, "duration": string } |
Fields | |
---|---|
startTime |
Start of the delay. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
duration |
Duration of the delay. A duration in seconds with up to nine fractional digits, ending with ' |
Transition
Transition between two events on the route. See the description of ShipmentRoute
.
If the vehicle does not have a startLocation
and/or endLocation
, the corresponding travel metrics are 0.
JSON representation |
---|
{ "travelDuration": string, "travelDistanceMeters": number, "trafficInfoUnavailable": boolean, "delayDuration": string, "breakDuration": string, "waitDuration": string, "totalDuration": string, "startTime": string, "routePolyline": { object ( |
Fields | |
---|---|
travelDuration |
Travel duration during this transition. A duration in seconds with up to nine fractional digits, ending with ' |
travelDistanceMeters |
Distance traveled during the transition. |
trafficInfoUnavailable |
When traffic is requested via |
delayDuration |
Sum of the delay durations applied to this transition. If any, the delay starts exactly A duration in seconds with up to nine fractional digits, ending with ' |
breakDuration |
Sum of the duration of the breaks occurring during this transition, if any. Details about each break's start time and duration are stored in A duration in seconds with up to nine fractional digits, ending with ' |
waitDuration |
Time spent waiting during this transition. Wait duration corresponds to idle time and does not include break time. Also note that this wait time may be split into several non-contiguous intervals. A duration in seconds with up to nine fractional digits, ending with ' |
totalDuration |
Total duration of the transition, provided for convenience. It is equal to:
A duration in seconds with up to nine fractional digits, ending with ' |
startTime |
Start time of this transition. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
routePolyline |
The encoded polyline representation of the route followed during the transition. This field is only populated if |
vehicleLoads |
Vehicle loads during this transition, for each type that either appears in this vehicle's The loads during the first transition are the starting loads of the vehicle route. Then, after each visit, the visit's |
loads[] |
Deprecated: Use |
EncodedPolyline
The encoded representation of a polyline. More information on polyline encoding can be found here: https://developers.google.com/maps/documentation/utilities/polylinealgorithm https://developers.google.com/maps/documentation/javascript/reference/geometry#encoding.
JSON representation |
---|
{ "points": string } |
Fields | |
---|---|
points |
String representing encoded points of the polyline. |
VehicleLoad
Reports the actual load of the vehicle at some point along the route, for a given type (see Transition.vehicle_loads
).
JSON representation |
---|
{ "amount": string } |
Fields | |
---|---|
amount |
The amount of load on the vehicle, for the given type. The unit of load is usually indicated by the type. See |
Break
Data representing the execution of a break.
JSON representation |
---|
{ "startTime": string, "duration": string } |
Fields | |
---|---|
startTime |
Start time of a break. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
duration |
Duration of a break. A duration in seconds with up to nine fractional digits, ending with ' |
AggregatedMetrics
Aggregated metrics for ShipmentRoute
(resp. for OptimizeToursResponse
over all Transition
and/or Visit
(resp. over all ShipmentRoute
) elements.
JSON representation |
---|
{
"performedShipmentCount": integer,
"travelDuration": string,
"waitDuration": string,
"delayDuration": string,
"breakDuration": string,
"visitDuration": string,
"totalDuration": string,
"travelDistanceMeters": number,
"maxLoads": {
string: {
object ( |
Fields | |
---|---|
performedShipmentCount |
Number of shipments performed. Note that a pickup and delivery pair only counts once. |
travelDuration |
Total travel duration for a route or a solution. A duration in seconds with up to nine fractional digits, ending with ' |
waitDuration |
Total wait duration for a route or a solution. A duration in seconds with up to nine fractional digits, ending with ' |
delayDuration |
Total delay duration for a route or a solution. A duration in seconds with up to nine fractional digits, ending with ' |
breakDuration |
Total break duration for a route or a solution. A duration in seconds with up to nine fractional digits, ending with ' |
visitDuration |
Total visit duration for a route or a solution. A duration in seconds with up to nine fractional digits, ending with ' |
totalDuration |
The total duration should be equal to the sum of all durations above. For routes, it also corresponds to: A duration in seconds with up to nine fractional digits, ending with ' |
travelDistanceMeters |
Total travel distance for a route or a solution. |
maxLoads |
Maximum load achieved over the entire route (resp. solution), for each of the quantities on this route (resp. solution), computed as the maximum over all |
costs |
Deprecated: Use |
totalCost |
Deprecated: Use |
TravelStep
Deprecated: Use ShipmentRoute.Transition
instead. Travel between each visit along the route: from the vehicle's startLocation
to the first visit's arrivalLocation
, then from the first visit's departureLocation
to the second visit's arrivalLocation
, and so on until the vehicle's endLocation
. This accounts only for the actual travel between visits, not counting the waiting time, the time spent performing a visit, nor the distance covered during a visit.
Invariant: travel_steps_size() == visits_size() + 1
.
If the vehicle does not have a start_ and/or endLocation, the corresponding travel metrics are 0 and/or empty.
JSON representation |
---|
{
"duration": string,
"distanceMeters": number,
"trafficInfoUnavailable": boolean,
"routePolyline": {
object ( |
Fields | |
---|---|
duration |
Duration of the travel step. A duration in seconds with up to nine fractional digits, ending with ' |
distanceMeters |
Distance traveled during the step. |
trafficInfoUnavailable |
When traffic is requested via |
routePolyline |
The encoded polyline representation of the route followed during the step. This field is only populated if |
SkippedShipment
Specifies details of unperformed shipments in a solution. For trivial cases and/or if we are able to identify the cause for skipping, we report the reason here.
JSON representation |
---|
{
"index": integer,
"label": string,
"shipmentName": string,
"reasons": [
{
object ( |
Fields | |
---|---|
index |
The index corresponds to the index of the shipment in the source |
label |
Copy of the corresponding |
shipmentName |
Name of the |
reasons[] |
A list of reasons that explain why the shipment was skipped. See comment above |
Reason
If we can explain why the shipment was skipped, reasons will be listed here. If the reason is not the same for all vehicles, reason
will have more than 1 element. A skipped shipment cannot have duplicate reasons, i.e. where all fields are the same except for exampleVehicleIndex
. Example:
reasons {
code: DEMAND_EXCEEDS_VEHICLE_CAPACITY
exampleVehicleIndex: 1
exampleExceededCapacityType: "Apples"
}
reasons {
code: DEMAND_EXCEEDS_VEHICLE_CAPACITY
exampleVehicleIndex: 3
exampleExceededCapacityType: "Pears"
}
reasons {
code: CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DISTANCE_LIMIT
exampleVehicleIndex: 1
}
The skipped shipment is incompatible with all vehicles. The reasons may be different for all vehicles but at least one vehicle's "Apples" capacity would be exceeded (including vehicle 1), at least one vehicle's "Pears" capacity would be exceeded (including vehicle 3) and at least one vehicle's distance limit would be exceeded (including vehicle 1).
JSON representation |
---|
{
"code": enum ( |
Fields | |
---|---|
code |
Refer to the comments of Code. |
exampleVehicleName |
If the reason is related to a shipment-vehicle incompatibility, this field provides the resource name of one relevant vehicle. This field is used in the stateful service only. |
exampleExceededCapacityType |
If the reason code is |
exampleVehicleIndex |
If the reason is related to a shipment-vehicle incompatibility, this field provides the index of one relevant vehicle. |
Code
Code identifying the reason type. The order here is meaningless. In particular, it gives no indication of whether a given reason will appear before another in the solution, if both apply.
Enums | |
---|---|
CODE_UNSPECIFIED |
This should never be used. If we are unable to understand why a shipment was skipped, we simply return an empty set of reasons. |
NO_VEHICLE |
There is no vehicle in the model making all shipments infeasible. |
DEMAND_EXCEEDS_VEHICLE_CAPACITY |
The demand of the shipment exceeds a vehicle's capacity for some capacity types, one of which is exampleExceededCapacityType . |
CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DISTANCE_LIMIT |
The minimum distance necessary to perform this shipment, i.e. from the vehicle's Note that for this computation we use the geodesic distances. |
CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DURATION_LIMIT |
The minimum time necessary to perform this shipment, including travel time, wait time and service time exceeds the vehicle's Note: travel time is computed in the best-case scenario, namely as geodesic distance x 36 m/s (roughly 130 km/hour). |
CANNOT_BE_PERFORMED_WITHIN_VEHICLE_TRAVEL_DURATION_LIMIT |
Same as above but we only compare minimum travel time and the vehicle's travelDurationLimit . |
CANNOT_BE_PERFORMED_WITHIN_VEHICLE_TIME_WINDOWS |
The vehicle cannot perform this shipment in the best-case scenario (see CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DURATION_LIMIT for time computation) if it starts at its earliest start time: the total time would make the vehicle end after its latest end time. |
VEHICLE_NOT_ALLOWED |
The allowedVehicleIndices field of the shipment is not empty and this vehicle does not belong to it. |
OptimizeToursValidationError
Describes an error encountered when validating an OptimizeToursRequest
.
JSON representation |
---|
{
"code": integer,
"displayName": string,
"fields": [
{
object ( |
Fields | |
---|---|
code |
A validation error is defined by the pair ( Other fields (below) provide more context about the error. MULTIPLE ERRORS: When there are multiple errors, the validation process tries to output several of them. Much like a compiler, this is an imperfect process. Some validation errors will be "fatal", meaning that they stop the entire validation process. This is the case for STABILITY: REFERENCE: A list of all (code, name) pairs:
|
displayName |
The error display name. |
fields[] |
An error context may involve 0, 1 (most of the time) or more fields. For example, referring to vehicle #4 and shipment #2's first pickup can be done as follows:
Note, however, that the cardinality of |
errorMessage |
Human-readable string describing the error. There is a 1:1 mapping between STABILITY: Not stable: the error message associated to a given |
offendingValues |
May contain the value(s) of the field(s). This is not always available. You should absolutely not rely on it and use it only for manual model debugging. |
FieldReference
Specifies a context for the validation error. A FieldReference
always refers to a given field in this file and follows the same hierarchical structure. For example, we may specify element #2 of startTimeWindows
of vehicle #5 using:
name: "vehicles" index: 5 subField { name: "endTimeWindows" index: 2 }
We however omit top-level entities such as OptimizeToursRequest
or ShipmentModel
to avoid crowding the message.
JSON representation |
---|
{ "name": string, "subField": { object ( |
Fields | |
---|---|
name |
Name of the field, e.g., "vehicles". |
subField |
Recursively nested sub-field, if needed. |
Union field
|
|
index |
Index of the field if repeated. |
key |
Key if the field is a map. |
Metrics
Overall metrics, aggregated over all routes.
JSON representation |
---|
{
"aggregatedRouteMetrics": {
object ( |
Fields | |
---|---|
aggregatedRouteMetrics |
Aggregated over the routes. Each metric is the sum (or max, for loads) over all |
skippedMandatoryShipmentCount |
Number of mandatory shipments skipped. |
usedVehicleCount |
Number of vehicles used. Note: if a vehicle route is empty and |
earliestVehicleStartTime |
The earliest start time for a used vehicle, computed as the minimum over all used vehicles of A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
latestVehicleEndTime |
The latest end time for a used vehicle, computed as the maximum over all used vehicles of A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
costs |
Cost of the solution, broken down by cost-related request fields. The keys are proto paths, relative to the input OptimizeToursRequest, e.g. "model.shipments.pickups.cost", and the values are the total cost generated by the corresponding cost field, aggregated over the whole solution. In other words, costs["model.shipments.pickups.cost"] is the sum of all pickup costs over the solution. All costs defined in the model are reported in detail here with the exception of costs related to TransitionAttributes that are only reported in an aggregated way as of 2022/01. |
totalCost |
Total cost of the solution. The sum of all values in the costs map. |
SolutionMetadata
Metadata for solutions.
JSON representation |
---|
{ "optimizer": string, "optimizationStartTime": string } |
Fields | |
---|---|
optimizer |
The name of the optimizer that generated this solution. |
optimizationStartTime |
The timestamp that this run of optimization started. The changes of entities (e.g. shipments and vehicles) after this are not captured in generating this solution. A timestamp in RFC3339 UTC "Zulu" format, with nanosecond resolution and up to nine fractional digits. Examples: |
Methods |
|
---|---|
|
Deletes a solution. |
|
Gets a solution. |
|
List the solutions based on certain conditions. |
|
Retrieves the OptimizeToursRequest that corresponds to the solution. |