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