Routing with Shifts

Shifts determine the start and end time of a route and limit the number of hours a driver can work. Shifts are specified using the following fields:

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 start_time, end_time, and max_working_time

It is possible to constrain the route with a start time:

{
  "id": "route0",
  "location": "39.718005, -104.969531",
  "start_time": "09:00"
}

And an end time:

{
  "id": "route0",
  "location": "39.718005, -104.969531",
  "start_time": "09:00",
  "end_time": "17:00"
}

Alternatively, the end time can be specified using max_working_time:

{
  "id": "route0",
  "location": "39.718005, -104.969531",
  "start_time": "09:00",
  "max_working_time": "08:00"
}

It is also possible to specify end time or max working time without specifying start time:

{
  "id": "route0",
  "location": "39.718005, -104.969531",
  "max_working_time": "08:00"
}

This example would limit the total route time to 8 hours, starting at 00:00.

If the maximum time of a route is short, then jobs are either assigned to a different route, or left unrouted if no routes have sufficient capacity.

Over-midnight Shifts

Shifts that span midnight can be specified as follows:

  "id": "route0",
  "location": "39.718005, -104.969531",
  "start_time": "18:00",
  "end_time": "1.06:00"

A shift between 6:00 PM and 6:00 AM

Request

{
  "routes": [
    {
      "id": "route0",
      "location": "39.718005, -104.969531",
      "start_time": "09:00",
      "max_working_time": "02:00"
    }, {
      "id": "route1",
      "location": "39.718005, -104.969531",
      "start_time": "09:00",
      "max_working_time": "02:00"
    }
  ],
  "jobs": [
    { "id": "job0", "location": "39.635928, -105.049219" },
    { "id": "job1", "time_on_site": "00:10", "location": "39.725375, -104.791080" },
    { "id": "job2", "time_on_site": "00:15", "location": "39.708990, -105.026954" },
    { "id": "job3", "time_on_site": "00:10", "location": "39.653975, -105.093750" },
    { "id": "job4", "time_on_site": "00:15", "location": "39.590789, -105.084376" },
    { "id": "job5", "time_on_site": "00:10", "location": "39.638635, -105.128906" },
    { "id": "job6", "time_on_site": "00:10", "location": "39.597111, -105.041015" },
    { "id": "job7", "time_on_site": "00:10", "location": "39.727919, -105.103126" },
    { "id": "job8", "time_on_site": "00:10", "location": "39.615167, -104.887500" },
    { "id": "job9", "time_on_site": "00:10", "location": "39.820688, -105.133594" },
    { "id": "job10", "time_on_site": "00:10", "location": "39.749546, -105.069141" },
    { "id": "job11", "time_on_site": "00:10", "location": "39.556465, -104.976563" }
  ]
}

The basic_vehicle_routing_constrained_build.json request - download it here. Click here to open it in the UI.

The request defines two routes, both with a max_working_time of two hours. This is not enough time to service all 12 jobs.

Response

{
  "routes": [
    {
      "id": "route0", ...
      "stops": [
        { "type": "depot", ... },
        { "type": "job", "id": "job6", ... },
        { "type": "job", "id": "job11", ... },
        { "type": "job", "id": "job8", ... },
        { "type": "depot", ... }
      ]
    },
    {
      "id": "route1", ...
      "stops": [
        { "type": "depot", ... },
        { "type": "job", "id": "job7", ... },
        { "type": "job", "id": "job5", ... },
        { "type": "job", "id": "job3", ... },
        { "type": "job", "id": "job0", ... },
        { "type": "job", "id": "job2", ... },
        { "type": "depot", ... }
      ]
    }
  ],
  "unrouted_jobs": [
    { "id": "job1" },
    { "id": "job4" },
    { "id": "job9" },
    { "id": "job10" }
  ]
}

A snipped version of the basic_vehicle_routing_constrained_build.json response. The full response is available here. Click here to open it in the UI.

RouteCloud returned two routes and four unrouted jobs. Jobs are assigned to routes so that costs are minimized; for example, jobs are assigned to the closest route, and if there is not sufficient capacity to route all jobs, the most expensive jobs are left unrouted.

Image of the route response
Image of the routes produced by running basic_vehicle_routing_constrained_build.json. Gray jobs are unrouted.

As shown in the image above, nearby jobs are routed together, and the four furthest outlier jobs are left unrouted to prevent the driver.max_working_time constraint being violated.

Routing with optimize_start_time

Request

