A service for optimizing vehicle tours.

Validity of certain types of fields:

• google.protobuf.Timestamp

  • Times are in Unix time: seconds since 1970-01-01T00:00:00+00:00.
  • seconds must be in [0, 253402300799], i.e. in[1970-01-01T00:00:00+00:00, 9999-12-31T23:59:59+00:00].
  • nanos must be unset or set to 0.

• google.protobuf.Duration

  • seconds must be in [0, 253402300799], i.e. in[1970-01-01T00:00:00+00:00, 9999-12-31T23:59:59+00:00].
  • nanos must be unset or set to 0.

• google.type.LatLng

  • latitude must be in [-90.0, 90.0].
  • longitude must be in [-180.0, 180.0].
  • at least one of latitude and longitude must be non-zero.

A service for optimizing vehicle tours.

Validity of certain types of fields:

• google.protobuf.Timestamp

  • Times are in Unix time: seconds since 1970-01-01T00:00:00+00:00.
  • seconds must be in [0, 253402300799], i.e. in[1970-01-01T00:00:00+00:00, 9999-12-31T23:59:59+00:00].
  • nanos must be unset or set to 0.

• google.protobuf.Duration

  • seconds must be in [0, 253402300799], i.e. in[1970-01-01T00:00:00+00:00, 9999-12-31T23:59:59+00:00].
  • nanos must be unset or set to 0.

• google.type.LatLng

  • latitude must be in [-90.0, 90.0].
  • longitude must be in [-180.0, 180.0].
  • at least one of latitude and longitude must be non-zero.

