This section presents an example of a Vehicle Routing Problem (VRP) and a Cloud Fleet Routing request that solves it.
Example problem
In this example, there are three vehicles and nine locations to be visited. All vehicles start at the same location, called depot. Here's a map of the locations including the depot (identified by the van icon).
The problem also includes time windows during which the locations can be visited, items to be picked up, and related constraints. All of the data for the problem is encoded in the request. When you send the request, the Cloud Fleet Routing service returns routes that visit each location with minimum total cost.
The following sections describe the main parts of the request, including sample messages in both JSON and protocol buffer formats.
Global start and end times
All vehicle travel along the routes must occur between the global start time and global end time. The following code defines these values:
"global_start_time":"1970-01-01T00:00:00+00:00",
"global_end_time":"1970-01-21T18:00:00+00:00",
global_start_time {
}
global_end_time {
seconds: 1792800
}
Shipments
Shipments messages describe the locations to be visited, time windows for the visits, and items to be picked up or delivered, if there are any. The following shows a shipment message for a single location:
{
"pickups":[
{
"arrival_location":{
"latitude":48.874507,
"longitude":2.30361
},
"time_windows":[
{
"start_time":"1970-01-07T04:20:00+00:00",
"end_time":"1970-01-08T00:03:20+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "40"
}
},
}
shipments {
pickups {
arrival_location {
latitude: 48.874507
longitude: 2.30361
}
time_windows {
start_time {
seconds: 534000
}
end_time {
seconds: 605000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 40 }
}
}
The shipment message contains the following data:
- Latitudes and longitudes of the locations to be visited.
- Time windows during which visits must occur.
- Visit durations.
- Load demands: the quantity of items to be picked up, which can be their quantity, total weight, volume, or other measure.
Vehicles
Vehicles messages describe the available vehicles for the problem. The following shows a message for a single vehicle.
{
"start_location":{
"latitude":48.863102,
"longitude":2.341204
},
"end_time_windows":[
{
"end_time":"1970-01-15T07:20:00+00:00"
}
],
"loadLimits": {
"weight": {
"maxLoad": 800
}
},
"cost_per_traveled_hour":3600
}
vehicles {
start_location {
latitude: 48.863102
longitude: 2.341204
}
load_limits {
key: "weight"
value: { max_load: 800 }
}
cost_per_traveled_hour: 3600
end_time_windows {
end_time {
seconds: 1236000
}
}
}
The vehicle message contains the following data:
- Vehicle start locations.
- End time windows: intervals in which vehicles must end their travel.
- Weight limits of vehicles.
- Costs per traveled hour. You can also specify other types of costs, which aren't used in this example.
For this problem, Cloud Fleet Routing minimizes the total cost of travel, based on the vehicles' cost per traveled hour.
Complete request
Here's the complete request for the example in both JSON and protocol buffer formats.
JSON
{
"model":{
"global_start_time":"1970-01-01T00:00:00+00:00",
"global_end_time":"1970-01-21T18:00:00+00:00",
"shipments":[
{
"pickups":[
{
"arrival_location":{
"latitude":48.843561,
"longitude":2.297602
},
"time_windows":[
{
"start_time":"1970-01-11T13:20:00+00:00",
"end_time":"1970-01-12T04:36:40+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "40"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.834862,
"longitude":2.309275
},
"time_windows":[
{
"start_time":"1970-01-10T13:10:00+00:00",
"end_time":"1970-01-11T01:40:00+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "120"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.830455,
"longitude":2.318888
},
"time_windows":[
{
"start_time":"1970-01-01T18:03:20+00:00",
"end_time":"1970-01-02T16:33:20+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "40"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.826387,
"longitude":2.363691
},
"time_windows":[
{
"start_time":"1970-01-09T09:56:40+00:00",
"end_time":"1970-01-10T01:13:20+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "40"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.84503,
"longitude":2.391672
},
"time_windows":[
{
"start_time":"1970-01-01T04:10:00+00:00",
"end_time":"1970-01-01T18:36:40+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "10"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.858246,
"longitude":2.375536
},
"time_windows":[
{
"start_time":"1970-01-08T04:30:00+00:00",
"end_time":"1970-01-09T03:00:00+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "80"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.875071,
"longitude":2.392874
},
"time_windows":[
{
"start_time":"1970-01-02T23:13:20+00:00",
"end_time":"1970-01-03T14:30:00+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "80"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.880942,
"longitude":2.323866
},
"time_windows":[
{
"start_time":"1970-01-03T22:50:00+00:00",
"end_time":"1970-01-04T18:00:00+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "80"
}
},
},
{
"pickups":[
{
"arrival_location":{
"latitude":48.874507,
"longitude":2.30361
},
"time_windows":[
{
"start_time":"1970-01-07T04:20:00+00:00",
"end_time":"1970-01-08T00:03:20+00:00"
}
],
"duration":"90000s"
}
],
"loadDemands": {
"weight": {
"amount": "40"
}
},
}
],
"vehicles":[
{
"start_location":{
"latitude":48.863102,
"longitude":2.341204
},
"end_time_windows":[
{
"end_time":"1970-01-15T07:20:00+00:00"
}
],
"loadLimits": {
"weight": {
"maxLoad": 800
}
},
"cost_per_traveled_hour":3600
},
{
"start_location":{
"latitude":48.863102,
"longitude":2.341204
},
"end_time_windows":[
{
"end_time":"1970-01-15T07:20:00+00:00"
}
],
"loadLimits": {
"weight": {
"maxLoad": 800
}
},
"cost_per_traveled_hour":3600
},
{
"start_location":{
"latitude":48.863102,
"longitude":2.341204
},
"end_time_windows":[
{
"end_time":"1970-01-15T07:20:00+00:00"
}
],
"loadLimits": {
"weight": {
"maxLoad": 800
}
},
"cost_per_traveled_hour":3600
}
]
}
}
Protocol buffer
# proto-file: google3/google/cloud/optimization/v1/fleet_routing.proto
# proto-message: OptimizeToursRequest
model {
shipments {
pickups {
arrival_location {
latitude: 48.843561
longitude: 2.297602
}
time_windows {
start_time {
seconds: 912000
}
end_time {
seconds: 967000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 40 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.834862
longitude: 2.309275
}
time_windows {
start_time {
seconds: 825000
}
end_time {
seconds: 870000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 120 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.830455
longitude: 2.318888
}
time_windows {
start_time {
seconds: 65000
}
end_time {
seconds: 146000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 40 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.826387
longitude: 2.363691
}
time_windows {
start_time {
seconds: 727000
}
end_time {
seconds: 782000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 40 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.84503
longitude: 2.391672
}
time_windows {
start_time {
seconds: 15000
}
end_time {
seconds: 67000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 10 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.858246
longitude: 2.375536
}
time_windows {
start_time {
seconds: 621000
}
end_time {
seconds: 702000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 80 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.875071
longitude: 2.392874
}
time_windows {
start_time {
seconds: 170000
}
end_time {
seconds: 225000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 80 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.880942
longitude: 2.323866
}
time_windows {
start_time {
seconds: 255000
}
end_time {
seconds: 324000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 80 }
}
}
shipments {
pickups {
arrival_location {
latitude: 48.874507
longitude: 2.30361
}
time_windows {
start_time {
seconds: 534000
}
end_time {
seconds: 605000
}
}
duration {
seconds: 90000
}
}
load_demands {
key: "weight"
value: { amount: 40 }
}
}
vehicles {
start_location {
latitude: 48.863102
longitude: 2.341204
}
load_limits {
key: "weight"
value: { max_load: 800 }
}
cost_per_traveled_hour: 3600
end_time_windows {
end_time {
seconds: 1236000
}
}
}
vehicles {
start_location {
latitude: 48.863102
longitude: 2.341204
}
load_limits {
key: "weight"
value: { max_load: 800 }
}
cost_per_traveled_hour: 3600
end_time_windows {
end_time {
seconds: 1236000
}
}
}
vehicles {
start_location {
latitude: 48.863102
longitude: 2.341204
}
load_limits {
key: "weight"
value: { max_load: 800 }
}
cost_per_traveled_hour: 3600
end_time_windows {
end_time {
seconds: 1236000
}
}
}
global_start_time {
}
global_end_time {
seconds: 1792800
}
}
Either the duration_distance_matrices
needs to be populated or the Google Maps For Fleet Routing plugin needs to be activated.
To learn how to send the request using Python or Java programs, see Quickstarts. The next section describes the request's response.
Response to the request
When you send a request, the Cloud Fleet Routing service returns a response. The following shows response examples in both formats. The response you get may be slightly different.
JSON
{
"routes": [
{
"vehicleStartTime": "1970-01-01T03:52:49Z",
"vehicleEndTime": "1970-01-10T10:56:40Z",
"visits": [
{
"shipmentIndex": 4,
"isPickup": true,
"startTime": "1970-01-01T04:10:00Z",
"detour": "0s",
"arrivalLoads": [
{
"type": "weight_kilograms"
}
]
},
{
"shipmentIndex": 6,
"isPickup": true,
"startTime": "1970-01-02T23:13:20Z",
"detour": "154629s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "10"
}
]
},
{
"shipmentIndex": 5,
"isPickup": true,
"startTime": "1970-01-08T04:30:00Z",
"detour": "606164s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "90"
}
]
},
{
"shipmentIndex": 3,
"isPickup": true,
"startTime": "1970-01-09T09:56:40Z",
"detour": "711792s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "170"
}
]
}
],
"travelSteps": [
{
"duration": "1031s",
"distanceMeters": 5435
},
{
"duration": "1031s",
"distanceMeters": 4642
},
{
"duration": "890s",
"distanceMeters": 3600
},
{
"duration": "1224s",
"distanceMeters": 5164
},
{
"duration": "0s"
}
],
"vehicleDetour": "803031s",
"endLoads": [
{
"type": "weight_kilograms",
"value": "210"
}
]
},
{
"vehicleIndex": 1,
"vehicleStartTime": "1970-01-01T17:39:35Z",
"vehicleEndTime": "1970-01-12T15:16:14Z",
"visits": [
{
"shipmentIndex": 2,
"isPickup": true,
"startTime": "1970-01-01T18:03:20Z",
"detour": "0s",
"arrivalLoads": [
{
"type": "weight_kilograms"
}
]
},
{
"shipmentIndex": 1,
"isPickup": true,
"startTime": "1970-01-10T13:10:00Z",
"detour": "760149s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "40"
}
]
},
{
"isPickup": true,
"startTime": "1970-01-11T14:16:14Z",
"detour": "850574s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "160"
}
]
}
],
"travelSteps": [
{
"duration": "1425s",
"distanceMeters": 6016
},
{
"duration": "222s",
"distanceMeters": 980
},
{
"duration": "374s",
"distanceMeters": 1573
},
{
"duration": "0s"
}
],
"vehicleDetour": "941799s",
"endLoads": [
{
"type": "weight_kilograms",
"value": "200"
}
]
},
{
"vehicleIndex": 2,
"vehicleStartTime": "1970-01-03T22:35:18Z",
"vehicleEndTime": "1970-01-08T05:20:00Z",
"visits": [
{
"shipmentIndex": 7,
"isPickup": true,
"startTime": "1970-01-03T22:50:00Z",
"detour": "0s",
"arrivalLoads": [
{
"type": "weight_kilograms"
}
]
},
{
"shipmentIndex": 8,
"isPickup": true,
"startTime": "1970-01-07T04:20:00Z",
"detour": "278910s",
"arrivalLoads": [
{
"type": "weight_kilograms",
"value": "80"
}
]
}
],
"travelSteps": [
{
"duration": "882s",
"distanceMeters": 3619
},
{
"duration": "531s",
"distanceMeters": 2288
},
{
"duration": "0s"
}
],
"vehicleDetour": "369882s",
"endLoads": [
{
"type": "weight_kilograms",
"value": "120"
}
]
}
],
"totalCost": 7610
}
Protocol buffer
routes {
vehicle_start_time {
seconds: 13969
}
vehicle_end_time {
seconds: 817000
}
visits {
shipment_index: 4
is_pickup: true
start_time {
seconds: 15000
}
detour {
}
arrival_loads {
type: "weight_kilograms"
}
}
visits {
shipment_index: 6
is_pickup: true
start_time {
seconds: 170000
}
detour {
seconds: 154629
}
arrival_loads {
type: "weight_kilograms"
value: 10
}
}
visits {
shipment_index: 5
is_pickup: true
start_time {
seconds: 621000
}
detour {
seconds: 606164
}
arrival_loads {
type: "weight_kilograms"
value: 90
}
}
visits {
shipment_index: 3
is_pickup: true
start_time {
seconds: 727000
}
detour {
seconds: 711792
}
arrival_loads {
type: "weight_kilograms"
value: 170
}
}
travel_steps {
duration {
seconds: 1031
}
distance_meters: 5435.0
}
travel_steps {
duration {
seconds: 1031
}
distance_meters: 4642.0
}
travel_steps {
duration {
seconds: 890
}
distance_meters: 3600.0
}
travel_steps {
duration {
seconds: 1224
}
distance_meters: 5164.0
}
travel_steps {
duration {
}
}
vehicle_detour {
seconds: 803031
}
end_loads {
type: "weight_kilograms"
value: 210
}
}
routes {
vehicle_index: 1
vehicle_start_time {
seconds: 63575
}
vehicle_end_time {
seconds: 1005374
}
visits {
shipment_index: 2
is_pickup: true
start_time {
seconds: 65000
}
detour {
}
arrival_loads {
type: "weight_kilograms"
}
}
visits {
shipment_index: 1
is_pickup: true
start_time {
seconds: 825000
}
detour {
seconds: 760149
}
arrival_loads {
type: "weight_kilograms"
value: 40
}
}
visits {
is_pickup: true
start_time {
seconds: 915374
}
detour {
seconds: 850574
}
arrival_loads {
type: "weight_kilograms"
value: 160
}
}
travel_steps {
duration {
seconds: 1425
}
distance_meters: 6016.0
}
travel_steps {
duration {
seconds: 222
}
distance_meters: 980.0
}
travel_steps {
duration {
seconds: 374
}
distance_meters: 1573.0
}
travel_steps {
duration {
}
}
vehicle_detour {
seconds: 941799
}
end_loads {
type: "weight_kilograms"
value: 200
}
}
routes {
vehicle_index: 2
vehicle_start_time {
seconds: 254118
}
vehicle_end_time {
seconds: 624000
}
visits {
shipment_index: 7
is_pickup: true
start_time {
seconds: 255000
}
detour {
}
arrival_loads {
type: "weight_kilograms"
}
}
visits {
shipment_index: 8
is_pickup: true
start_time {
seconds: 534000
}
detour {
seconds: 278910
}
arrival_loads {
type: "weight_kilograms"
value: 80
}
}
travel_steps {
duration {
seconds: 882
}
distance_meters: 3619.0
}
travel_steps {
duration {
seconds: 531
}
distance_meters: 2288.0
}
travel_steps {
duration {
}
}
vehicle_detour {
seconds: 369882
}
end_loads {
type: "weight_kilograms"
value: 120
}
}
total_cost: 7610.0
The preceding response example contains three routes (numbered 0, 1, and 2),
for the three vehicles.
The indices of the second and third routes (1 and 2) explicitly appear in the
vehicleIndex field of the route. However,
the field is omitted for the first route (with index 0), because its value is the
default. See
Why some fields are missing from the response.
Each route contains the overall start and end times of the corresponding
vehicle, along with a list of visits the vehicle makes along the route and
their start times. A visit's shipmentIndex corresponds to the order of the
shipment in the request. You can determine the location of the visit from
the corresponding shipment's location.
Similar to the vehicleIndex field, the shipmentIndex field is omitted
for the first shipment in the request.
Here's a map in which the locations are color-coded by route.
Why some fields are missing from the response
As mentioned earlier, the vehicleIndex field is omitted
from the first
route in the response. The reason is that the vehicleIndex is 0, which
is the default value of the field. By convention, responses in JSON format
omit fields when their value is the default.
In the third visit of vehicle 2's route, the
shipmentIndex field is omitted because its value is 0.