Introduction to Vehicle Routing Problem

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:

JSON
    "global_start_time":"1970-01-01T00:00:00+00:00",
    "global_end_time":"1970-01-21T18:00:00+00:00",
Protocol buffer
  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:

JSON
      {
        "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"
          }
        },
      }
Protocol buffer
  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.

JSON
      {
        "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
  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.