This scenario optimizes the order of stops assigned to a vehicle with simple cost parameters. This is the simplest mode of Route Optimization operation, and ensures that all stops are visited within the specified timeframe.
The following example illustrates a basic scenario with one vehicle and three shipments, all originating from a single location called a depot.
See an example request
{ "populatePolylines": true, "populateTransitionPolylines": true, "model": { "globalStartTime": "2023-01-13T16:00:00-08:00", "globalEndTime": "2023-01-14T16:00:00-08:00", "shipments": [ { "deliveries": [ { "arrivalLocation": { "latitude": 37.789456, "longitude": -122.390192 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ] }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.789116, "longitude": -122.395080 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ] }, { "deliveries": [ { "arrivalLocation": { "latitude": 37.795242, "longitude": -122.399347 }, "duration": "250s" } ], "pickups": [ { "arrivalLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "duration": "150s" } ] } ], "vehicles": [ { "endLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "startLocation": { "latitude": 37.794465, "longitude": -122.394839 }, "costPerKilometer": 10.0, "costPerHour": 40.0 } ] } }
Route Optimization request fields
As mentioned in the Overview, the most important Route Optimization request
properties are vehicles and shipments.
In addition to a vehicle and shipments, the request includes the following fields:
Polylines
populatePolylines and populateTransitionPolylines specify whether Route
Optimization should return polylines.
The service encodes Polylines using the Maps JS polyline codec, which represents
binary polyline data using printable ASCII characters. You can use the
Interactive Polyline Encoder Utility to visualize the paths computed by
Route Optimization. The example in this guide sets populatePolylines and
populateTransitionPolylines to true but other guides set them to false to
reduce response size.
See Encoded Polyline Algorithm Format for a description of the encoding format.
Global time constraints
model.globalStartTime and model.globalEndTime are set to an arbitrary 24
hour period. This makes output timestamps easier to interpret.
Visit locations
The example request uses only model.shipments[].pickups[].arrivalLocation and
model.shipments[].deliveries[].arrivalLocation. There is also a
departureLocation property for situations where the vehicle leaves from a
different point than where it arrives, like a parking complex with an entrance
on one side of the building and an exit on another. In this and subsequent
guides, the arrival and departure points are assumed to be the same.
Arrival and departure waypoint also exist as an alternative to latLng.
Waypoint fields support using Google Place IDs as an alternative to LatLng,
and can also specify vehicle headings. See the reference documentation
(REST, gRPC) for more details.
Constraints in the example
This scenario constrains the optimizer in several ways:
- All activity must be completed between the global start and end times. In this scenario, start and end times are a very lax constraint given the close proximity of the shipments and the wide global time window.
- All shipments must be completed. This is the default behavior when
penalty costs are not specified on
shipments. costPerKilometerandcostPerHourare set on the vehicle.
Costs are addressed in Cost Model Parameters.
Route Optimization response properties
See a response to the example request
{ "routes": [ { "vehicleStartTime": "2023-01-14T00:00:00Z", "vehicleEndTime": "2023-01-14T00:36:41Z", "visits": [ { "shipmentIndex": 2, "isPickup": true, "startTime": "2023-01-14T00:00:00Z", "detour": "0s" }, { "shipmentIndex": 1, "isPickup": true, "startTime": "2023-01-14T00:02:30Z", "detour": "150s" }, { "isPickup": true, "startTime": "2023-01-14T00:05:00Z", "detour": "300s" }, { "startTime": "2023-01-14T00:11:25Z", "detour": "0s" }, { "shipmentIndex": 1, "startTime": "2023-01-14T00:19:29Z", "detour": "503s" }, { "shipmentIndex": 2, "startTime": "2023-01-14T00:29:02Z", "detour": "1324s" } ], "transitions": [ { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:00:00Z", "routePolyline": {} }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:02:30Z", "routePolyline": {} }, { "travelDuration": "0s", "waitDuration": "0s", "totalDuration": "0s", "startTime": "2023-01-14T00:05:00Z", "routePolyline": {} }, { "travelDuration": "235s", "travelDistanceMeters": 795, "waitDuration": "0s", "totalDuration": "235s", "startTime": "2023-01-14T00:07:30Z", "routePolyline": { "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@" } }, { "travelDuration": "234s", "travelDistanceMeters": 793, "waitDuration": "0s", "totalDuration": "234s", "startTime": "2023-01-14T00:15:35Z", "routePolyline": { "points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@" } }, { "travelDuration": "323s", "travelDistanceMeters": 1204, "waitDuration": "0s", "totalDuration": "323s", "startTime": "2023-01-14T00:23:39Z", "routePolyline": { "points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@" } }, { "travelDuration": "209s", "travelDistanceMeters": 665, "waitDuration": "0s", "totalDuration": "209s", "startTime": "2023-01-14T00:33:12Z", "routePolyline": { "points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A" } } ], "routePolyline": { "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@RWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@STY@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A" }, "metrics": { "performedShipmentCount": 3, "travelDuration": "1001s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2201s", "travelDistanceMeters": 3457 }, "travelSteps": [ { "duration": "0s", "routePolyline": {} }, { "duration": "0s", "routePolyline": {} }, { "duration": "0s", "routePolyline": {} }, { "duration": "227s", "distanceMeters": 794, "routePolyline": { "points": "kvteFtfjVAA?C?C@C?A?C@AFMj@s@JKb@k@Zc@LSjA}ARWDGdAxAdAvAXa@@k@AsA\\c@FKp@_A\\c@Ze@fA{ALSFGd@o@rAgBB{BZc@" } }, { "duration": "233s", "distanceMeters": 791, "routePolyline": { "points": "cwseFti_jVRWj@w@x@eAHLNRHJbApAHLX\\V^?@hA~AT\\PVFFDHDFJNp@~@NRLNNTFFUZIJY^Y^g@p@[`@KP{@fAEFSXe@l@c@h@WZY\\?BELk@v@MNa@l@" } }, { "duration": "322s", "distanceMeters": 1205, "routePolyline": { "points": "cuseFhjVSTY`@Yb@GHEDIJEF]f@IJi@r@oAbBeCfDKLaApAKNQVIPKPCDQJIBIBM@iAJeALqBVC@C?A?QBYDI@C?_@Dc@FO@a@FDp@HfAHvABVDl@Dj@PpCQDiALsALAQASKwAOgBEe@COCYEa@Es@Eg@" } }, { "duration": "208s", "distanceMeters": 666, "routePolyline": { "points": "{zteFxbajV?CAYEc@AMC_@AOAK?E?CCWAOAKCe@CY?WScDEm@d@EFA\\ENCB?XEVC^E`@EhBUVCNEB?@?\\Er@IMUe@k@k@w@AAMQa@i@SWQWMQi@u@AC?A" } } ], "vehicleDetour": "2201s", "routeCosts": { "model.vehicles.cost_per_hour": 24.455555555555556, "model.vehicles.cost_per_kilometer": 34.57 }, "routeTotalCost": 59.025555555555556 } ], "totalCost": 59.025555555555556, "metrics": { "aggregatedRouteMetrics": { "performedShipmentCount": 3, "travelDuration": "1001s", "waitDuration": "0s", "delayDuration": "0s", "breakDuration": "0s", "visitDuration": "1200s", "totalDuration": "2201s", "travelDistanceMeters": 3457 }, "usedVehicleCount": 1, "earliestVehicleStartTime": "2023-01-14T00:00:00Z", "latestVehicleEndTime": "2023-01-14T00:36:41Z", "totalCost": 59.025555555555556, "costs": { "model.vehicles.cost_per_kilometer": 34.57, "model.vehicles.cost_per_hour": 24.455555555555556 } } }
The Route Optimization response includes a top-level routes field that
represents the proposed routes, with one route per vehicle. Because the example
request in this guide specifies only one vehicle, routes includes one
ShipmentRoute message.
ShipmentRoute properties
The two most important properties for the ShipmentRoute message type are
visits and transitions.
Each Visit represents the completion of a pickup or a delivery from one of
the request message's VisitRequests. A visit is effectively assigned work to
be completed by a vehicle at some place and time.
Each Transition represents the vehicle traveling from one location to the
next. Transitions can occur between a pair of the vehicle's start point, a visit
location, and the vehicle's endpoint.
To reconstruct the vehicle's complete route the ShipmentRoute's visits and
transitions must be combined. The combination of fields into a progression of
vehicle activity looks like the following:
request.vehicles[0].startLocation -> transitions[0] -> visits[0] ->
transitions[1] -> visits[1] -> transitions[2] -> ... -> visits[3] ->
transitions[4] -> request.vehicles[0].endLocation
A ShipmentRoute always has one more transitions than visits, as the
vehicle must travel from its start location to its first visit at the beginning
of the route and from its last visit to its end location at the end of the
route. If the vehicle lacks a start or end location, there will still be one
more transitions than visits because the first or last visit's location is
used as the vehicle's start or end location respectively.
In this example, the first three pickup visits have transitions between them with zero distance and duration because all three pickups share the same location in the request.
See the ShipmentRoute reference documentation (REST, gRPC) for more
details.
Simple waypoint order optimization
As this example demonstrates, Route Optimization models visits as properties of
shipments and does not have a notion of waypoints or stops as an independent
entity. However, it is possible to represent stops or waypoints as shipments
with exactly one VisitRequest as a pickup or delivery. The vehicle must still
be assigned a costPerHour or costPerKilometer for the optimizer to find an
optimal route (as opposed to finding any feasible route).