Routing with Capacities
In addition to maximum time, the number of jobs on a route can be limited by using load capacities and route.max_jobs_on_route. The simplest way to limit the number of jobs by a route is to use route.max_jobs_on_route. For more complex scenarios involving variable load at each job, see the routing with a single load capacity and routing with multiple load capacities sections below.
Note
To run the examples in this tutorial, you will need:
- A RouteCloud API login. Use your Verizon Connect Enterprise username and password to authenticate with the RouteCloud API. To obtain a username and password, contact Verizon Connect sales.
- cURL to run the requests. You can download a cURL binary from here.
Routing with max_jobs_on_route
Request
{
"routes": [
{
"id": "route0",
"location": "39.718005, -104.969531",
"max_jobs_on_route": 3
}
],
"jobs": [
{ "id": "job0", "location": "39.635928, -105.049219" },
{ "id": "job1", "location": "39.725375, -104.791080" },
{ "id": "job2", "location": "39.708990, -105.026954" },
{ "id": "job3", "location": "39.653975, -105.093750" }
]
}
The routing_with_max_jobs_on_route.json
request - download it here. Click here to open it in the UI.
routing_with_max_jobs_on_route.json
defines a route with max_jobs_on_route set to three, and four stops. Since the route is limited to three jobs, only three of the four jobs will be routed.
Response
{
"routes": [
{
"id": "route0", ...
"stops": [
{ "type": "depot", ... },
{ "id": "job2", ... },
{ "id": "job3", ... },
{ "id": "job0", ... },
{ "type": "depot", ... }
]
}
],
"unrouted_jobs": [ { "id": "job1" } ]
}
Snipped version of the response - download the full response here. Click here to open it in the UI.
The response shows that, as expected, only three of the four jobs were routed. job1
was not routed because it is furthest from the other stops, and therefore the most expensive to route.
Routing with a Single Load Capacity
The route.load_capacity field can be used in combination with job.load to define capacitated vehicle routing problems. That is, routes that are limited by a maximum load capacity represented by arbitrary units.
route.load_capacity defines the total amount of job.load that a route can service.
Note
In a single request, load/load_capacity cannot be used in conjunction with loads/load_capacities.
Using load/load_capacity is simpler but limited to a single capacity, while loads/load_capacities allows multiple named capacities.
See routing with multiple load capacities for the more powerful alternative.
Request
{
"routes": [
{
"id": "route0",
"location": "39.718005, -104.969531",
"load_capacity": 10
}, {
"id": "route1",
"location": "39.718005, -104.969531",
"load_capacity": 20
}
],
"jobs": [
{ "id": "job0", "location": "39.635928, -105.049219", "load": 5 },
{ "id": "job1", "location": "39.725375, -104.791080", "load": 4 },
{ "id": "job2", "location": "39.708990, -105.026954", "load": 6 },
{ "id": "job3", "location": "39.653975, -105.093750", "load": 1 },
{ "id": "job4", "location": "39.590789, -105.084376", "load": 5 },
{ "id": "job5", "location": "39.638635, -105.128906", "load": 1 },
{ "id": "job6", "location": "39.597111, -105.041015", "load": 2 },
{ "id": "job7", "location": "39.727919, -105.103126", "load": 4 },
{ "id": "job8", "location": "39.615167, -104.887500", "load": 6 },
{ "id": "job9", "location": "39.820688, -105.133594", "load": 3 }
]
}
The routing_with_capacites.json
request - download it here. Click here to open it in the UI.
routing_with_capacites.json
defines two routes, and 10 stops.
route0
has a maximum capacity of 10, and route1
has a maximum capacity of 20.
The jobs have varying load amounts. The total combined load of all 10 jobs is 37, and the largest individual job load is six, meaning that at least two stops
will not be routed to accommodate the load total of the routes, 30.
Note
When building routes, if any job
has a load field set, then all routes must have a load_capacity field.
Also, if any route
has a load_capacity field, then all other routes must have a load_capacity field.
Response
{
"routes": [
{
"id": "route0", ...
"stops": [
{ "type": "depot", ... },
{ "id": "job3", ... },
{ "id": "job5", ... },
{ "id": "job4", ... },
{ "id": "job6", ... },
{ "type": "depot", ... }
]
}, {
"id": "route1",
"stops": [
{ "type": "depot", ... },
{ "id": "job7", ... },
{ "id": "job2", ... },
{ "id": "job8", ... },
{ "id": "job1", ... },
{ "type": "depot", ... }
]
}
],
"unrouted_jobs": [
{ "id": "job0" },
{ "id": "job9" }
]
}
Snipped version of the response - download the full response here. Click here to open it in the UI.
job0
and job9
were not routed, because there was insufficient capacity on the routes - route0
was filled to nine out of 10 capacity, and route1
to 20 out of 20 capacity.
Routing with Multiple Load Capacities
The route.load_capacities field can be used in combination with job.loads to define capacitated vehicle routing problems with multiple capacity limits. That is, routes that are limited by maximum load capacities represented by arbitrary units. Up to four unique metrics may be used within a request.
Note
In a single request, loads/load_capacities cannot be used in conjunction with load/load_capacity.
Using load/load_capacity is simpler but limited to a single capacity, while loads/load_capacities allows multiple named capacities.
See routing with a single load capacity for the simpler alternative.
Request
{
"routes": [
{
"id": "route0",
"location": "39.718005, -104.969531",
"load_capacities": [
{ "metric": "box_count", "amount": 5 }
]
}, {
"id": "route1",
"location": "39.718005, -104.969531",
"load_capacities": [
{ "metric": "box_count", "amount": 10 },
{ "metric": "weight_lb", "amount": 1000 }
]
}
],
"jobs": [
{ "id": "job0_4_100", "location": "39.635928, -105.049219", "loads": [
{ "metric": "box_count", "amount": 4 },
{ "metric": "weight_lb", "amount": 100 }
] },
{ "id": "job1_6_650", "location": "39.725375, -104.791080", "loads": [
{ "metric": "box_count", "amount": 6 },
{ "metric": "weight_lb", "amount": 650 }
] },
{ "id": "job2_1_0", "location": "39.708990, -105.026954", "loads": [
{ "metric": "box_count", "amount": 1 }
] },
{ "id": "job3_0_0", "location": "39.653975, -105.093750" },
{ "id": "job4_7_950", "location": "39.590789, -105.084376", "loads": [
{ "metric": "box_count", "amount": 7 },
{ "metric": "weight_lb", "amount": 950 }
] }
]
}
The routing_with_multiple_capacities.json
request - download it here. Click here to open it in the UI.
routing_with_multiple_capacities.json
defines two routes, and five jobs.
route0
has a maximum capacity of five boxes, and no capacity limit for weight.route1
has a maximum capacity of 10 boxes, and a maximum capacity of 1000 lb. Exceeding either of these results in a violation.
The jobs have varying load amounts of the two metrics, box_count
and weight_lb
. For jobs that do not have a load amount
for a given metric, the amount
is taken to be zero.
Response
{
"routes": [
{
"id": "route0", ...
"stops": [
{ "type": "depot", ... },
{ "id": "job2_1_0", ... },
{ "id": "job0_4_100", ... },
{ "type": "depot", ... }
]
}, {
"id": "route1",
"stops": [
{ "type": "depot", ... },
{ "id": "job3_0_0", ... },
{ "id": "job4_7_950", ... },
{ "type": "depot", ... }
]
}
],
"unrouted_jobs": [
{ "id": "job1_6_650" }
]
}
Snipped version of the response - download the full response here. Click here to open it in the UI.
Neither job1_6_650
nor job4_7_950
can go on route0
due to box_count
, and only one of them can go on route1
, so one of them
must remain unrouted. job0_4_100
must then go on route0
. Both job2_1_0
and job3_0_0
can go on either route. The only differentiator
is the shortest total driving distance.
Routing with Return to Depot
The settings.enable_mid_route_return_to_depot flag can be used to enable a mid-route return to a depot. If a vehicle reaches its maximum route.load_capacity, the driver can return to either their start location or another depot mid-route to reset the capacity constraint.
If settings.enable_mid_route_return_to_depot is set to true
, the optional setting return_to_depot_strategy is enabled. Use this setting to specify which depot the driver can return to mid-route. The default value is return_to_start
. Alternatively, you can choose nearest_depot
, which returns the driver to the depot location that is nearest to the current job.
Request
{
"routes": [
{
"id": "route0",
"location": "depot1",
"load_capacity": 2,
"time_on_site_at_start_location": "00:20:00",
"time_on_site_at_return_to_depot": "00:10:00",
"time_on_site_at_end_location": "00:05:00"
}
],
"jobs": [
{ "id": "job0", "location": "39.635928, -105.049219", "load": 1 },
{ "id": "job1", "location": "39.725375, -104.791080", "load": 1 },
{ "id": "job2", "location": "39.708990, -105.026954", "load": 1 },
{ "id": "job3", "location": "39.653975, -105.093750", "load": 1 },
{ "id": "job4", "location": "39.590789, -105.084376", "load": 1 }
],
"markers": [
{ "id": "depot0", "location": "39.638681, -105.08371", "is_depot": true },
{ "id": "depot1", "location": "39.718005, -104.969531", "is_depot": true }
],
"settings": {
"enable_mid_route_return_to_depot": true,
"return_to_depot_strategy": "nearest_depot"
}
}
The routing_with_return_to_depot.json
request - download it here. Click here to open it in the UI.
Response
Since routing_with_return_to_depot.json
defines a route with a load_capacity
of 2
and five stops, the route returns to the depot twice:
{
"routes": [
{
"id": "route0", ...
"stops": [
{ "type": "depot", "time_on_site": "00:20:00", ... },
{ "id": "job1", ... },
{ "id": "job0", ... },
{ "type": "depot", "time_on_site": "00:10:00", ... },
{ "id": "job3", ... },
{ "id": "job4", ... },
{ "type": "depot", "time_on_site": "00:10:00", ... },
{ "id": "job2", ... },
{ "type": "depot", "time_on_site": "00:05:00", ... }
]
}
],
"unrouted_jobs": [
]
}
Snipped version of the response - download the full response here. Click here to open it in the UI.
As expected, the driver returns to the nearest depot (as defined by return_to_depot_strategy) when their vehicle is full. The time-on-site is 20 minutes at the starting depot stop, as defined by time_on_site_at_start_location. The time-on-site is 10 minutes at both return-to-depot stops, as defined by time_on_site_at_return_to_depot. The time-on-site is five minutes at the ending depot stop, as defined by time_on_site_at_end_location.
Violations
route_over_max_jobs Violations
Routes that violate their max_jobs_on_route receive a route_over_max_jobs violation on their route response object:
{
"id": "route0",
"cost": 16.02,
"internal_cost": 124.26,
"distance_meters": 38810.0,
"working_time": "01:04:04",
"driving_time": "00:54:04",
"violations": [
{ "type": "route_over_max_jobs" }
]
}
A route with a route_over_max_jobs
violation.
Note
build requests should never produce a route_over_max_jobs violation violation, but sequence, recommend, and evaluate requests may.
route_over_load_capacity Violations
Routes that violate their load_capacity receive a route_over_load_capacity violation on their route response object:
{
"id": "route0",
"cost": 16.02,
"internal_cost": 124.26,
"distance_meters": 38810.0,
"working_time": "01:04:04",
"driving_time": "00:54:04",
"violations": [
{ "type": "route_over_load_capacity" }
]
}
A route with a route_over_load_capacity
violation.
Note
build requests should never produce a route_over_load_capacity violation, but sequence, recommend, and evaluate requests may.
See Also
- The job.load field.
- The route.load_capacity field.
- The job.loads field.
- The route.load_capacities field.
- The route.max_jobs_on_route field.
- The settings.enable_mid_route_return_to_depot field.
- The route_over_max_jobs violation.
- The route_over_load_capacity violation.