Aggregated metrics forShipmentRoute (resp.forOptimizeToursResponseover allTransitionand/orVisit(resp. over allShipmentRoute)elements.

The abstract base class for a message.

The abstract base class for a message.

The long running operation metadata for async model relatedmethods.

Possible states of the operation.

Request to batch optimize tours as an asynchronous operation. Eachinput file should contain oneOptimizeToursRequest, and eachoutput file will contain oneOptimizeToursResponse. The requestcontains information to read/write and parse the files. All theinput and output files should be under the same project.

Information for solving one optimization modelasynchronously.

Response to aBatchOptimizeToursRequest. This is returned in theLRO Operation after the operation is complete.

Rules to generate time breaks for a vehicle (e.g. lunch breaks). Abreak is a contiguous period of time during which the vehicleremains idle at its current position and cannot perform any visit. Abreak may occur:

• during the travel between two visits (which includes the timeright before or right after a visit, but not in the middle of avisit), in which case it extends the corresponding transit timebetween the visits,
• or before the vehicle start (the vehicle may not start in themiddle of a break), in which case it does not affect the vehiclestart time.
• or after the vehicle end (ditto, with the vehicle end time).

The sequence of breaks (i.e. their number and order) that apply toeach vehicle must be known beforehand. The repeatedBreakRequest\ s define that sequence, in the order in which theymust occur. Their time windows (earliest_start_time /latest_start_time) may overlap, but they must be compatible withthe order (this is checked).

One may further constrain the frequency and duration of the breaksspecified above, by enforcing a minimum break frequency, such as"There must be a break of at least 1 hour every 12 hours". Assumingthat this can be interpreted as "Within any sliding time window of12h, there must be at least one break of at least one hour", thatexample would translate to the followingFrequencyConstraint:

::

{ min_break_duration { seconds: 3600 } # 1 hour. max_inter_break_duration { seconds: 39600 } # 11 hours (12 - 1 = 11). }

The timing and duration of the breaks in the solution will respectall such constraints, in addition to the time windows and minimumdurations already specified in theBreakRequest.

AFrequencyConstraint may in practice apply to non-consecutivebreaks. For example, the following schedule honors the "1h every12h" example:

::

 04:00 vehicle start  .. performing travel and visits .. 09:00 1 hour break 10:00 end of the break  .. performing travel and visits .. 12:00 20-min lunch break 12:20 end of the break  .. performing travel and visits .. 21:00 1 hour break 22:00 end of the break  .. performing travel and visits .. 23:59 vehicle end

Deprecated: UseVehicle.LoadLimit.Intervalinstead.

Deprecated: UseVehicle.LoadLimit.Intervalinstead.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Data formats for input and output files.

A limit defining a maximum distance which can be traveled. It can beeither hard or soft.

If a soft limit is defined, bothsoft_max_meters andcost_per_kilometer_above_soft_max must be defined and benonnegative.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

The Google Cloud Storage location where the output file willbe written to.

The Google Cloud Storage location where the input file willbe read from.

Solution injected in the request including information aboutwhich visits must be constrained and how they must beconstrained.

For a group of vehicles, specifies at what threshold(s) constraintson visits will be relaxed and to which level. Shipments listed intheskipped_shipment field are constrained to be skipped; i.e.,they cannot be performed.

Ifrelaxations is empty, the start time and sequence of allvisits onroutes are fully constrained and no new visits may beinserted or added to those routes. Also, a vehicle's start and endtime inroutes is fully constrained, unless the vehicle is empty(i.e., has no visits and hasused_if_route_is_empty set to falsein the model).

relaxations(i).level specifies the constraint relaxation levelapplied to a visit #j that satisfies:

• route.visits(j).start_time >= relaxations(i).threshold_timeAND
• j + 1 >= relaxations(i).threshold_visit_count

Similarly, the vehicle start is relaxed torelaxations(i).levelif it satisfies:

• vehicle_start_time >= relaxations(i).threshold_time AND
• relaxations(i).threshold_visit_count == 0 and the vehicle endis relaxed torelaxations(i).level if it satisfies:
• vehicle_end_time >= relaxations(i).threshold_time AND
• route.visits_size() + 1 >= relaxations(i).threshold_visit_count

To apply a relaxation level if a visit meets thethreshold_visit_count OR thethreshold_time add tworelaxations with the samelevel: one with onlythreshold_visit_count set and the other with onlythreshold_time set. If a visit satisfies the conditions ofmultiplerelaxations, the most relaxed level applies. As aresult, from the vehicle start through the route visits in order tothe vehicle end, the relaxation level becomes more relaxed: i.e.,the relaxation level is non-decreasing as the route progresses.

The timing and sequence of route visits that do not satisfy thethreshold conditions of anyrelaxations are fully constrainedand no visits may be inserted into these sequences. Also, if avehicle start or end does not satisfy the conditions of anyrelaxation the time is fixed, unless the vehicle is empty.

Expresses the different constraint relaxation levels, whichare applied for a visit and those that follow when it satisfiesthe threshold conditions.

The enumeration below is in order of increasing relaxation.

    This value must not be explicitly used in `level`.RELAX_VISIT_TIMES_AFTER_THRESHOLD (1):    Visit start times and vehicle start/end times    will be relaxed, but each visit remains bound to    the same vehicle and the visit sequence must be    observed: no visit can be inserted between them    or before them.RELAX_VISIT_TIMES_AND_SEQUENCE_AFTER_THRESHOLD (2):    Same as `RELAX_VISIT_TIMES_AFTER_THRESHOLD`, but the visit    sequence is also relaxed: visits can only be performed by    this vehicle, but can potentially become unperformed.RELAX_ALL_AFTER_THRESHOLD (3):    Same as `RELAX_VISIT_TIMES_AND_SEQUENCE_AFTER_THRESHOLD`,    but the vehicle is also relaxed: visits are completely free    at or after the threshold time and can potentially become    unperformed.

The desired input location information.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Encapsulates a location (a geographic point, and an optionalheading).

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Request to be given to a tour optimization solver whichdefines the shipment model to solve as well as optimizationparameters.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Mode defining the behavior of the search, trading off latencyversus solution quality. In all modes, the global requestdeadline is enforced.

Defines how the solver should handle the request. In all modes butVALIDATE_ONLY, if the request is invalid, you will receive anINVALID_REQUEST error. Seemax_validation_errorsto cap the number of errors returned.

    *IMPORTANT*: not all infeasible shipments are returned here,    but only the ones that are detected as infeasible during    preprocessing.

Response after solving a tour optimization problem containingthe routes followed by each vehicle, the shipments which havebeen skipped and the overall cost of the solution.

Overall metrics, aggregated over all routes.

The abstract base class for a message.

Describes an error encountered when validating anOptimizeToursRequest.

Specifies a context for the validation error. AFieldReferencealways refers to a given field in this file and follows the samehierarchical structure. For example, we may specify element #2 ofstart_time_windows of vehicle #5 using:

::

name: "vehicles" index: 5 sub_field { name: "end_time_windows" index: 2 }

We however omit top-level entities such asOptimizeToursRequestorShipmentModel to avoid crowding the message.

This message hasoneof_ fields (mutually exclusive fields).For each oneof, at most one member field can be set at the same time.Setting any member of the oneof automatically clears all othermembers.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

The desired output location.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Encapsulates a set of optional conditions to satisfy whencalculating vehicle routes. This is similar toRouteModifiers inthe Google Maps Platform API; see:https://developers.google.com/maps/documentation/routes/reference/rest/v2/RouteModifiers.

The shipment of a single item, from one of its pickups to oneof its deliveries. For the shipment to be considered asperformed, a unique vehicle must visit one of its pickuplocations (and decrease its spare capacities accordingly), thenvisit one of its delivery locations later on (and thereforere-increase its spare capacities accordingly).

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

When performing a visit, a predefined amount may be added to thevehicle load if it's a pickup, or subtracted if it's a delivery.This message defines such amount. Seeload_demands.

The abstract base class for a message.

Request for a visit which can be done by a vehicle: it has ageo-location (or two, see below), opening and closing timesrepresented by time windows, and a service duration time (timespent by the vehicle once it has arrived to pickup or drop offgoods).

The abstract base class for a message.

A shipment model contains a set of shipments which must be performedby a set of vehicles, while minimizing the overall cost, which isthe sum of:

• the cost of routing the vehicles (sum of cost per total time, costper travel time, and fixed cost over all vehicles).
• the unperformed shipment penalties.
• the cost of the global duration of the shipments

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Deprecated: Use top levelBreakRuleinstead. Rules to generate time breaks for a vehicle (e.g. lunchbreaks). A break is a contiguous period of time during which thevehicle remains idle at its current position and cannot perform anyvisit. A break may occur:

• during the travel between two visits (which includes the timeright before or right after a visit, but not in the middle of avisit), in which case it extends the corresponding transit timebetween the visits
• before the vehicle start (the vehicle may not start in the middleof a break), in which case it does not affect the vehicle starttime.
• after the vehicle end (ditto, with the vehicle end time).

The sequence of breaks (i.e. their number and order) that apply toeach vehicle must be known beforehand. The repeatedBreakRequest\ s define that sequence, in the order in which theymust occur. Their time windows (earliest_start_time /latest_start_time) may overlap, but they must be compatible withthe order (this is checked).

One may further constrain the frequency and duration of the breaksspecified above, by enforcing a minimum break frequency, such as"There must be a break of at least 1 hour every 12 hours". Assumingthat this can be interpreted as "Within any sliding time window of12h, there must be at least one break of at least one hour", thatexample would translate to the followingFrequencyConstraint:

::

{ min_break_duration { seconds: 3600 } # 1 hour. max_inter_break_duration { seconds: 39600 } # 11 hours (12 - 1 = 11). }

The timing and duration of the breaks in the solution will respectall such constraints, in addition to the time windows and minimumdurations already specified in theBreakRequest.

AFrequencyConstraint may in practice apply to non-consecutivebreaks. For example, the following schedule honors the "1h every12h" example:

::

 04:00 vehicle start  .. performing travel and visits .. 09:00 1 hour break 10:00 end of the break  .. performing travel and visits .. 12:00 20-min lunch break 12:20 end of the break  .. performing travel and visits .. 21:00 1 hour break 22:00 end of the break  .. performing travel and visits .. 23:59 vehicle end

Specifies a duration and distance matrix from visit andvehicle start locations to visit and vehicle end locations.

Specifies a row of the duration and distance matrix.

A precedence rule between two events (each event is the pickup orthe delivery of a shipment): the "second" event has to start atleastoffset_duration after "first" has started.

Several precedences can refer to the same (or related) events, e.g.,"pickup of B happens after delivery of A" and "pickup of C happensafter pickup of B".

Furthermore, precedences only apply when both shipments areperformed and are otherwise ignored.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

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 eachvisit's start and end (aka arrival and departure). They happen ata given second.
• "time intervals", such as the visits themselves, and thetransition between visits. Though time intervals can sometimeshave zero duration, i.e. start and end at the same second, theyoften 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 (sameindex) 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 aTransition and aVisit:

::

---+-------------------------------------+-----------------------------+--> | 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 bearranged during a transition.

• They don't overlap.
• The DELAY is unique andmust be a contiguous period of timeright before the next visit (or vehicle end). Thus, it suffice toknow the delay duration to know its start and end time.
• The BREAKS are contiguous, non-overlapping periods of time. Theresponse specifies the start time and duration of each break.
• TRAVEL and WAIT are "preemptable": they can be interrupted severaltimes during this transition. Clients can assume that travelhappens "as soon as possible" and that "wait" fills the remainingtime.

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 | | | | || || | | | | | | || --++-----------------------------------------------------------------++-->

Data representing the execution of a break.

Deprecated: UseShipmentRoute.Transition.delay_durationinstead. Time interval spent on the route resulting from aTransitionAttributes.delay.

The encoded representation of a polyline. More information onpolyline encoding can be found here:

https://developers.google.com/maps/documentation/utilities/polylinealgorithmhttps://developers.google.com/maps/documentation/javascript/reference/geometry#encoding.

The abstract base class for a message.

Transition between two events on the route. See the description ofShipmentRoute.

If the vehicle does not have astart_location and/orend_location, the corresponding travel metrics are 0.

The abstract base class for a message.

Deprecated: UseShipmentRoute.Transitioninstead. Travel between each visit along the route: from thevehicle'sstart_location to the first visit'sarrival_location, then from the first visit'sdeparture_location to the second visit'sarrival_location,and so on until the vehicle'send_location. This accounts onlyfor the actual travel between visits, not counting the waiting time,the time spent performing a visit, nor the distance covered during avisit.

Invariant:travel_steps_size() == visits_size() + 1.

If the vehicle does not have a start_ and/or end_location, thecorresponding travel metrics are 0 and/or empty.

Reports the actual load of the vehicle at some point along theroute, for a given type (seeTransition.vehicle_loads).

A visit performed during a route. This visit corresponds to a pickupor a delivery of aShipment.

The abstract base class for a message.

Specifies incompatibilties between shipments depending on theirshipment_type. The appearance of incompatible shipments on the sameroute is restricted based on the incompatibility mode.

Modes defining how the appearance of incompatible shipmentsare restricted on the same route.

    - If both are pickups only (no deliveries) or deliveries      only (no pickups), they cannot share the same vehicle at      all.    - If one of the shipments has a delivery and the other a      pickup, the two shipments can share the same vehicle iff      the former shipment is delivered before the latter is      picked up.

Specifies requirements between shipments based on theirshipment_type. The specifics of the requirement are defined by therequirement mode.

Modes defining the appearance of dependent shipments on aroute.

    A "dependent" shipment pickup must therefore have either:    - A delivery-only "required" shipment delivered on the route      after, or    - A "required" shipment picked up on the route before it,      and if the "required" shipment has a delivery, this      delivery must be performed after the "dependent"      shipment's pickup.IN_SAME_VEHICLE_AT_DELIVERY_TIME (3):    Same as before, except the "dependent" shipments need to    have a "required" shipment on their vehicle at the time of    their *delivery*.

Specifies details of unperformed shipments in a solution. Fortrivial cases and/or if we are able to identify the cause forskipping, we report the reason here.

If we can explain why the shipment was skipped, reasons will belisted here. If the reason is not the same for all vehicles,reason will have more than 1 element. A skipped shipment cannothave duplicate reasons, i.e. where all fields are the same exceptforexample_vehicle_index. Example:

::

reasons { code: DEMAND_EXCEEDS_VEHICLE_CAPACITY example_vehicle_index: 1 example_exceeded_capacity_type: "Apples" } reasons { code: DEMAND_EXCEEDS_VEHICLE_CAPACITY example_vehicle_index: 3 example_exceeded_capacity_type: "Pears" } reasons { code: CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DISTANCE_LIMIT example_vehicle_index: 1 }

The skipped shipment is incompatible with all vehicles. The reasonsmay be different for all vehicles but at least one vehicle's"Apples" capacity would be exceeded (including vehicle 1), at leastone vehicle's "Pears" capacity would be exceeded (including vehicle3) and at least one vehicle's distance limit would be exceeded(including vehicle 1).

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Code identifying the reason type. The order here ismeaningless. In particular, it gives no indication of whether agiven reason will appear before another in the solution, if bothapply.

    Note that for this computation we use the geodesic    distances.CANNOT_BE_PERFORMED_WITHIN_VEHICLE_DURATION_LIMIT (4):    The minimum time necessary to perform this shipment,    including travel time, wait time and service time exceeds    the vehicle's `route_duration_limit`.    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 (5):    Same as above but we only compare minimum travel time and    the vehicle's `travel_duration_limit`.CANNOT_BE_PERFORMED_WITHIN_VEHICLE_TIME_WINDOWS (6):    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 (7):    The `allowed_vehicle_indices` field of the shipment is not    empty and this vehicle does not belong to it.

Time windows constrain the time of an event, such as the arrivaltime at a visit, or the start and end time of a vehicle.

Hard time window bounds,start_time andend_time, enforcethe earliest and latest time of the event, such thatstart_time <= event_time <= end_time. The soft time window lowerbound,soft_start_time, expresses a preference for the event tohappen at or aftersoft_start_time by incurring a costproportional to how long before soft_start_time the event occurs.The soft time window upper bound,soft_end_time, expresses apreference for the event to happen at or beforesoft_end_time byincurring a cost proportional to how long aftersoft_end_timethe event occurs.start_time,end_time,soft_start_timeandsoft_end_time should be within the global time limits (seeShipmentModel.global_start_timeandShipmentModel.global_end_time)and should respect:

::

 0 <= `start_time` <= `soft_start_time` <= `end_time` and 0 <= `start_time` <= `soft_end_time` <= `end_time`.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Specifies attributes of transitions between two consecutive visitson a route. SeveralTransitionAttributes may apply to the sametransition: in that case, all extra costs add up and the strictestconstraint or limit applies (following natural "AND" semantics).

Models a vehicle in a shipment problem. Solving a shipment problemwill build a route starting fromstart_location and ending atend_location for this vehicle. A route is a sequence of visits(seeShipmentRoute).

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

A limit defining a maximum duration of the route of avehicle. It can be either hard or soft.

When a soft limit field is defined, both the soft max thresholdand its associated cost must be defined together.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

The abstract base class for a message.

Defines a load limit applying to a vehicle, e.g. "this truck mayonly carry up to 3500 kg". Seeload_limits.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

Interval of acceptable load amounts.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields

The abstract base class for a message.

Travel modes which can be used by vehicles.

These should be a subset of the Google Maps Platform RoutesPreferred API travel modes, see:https://developers.google.com/maps/documentation/routes_preferred/reference/rest/Shared.Types/RouteTravelMode.

Policy on how a vehicle can be unloaded. Applies only to shipmentshaving both a pickup and a delivery.

Other shipments are free to occur anywhere on the route independentofunloading_policy.

Encapsulates a waypoint. Waypoints mark arrival and departurelocations of VisitRequests, and start and end locations ofVehicles.

This message hasoneof_ fields (mutually exclusive fields).For each oneof, at most one member field can be set at the same time.Setting any member of the oneof automatically clears all othermembers.

.. _oneof:https://proto-plus-python.readthedocs.io/en/stable/fields.html#oneofs-mutually-exclusive-fields