For some problems, Cloud Fleet Routing might return a solution in which some scheduled arrival times for visits are close to the end of their requested time windows. In such cases, you might prefer a solution with earlier arrival times. Here are a couple of reasons:
If the arrival times are near the middle of the time windows, drivers have more time to perform tasks at the visits.
If a scheduled arrival time is too close to the end of a time window, a driver who is running late might not be able to make the visit on time.
To make Cloud Fleet Routing schedule an earlier arrival, you can add a soft_end_time
to the time window for a visit. The soft_end_time, which is earlier than the
window's end_time, adds a
cost to the objective function proportional
to the difference between the arrival time and the soft_end_time (if the
arrival time is later than the soft_end_time).
This gives the Cloud Fleet Routing service an incentive to schedule an earlier arrival.
Note that soft_end_time just creates a preference: the arrival time could still
be later than soft_end_time.
Example
This section presents a simple Python example that involves 4 locations and
1 vehicle. In this example, the Cloud Fleet Routing service returns a
solution with an arrival time close to the end of the requested time window.
The example shows how to get an earlier visit's arrival time by
adding a soft_end_time.
The following shows the request code for this example. You can send this request using the Python program Python API Client Library. described previously.
{
"parent": "projects/${YOUR_GCP_PROJECT_ID}",
"googleMapsApiKey": "${YOUR_MAPS_API_KEY}",
"model":{
"globalStartTime":"1970-01-01T00:00:00+00:00",
"globalEndTime":"1970-01-01T23:00:00+00:00",
"shipments":[
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.351365,
"longitude":-71.069619
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T10:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.340630,
"longitude":-71.082230
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T11:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.339755,
"longitude":-71.104922
},
"timeWindows":[
{
"startTime":"1970-01-01T09:00:00+00:00",
"endTime":"1970-01-01T10:30:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.311911,
"longitude":-71.146368
},
"timeWindows":[
{
"startTime":"1970-01-01T11:00:00+00:00",
"endTime":"1970-01-01T13:00:00+00:00"
}
],
"duration":"3600s"
}
]
}
],
"vehicles":[
{
"startLocation":{
"latitude":42.353404,
"longitude":-71.060771
},
"endTimeWindows":[
{
"endTime":"1970-01-01T23:00:00+00:00"
}
],
"costPerTraveledHour":3600
}
]
}
}
Arrival times
The response to the earlier request contains the scheduled arrival times shown in the following table. This table also shows the requested visit's time windows. To make the times easier to read, the table only displays hours and minutes.
| Shipment index | Scheduled arrival time | Requested time window |
|---|---|---|
| 0 | 08:00 | 08:00 - 10:00 |
| 1 | 09:08 | 08:00 - 11:00 |
| 2 | 10:18 | 08:00 - 10:30 |
| 3 | 11:33 | 11:00 - 13:00 |
Notice that the scheduled arrival time for shipment 2 is 10:18, which is very close to the end of the requested time window, 10:30.
Add a soft end time
To get a solution with an earlier arrival time for shipment 2, add the following to the visit's time window:
"softEndTime":"09:45", set to the middle of the requested time interval."costPerHourAfterSoftEndTime":1000. If the scheduled arrival time is later than thesoft_end_time, the solver adds a cost to the objective function that is equal to thecost_per_hour_after_soft_end_timemultiplied by the length of time from thesoft_end_timeto the scheduled visit.
The following shows the complete time window for shipment 2.
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T10:30:00+00:00",
"softEndTime":"09:45",
"costPerHourAfterSoftEndTime":1000
You might have to try different values for the
cost_per_hour_after_soft_end_time to get a schedule that meets your needs.
Arrival times using soft_end_time
After adding a soft end time to the request, here are the new resulting scheduled arrival times (in hours and minutes only).
| Shipment index | Scheduled arrival time | Requested time window |
|---|---|---|
| 0 | 08:00 | 08:00 - 10:00 |
| 2 | 09:11 | 08:00 - 10:30 |
| 1 | 10:20 | 08:00 - 11:00 |
| 3 | 11:41 | 11:00 - 13:00 |
This time the proposed route is different: Shipment 2 is delivered before Shipment 1. Also, shipment 2's scheduled arrival is now 09:11, leaving plenty of time before the end of the requested time window.
Note that the total cost of this solution is greater than the previous solution:
- Total cost without soft end time:
2491.0 - Total cost with soft end time:
3071.0
You'll need to balance the additional cost against the improvement to the schedule.
Complete requests and responses
Here is the complete source code of requests and responses, with and without soft_end_time.
Request (no soft_end_time)
{
"parent": "projects/${YOUR_GCP_PROJECT_ID}",
"googleMapsApiKey": "${YOUR_MAPS_API_KEY}",
"model":{
"globalStartTime":"1970-01-01T00:00:00+00:00",
"globalEndTime":"1970-01-01T23:00:00+00:00",
"shipments":[
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.351365,
"longitude":-71.069619
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T10:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.340630,
"longitude":-71.082230
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T11:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.339755,
"longitude":-71.104922
},
"timeWindows":[
{
"startTime":"1970-01-01T09:00:00+00:00",
"endTime":"1970-01-01T10:30:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.311911,
"longitude":-71.146368
},
"timeWindows":[
{
"startTime":"1970-01-01T11:00:00+00:00",
"endTime":"1970-01-01T13:00:00+00:00"
}
],
"duration":"3600s"
}
]
}
],
"vehicles":[
{
"startLocation":{
"latitude":42.353404,
"longitude":-71.060771
},
"endTimeWindows":[
{
"endTime":"1970-01-01T23:00:00+00:00"
}
],
"costPerTraveledHour":3600
}
]
}
}
Response (no soft_end_time)
{
"routes": [
{
"vehicleStartTime": "1970-01-01T07:53:42Z",
"vehicleEndTime": "1970-01-01T12:33:28Z",
"visits": [
{
"isPickup": true,
"startTime": "1970-01-01T08:00:00Z",
"detour": "0s"
},
{
"shipmentIndex": 1,
"isPickup": true,
"startTime": "1970-01-01T09:08:18Z",
"detour": "3819s"
},
{
"shipmentIndex": 2,
"isPickup": true,
"startTime": "1970-01-01T10:18:53Z",
"detour": "7835s"
},
{
"shipmentIndex": 3,
"isPickup": true,
"startTime": "1970-01-01T11:33:28Z",
"detour": "11519s"
}
],
"travelSteps": [
{
"duration": "378s",
"distanceMeters": 1112
},
{
"duration": "498s",
"distanceMeters": 1970
},
{
"duration": "635s",
"distanceMeters": 3122
},
{
"duration": "875s",
"distanceMeters": 6529
},
{
"duration": "0s"
}
],
"vehicleDetour": "16786s",
"transitions": [
{
"travelDuration": "378s",
"travelDistanceMeters": 1112
},
{
"travelDuration": "498s",
"travelDistanceMeters": 1970
},
{
"travelDuration": "635s",
"travelDistanceMeters": 3122
},
{
"travelDuration": "875s",
"travelDistanceMeters": 6529
},
{
"travelDuration": "0s"
}
]
}
],
"totalCost": 2386
}
Request (with soft_end_time)
{
"parent": "projects/${YOUR_GCP_PROJECT_ID}",
"googleMapsApiKey": "${YOUR_MAPS_API_KEY}",
"model":{
"globalStartTime":"1970-01-01T00:00:00+00:00",
"globalEndTime":"1970-01-01T23:00:00+00:00",
"shipments":[
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.351365,
"longitude":-71.069619
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T10:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.340630,
"longitude":-71.082230
},
"timeWindows":[
{
"startTime":"1970-01-01T08:00:00+00:00",
"endTime":"1970-01-01T11:00:00+00:00"
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.339755,
"longitude":-71.104922
},
"timeWindows":[
{
"startTime":"1970-01-01T09:00:00+00:00",
"endTime":"1970-01-01T10:30:00+00:00",
"softEndTime":"1970-01-01T9:45:00+00:00",
"costPerHourAfterSoftEndTime": 1000
}
],
"duration":"3600s"
}
]
},
{
"pickups":[
{
"arrivalLocation":{
"latitude":42.311911,
"longitude":-71.146368
},
"timeWindows":[
{
"startTime":"1970-01-01T11:00:00+00:00",
"endTime":"1970-01-01T13:00:00+00:00"
}
],
"duration":"3600s"
}
]
}
],
"vehicles":[
{
"startLocation":{
"latitude":42.353404,
"longitude":-71.060771
},
"endTimeWindows":[
{
"endTime":"1970-01-01T23:00:00+00:00"
}
],
"costPerTraveledHour":3600
}
]
}
}
Response (with soft_end_time)
{
"routes": [
{
"vehicleStartTime": "1970-01-01T07:53:42Z",
"vehicleEndTime": "1970-01-01T12:41:32Z",
"visits": [
{
"isPickup": true,
"startTime": "1970-01-01T08:00:00Z",
"detour": "0s"
},
{
"shipmentIndex": 2,
"isPickup": true,
"startTime": "1970-01-01T09:11:12Z",
"detour": "3774s"
},
{
"shipmentIndex": 1,
"isPickup": true,
"startTime": "1970-01-01T10:20:14Z",
"detour": "8135s"
},
{
"shipmentIndex": 3,
"isPickup": true,
"startTime": "1970-01-01T11:41:32Z",
"detour": "12003s"
}
],
"travelSteps": [
{
"duration": "378s",
"distanceMeters": 1112
},
{
"duration": "672s",
"distanceMeters": 4857
},
{
"duration": "542s",
"distanceMeters": 2821
},
{
"duration": "1278s",
"distanceMeters": 8374
},
{
"duration": "0s"
}
],
"vehicleDetour": "17270s",
"transitions": [
{
"travelDuration": "378s",
"travelDistanceMeters": 1112
},
{
"travelDuration": "672s",
"travelDistanceMeters": 4857
},
{
"travelDuration": "542s",
"travelDistanceMeters": 2821
},
{
"travelDuration": "1278s",
"travelDistanceMeters": 8374
},
{
"travelDuration": "0s"
}
]
}
],
"totalCost": 2870
}