{
  "routes": [
    {
      "id": "route0",
      "location": "39.718005, -104.969531",
      "start_time": "08:00",
      "end_time": "17:00",
      "max_working_time": "09:00",
      "optimize_start_time": false,
      "date": "2016-1-18"
    }
  ],
  "jobs": [
    { "id": "job0", "time_on_site": "01:00", "location": "39.635928, -105.049219", "time_window": { "start" : "08:00", "end" : "12:00" } },
    { "id": "job1", "time_on_site": "01:00", "location": "39.597111, -105.041015", "time_window": { "start" : "08:00", "end" : "12:00" } },
    { "id": "job2", "time_on_site": "01:00", "location": "39.708990, -105.026954", "time_window": { "start" : "13:00", "end" : "17:00" } },
    { "id": "job3", "time_on_site": "01:00", "location": "39.653975, -105.093750", "time_window": { "start" : "13:00", "end" : "17:00" } },
    { "id": "job4", "time_on_site": "01:00", "location": "39.590789, -105.084376", "time_window": { "start" : "13:00", "end" : "17:00" } }
  ]
}

The routing_without_optimize_start_time.json request - download it here. Click here to open it in the UI.

The request defines one route and five jobs:

  • route0 has a start_time of 8:00 AM.
  • job0 and job1 are morning jobs, with a time window of 8:00 AM to 12:00 PM.
  • job2, job3, and job4 are afternoon jobs, with a time window of 1:00 PM to 5:00 PM.

Response without optimize_start_time

{
  "routes": [
    {
      "id": "route0",
      "working_time": "08:39:24",
      "stops": [
        { "type": "depot", "arrival_datetime": "2016-01-18T08:00:00", ... },
        { "type": "job", "id": "job0", "arrival_datetime": "2016-01-18T08:23:06", ... },
        { "type": "job", "id": "job1", "arrival_datetime": "2016-01-18T09:34:16", ... },
        { "type": "job", "id": "job4", "arrival_datetime": "2016-01-18T13:00:00", "idle_time": "02:17:16", ... },
        { "type": "job", "id": "job3", "arrival_datetime": "2016-01-18T14:12:16", ... },
        { "type": "job", "id": "job2", "arrival_datetime": "2016-01-18T15:27:34", ... },
        { "type": "depot", "arrival_datetime": "2016-01-18T16:39:24", ... }
      ]
    }
  ],
  "unrouted_jobs": []
}

A snipped version of the routing_without_optimize_start_time.json response. The full response is available here. Click here to open it in the UI.

The arrival_datetime of the first stop indicates that the route starts at 8:00 AM. There are not enough jobs to fill the morning, creating idle time of 02:17:16 before the first afternoon stop job4. This idle time is inefficient, and can be eliminated by allowing the route to start later using optimize_start_time. Click here to download the same request with optimize_start_time set to true.

Response with optimize_start_time

{
  "routes": [
    {
      "id": "route0",
      "working_time": "06:22:08",
      "stops": [
        { "type": "depot", "arrival_datetime": "2016-01-18T10:17:16", ... },
        { "type": "job", "id": "job0", "arrival_datetime": "2016-01-18T10:40:22", ... },
        { "type": "job", "id": "job1", "arrival_datetime": "2016-01-18T11:51:32", ... },
        { "type": "job", "id": "job4", "arrival_datetime": "2016-01-18T13:00:00", ... },
        { "type": "job", "id": "job3", "arrival_datetime": "2016-01-18T14:12:16", ... },
        { "type": "job", "id": "job2", "arrival_datetime": "2016-01-18T15:27:34", ... },
        { "type": "depot", "arrival_datetime": "2016-01-18T16:39:24", ... }
      ]
    ...
    }
  ],
  "unrouted_jobs": []
}

A snipped version of the routing_with_optimize_start_time.json response. The full response is available here. Click here to open it in the UI.

With optimize_start_time enabled, RouteCloud chooses to start the route at 10:17 AM instead of 8:00 AM, as indicated by the arrival_datetime of the first stop. This eliminates the idle time seen previously, and reduces the total working_time from 08:39:24 to 06:22:08.

Violations

If the max_working_time_as_hard_constraint settings flag is set to false, then RouteCloud may allow a driver to violate their max_working_time constraint in order to route more stops. By default, max_working_time_as_hard_constraint is set to true.

{
  "routes": [ ... ],
  "jobs": [ ... ],
  "settings": {
    "max_working_time_as_hard_constraint": false
  }
}

max_working_time as a soft constraint.

Routes that violate their max_working_time receive a route_over_max_working_time 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_working_time" }
  ]
}
Note

If maximum working time is set as a hard constraint, build requests should never produce a route_over_max_working_time violation, but sequence, recommend, and evaluate requests may.

See Also