CVRP CVRPTWCVRPTW
Overview
The CVRPTW is exactly what it sounds like, a CVRP but with the addition of time windows. The time windows work in this context in the same way that the time windows for a TSP work. We measure the start and end of the time window with respect to the number of minutes since midnight (time zero).
Endpoints
- POST: https://api.icepack.ai/vehicle-router/solve/ (input)
- GET: https://api.icepack.ai/vehicle-router/solve/{requestid} (output)
Input
The cvrptw-acyas3nzweqb
schema defines a CVRPTW and you’ll notice it looks really similar to the CVRP schema, but with the addition of two optional fields, the windowStart
and windowEnd
on the Geocode
.
message Geocode {
required string id = 1;
required float x = 2; // longitude for earth-routing
required float y = 3; // latitude for earth-routing
required float quantity = 4 [default = 0];
optional float windowStart = 5; // the earliest arrival
optional float windowEnd = 6; // the latest arrival
}
Populating these two fields (when needed) will place an additional constraint on the arrival time at these nodes.
points {
id: "The Confession Box"
x: -6.25840282
y: 53.3503418
quantity: 20
windowStart: 720
windowEnd: 960
}
...
depot {
id: "The Oval Bar Dublin"
x: -6.26029587
y: 53.348465
quantity: 0
}
NumberOfVehicles: 3
VehicleCapacity: 100
distancetype: RoadNetwork
For examples on building a CVRPTW model from scratch and calling the API with the model see the examples repo.
Ouput
The output schema of the CVRPTW also mirrors the CVRP schema but with the addition of the arrivalTimes
field which provides the arrival time at each stop.
message Edge {
message Geometry{
required float x = 1;
required float y = 2;
}
required string from = 1;
required string to = 2;
optional float distance = 3;
repeated Geometry geometry = 5; // geometry is populated for road network pathing.
}
message SolutionResponse {
message Route{
repeated string sequence = 1;
repeated Edge edges = 2;
repeated float visitCapacities = 3;
repeated float arrivalTimes = 4;
};
repeated Route routes = 1; // Each vehicle produces a single route.
required float objective = 2; // The total cost of the solution
}
A successful solve response from the API will include an arrival time, capacity loaded, stop number and a geometry (if a road network metric is used) which will produce route outputs which conform to the following:
sequence: "Guinness Storehouse"
sequence: "The Confession Box"
sequence: "Johnnie Fox\'s Pub"
sequence: "Davy Byrne\'s pub"
sequence: "Kehoes Pub"
sequence: "The Oval Bar Dublin"
sequence: "Guinness Storehouse"
edges {
from: "Guinness Storehouse"
to: "The Confession Box"
distance: 8.185
geometry {
x: -6.28681278
y: 53.3415604
}
geometry {
x: -6.28626823
y: 53.3415527
}
geometry {
x: -6.28518
y: 53.3415413
}
geometry {
x: -6.28391314
y: 53.3415146
}
geometry {
x: -6.28390121
y: 53.3417206
}
... truncated
}
... truncated
visitCapacities: 0
visitCapacities: 20
visitCapacities: 20
visitCapacities: 20
visitCapacities: 20
visitCapacities: 20
visitCapacities: 0
arrivalTimes: 0
arrivalTimes: 480
arrivalTimes: 497.186
arrivalTimes: 720
arrivalTimes: 720.076
arrivalTimes: 722.222
arrivalTimes: 725.005
As before, these are relatively straight forward to plot in R and Python and we recommend interested users have a look at the examples repo.