Order Level Constraints


Visit Range and Visit Gap — visit_range and visit_gap

Description

The visit_range and visit_gap constraints often work together to meet specific visit requirements at the orders. Visit range allows one to specify the number of times an order is visited, and visit gap allows one to constrain the spacing of these visits. Both are described individually below, and the example demonstrates how they work in conjunction with one another. Both constraints can be restricted to a subset of orders if desired by specifying an optional order_id‘s array as shown below.

Visit Range

Ensure an order receives a specified minimum and/or maximum number of visits over the entire planning period. This constraint is particularly useful in problems that span multiple days where vehicles have multiple shifts. The default value of min_visits is 1 for any order. If the visit range constraint is not included in a request, then the optimization has no incentive to visit the orders, and the default behavior would be to simply not visit any orders and return an empty solution. Since this is surely not the desired behavior, the user is protected in the event they do not include a visit range constraint and the optimization proceeds as if one does want to visit all the orders one time.

{
    "constraint_name": "visit as many orders as possible",
    "violation_increment": 1,
    "constraint_type": "visit_range",
    "penalty_per_violation": 10000
}

Visit Gap

Ensure the spacing of visits at an order meets requirements. The gap between consecutive visits at a single order is measured as the difference in the first arrival time and the next arrival time. The constraint checks the visit spacing at each order against the values for min_days and max_days which can be specified for each order object. If the amount of time between visits at an order falls outside of this range, then a penalty is assessed. The units of violation_increment is days.

{
    "constraint_name": "space visits",
    "violation_increment": 1,
    "constraint_type": "Visit_Gap",
    "penalty_per_violation": 10000,
    "order_ids": [
        "order 1",
        "order 867"
    ]
}

Example: Revenue Optimization

If we use the default travel_time constraint so that one second of travel by a vehicle is equivalent to one unit of penalty, then we can use visit range as a way to express our problem as a revenue optimization problem. In the example below, we have two visit_range constraints – one for generic orders with a penalty of 1000 and another with a penalty of 40,000 for a set of “high profit” orders. Now the tradeoff is that for the typical order, if we must travel more than 2000 seconds out of the way to visit a location, we will choose not to do so. For the high profit orders, if we must travel more than 40,000 seconds out of the way in order to hit these then we will choose not to do so. If one has a dollar cost associated with a vehicle traveling 1 second, and a dollar revenue amount for visiting each location, then the objective function becomes a very good proxy for the profit of the route. The request below includes both visit range constraints (for the generic orders and the high profit orders). Note that it is also possible to achieve this behavior with the order_priority constraint – here we are just expressing this in a slightly different way.

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "max_travel_time_seconds": 0,
            "constraint_name": "limit travel"
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 40000,
            "constraint_name": "service high profit orders",
            "order_ids": [
                "509217",
                "623404",
                "693858",
                "617086",
                "694498",
                "340637"
            ]
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 2000,
            "constraint_name": "service generic orders assuming each is worth at most 2000 seconds of travel time"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "shift_id": "v1shift1",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc20",
                    "end_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "shift_id": "v2shift1",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc99",
                    "end_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle2"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T09:10:00-04:00",
                    "shift_id": "v3shift",
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "start_location_id": "loc16",
                    "end_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle3"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "duration": 600,
            "location_id": "loc1"
        },
        {
            "order_id": "689105",
            "duration": 600,
            "location_id": "loc3"
        },
        {
            "order_id": "692039",
            "duration": 1800,
            "location_id": "loc5"
        },
        {
            "order_id": "583368",
            "duration": 600,
            "location_id": "loc6"
        },
        {
            "order_id": "677048",
            "duration": 600,
            "location_id": "loc7"
        },
        {
            "order_id": "685086",
            "duration": 600,
            "location_id": "loc8"
        },
        {
            "order_id": "690020",
            "duration": 600,
            "location_id": "loc9"
        },
        {
            "order_id": "674660",
            "duration": 600,
            "location_id": "loc11"
        },
        {
            "order_id": "413170",
            "duration": 600,
            "location_id": "loc13"
        },
        {
            "order_id": "685945",
            "duration": 600,
            "location_id": "loc14"
        },
        {
            "order_id": "692592",
            "duration": 600,
            "location_id": "loc15"
        },
        {
            "order_id": "678545",
            "duration": 600,
            "location_id": "loc17"
        },
        {
            "order_id": "692829",
            "duration": 600,
            "location_id": "loc18"
        },
        {
            "order_id": "695124",
            "duration": 600,
            "location_id": "loc19"
        },
        {
            "order_id": "693192",
            "duration": 600,
            "location_id": "loc21"
        },
        {
            "order_id": "649953",
            "duration": 600,
            "location_id": "loc22"
        },
        {
            "order_id": "694498",
            "duration": 600,
            "location_id": "loc23"
        },
        {
            "order_id": "693854",
            "duration": 600,
            "location_id": "loc24"
        },
        {
            "order_id": "688899",
            "duration": 600,
            "location_id": "loc25"
        },
        {
            "order_id": "617086",
            "duration": 600,
            "location_id": "loc26"
        },
        {
            "order_id": "340637",
            "duration": 600,
            "location_id": "loc27"
        },
        {
            "order_id": "693098",
            "duration": 600,
            "location_id": "loc28"
        },
        {
            "order_id": "683931",
            "duration": 600,
            "location_id": "loc29"
        },
        {
            "order_id": "685382",
            "duration": 600,
            "location_id": "loc30"
        },
        {
            "order_id": "691449",
            "duration": 600,
            "location_id": "loc31"
        },
        {
            "order_id": "509217",
            "duration": 600,
            "location_id": "loc32"
        },
        {
            "order_id": "691287",
            "duration": 600,
            "location_id": "loc33"
        },
        {
            "order_id": "640723",
            "duration": 600,
            "location_id": "loc34"
        },
        {
            "order_id": "665537",
            "duration": 600,
            "location_id": "loc35"
        },
        {
            "order_id": "693858",
            "duration": 600,
            "location_id": "loc36"
        },
        {
            "order_id": "392888",
            "duration": 600,
            "location_id": "loc37"
        },
        {
            "order_id": "623404",
            "duration": 600,
            "location_id": "loc38"
        },
        {
            "order_id": "695743",
            "duration": 600,
            "location_id": "loc39"
        },
        {
            "order_id": "692431",
            "duration": 600,
            "location_id": "loc40"
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ]
}

img

The solution when we just account for revenue at the generic orders and do not treat any of the high profit orders differently. Note the unserviced orders boxed in red – these will be added to the second visit_range constraint in the next request.

img

The solution after adding the second visit_range constraint for the high profit orders. Now note that all of the outlying orders missed in the first solution are now visited (green boxes above).

Example: Combining Visit Gap and Visit Range

In the full example below, we specify a problem with four vehicles where each vehicle has two shifts over two consecutive days. Many of the orders now require a minimum of two visits with a gap (min_days) of 1. If the visit gap constraint is not given, then the routes simply consecutively visit each of these orders that require two visits. This allows a solution with only three vehicles and another vehicle that is only active on one of the days. With the visit gap constraint in place we must have at least 1 day (24 hours) between visits – all visit requirements are still met, but all 8 shifts are required. The request below contains both the visit_range and Visit_Gap constraints

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "max_travel_time_seconds": 0,
            "constraint_name": "limit travel"
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "meet visit requirements"
        },
        {
            "constraint_type": "Visit_Gap",
            "penalty_per_violation": 5000,
            "violation_increment": 1,
            "constraint_name": "space visits"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "shift_id": "v1shift1",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc20",
                    "end_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                },
                {
                    "shift_end": "2017-08-25T17:10:00-04:00",
                    "shift_id": "v1shift2",
                    "shift_start": "2017-08-25T08:05:00-04:00",
                    "break_end": [
                        "2017-08-25T13:00:00-04:00"
                    ],
                    "start_location_id": "loc20",
                    "end_location_id": "loc20",
                    "break_start": [
                        "2017-08-25T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "shift_id": "v2shift1",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc99",
                    "end_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                },
                {
                    "shift_end": "2017-08-25T15:10:00-04:00",
                    "shift_id": "v2shift2",
                    "shift_start": "2017-08-25T10:05:00-04:00",
                    "break_end": [
                        "2017-08-25T13:00:00-04:00"
                    ],
                    "start_location_id": "loc99",
                    "end_location_id": "loc99",
                    "break_start": [
                        "2017-08-25T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle2"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T13:10:00-04:00",
                    "shift_id": "v3shift",
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "start_location_id": "loc16",
                    "end_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ]
                },
                {
                    "shift_end": "2017-08-25T13:10:00-04:00",
                    "shift_id": "v3shift1",
                    "shift_start": "2017-08-25T07:05:00-04:00",
                    "break_end": [
                        "2017-08-25T10:00:00-04:00"
                    ],
                    "start_location_id": "loc16",
                    "end_location_id": "loc16",
                    "break_start": [
                        "2017-08-25T09:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle3"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T16:10:00-04:00",
                    "shift_id": "v4shift1",
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc100",
                    "end_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                },
                {
                    "shift_end": "2017-08-25T16:10:00-04:00",
                    "shift_id": "v4shift2",
                    "shift_start": "2017-08-25T09:05:00-04:00",
                    "break_end": [
                        "2017-08-25T13:00:00-04:00"
                    ],
                    "start_location_id": "loc100",
                    "end_location_id": "loc100",
                    "break_start": [
                        "2017-08-25T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle4"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "duration": 600,
            "location_id": "loc1",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "689105",
            "duration": 600,
            "location_id": "loc3",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "692039",
            "duration": 1800,
            "location_id": "loc5"
        },
        {
            "order_id": "583368",
            "duration": 600,
            "location_id": "loc6"
        },
        {
            "order_id": "677048",
            "duration": 600,
            "location_id": "loc7",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "685086",
            "duration": 600,
            "location_id": "loc8",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "690020",
            "duration": 600,
            "location_id": "loc9",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "674660",
            "duration": 600,
            "location_id": "loc11",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "413170",
            "duration": 600,
            "location_id": "loc13",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "685945",
            "duration": 600,
            "location_id": "loc14"
        },
        {
            "order_id": "692592",
            "duration": 600,
            "location_id": "loc15"
        },
        {
            "order_id": "678545",
            "duration": 600,
            "location_id": "loc17",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "692829",
            "duration": 600,
            "location_id": "loc18"
        },
        {
            "order_id": "695124",
            "duration": 600,
            "location_id": "loc19",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "693192",
            "duration": 600,
            "location_id": "loc21"
        },
        {
            "order_id": "649953",
            "duration": 600,
            "location_id": "loc22",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "694498",
            "duration": 600,
            "location_id": "loc23"
        },
        {
            "order_id": "693854",
            "duration": 600,
            "location_id": "loc24",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "688899",
            "duration": 600,
            "location_id": "loc25",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "617086",
            "duration": 600,
            "location_id": "loc26",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "340637",
            "duration": 600,
            "location_id": "loc27"
        },
        {
            "order_id": "693098",
            "duration": 600,
            "location_id": "loc28",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "683931",
            "duration": 600,
            "location_id": "loc29",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "685382",
            "duration": 600,
            "location_id": "loc30"
        },
        {
            "order_id": "691449",
            "duration": 600,
            "location_id": "loc31",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "509217",
            "duration": 600,
            "location_id": "loc32",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "691287",
            "duration": 600,
            "location_id": "loc33",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "640723",
            "duration": 600,
            "location_id": "loc34",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "665537",
            "duration": 600,
            "location_id": "loc35",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "693858",
            "duration": 600,
            "location_id": "loc36",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "392888",
            "duration": 600,
            "location_id": "loc37",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "623404",
            "duration": 600,
            "location_id": "loc38",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "695743",
            "duration": 600,
            "location_id": "loc39",
            "min_visits": 2,
            "min_days": 1
        },
        {
            "order_id": "692431",
            "duration": 600,
            "location_id": "loc40",
            "min_visits": 2,
            "min_days": 1
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ]
}

imgThe solution where no visit gap constraint is specified. All the orders that require multiple visits are now visited back to back on the route since there is no incentive to space out the visits. The vehicle starting at the northwest-most location is not needed at all.

imgThe solution when we use both visit range and visit gap constraints. Visits to each customer location now do not occur within 24 hours of one another, and all 4 vehicles are active on both days.


Time Window — time_window

Description

Individual orders can have time windows – intervals during which a vehicle must arrive and begin service. This constraint determines the importance of meeting time windows at each customer. By default it applies to all orders, but if specific orders have time windows that are more important, then this constraint can be used multiple times for sets of order_ids. The constraint checks each order’s visit(s) against the time windows that are defined inside the order object.

Example

{
    "constraints": [
        {
            "constraint_name": "limit travel",
            "violation_increment": 1,
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0,
            "penalty_per_violation": 1
        },
        {
            "constraint_name": "visit as many orders as possible",
            "violation_increment": 1,
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000
        },
        {
            "constraint_name": "honor time windows",
            "violation_increment": 3600,
            "constraint_type": "Time_Window",
            "penalty_per_violation": 1000
        }
    ],
    "orders": [
        {
            "location_id": "loc1",
            "duration": 600,
            "order_id": "688798",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T10:30:00-04:00",
                    "end_time_window": "2017-08-24T11:30:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc3",
            "duration": 600,
            "order_id": "689105",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T13:30:00-04:00",
                    "end_time_window": "2017-08-24T14:00:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc5",
            "duration": 1800,
            "order_id": "692039",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T14:30:00-04:00",
                    "end_time_window": "2017-08-24T17:30:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc6",
            "duration": 600,
            "order_id": "583368",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T10:30:00-04:00",
                    "end_time_window": "2017-08-24T10:46:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc7",
            "duration": 600,
            "order_id": "677048",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T10:30:00-04:00",
                    "end_time_window": "2017-08-24T11:30:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc8",
            "duration": 600,
            "order_id": "685086",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T10:30:00-04:00",
                    "end_time_window": "2017-08-24T11:30:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc9",
            "duration": 600,
            "order_id": "690020",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T10:30:00-04:00",
                    "end_time_window": "2017-08-24T11:30:00-04:00"
                }
            ]
        },
        {
            "location_id": "loc11",
            "duration": 600,
            "order_id": "674660"
        },
        {
            "location_id": "loc13",
            "duration": 600,
            "order_id": "413170"
        },
        {
            "location_id": "loc14",
            "duration": 600,
            "order_id": "685945"
        },
        {
            "location_id": "loc15",
            "duration": 600,
            "order_id": "692592"
        },
        {
            "location_id": "loc17",
            "duration": 600,
            "order_id": "678545"
        },
        {
            "location_id": "loc18",
            "duration": 600,
            "order_id": "692829"
        },
        {
            "location_id": "loc19",
            "duration": 600,
            "order_id": "695124"
        },
        {
            "location_id": "loc21",
            "duration": 600,
            "order_id": "693192"
        },
        {
            "location_id": "loc22",
            "duration": 600,
            "order_id": "649953"
        },
        {
            "location_id": "loc23",
            "duration": 600,
            "order_id": "694498"
        },
        {
            "location_id": "loc24",
            "duration": 600,
            "order_id": "693854"
        },
        {
            "location_id": "loc25",
            "duration": 600,
            "order_id": "688899"
        },
        {
            "location_id": "loc26",
            "duration": 600,
            "order_id": "617086"
        },
        {
            "location_id": "loc27",
            "duration": 600,
            "order_id": "340637"
        },
        {
            "location_id": "loc28",
            "duration": 600,
            "order_id": "693098"
        },
        {
            "location_id": "loc29",
            "duration": 600,
            "order_id": "683931"
        },
        {
            "location_id": "loc30",
            "duration": 600,
            "order_id": "685382"
        },
        {
            "location_id": "loc31",
            "duration": 600,
            "order_id": "691449"
        },
        {
            "location_id": "loc32",
            "duration": 600,
            "order_id": "509217"
        },
        {
            "location_id": "loc33",
            "duration": 600,
            "order_id": "691287"
        },
        {
            "location_id": "loc34",
            "duration": 600,
            "order_id": "640723"
        },
        {
            "location_id": "loc35",
            "duration": 600,
            "order_id": "665537"
        },
        {
            "location_id": "loc36",
            "duration": 600,
            "order_id": "693858"
        },
        {
            "location_id": "loc37",
            "duration": 600,
            "order_id": "392888"
        },
        {
            "location_id": "loc38",
            "duration": 600,
            "order_id": "623404"
        },
        {
            "location_id": "loc39",
            "duration": 600,
            "order_id": "695743"
        },
        {
            "location_id": "loc40",
            "duration": 600,
            "order_id": "692431"
        }
    ],
    "locations": [
        {
            "location_id": "loc1",
            "longitude": -84.07639,
            "latitude": 33.3300399
        },
        {
            "location_id": "loc2",
            "longitude": -84.4153667,
            "latitude": 33.5179638
        },
        {
            "location_id": "loc3",
            "longitude": -84.52763,
            "latitude": 34.07687
        },
        {
            "location_id": "loc4",
            "longitude": -85.15883,
            "latitude": 33.73872
        },
        {
            "location_id": "loc5",
            "longitude": -84.1256499,
            "latitude": 34.02463
        },
        {
            "location_id": "loc6",
            "longitude": -84.30268,
            "latitude": 33.78583
        },
        {
            "location_id": "loc7",
            "longitude": -84.5738499,
            "latitude": 34.07687
        },
        {
            "location_id": "loc8",
            "longitude": -83.7661399,
            "latitude": 33.98557
        },
        {
            "location_id": "loc9",
            "longitude": -84.69128,
            "latitude": 34.02403
        },
        {
            "location_id": "loc11",
            "longitude": -84.26431,
            "latitude": 33.57832
        },
        {
            "location_id": "loc12",
            "longitude": -84.51451,
            "latitude": 33.56882
        },
        {
            "location_id": "loc13",
            "longitude": -84.30606,
            "latitude": 33.8200999
        },
        {
            "location_id": "loc14",
            "longitude": -84.02126,
            "latitude": 33.98078
        },
        {
            "location_id": "loc15",
            "longitude": -84.20871,
            "latitude": 33.98596
        },
        {
            "location_id": "loc16",
            "longitude": -83.789905,
            "latitude": 34.098671
        },
        {
            "location_id": "loc17",
            "longitude": -84.3739,
            "latitude": 33.68959
        },
        {
            "location_id": "loc18",
            "longitude": -84.08495,
            "latitude": 33.8965699
        },
        {
            "location_id": "loc19",
            "longitude": -84.5491,
            "latitude": 34.0078
        },
        {
            "location_id": "loc20",
            "longitude": -84.78468,
            "latitude": 33.44852
        },
        {
            "location_id": "loc21",
            "longitude": -84.7372199,
            "latitude": 33.45099
        },
        {
            "location_id": "loc22",
            "longitude": -84.44377,
            "latitude": 33.7084199
        },
        {
            "location_id": "loc23",
            "longitude": -84.37416,
            "latitude": 34.0286
        },
        {
            "location_id": "loc24",
            "longitude": -84.23121,
            "latitude": 33.82054
        },
        {
            "location_id": "loc25",
            "longitude": -84.21402,
            "latitude": 33.83828
        },
        {
            "location_id": "loc26",
            "longitude": -84.31995,
            "latitude": 34.05614
        },
        {
            "location_id": "loc27",
            "longitude": -84.6712,
            "latitude": 33.7435386
        },
        {
            "location_id": "loc28",
            "longitude": -84.8082699,
            "latitude": 33.99045
        },
        {
            "location_id": "loc29",
            "longitude": -84.7469,
            "latitude": 33.84614
        },
        {
            "location_id": "loc30",
            "longitude": -84.23972,
            "latitude": 33.68736
        },
        {
            "location_id": "loc31",
            "longitude": -84.3845599,
            "latitude": 33.7757999
        },
        {
            "location_id": "loc32",
            "longitude": -84.1556,
            "latitude": 34.19941
        },
        {
            "location_id": "loc33",
            "longitude": -84.35911,
            "latitude": 33.75112
        },
        {
            "location_id": "loc34",
            "longitude": -83.707189,
            "latitude": 33.9854531
        },
        {
            "location_id": "loc35",
            "longitude": -84.36567,
            "latitude": 33.52079
        },
        {
            "location_id": "loc36",
            "longitude": -84.2661811,
            "latitude": 34.104
        },
        {
            "location_id": "loc37",
            "longitude": -84.20234,
            "latitude": 33.88826
        },
        {
            "location_id": "loc38",
            "longitude": -84.32034,
            "latitude": 33.4439
        },
        {
            "location_id": "loc39",
            "longitude": -84.23654,
            "latitude": 33.96681
        },
        {
            "location_id": "loc40",
            "longitude": -83.81919,
            "latitude": 34.1162
        },
        {
            "location_id": "loc99",
            "longitude": -85.0148499,
            "latitude": 34.07697
        },
        {
            "location_id": "loc100",
            "longitude": -84.52097,
            "latitude": 33.9157
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_id": "v1shift",
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "start_location_id": "loc20",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "end_location_id": "loc20",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_id": "v2shift",
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "start_location_id": "loc99",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "end_location_id": "loc99",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle2"
        },
        {
            "shifts": [
                {
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "shift_id": "v3shift",
                    "shift_end": "2017-08-24T13:10:00-04:00",
                    "start_location_id": "loc16",
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "end_location_id": "loc16",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle3"
        },
        {
            "shifts": [
                {
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_id": "v4shift",
                    "shift_end": "2017-08-24T16:10:00-04:00",
                    "start_location_id": "loc100",
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "end_location_id": "loc100",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle4"
        }
    ]
}

imgOriginal four vehicle solution with no time window constraints

imgFour vehicle solution after adding time window constraints. The bottom orange route changes substantially and we can see backtracking in this route to satisfy the time windows. We add about an hour to the total travel time across all routes in order to satisfy all the time windows.


Scheduled Appointment — scheduled_appointment, scheduled_appointment_shift, and scheduled_appointment_vehicle

Description

A scheduled appointment is more stringent than a time window. Appointments are expressed inside the order object, and they must include an appointment_start and appointment_end time. One can additionally specify a specific shift_id and/or a vehicle_id if the appointment should be satisfied by a particular shift or vehicle. Given some appointment at an order, service must begin exactly at the specified time and end at the specified time. Meeting an appointment can sometimes force the vehicle to idle/wait in order to meet the appointment, often resulting in fewer orders being visited due to the lack of flexibility in determining the route(s). The scheduled_appointment constraint ensures that the appointment times given in each order are met – note that if appointments are given in the orders but there is no scheduled_appointment constraint, then the appointments will effectively be ignored. In order to ensure that a specific shift or vehicle satisfies the appointment, then one should invoke the scheduled_appointment_shift or scheduled_appointment_vehicle constraint. By applying a combination of these constraint types to a particular appointment, one can ensure that service at the order begins at the right time by a specific vehicle or shift. This technique can be useful when an existing schedule has been determined and a new disruptive event occurs – this leads to a so-called "schedule repair" problem where one of the considerations is to produce a new schedule that is "similar" to what was planned. By expressing this previously determined schedule as a set of appointments, one can generate a new optimization problem where part of the objective is to adhere to this former plan.

Example

{
    "constraints": [
        {
            "penalty_per_violation": 1,
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0,
            "constraint_name": "limit travel",
            "violation_increment": 1
        },
        {
            "penalty_per_violation": 10000,
            "constraint_type": "visit_range",
            "constraint_name": "visit as many orders as possible",
            "violation_increment": 1
        },
        {
            "penalty_per_violation": 10000,
            "constraint_type": "Scheduled_Appointment",
            "constraint_name": "Meet scheduled appointments",
            "violation_increment": 1
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "location_id": "loc1",
            "duration": 600
        },
        {
            "order_id": "689105",
            "location_id": "loc3",
            "duration": 600
        },
        {
            "order_id": "692039",
            "location_id": "loc5",
            "duration": 1800
        },
        {
            "order_id": "583368",
            "location_id": "loc6",
            "duration": 600
        },
        {
            "order_id": "677048",
            "location_id": "loc7",
            "duration": 600
        },
        {
            "order_id": "685086",
            "location_id": "loc8",
            "duration": 600
        },
        {
            "order_id": "690020",
            "location_id": "loc9",
            "duration": 600
        },
        {
            "order_id": "674660",
            "location_id": "loc11",
            "duration": 600
        },
        {
            "order_id": "413170",
            "location_id": "loc13",
            "duration": 600
        },
        {
            "order_id": "685945",
            "location_id": "loc14",
            "duration": 600
        },
        {
            "order_id": "692592",
            "location_id": "loc15",
            "duration": 600
        },
        {
            "order_id": "678545",
            "location_id": "loc17",
            "duration": 600
        },
        {
            "order_id": "692829",
            "location_id": "loc18",
            "duration": 600
        },
        {
            "order_id": "695124",
            "location_id": "loc19",
            "appointments": [
                {
                    "appointment_start": "2017-08-24T10:15:00-04:00",
                    "appointment_end": "2017-08-24T10:25:00-04:00"
                }
            ],
            "duration": 600
        },
        {
            "order_id": "693192",
            "location_id": "loc21",
            "duration": 600
        },
        {
            "order_id": "649953",
            "location_id": "loc22",
            "duration": 600
        },
        {
            "order_id": "694498",
            "location_id": "loc23",
            "duration": 600
        },
        {
            "order_id": "693854",
            "location_id": "loc24",
            "duration": 600
        },
        {
            "order_id": "688899",
            "location_id": "loc25",
            "duration": 600
        },
        {
            "order_id": "617086",
            "location_id": "loc26",
            "duration": 600
        },
        {
            "order_id": "340637",
            "location_id": "loc27",
            "duration": 600
        },
        {
            "order_id": "693098",
            "location_id": "loc28",
            "appointments": [
                {
                    "appointment_start": "2017-08-24T13:15:00-04:00",
                    "appointment_end": "2017-08-24T13:25:00-04:00"
                }
            ],
            "duration": 600
        },
        {
            "order_id": "683931",
            "location_id": "loc29",
            "duration": 600
        },
        {
            "order_id": "685382",
            "location_id": "loc30",
            "duration": 600
        },
        {
            "order_id": "691449",
            "location_id": "loc31",
            "duration": 600
        },
        {
            "order_id": "509217",
            "location_id": "loc32",
            "duration": 600
        },
        {
            "order_id": "691287",
            "location_id": "loc33",
            "duration": 600
        },
        {
            "order_id": "640723",
            "location_id": "loc34",
            "duration": 600
        },
        {
            "order_id": "665537",
            "location_id": "loc35",
            "duration": 600
        },
        {
            "order_id": "693858",
            "location_id": "loc36",
            "duration": 600
        },
        {
            "order_id": "392888",
            "location_id": "loc37",
            "duration": 600
        },
        {
            "order_id": "623404",
            "location_id": "loc38",
            "duration": 600
        },
        {
            "order_id": "695743",
            "location_id": "loc39",
            "duration": 600
        },
        {
            "order_id": "692431",
            "location_id": "loc40",
            "duration": 600
        }
    ],
    "locations": [
        {
            "location_id": "loc1",
            "longitude": -84.07639,
            "latitude": 33.3300399
        },
        {
            "location_id": "loc2",
            "longitude": -84.4153667,
            "latitude": 33.5179638
        },
        {
            "location_id": "loc3",
            "longitude": -84.52763,
            "latitude": 34.07687
        },
        {
            "location_id": "loc4",
            "longitude": -85.15883,
            "latitude": 33.73872
        },
        {
            "location_id": "loc5",
            "longitude": -84.1256499,
            "latitude": 34.02463
        },
        {
            "location_id": "loc6",
            "longitude": -84.30268,
            "latitude": 33.78583
        },
        {
            "location_id": "loc7",
            "longitude": -84.5738499,
            "latitude": 34.07687
        },
        {
            "location_id": "loc8",
            "longitude": -83.7661399,
            "latitude": 33.98557
        },
        {
            "location_id": "loc9",
            "longitude": -84.69128,
            "latitude": 34.02403
        },
        {
            "location_id": "loc11",
            "longitude": -84.26431,
            "latitude": 33.57832
        },
        {
            "location_id": "loc12",
            "longitude": -84.51451,
            "latitude": 33.56882
        },
        {
            "location_id": "loc13",
            "longitude": -84.30606,
            "latitude": 33.8200999
        },
        {
            "location_id": "loc14",
            "longitude": -84.02126,
            "latitude": 33.98078
        },
        {
            "location_id": "loc15",
            "longitude": -84.20871,
            "latitude": 33.98596
        },
        {
            "location_id": "loc16",
            "longitude": -83.789905,
            "latitude": 34.098671
        },
        {
            "location_id": "loc17",
            "longitude": -84.3739,
            "latitude": 33.68959
        },
        {
            "location_id": "loc18",
            "longitude": -84.08495,
            "latitude": 33.8965699
        },
        {
            "location_id": "loc19",
            "longitude": -84.5491,
            "latitude": 34.0078
        },
        {
            "location_id": "loc20",
            "longitude": -84.78468,
            "latitude": 33.44852
        },
        {
            "location_id": "loc21",
            "longitude": -84.7372199,
            "latitude": 33.45099
        },
        {
            "location_id": "loc22",
            "longitude": -84.44377,
            "latitude": 33.7084199
        },
        {
            "location_id": "loc23",
            "longitude": -84.37416,
            "latitude": 34.0286
        },
        {
            "location_id": "loc24",
            "longitude": -84.23121,
            "latitude": 33.82054
        },
        {
            "location_id": "loc25",
            "longitude": -84.21402,
            "latitude": 33.83828
        },
        {
            "location_id": "loc26",
            "longitude": -84.31995,
            "latitude": 34.05614
        },
        {
            "location_id": "loc27",
            "longitude": -84.6712,
            "latitude": 33.7435386
        },
        {
            "location_id": "loc28",
            "longitude": -84.8082699,
            "latitude": 33.99045
        },
        {
            "location_id": "loc29",
            "longitude": -84.7469,
            "latitude": 33.84614
        },
        {
            "location_id": "loc30",
            "longitude": -84.23972,
            "latitude": 33.68736
        },
        {
            "location_id": "loc31",
            "longitude": -84.3845599,
            "latitude": 33.7757999
        },
        {
            "location_id": "loc32",
            "longitude": -84.1556,
            "latitude": 34.19941
        },
        {
            "location_id": "loc33",
            "longitude": -84.35911,
            "latitude": 33.75112
        },
        {
            "location_id": "loc34",
            "longitude": -83.707189,
            "latitude": 33.9854531
        },
        {
            "location_id": "loc35",
            "longitude": -84.36567,
            "latitude": 33.52079
        },
        {
            "location_id": "loc36",
            "longitude": -84.2661811,
            "latitude": 34.104
        },
        {
            "location_id": "loc37",
            "longitude": -84.20234,
            "latitude": 33.88826
        },
        {
            "location_id": "loc38",
            "longitude": -84.32034,
            "latitude": 33.4439
        },
        {
            "location_id": "loc39",
            "longitude": -84.23654,
            "latitude": 33.96681
        },
        {
            "location_id": "loc40",
            "longitude": -83.81919,
            "latitude": 34.1162
        },
        {
            "location_id": "loc99",
            "longitude": -85.0148499,
            "latitude": 34.07697
        },
        {
            "location_id": "loc100",
            "longitude": -84.52097,
            "latitude": 33.9157
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "shift_id": "v1shift",
                    "start_location_id": "loc20",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "end_location_id": "loc20",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "shift_id": "v2shift",
                    "start_location_id": "loc99",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "end_location_id": "loc99",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle2"
        }
    ]
}

imgOriginal two vehicle solution with no scheduled appointments. With two vehicles, we are left with 12 orders that cannot be feasibly visited.

imgSolution with scheduled appointments met at the orders with black boxes around them. This results in a total of 14 unvisited orders vs. 12 unvisited in the case of 2 vehicles with no scheduled appointments. Also note the relative inefficiency of the pink route where stop 3 must be now added to this route since it is not possible for a single vehicle to satisfy both of the scheduled appointments.


Urgency — urgency

Description

This constraint encourages the solution to visit orders with higher urgency values earlier on in the planning period. An order’s urgency must be in the range 1-99 and should be viewed as a percentile. An urgency of 90 means that we want to visit this order in the first 10% of the planning period. If violation_increment is specified then additional penalty is assessed for each percentile outside of the desired range. So if the planning period is 10,000 seconds and an order has urgency 89, then we will penalize a solution that has us visiting this order after ((100-89)/100)*10,000 = 1100 seconds. In this case, the violation increment is in percentage points.

Example

{
    "constraints": [
        {
            "max_travel_time_seconds": 0,
            "constraint_name": "limit travel",
            "violation_increment": 1,
            "constraint_type": "travel_time",
            "penalty_per_violation": 1
        },
        {
            "constraint_name": "visit as many orders as possible",
            "violation_increment": 1,
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000
        },
        {
            "constraint_name": "visit urgent orders early",
            "violation_increment": 1,
            "constraint_type": "Urgency",
            "penalty_per_violation": 1000
        }
    ],
    "orders": [
        {
            "location_id": "loc1",
            "order_id": "688798",
            "duration": 600
        },
        {
            "location_id": "loc3",
            "order_id": "689105",
            "duration": 600,
            "urgency": 99
        },
        {
            "location_id": "loc5",
            "order_id": "692039",
            "duration": 1800
        },
        {
            "location_id": "loc6",
            "order_id": "583368",
            "duration": 600
        },
        {
            "location_id": "loc7",
            "order_id": "677048",
            "duration": 600
        },
        {
            "location_id": "loc8",
            "order_id": "685086",
            "duration": 600
        },
        {
            "location_id": "loc9",
            "order_id": "690020",
            "duration": 600
        },
        {
            "location_id": "loc11",
            "order_id": "674660",
            "duration": 600
        },
        {
            "location_id": "loc13",
            "order_id": "413170",
            "duration": 600
        },
        {
            "location_id": "loc14",
            "order_id": "685945",
            "duration": 600
        },
        {
            "location_id": "loc15",
            "order_id": "692592",
            "duration": 600
        },
        {
            "location_id": "loc17",
            "order_id": "678545",
            "duration": 600,
            "urgency": 99
        },
        {
            "location_id": "loc18",
            "order_id": "692829",
            "duration": 600
        },
        {
            "location_id": "loc19",
            "order_id": "695124",
            "duration": 600,
            "urgency": 99
        },
        {
            "location_id": "loc21",
            "order_id": "693192",
            "duration": 600
        },
        {
            "location_id": "loc22",
            "order_id": "649953",
            "duration": 600
        },
        {
            "location_id": "loc23",
            "order_id": "694498",
            "duration": 600
        },
        {
            "location_id": "loc24",
            "order_id": "693854",
            "duration": 600
        },
        {
            "location_id": "loc25",
            "order_id": "688899",
            "duration": 600
        },
        {
            "location_id": "loc26",
            "order_id": "617086",
            "duration": 600
        },
        {
            "location_id": "loc27",
            "order_id": "340637",
            "duration": 600
        },
        {
            "location_id": "loc28",
            "order_id": "693098",
            "duration": 600
        },
        {
            "location_id": "loc29",
            "order_id": "683931",
            "duration": 600
        },
        {
            "location_id": "loc30",
            "order_id": "685382",
            "duration": 600
        },
        {
            "location_id": "loc31",
            "order_id": "691449",
            "duration": 600
        },
        {
            "location_id": "loc32",
            "order_id": "509217",
            "duration": 600
        },
        {
            "location_id": "loc33",
            "order_id": "691287",
            "duration": 600,
            "urgency": 99
        },
        {
            "location_id": "loc34",
            "order_id": "640723",
            "duration": 600
        },
        {
            "location_id": "loc35",
            "order_id": "665537",
            "duration": 600
        },
        {
            "location_id": "loc36",
            "order_id": "693858",
            "duration": 600
        },
        {
            "location_id": "loc37",
            "order_id": "392888",
            "duration": 600
        },
        {
            "location_id": "loc38",
            "order_id": "623404",
            "duration": 600
        },
        {
            "location_id": "loc39",
            "order_id": "695743",
            "duration": 600
        },
        {
            "location_id": "loc40",
            "order_id": "692431",
            "duration": 600
        }
    ],
    "locations": [
        {
            "location_id": "loc1",
            "longitude": -84.07639,
            "latitude": 33.3300399
        },
        {
            "location_id": "loc2",
            "longitude": -84.4153667,
            "latitude": 33.5179638
        },
        {
            "location_id": "loc3",
            "longitude": -84.52763,
            "latitude": 34.07687
        },
        {
            "location_id": "loc4",
            "longitude": -85.15883,
            "latitude": 33.73872
        },
        {
            "location_id": "loc5",
            "longitude": -84.1256499,
            "latitude": 34.02463
        },
        {
            "location_id": "loc6",
            "longitude": -84.30268,
            "latitude": 33.78583
        },
        {
            "location_id": "loc7",
            "longitude": -84.5738499,
            "latitude": 34.07687
        },
        {
            "location_id": "loc8",
            "longitude": -83.7661399,
            "latitude": 33.98557
        },
        {
            "location_id": "loc9",
            "longitude": -84.69128,
            "latitude": 34.02403
        },
        {
            "location_id": "loc11",
            "longitude": -84.26431,
            "latitude": 33.57832
        },
        {
            "location_id": "loc12",
            "longitude": -84.51451,
            "latitude": 33.56882
        },
        {
            "location_id": "loc13",
            "longitude": -84.30606,
            "latitude": 33.8200999
        },
        {
            "location_id": "loc14",
            "longitude": -84.02126,
            "latitude": 33.98078
        },
        {
            "location_id": "loc15",
            "longitude": -84.20871,
            "latitude": 33.98596
        },
        {
            "location_id": "loc16",
            "longitude": -83.789905,
            "latitude": 34.098671
        },
        {
            "location_id": "loc17",
            "longitude": -84.3739,
            "latitude": 33.68959
        },
        {
            "location_id": "loc18",
            "longitude": -84.08495,
            "latitude": 33.8965699
        },
        {
            "location_id": "loc19",
            "longitude": -84.5491,
            "latitude": 34.0078
        },
        {
            "location_id": "loc20",
            "longitude": -84.78468,
            "latitude": 33.44852
        },
        {
            "location_id": "loc21",
            "longitude": -84.7372199,
            "latitude": 33.45099
        },
        {
            "location_id": "loc22",
            "longitude": -84.44377,
            "latitude": 33.7084199
        },
        {
            "location_id": "loc23",
            "longitude": -84.37416,
            "latitude": 34.0286
        },
        {
            "location_id": "loc24",
            "longitude": -84.23121,
            "latitude": 33.82054
        },
        {
            "location_id": "loc25",
            "longitude": -84.21402,
            "latitude": 33.83828
        },
        {
            "location_id": "loc26",
            "longitude": -84.31995,
            "latitude": 34.05614
        },
        {
            "location_id": "loc27",
            "longitude": -84.6712,
            "latitude": 33.7435386
        },
        {
            "location_id": "loc28",
            "longitude": -84.8082699,
            "latitude": 33.99045
        },
        {
            "location_id": "loc29",
            "longitude": -84.7469,
            "latitude": 33.84614
        },
        {
            "location_id": "loc30",
            "longitude": -84.23972,
            "latitude": 33.68736
        },
        {
            "location_id": "loc31",
            "longitude": -84.3845599,
            "latitude": 33.7757999
        },
        {
            "location_id": "loc32",
            "longitude": -84.1556,
            "latitude": 34.19941
        },
        {
            "location_id": "loc33",
            "longitude": -84.35911,
            "latitude": 33.75112
        },
        {
            "location_id": "loc34",
            "longitude": -83.707189,
            "latitude": 33.9854531
        },
        {
            "location_id": "loc35",
            "longitude": -84.36567,
            "latitude": 33.52079
        },
        {
            "location_id": "loc36",
            "longitude": -84.2661811,
            "latitude": 34.104
        },
        {
            "location_id": "loc37",
            "longitude": -84.20234,
            "latitude": 33.88826
        },
        {
            "location_id": "loc38",
            "longitude": -84.32034,
            "latitude": 33.4439
        },
        {
            "location_id": "loc39",
            "longitude": -84.23654,
            "latitude": 33.96681
        },
        {
            "location_id": "loc40",
            "longitude": -83.81919,
            "latitude": 34.1162
        },
        {
            "location_id": "loc99",
            "longitude": -85.0148499,
            "latitude": 34.07697
        },
        {
            "location_id": "loc100",
            "longitude": -84.52097,
            "latitude": 33.9157
        }
    ],
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "shifts": [
                {
                    "start_location_id": "loc20",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "shift_id": "v1shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc20",
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "shifts": [
                {
                    "start_location_id": "loc99",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "shift_id": "v2shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc99",
                    "shift_end": "2017-08-24T15:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "shifts": [
                {
                    "start_location_id": "loc16",
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "shift_id": "v3shift",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "end_location_id": "loc16",
                    "shift_end": "2017-08-24T13:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "shifts": [
                {
                    "start_location_id": "loc100",
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "shift_id": "v4shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc100",
                    "shift_end": "2017-08-24T16:10:00-04:00"
                }
            ]
        }
    ]
}

imgOriginal 4 vehicle solution with no urgency enforced.

img We add an urgency of 99 to 4 orders, indicating that we want them to be visited in the first 1% of the available time in the planning period. These 4 orders now become one of the first 2 orders visited on the cyan route and orange route. This comes at an expense of increasing total travel time by about 90 minutes. Since it is not possible to visit all these orders in the first 1% of the planning period, we still incur penalty from this constraint. However, since the constraint in the example utilizes violation_increment, a lower total score of the solution is obtained when we visit these orders as early as possible even if we still violate the constraint.


Order Priority — order_priority

Description

Favor visiting high priority orders. If the priority p is greater than 1 and order with min_visits m is visited k times in the solution with k < m, then we assess a penalty amount of ( p – 1 ) * (m – k) . Thus, an order with a priority of 1 will not receive a penalty, and otherwise the higher the order’s priority the higher the penalty for not visiting at least min_visits times. No additional parameters are necessary for this constraint beyond the defaults as the priority information is part of each order object.

Example

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0,
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "constraint_name": "limit travel"
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible"
        },
        {
            "constraint_type": "Order_Priority",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "favor visiting high priority orders"
        }
    ],
    "orders": [
        {
            "duration": 600,
            "priority": 10,
            "order_id": "688798",
            "location_id": "loc1"
        },
        {
            "duration": 600,
            "order_id": "689105",
            "location_id": "loc3"
        },
        {
            "duration": 1800,
            "priority": 10,
            "order_id": "692039",
            "location_id": "loc5"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "583368",
            "location_id": "loc6"
        },
        {
            "duration": 600,
            "order_id": "677048",
            "location_id": "loc7"
        },
        {
            "duration": 600,
            "order_id": "685086",
            "location_id": "loc8"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "690020",
            "location_id": "loc9"
        },
        {
            "duration": 600,
            "order_id": "674660",
            "location_id": "loc11"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "413170",
            "location_id": "loc13"
        },
        {
            "duration": 600,
            "order_id": "685945",
            "location_id": "loc14"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "692592",
            "location_id": "loc15"
        },
        {
            "duration": 600,
            "order_id": "678545",
            "location_id": "loc17"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "692829",
            "location_id": "loc18"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "695124",
            "location_id": "loc19"
        },
        {
            "duration": 600,
            "order_id": "693192",
            "location_id": "loc21"
        },
        {
            "duration": 600,
            "order_id": "649953",
            "location_id": "loc22"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "694498",
            "location_id": "loc23"
        },
        {
            "duration": 600,
            "order_id": "693854",
            "location_id": "loc24"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "688899",
            "location_id": "loc25"
        },
        {
            "duration": 600,
            "order_id": "617086",
            "location_id": "loc26"
        },
        {
            "duration": 600,
            "order_id": "340637",
            "location_id": "loc27"
        },
        {
            "duration": 600,
            "order_id": "693098",
            "location_id": "loc28"
        },
        {
            "duration": 600,
            "order_id": "683931",
            "location_id": "loc29"
        },
        {
            "duration": 600,
            "order_id": "685382",
            "location_id": "loc30"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "691449",
            "location_id": "loc31"
        },
        {
            "duration": 600,
            "order_id": "509217",
            "location_id": "loc32"
        },
        {
            "duration": 600,
            "order_id": "691287",
            "location_id": "loc33"
        },
        {
            "duration": 600,
            "order_id": "640723",
            "location_id": "loc34"
        },
        {
            "duration": 600,
            "order_id": "665537",
            "location_id": "loc35"
        },
        {
            "duration": 600,
            "order_id": "693858",
            "location_id": "loc36"
        },
        {
            "duration": 600,
            "priority": 10,
            "order_id": "392888",
            "location_id": "loc37"
        },
        {
            "duration": 600,
            "order_id": "623404",
            "location_id": "loc38"
        },
        {
            "duration": 600,
            "order_id": "695743",
            "location_id": "loc39"
        },
        {
            "duration": 600,
            "order_id": "692431",
            "location_id": "loc40"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "start_location_id": "loc20",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "end_location_id": "loc20",
                    "shift_id": "v1shift",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "start_location_id": "loc99",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "end_location_id": "loc99",
                    "shift_id": "v2shift",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T15:10:00-04:00"
                }
            ],
            "vehicle_id": "Vehicle2"
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "location_id": "loc1",
            "latitude": 33.3300399
        },
        {
            "longitude": -84.4153667,
            "location_id": "loc2",
            "latitude": 33.5179638
        },
        {
            "longitude": -84.52763,
            "location_id": "loc3",
            "latitude": 34.07687
        },
        {
            "longitude": -85.15883,
            "location_id": "loc4",
            "latitude": 33.73872
        },
        {
            "longitude": -84.1256499,
            "location_id": "loc5",
            "latitude": 34.02463
        },
        {
            "longitude": -84.30268,
            "location_id": "loc6",
            "latitude": 33.78583
        },
        {
            "longitude": -84.5738499,
            "location_id": "loc7",
            "latitude": 34.07687
        },
        {
            "longitude": -83.7661399,
            "location_id": "loc8",
            "latitude": 33.98557
        },
        {
            "longitude": -84.69128,
            "location_id": "loc9",
            "latitude": 34.02403
        },
        {
            "longitude": -84.26431,
            "location_id": "loc11",
            "latitude": 33.57832
        },
        {
            "longitude": -84.51451,
            "location_id": "loc12",
            "latitude": 33.56882
        },
        {
            "longitude": -84.30606,
            "location_id": "loc13",
            "latitude": 33.8200999
        },
        {
            "longitude": -84.02126,
            "location_id": "loc14",
            "latitude": 33.98078
        },
        {
            "longitude": -84.20871,
            "location_id": "loc15",
            "latitude": 33.98596
        },
        {
            "longitude": -83.789905,
            "location_id": "loc16",
            "latitude": 34.098671
        },
        {
            "longitude": -84.3739,
            "location_id": "loc17",
            "latitude": 33.68959
        },
        {
            "longitude": -84.08495,
            "location_id": "loc18",
            "latitude": 33.8965699
        },
        {
            "longitude": -84.5491,
            "location_id": "loc19",
            "latitude": 34.0078
        },
        {
            "longitude": -84.78468,
            "location_id": "loc20",
            "latitude": 33.44852
        },
        {
            "longitude": -84.7372199,
            "location_id": "loc21",
            "latitude": 33.45099
        },
        {
            "longitude": -84.44377,
            "location_id": "loc22",
            "latitude": 33.7084199
        },
        {
            "longitude": -84.37416,
            "location_id": "loc23",
            "latitude": 34.0286
        },
        {
            "longitude": -84.23121,
            "location_id": "loc24",
            "latitude": 33.82054
        },
        {
            "longitude": -84.21402,
            "location_id": "loc25",
            "latitude": 33.83828
        },
        {
            "longitude": -84.31995,
            "location_id": "loc26",
            "latitude": 34.05614
        },
        {
            "longitude": -84.6712,
            "location_id": "loc27",
            "latitude": 33.7435386
        },
        {
            "longitude": -84.8082699,
            "location_id": "loc28",
            "latitude": 33.99045
        },
        {
            "longitude": -84.7469,
            "location_id": "loc29",
            "latitude": 33.84614
        },
        {
            "longitude": -84.23972,
            "location_id": "loc30",
            "latitude": 33.68736
        },
        {
            "longitude": -84.3845599,
            "location_id": "loc31",
            "latitude": 33.7757999
        },
        {
            "longitude": -84.1556,
            "location_id": "loc32",
            "latitude": 34.19941
        },
        {
            "longitude": -84.35911,
            "location_id": "loc33",
            "latitude": 33.75112
        },
        {
            "longitude": -83.707189,
            "location_id": "loc34",
            "latitude": 33.9854531
        },
        {
            "longitude": -84.36567,
            "location_id": "loc35",
            "latitude": 33.52079
        },
        {
            "longitude": -84.2661811,
            "location_id": "loc36",
            "latitude": 34.104
        },
        {
            "longitude": -84.20234,
            "location_id": "loc37",
            "latitude": 33.88826
        },
        {
            "longitude": -84.32034,
            "location_id": "loc38",
            "latitude": 33.4439
        },
        {
            "longitude": -84.23654,
            "location_id": "loc39",
            "latitude": 33.96681
        },
        {
            "longitude": -83.81919,
            "location_id": "loc40",
            "latitude": 34.1162
        },
        {
            "longitude": -85.0148499,
            "location_id": "loc99",
            "latitude": 34.07697
        },
        {
            "longitude": -84.52097,
            "location_id": "loc100",
            "latitude": 33.9157
        }
    ]
}

img

Original solution with 2 vehicles and no order_priority constraint.

img

In the original 2 vehicle solution, we have 12 unvisited orders. We now add the order_priority constraint and specify a priority for many orders. In the resulting solution we have 17 unvisited orders but we visit all of the orders that have a priority greater than 1. In other words, we visit fewer customers, but hit the important ones. Order 688798 at the bottom is boxed in black – we do not visit this order in the original solution since it is so far out of the way. However, the penalty for missing this priority 10 order is now high enough that a lower overall score is obtained by adding this order to the solution.


Span — span

Description

The span constraint allows us to try and ensure that the service at all orders in a provided set is completed within a certain time limit. The constraint provides an array of order_id’s and a max_seconds value and the constraint is violated if the difference between the latest departure and earliest service start exceeds max_seconds.

Example

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "constraint_name": "limit travel",
            "max_travel_time_seconds": 0
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible"
        },
        {
            "constraint_type": "Span",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "order_ids": [
                "691449",
                "583368",
                "413170",
                "693854",
                "688899",
                "691287",
                "649953",
                "678545",
                "392888"
            ],
            "max_seconds": 7200,
            "constraint_name": "visit central orders within 7200 seconds"
        }
    ],
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "shifts": [
                {
                    "end_location_id": "loc20",
                    "shift_id": "v1shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "shifts": [
                {
                    "end_location_id": "loc99",
                    "shift_id": "v2shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "start_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T15:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "shifts": [
                {
                    "end_location_id": "loc16",
                    "shift_id": "v3shift",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "start_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T13:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "shifts": [
                {
                    "end_location_id": "loc100",
                    "shift_id": "v4shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "start_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T16:10:00-04:00"
                }
            ]
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "location_id": "loc1",
            "duration": 600
        },
        {
            "order_id": "689105",
            "location_id": "loc3",
            "duration": 600
        },
        {
            "order_id": "692039",
            "location_id": "loc5",
            "duration": 1800
        },
        {
            "order_id": "583368",
            "location_id": "loc6",
            "duration": 600
        },
        {
            "order_id": "677048",
            "location_id": "loc7",
            "duration": 600
        },
        {
            "order_id": "685086",
            "location_id": "loc8",
            "duration": 600
        },
        {
            "order_id": "690020",
            "location_id": "loc9",
            "duration": 600
        },
        {
            "order_id": "674660",
            "location_id": "loc11",
            "duration": 600
        },
        {
            "order_id": "413170",
            "location_id": "loc13",
            "duration": 600
        },
        {
            "order_id": "685945",
            "location_id": "loc14",
            "duration": 600
        },
        {
            "order_id": "692592",
            "location_id": "loc15",
            "duration": 600
        },
        {
            "order_id": "678545",
            "location_id": "loc17",
            "duration": 600
        },
        {
            "order_id": "692829",
            "location_id": "loc18",
            "duration": 600
        },
        {
            "order_id": "695124",
            "location_id": "loc19",
            "duration": 600
        },
        {
            "order_id": "693192",
            "location_id": "loc21",
            "duration": 600
        },
        {
            "order_id": "649953",
            "location_id": "loc22",
            "duration": 600
        },
        {
            "order_id": "694498",
            "location_id": "loc23",
            "duration": 600
        },
        {
            "order_id": "693854",
            "location_id": "loc24",
            "duration": 600
        },
        {
            "order_id": "688899",
            "location_id": "loc25",
            "duration": 600
        },
        {
            "order_id": "617086",
            "location_id": "loc26",
            "duration": 600
        },
        {
            "order_id": "340637",
            "location_id": "loc27",
            "duration": 600
        },
        {
            "order_id": "693098",
            "location_id": "loc28",
            "duration": 600
        },
        {
            "order_id": "683931",
            "location_id": "loc29",
            "duration": 600
        },
        {
            "order_id": "685382",
            "location_id": "loc30",
            "duration": 600
        },
        {
            "order_id": "691449",
            "location_id": "loc31",
            "duration": 600
        },
        {
            "order_id": "509217",
            "location_id": "loc32",
            "duration": 600
        },
        {
            "order_id": "691287",
            "location_id": "loc33",
            "duration": 600
        },
        {
            "order_id": "640723",
            "location_id": "loc34",
            "duration": 600
        },
        {
            "order_id": "665537",
            "location_id": "loc35",
            "duration": 600
        },
        {
            "order_id": "693858",
            "location_id": "loc36",
            "duration": 600
        },
        {
            "order_id": "392888",
            "location_id": "loc37",
            "duration": 600
        },
        {
            "order_id": "623404",
            "location_id": "loc38",
            "duration": 600
        },
        {
            "order_id": "695743",
            "location_id": "loc39",
            "duration": 600
        },
        {
            "order_id": "692431",
            "location_id": "loc40",
            "duration": 600
        }
    ]
}

img

Solution before adding the Span constraint.

img

In this example, we force a set of 9 orders in the center of Atlanta (inside black region) to all be visited around the same time – the time between the earliest arrival and the latest departure must be <= 120 minutes. These orders are visited by two routes (cyan and purple), the earliest arrival being at and the cyan route in particular becomes quite inefficient due to this constraint. Overall travel time increases by about 30 minutes over the case where we don’t have this constraint.


Match Attributes — match_attributes

Description

Matches the attributes of an order with the attributes of the vehicle servicing the order. This can be used to enforce “skill matching” type constraints. Each order can be given a set of attributes. If any one of these attributes is not present in the attributes of the vehicle that services this order, then a penalty is assessed. The violation_increment is in terms of the percentage points of the attributes matched at an order. For example, if an order has 5 attributes and 3 are matched by the vehicle that services it, then 60% of the attributes are matched. A violation increment of 10 would mean that this scenario would incur a penalty of 4 times the original penalty amount since 40% of the attributes are unmatched and 40/10 =4.

If some attributes are more important than others when assigning vehicles to orders, then the constraint can be used to assign different penalties at the attribute level. This is illustrated in the second example below.

Example

{
    "constraints": [
        {
            "constraint_name": "limit travel",
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0,
            "violation_increment": 1,
            "penalty_per_violation": 1
        },
        {
            "constraint_name": "visit as many orders as possible",
            "constraint_type": "visit_range",
            "violation_increment": 1,
            "penalty_per_violation": 10000
        },
        {
            "constraint_name": "Spanish language matching",
            "constraint_type": "Match_Attributes",
            "penalty_per_violation": 100000
        }
    ],
    "orders": [
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc1",
            "order_id": "688798",
            "duration": 600
        },
        {
            "location_id": "loc3",
            "order_id": "689105",
            "duration": 600
        },
        {
            "location_id": "loc5",
            "order_id": "692039",
            "duration": 1800
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc6",
            "order_id": "583368",
            "duration": 600
        },
        {
            "location_id": "loc7",
            "order_id": "677048",
            "duration": 600
        },
        {
            "location_id": "loc8",
            "order_id": "685086",
            "duration": 600
        },
        {
            "location_id": "loc9",
            "order_id": "690020",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc11",
            "order_id": "674660",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc13",
            "order_id": "413170",
            "duration": 600
        },
        {
            "location_id": "loc14",
            "order_id": "685945",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc15",
            "order_id": "692592",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc17",
            "order_id": "678545",
            "duration": 600
        },
        {
            "location_id": "loc18",
            "order_id": "692829",
            "duration": 600
        },
        {
            "location_id": "loc19",
            "order_id": "695124",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc21",
            "order_id": "693192",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc22",
            "order_id": "649953",
            "duration": 600
        },
        {
            "location_id": "loc23",
            "order_id": "694498",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc24",
            "order_id": "693854",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc25",
            "order_id": "688899",
            "duration": 600
        },
        {
            "location_id": "loc26",
            "order_id": "617086",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc27",
            "order_id": "340637",
            "duration": 600
        },
        {
            "attributes": [
                "speaks Spanish"
            ],
            "location_id": "loc28",
            "order_id": "693098",
            "duration": 600
        },
        {
            "location_id": "loc29",
            "order_id": "683931",
            "duration": 600
        },
        {
            "location_id": "loc30",
            "order_id": "685382",
            "duration": 600
        },
        {
            "location_id": "loc31",
            "order_id": "691449",
            "duration": 600
        },
        {
            "location_id": "loc32",
            "order_id": "509217",
            "duration": 600
        },
        {
            "location_id": "loc33",
            "order_id": "691287",
            "duration": 600
        },
        {
            "location_id": "loc34",
            "order_id": "640723",
            "duration": 600
        },
        {
            "location_id": "loc35",
            "order_id": "665537",
            "duration": 600
        },
        {
            "location_id": "loc36",
            "order_id": "693858",
            "duration": 600
        },
        {
            "location_id": "loc37",
            "order_id": "392888",
            "duration": 600
        },
        {
            "location_id": "loc38",
            "order_id": "623404",
            "duration": 600
        },
        {
            "location_id": "loc39",
            "order_id": "695743",
            "duration": 600
        },
        {
            "location_id": "loc40",
            "order_id": "692431",
            "duration": 600
        }
    ],
    "vehicles": [
        {
            "attributes": [
                "speaks Spanish"
            ],
            "shifts": [
                {
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "shift_id": "v1shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc20"
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "shift_id": "v2shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "start_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc99"
                }
            ],
            "vehicle_id": "Vehicle2"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T13:10:00-04:00",
                    "shift_id": "v3shift",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "start_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "end_location_id": "loc16"
                }
            ],
            "vehicle_id": "Vehicle3"
        },
        {
            "attributes": [
                "speaks Russian",
                "speaks Spanish"
            ],
            "shifts": [
                {
                    "shift_end": "2017-08-24T16:10:00-04:00",
                    "shift_id": "v4shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "start_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "end_location_id": "loc100"
                }
            ],
            "vehicle_id": "Vehicle4"
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ]
}

imgSolution to original problem with no Match Attributes constraint.

imgVehicle 1 (blue route) is assigned the attribute “speaks Spanish” while Vehicle 4 (red route) has the attributes “speaks Russian” and “speaks Spanish”. Various order are now assigned these attributes and we see that the blue route (vehicle 1) and red route (vehicle 2) now cover a much larger geographical area since the Match_Attributes constraints has a high penalty, effectively forbidding any vehicle from visiting these orders unless they have the correct attributes.

Example: Matching Drivers to Orders

In this example, we have a more nuanced approach towards the attribute matching. Our vehicles now have a variety of attributes: paint, drywall, gutters, Charles, and Gavin. The skill (paint, drywall, or gutter) is enforced to match with a very high penalty. In fact, the penalty for matching these attributes is higher than visit_range so that the optimization will only visit an order if the skill is matched – visiting an order with inadequate skills incurs a higher penalty than missing an order to enforce this behavior. Additional Match_Attributes constraints enforce a “soft matching” with the preferred driver, either Gavin or Charles. These assignments are violated due to the lower penalty.

{
    "constraints": [
        {
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "constraint_name": "limit travel",
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0
        },
        {
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible",
            "constraint_type": "visit_range"
        },
        {
            "constraint_name": "Charles desired - penalty 1000",
            "penalty_per_violation": 1000,
            "attributes": [
                "Charles"
            ],
            "constraint_type": "Match_Attributes"
        },
        {
            "constraint_name": "Match paint, drywall, gutters - penalty 100000 so better to not service than mismatch attributes",
            "penalty_per_violation": 100000,
            "attributes": [
                "paint",
                "drywall",
                "gutters"
            ],
            "constraint_type": "Match_Attributes"
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "location_id": "loc1",
            "latitude": 33.3300399
        },
        {
            "longitude": -84.4153667,
            "location_id": "loc2",
            "latitude": 33.5179638
        },
        {
            "longitude": -84.52763,
            "location_id": "loc3",
            "latitude": 34.07687
        },
        {
            "longitude": -85.15883,
            "location_id": "loc4",
            "latitude": 33.73872
        },
        {
            "longitude": -84.1256499,
            "location_id": "loc5",
            "latitude": 34.02463
        },
        {
            "longitude": -84.30268,
            "location_id": "loc6",
            "latitude": 33.78583
        },
        {
            "longitude": -84.5738499,
            "location_id": "loc7",
            "latitude": 34.07687
        },
        {
            "longitude": -83.7661399,
            "location_id": "loc8",
            "latitude": 33.98557
        },
        {
            "longitude": -84.69128,
            "location_id": "loc9",
            "latitude": 34.02403
        },
        {
            "longitude": -84.26431,
            "location_id": "loc11",
            "latitude": 33.57832
        },
        {
            "longitude": -84.51451,
            "location_id": "loc12",
            "latitude": 33.56882
        },
        {
            "longitude": -84.30606,
            "location_id": "loc13",
            "latitude": 33.8200999
        },
        {
            "longitude": -84.02126,
            "location_id": "loc14",
            "latitude": 33.98078
        },
        {
            "longitude": -84.20871,
            "location_id": "loc15",
            "latitude": 33.98596
        },
        {
            "longitude": -83.789905,
            "location_id": "loc16",
            "latitude": 34.098671
        },
        {
            "longitude": -84.3739,
            "location_id": "loc17",
            "latitude": 33.68959
        },
        {
            "longitude": -84.08495,
            "location_id": "loc18",
            "latitude": 33.8965699
        },
        {
            "longitude": -84.5491,
            "location_id": "loc19",
            "latitude": 34.0078
        },
        {
            "longitude": -84.78468,
            "location_id": "loc20",
            "latitude": 33.44852
        },
        {
            "longitude": -84.7372199,
            "location_id": "loc21",
            "latitude": 33.45099
        },
        {
            "longitude": -84.44377,
            "location_id": "loc22",
            "latitude": 33.7084199
        },
        {
            "longitude": -84.37416,
            "location_id": "loc23",
            "latitude": 34.0286
        },
        {
            "longitude": -84.23121,
            "location_id": "loc24",
            "latitude": 33.82054
        },
        {
            "longitude": -84.21402,
            "location_id": "loc25",
            "latitude": 33.83828
        },
        {
            "longitude": -84.31995,
            "location_id": "loc26",
            "latitude": 34.05614
        },
        {
            "longitude": -84.6712,
            "location_id": "loc27",
            "latitude": 33.7435386
        },
        {
            "longitude": -84.8082699,
            "location_id": "loc28",
            "latitude": 33.99045
        },
        {
            "longitude": -84.7469,
            "location_id": "loc29",
            "latitude": 33.84614
        },
        {
            "longitude": -84.23972,
            "location_id": "loc30",
            "latitude": 33.68736
        },
        {
            "longitude": -84.3845599,
            "location_id": "loc31",
            "latitude": 33.7757999
        },
        {
            "longitude": -84.1556,
            "location_id": "loc32",
            "latitude": 34.19941
        },
        {
            "longitude": -84.35911,
            "location_id": "loc33",
            "latitude": 33.75112
        },
        {
            "longitude": -83.707189,
            "location_id": "loc34",
            "latitude": 33.9854531
        },
        {
            "longitude": -84.36567,
            "location_id": "loc35",
            "latitude": 33.52079
        },
        {
            "longitude": -84.2661811,
            "location_id": "loc36",
            "latitude": 34.104
        },
        {
            "longitude": -84.20234,
            "location_id": "loc37",
            "latitude": 33.88826
        },
        {
            "longitude": -84.32034,
            "location_id": "loc38",
            "latitude": 33.4439
        },
        {
            "longitude": -84.23654,
            "location_id": "loc39",
            "latitude": 33.96681
        },
        {
            "longitude": -83.81919,
            "location_id": "loc40",
            "latitude": 34.1162
        },
        {
            "longitude": -85.0148499,
            "location_id": "loc99",
            "latitude": 34.07697
        },
        {
            "longitude": -84.52097,
            "location_id": "loc100",
            "latitude": 33.9157
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc1"
        },
        {
            "order_id": "689105",
            "attributes": [
                "drywall",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc3"
        },
        {
            "order_id": "692039",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc5"
        },
        {
            "order_id": "583368",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc6"
        },
        {
            "order_id": "677048",
            "attributes": [
                "paint",
                "drywall",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc7"
        },
        {
            "order_id": "685086",
            "attributes": [
                "paint",
                "drywall",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc8"
        },
        {
            "order_id": "690020",
            "attributes": [
                "paint",
                "drywall",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc9"
        },
        {
            "order_id": "674660",
            "attributes": [
                "paint",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc11"
        },
        {
            "order_id": "413170",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc13"
        },
        {
            "order_id": "685945",
            "attributes": [
                "paint",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc14"
        },
        {
            "order_id": "692592",
            "attributes": [
                "drywall",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc15"
        },
        {
            "order_id": "678545",
            "attributes": [
                "paint",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc17"
        },
        {
            "order_id": "692829",
            "attributes": [
                "drywall"
            ],
            "duration": 2700,
            "location_id": "loc18"
        },
        {
            "order_id": "695124",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc19"
        },
        {
            "order_id": "649953",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc22"
        },
        {
            "order_id": "694498",
            "duration": 2700,
            "location_id": "loc23"
        },
        {
            "order_id": "693854",
            "attributes": [
                "paint",
                "drywall"
            ],
            "duration": 2700,
            "location_id": "loc24"
        },
        {
            "order_id": "688899",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc25"
        },
        {
            "order_id": "617086",
            "attributes": [
                "paint",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc26"
        },
        {
            "order_id": "340637",
            "attributes": [
                "drywall",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc27"
        },
        {
            "order_id": "693098",
            "attributes": [
                "drywall",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc28"
        },
        {
            "order_id": "509217",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc32"
        },
        {
            "order_id": "691287",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc33"
        },
        {
            "order_id": "640723",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc34"
        },
        {
            "order_id": "665537",
            "attributes": [
                "drywall"
            ],
            "duration": 2700,
            "location_id": "loc35"
        },
        {
            "order_id": "693858",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc36"
        },
        {
            "order_id": "392888",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc37"
        },
        {
            "order_id": "623404",
            "attributes": [
                "gutters"
            ],
            "duration": 2700,
            "location_id": "loc38"
        },
        {
            "order_id": "695743",
            "attributes": [
                "drywall",
                "Charles"
            ],
            "duration": 2700,
            "location_id": "loc39"
        },
        {
            "order_id": "692431",
            "attributes": [
                "paint",
                "Gavin"
            ],
            "duration": 2700,
            "location_id": "loc40"
        }
    ],
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "attributes": [
                "paint",
                "drywall",
                "Gavin"
            ],
            "shifts": [
                {
                    "shift_end": "2019-03-06T18:00:00-04:00",
                    "shift_start": "2019-03-06T08:30:00-04:00",
                    "shift_id": "v1shift",
                    "end_location_id": "loc2",
                    "start_location_id": "loc2"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "attributes": [
                "paint",
                "drywall",
                "Charles"
            ],
            "shifts": [
                {
                    "shift_end": "2019-03-06T18:00:00-04:00",
                    "shift_start": "2019-03-06T08:30:00-04:00",
                    "shift_id": "v2shift",
                    "end_location_id": "loc6",
                    "start_location_id": "loc6"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "attributes": [
                "paint"
            ],
            "shifts": [
                {
                    "shift_end": "2019-03-06T18:00:00-04:00",
                    "shift_start": "2019-03-06T08:30:00-04:00",
                    "shift_id": "v3shift",
                    "end_location_id": "loc6",
                    "start_location_id": "loc6"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "attributes": [
                "gutters"
            ],
            "shifts": [
                {
                    "shift_end": "2019-03-06T18:00:00-04:00",
                    "shift_start": "2019-03-06T08:30:00-04:00",
                    "shift_id": "v4shift",
                    "end_location_id": "loc11",
                    "start_location_id": "loc11"
                }
            ]
        }
    ]
}

imgIn this example, the two unserved orders have the attribute “gutter”. The only route with the “gutter” attribute is the light blue route which has less than a minute of extra time and can thus not visit any more orders. The pink route has 2.5 hours of slack time, but since the vehicle does not have the “gutter” attribute, the two unserved “gutter” orders are not visited by this vehicle.


Avoid Attributes — avoid_attributes

Description

Prevent orders from being assigned to vehicles with attributes that are “undesirable” for some orders. The attributes_to_avoid are specified at the order level, and then vehicle attributes are compared against these values when evaluating the constraint. Thus there are no additional constraint parameters beyond the default. Violation increment has no impact on this constraint.

Example

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "max_travel_time_seconds": 0,
            "constraint_name": "limit travel"
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible"
        },
        {
            "constraint_type": "Avoid_Attributes",
            "penalty_per_violation": 100000,
            "constraint_name": "No loud vehicles"
        }
    ],
    "vehicles": [
        {
            "attributes": [
                "Loud vehicle"
            ],
            "shifts": [
                {
                    "shift_end": "2017-08-24T17:10:00-04:00",
                    "shift_id": "v1shift",
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc20",
                    "end_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle1"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T15:10:00-04:00",
                    "shift_id": "v2shift",
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc99",
                    "end_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle2"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T13:10:00-04:00",
                    "shift_id": "v3shift",
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "start_location_id": "loc16",
                    "end_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle3"
        },
        {
            "shifts": [
                {
                    "shift_end": "2017-08-24T16:10:00-04:00",
                    "shift_id": "v4shift",
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "start_location_id": "loc100",
                    "end_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ]
                }
            ],
            "vehicle_id": "Vehicle4"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "duration": 600,
            "location_id": "loc1",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "689105",
            "duration": 600,
            "location_id": "loc3"
        },
        {
            "order_id": "692039",
            "duration": 1800,
            "location_id": "loc5"
        },
        {
            "order_id": "583368",
            "duration": 600,
            "location_id": "loc6",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "677048",
            "duration": 600,
            "location_id": "loc7"
        },
        {
            "order_id": "685086",
            "duration": 600,
            "location_id": "loc8"
        },
        {
            "order_id": "690020",
            "duration": 600,
            "location_id": "loc9"
        },
        {
            "order_id": "674660",
            "duration": 600,
            "location_id": "loc11",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "413170",
            "duration": 600,
            "location_id": "loc13",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "685945",
            "duration": 600,
            "location_id": "loc14"
        },
        {
            "order_id": "692592",
            "duration": 600,
            "location_id": "loc15"
        },
        {
            "order_id": "678545",
            "duration": 600,
            "location_id": "loc17",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "692829",
            "duration": 600,
            "location_id": "loc18"
        },
        {
            "order_id": "695124",
            "duration": 600,
            "location_id": "loc19"
        },
        {
            "order_id": "693192",
            "duration": 600,
            "location_id": "loc21",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "649953",
            "duration": 600,
            "location_id": "loc22",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "694498",
            "duration": 600,
            "location_id": "loc23"
        },
        {
            "order_id": "693854",
            "duration": 600,
            "location_id": "loc24",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "688899",
            "duration": 600,
            "location_id": "loc25",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "617086",
            "duration": 600,
            "location_id": "loc26"
        },
        {
            "order_id": "340637",
            "duration": 600,
            "location_id": "loc27",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "693098",
            "duration": 600,
            "location_id": "loc28"
        },
        {
            "order_id": "683931",
            "duration": 600,
            "location_id": "loc29"
        },
        {
            "order_id": "685382",
            "duration": 600,
            "location_id": "loc30",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "691449",
            "duration": 600,
            "location_id": "loc31",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "509217",
            "duration": 600,
            "location_id": "loc32"
        },
        {
            "order_id": "691287",
            "duration": 600,
            "location_id": "loc33",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "640723",
            "duration": 600,
            "location_id": "loc34"
        },
        {
            "order_id": "665537",
            "duration": 600,
            "location_id": "loc35",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "693858",
            "duration": 600,
            "location_id": "loc36"
        },
        {
            "order_id": "392888",
            "duration": 600,
            "location_id": "loc37"
        },
        {
            "order_id": "623404",
            "duration": 600,
            "location_id": "loc38",
            "attributes_to_avoid": [
                "Loud vehicle"
            ]
        },
        {
            "order_id": "695743",
            "duration": 600,
            "location_id": "loc39"
        },
        {
            "order_id": "692431",
            "duration": 600,
            "location_id": "loc40"
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ]
}

imgSolution with no attempt to avoid incompatible attributes

imgWe assign the attribute “Loud vehicle” to Vehicle 1 represented by the pink route in the new solution. Many orders now request to avoid this attribute via the constraint, forcing the route for vehicle 1 to be very inefficient, traveling far from the start location to service orders. In particular, order 693192 boxed in red is right next to the start/end location for Vehicle 1. However, since this order has “Loud vehicle” in its attributes_to_avoid, Vehicle 1 does not visit it, forcing the green route to travel very far out of the way to hit this order.


Prevent Segment — prevent_segment

Description

There may be some cases where traversing a particular segment in a solution is undesirable (here a segment refers to the path between two stops, not particular streets or roads). Such segments can be avoided by using the Prevent_Segment constraint which takes in an array of pairs of location_ids and penalizes the solution if the segment connecting these pairs is present in the solution.

Example

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "constraint_name": "limit travel",
            "max_travel_time_seconds": 0
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible"
        },
        {
            "constraint_type": "Prevent_Segment",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "prevent obvious segments in and out of order 509217 (loc32)",
            "segments": [
                {
                    "start_location_id": "loc32",
                    "end_location_id": "loc36"
                },
                {
                    "start_location_id": "loc32",
                    "end_location_id": "loc26"
                },
                {
                    "start_location_id": "loc32",
                    "end_location_id": "loc23"
                },
                {
                    "start_location_id": "loc32",
                    "end_location_id": "loc15"
                },
                {
                    "start_location_id": "loc32",
                    "end_location_id": "loc39"
                },
                {
                    "end_location_id": "loc32",
                    "start_location_id": "loc36"
                },
                {
                    "end_location_id": "loc32",
                    "start_location_id": "loc26"
                },
                {
                    "end_location_id": "loc32",
                    "start_location_id": "loc23"
                },
                {
                    "end_location_id": "loc32",
                    "start_location_id": "loc15"
                },
                {
                    "end_location_id": "loc32",
                    "start_location_id": "loc39"
                }
            ]
        }
    ],
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "shifts": [
                {
                    "end_location_id": "loc20",
                    "shift_id": "v1shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "shifts": [
                {
                    "end_location_id": "loc99",
                    "shift_id": "v2shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "start_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T15:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "shifts": [
                {
                    "end_location_id": "loc16",
                    "shift_id": "v3shift",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "start_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T13:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "shifts": [
                {
                    "end_location_id": "loc100",
                    "shift_id": "v4shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "start_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T16:10:00-04:00"
                }
            ]
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "location_id": "loc1",
            "duration": 600
        },
        {
            "order_id": "689105",
            "location_id": "loc3",
            "duration": 600
        },
        {
            "order_id": "692039",
            "location_id": "loc5",
            "duration": 1800
        },
        {
            "order_id": "583368",
            "location_id": "loc6",
            "duration": 600
        },
        {
            "order_id": "677048",
            "location_id": "loc7",
            "duration": 600
        },
        {
            "order_id": "685086",
            "location_id": "loc8",
            "duration": 600
        },
        {
            "order_id": "690020",
            "location_id": "loc9",
            "duration": 600
        },
        {
            "order_id": "674660",
            "location_id": "loc11",
            "duration": 600
        },
        {
            "order_id": "413170",
            "location_id": "loc13",
            "duration": 600
        },
        {
            "order_id": "685945",
            "location_id": "loc14",
            "duration": 600
        },
        {
            "order_id": "692592",
            "location_id": "loc15",
            "duration": 600
        },
        {
            "order_id": "678545",
            "location_id": "loc17",
            "duration": 600
        },
        {
            "order_id": "692829",
            "location_id": "loc18",
            "duration": 600
        },
        {
            "order_id": "695124",
            "location_id": "loc19",
            "duration": 600
        },
        {
            "order_id": "693192",
            "location_id": "loc21",
            "duration": 600
        },
        {
            "order_id": "649953",
            "location_id": "loc22",
            "duration": 600
        },
        {
            "order_id": "694498",
            "location_id": "loc23",
            "duration": 600
        },
        {
            "order_id": "693854",
            "location_id": "loc24",
            "duration": 600
        },
        {
            "order_id": "688899",
            "location_id": "loc25",
            "duration": 600
        },
        {
            "order_id": "617086",
            "location_id": "loc26",
            "duration": 600
        },
        {
            "order_id": "340637",
            "location_id": "loc27",
            "duration": 600
        },
        {
            "order_id": "693098",
            "location_id": "loc28",
            "duration": 600
        },
        {
            "order_id": "683931",
            "location_id": "loc29",
            "duration": 600
        },
        {
            "order_id": "685382",
            "location_id": "loc30",
            "duration": 600
        },
        {
            "order_id": "691449",
            "location_id": "loc31",
            "duration": 600
        },
        {
            "order_id": "509217",
            "location_id": "loc32",
            "duration": 600
        },
        {
            "order_id": "691287",
            "location_id": "loc33",
            "duration": 600
        },
        {
            "order_id": "640723",
            "location_id": "loc34",
            "duration": 600
        },
        {
            "order_id": "665537",
            "location_id": "loc35",
            "duration": 600
        },
        {
            "order_id": "693858",
            "location_id": "loc36",
            "duration": 600
        },
        {
            "order_id": "392888",
            "location_id": "loc37",
            "duration": 600
        },
        {
            "order_id": "623404",
            "location_id": "loc38",
            "duration": 600
        },
        {
            "order_id": "695743",
            "location_id": "loc39",
            "duration": 600
        },
        {
            "order_id": "692431",
            "location_id": "loc40",
            "duration": 600
        }
    ]
}

imgOriginal 4 vehicle solution before any segments are penalized

img

The example introduces a Prevent_Segment constraint that penalizes links that start or end at location “loc36” (boxed in black) and the five other locations boxed in red. This results in the blue northeast route now traveling far out of the way since the Cumming order is effectively prevented from being serviced by the green route. This results in an overall increase in travel time, but all of these undesirable segments are avoided.


Vehicle Coverage — vehicle_coverage

Description

The vehicle_coverage constraint allows one to specify that a certain set of orders must be visited by a small number of vehicles. Typically, this would be to force a set of orders to all be covered by a single vehicle, but it is flexible enough to handle more complex use cases. The constraint must specify a set of orders and values for min_vehicles and max_vehicles, and if violation_increment is specified, then the units are expressed in the # of vehicles used to cover the set of orders. For example, if we have a penalty of 1000 with min_vehicles=1, max_vehicles=2, violation_increment=1 and 4 vehicles are used to service a set of orders, then a penalty of 3000 will be assessed: 1000 for using too many vehicles, and an additional penalty of 2000 for exceeding the limit by 2.

Example

{
    "constraints": [
        {
            "constraint_type": "travel_time",
            "penalty_per_violation": 1,
            "violation_increment": 1,
            "constraint_name": "limit travel",
            "max_travel_time_seconds": 0
        },
        {
            "constraint_type": "visit_range",
            "penalty_per_violation": 10000,
            "violation_increment": 1,
            "constraint_name": "visit as many orders as possible"
        },
        {
            "constraint_type": "Vehicle_Coverage",
            "penalty_per_violation": 100000,
            "violation_increment": 1,
            "order_ids": [
                "693192",
                "693098",
                "688798"
            ],
            "min_vehicles": 0,
            "max_vehicles": 1,
            "constraint_name": "cover 3 widely spread orders with single vehicle"
        }
    ],
    "vehicles": [
        {
            "vehicle_id": "Vehicle1",
            "shifts": [
                {
                    "end_location_id": "loc20",
                    "shift_id": "v1shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T08:05:00-04:00",
                    "start_location_id": "loc20",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T17:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle2",
            "shifts": [
                {
                    "end_location_id": "loc99",
                    "shift_id": "v2shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T10:05:00-04:00",
                    "start_location_id": "loc99",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T15:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle3",
            "shifts": [
                {
                    "end_location_id": "loc16",
                    "shift_id": "v3shift",
                    "break_end": [
                        "2017-08-24T10:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T07:05:00-04:00",
                    "start_location_id": "loc16",
                    "break_start": [
                        "2017-08-24T09:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T13:10:00-04:00"
                }
            ]
        },
        {
            "vehicle_id": "Vehicle4",
            "shifts": [
                {
                    "end_location_id": "loc100",
                    "shift_id": "v4shift",
                    "break_end": [
                        "2017-08-24T13:00:00-04:00"
                    ],
                    "shift_start": "2017-08-24T09:05:00-04:00",
                    "start_location_id": "loc100",
                    "break_start": [
                        "2017-08-24T12:00:00-04:00"
                    ],
                    "shift_end": "2017-08-24T16:10:00-04:00"
                }
            ]
        }
    ],
    "locations": [
        {
            "longitude": -84.07639,
            "latitude": 33.3300399,
            "location_id": "loc1"
        },
        {
            "longitude": -84.4153667,
            "latitude": 33.5179638,
            "location_id": "loc2"
        },
        {
            "longitude": -84.52763,
            "latitude": 34.07687,
            "location_id": "loc3"
        },
        {
            "longitude": -85.15883,
            "latitude": 33.73872,
            "location_id": "loc4"
        },
        {
            "longitude": -84.1256499,
            "latitude": 34.02463,
            "location_id": "loc5"
        },
        {
            "longitude": -84.30268,
            "latitude": 33.78583,
            "location_id": "loc6"
        },
        {
            "longitude": -84.5738499,
            "latitude": 34.07687,
            "location_id": "loc7"
        },
        {
            "longitude": -83.7661399,
            "latitude": 33.98557,
            "location_id": "loc8"
        },
        {
            "longitude": -84.69128,
            "latitude": 34.02403,
            "location_id": "loc9"
        },
        {
            "longitude": -84.26431,
            "latitude": 33.57832,
            "location_id": "loc11"
        },
        {
            "longitude": -84.51451,
            "latitude": 33.56882,
            "location_id": "loc12"
        },
        {
            "longitude": -84.30606,
            "latitude": 33.8200999,
            "location_id": "loc13"
        },
        {
            "longitude": -84.02126,
            "latitude": 33.98078,
            "location_id": "loc14"
        },
        {
            "longitude": -84.20871,
            "latitude": 33.98596,
            "location_id": "loc15"
        },
        {
            "longitude": -83.789905,
            "latitude": 34.098671,
            "location_id": "loc16"
        },
        {
            "longitude": -84.3739,
            "latitude": 33.68959,
            "location_id": "loc17"
        },
        {
            "longitude": -84.08495,
            "latitude": 33.8965699,
            "location_id": "loc18"
        },
        {
            "longitude": -84.5491,
            "latitude": 34.0078,
            "location_id": "loc19"
        },
        {
            "longitude": -84.78468,
            "latitude": 33.44852,
            "location_id": "loc20"
        },
        {
            "longitude": -84.7372199,
            "latitude": 33.45099,
            "location_id": "loc21"
        },
        {
            "longitude": -84.44377,
            "latitude": 33.7084199,
            "location_id": "loc22"
        },
        {
            "longitude": -84.37416,
            "latitude": 34.0286,
            "location_id": "loc23"
        },
        {
            "longitude": -84.23121,
            "latitude": 33.82054,
            "location_id": "loc24"
        },
        {
            "longitude": -84.21402,
            "latitude": 33.83828,
            "location_id": "loc25"
        },
        {
            "longitude": -84.31995,
            "latitude": 34.05614,
            "location_id": "loc26"
        },
        {
            "longitude": -84.6712,
            "latitude": 33.7435386,
            "location_id": "loc27"
        },
        {
            "longitude": -84.8082699,
            "latitude": 33.99045,
            "location_id": "loc28"
        },
        {
            "longitude": -84.7469,
            "latitude": 33.84614,
            "location_id": "loc29"
        },
        {
            "longitude": -84.23972,
            "latitude": 33.68736,
            "location_id": "loc30"
        },
        {
            "longitude": -84.3845599,
            "latitude": 33.7757999,
            "location_id": "loc31"
        },
        {
            "longitude": -84.1556,
            "latitude": 34.19941,
            "location_id": "loc32"
        },
        {
            "longitude": -84.35911,
            "latitude": 33.75112,
            "location_id": "loc33"
        },
        {
            "longitude": -83.707189,
            "latitude": 33.9854531,
            "location_id": "loc34"
        },
        {
            "longitude": -84.36567,
            "latitude": 33.52079,
            "location_id": "loc35"
        },
        {
            "longitude": -84.2661811,
            "latitude": 34.104,
            "location_id": "loc36"
        },
        {
            "longitude": -84.20234,
            "latitude": 33.88826,
            "location_id": "loc37"
        },
        {
            "longitude": -84.32034,
            "latitude": 33.4439,
            "location_id": "loc38"
        },
        {
            "longitude": -84.23654,
            "latitude": 33.96681,
            "location_id": "loc39"
        },
        {
            "longitude": -83.81919,
            "latitude": 34.1162,
            "location_id": "loc40"
        },
        {
            "longitude": -85.0148499,
            "latitude": 34.07697,
            "location_id": "loc99"
        },
        {
            "longitude": -84.52097,
            "latitude": 33.9157,
            "location_id": "loc100"
        }
    ],
    "orders": [
        {
            "order_id": "688798",
            "location_id": "loc1",
            "duration": 600
        },
        {
            "order_id": "689105",
            "location_id": "loc3",
            "duration": 600
        },
        {
            "order_id": "692039",
            "location_id": "loc5",
            "duration": 1800
        },
        {
            "order_id": "583368",
            "location_id": "loc6",
            "duration": 600
        },
        {
            "order_id": "677048",
            "location_id": "loc7",
            "duration": 600
        },
        {
            "order_id": "685086",
            "location_id": "loc8",
            "duration": 600
        },
        {
            "order_id": "690020",
            "location_id": "loc9",
            "duration": 600
        },
        {
            "order_id": "674660",
            "location_id": "loc11",
            "duration": 600
        },
        {
            "order_id": "413170",
            "location_id": "loc13",
            "duration": 600
        },
        {
            "order_id": "685945",
            "location_id": "loc14",
            "duration": 600
        },
        {
            "order_id": "692592",
            "location_id": "loc15",
            "duration": 600
        },
        {
            "order_id": "678545",
            "location_id": "loc17",
            "duration": 600
        },
        {
            "order_id": "692829",
            "location_id": "loc18",
            "duration": 600
        },
        {
            "order_id": "695124",
            "location_id": "loc19",
            "duration": 600
        },
        {
            "order_id": "693192",
            "location_id": "loc21",
            "duration": 600
        },
        {
            "order_id": "649953",
            "location_id": "loc22",
            "duration": 600
        },
        {
            "order_id": "694498",
            "location_id": "loc23",
            "duration": 600
        },
        {
            "order_id": "693854",
            "location_id": "loc24",
            "duration": 600
        },
        {
            "order_id": "688899",
            "location_id": "loc25",
            "duration": 600
        },
        {
            "order_id": "617086",
            "location_id": "loc26",
            "duration": 600
        },
        {
            "order_id": "340637",
            "location_id": "loc27",
            "duration": 600
        },
        {
            "order_id": "693098",
            "location_id": "loc28",
            "duration": 600
        },
        {
            "order_id": "683931",
            "location_id": "loc29",
            "duration": 600
        },
        {
            "order_id": "685382",
            "location_id": "loc30",
            "duration": 600
        },
        {
            "order_id": "691449",
            "location_id": "loc31",
            "duration": 600
        },
        {
            "order_id": "509217",
            "location_id": "loc32",
            "duration": 600
        },
        {
            "order_id": "691287",
            "location_id": "loc33",
            "duration": 600
        },
        {
            "order_id": "640723",
            "location_id": "loc34",
            "duration": 600
        },
        {
            "order_id": "665537",
            "location_id": "loc35",
            "duration": 600
        },
        {
            "order_id": "693858",
            "location_id": "loc36",
            "duration": 600
        },
        {
            "order_id": "392888",
            "location_id": "loc37",
            "duration": 600
        },
        {
            "order_id": "623404",
            "location_id": "loc38",
            "duration": 600
        },
        {
            "order_id": "695743",
            "location_id": "loc39",
            "duration": 600
        },
        {
            "order_id": "692431",
            "location_id": "loc40",
            "duration": 600
        }
    ]
}

img

Original solution with no vehicle_coverage constraint.

img

Three widely spread orders (boxed in black) are added to the vehicle_coverage constraint with min_vehicles equal to 1 and max_vehicles equal to 1. The result is that the route for Vehicle 1 now covers a huge territory and visits all three of these orders. Note that Vehicle 2 is now not used at all, leading to a very unbalanced solution in terms of the # stops per route as well as total travel time per route.

Journey Time — journey_time

Description

The journey_time constraint specifies the maximum number of seconds between when an item is picked up and dropped off, delivered, or the route ends. For example, if refrigerated goods can only be on a vehicle for one hour before beginning to spoil, then add the journey_time constraint with the max_journey_seconds parameter set to 3600. The associated violation_increment is in seconds.

Example

In the passenger pickup and dropoff example below, the journey_time, additional_journey_time, and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person".

{
    "constraints": [
        {
            "violation_increment": 1,
            "penalty_per_violation": 1,
            "constraint_name": "limit travel",
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0
        },
        {
            "violation_increment": 1,
            "penalty_per_violation": 10000000,
            "constraint_name": "visit as many orders as possible",
            "constraint_type": "visit_range"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 50000,
            "constraint_name": "honor time windows",
            "constraint_type": "Time_Window"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 10000,
            "constraint_name": "meet dropoff deadline",
            "constraint_type": "Dropoff_Deadline"
        },
        {
            "violation_increment": 600,
            "max_journey_seconds": 3600,
            "penalty_per_violation": 10000,
            "constraint_name": "Limit journey time to 60 minutes",
            "constraint_type": "Journey_Time"
        },
        {
            "violation_increment": 600,
            "max_additional_journey_seconds": 1800,
            "penalty_per_violation": 10000,
            "constraint_name": "Add no more than 30 minutes to any passenger journey",
            "constraint_type": "Additional_Journey_Time"
        }
    ],
    "items": [
        {
            "item_type": "person"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta Hyatt",
                    "shift_id": "v1 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta Hyatt",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Hyatt van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta W Hotel",
                    "shift_id": "v2 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta W Hotel",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger W Hotel van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "The Ritz-Carlton",
                    "shift_id": "v3 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "The Ritz-Carlton",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Ritz-Carlton van"
        }
    ],
    "locations": [
        {
            "location_id": "SunTrust Park",
            "latitude": 33.891142,
            "longitude": -84.467831
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "latitude": 33.874745,
            "longitude": -84.302473
        },
        {
            "location_id": "Tennis Tournament",
            "latitude": 33.801666,
            "longitude": -84.399962
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "latitude": 33.757539,
            "longitude": -84.396324
        },
        {
            "location_id": "Atlanta Convention Center",
            "latitude": 33.760325,
            "longitude": -84.388282
        },
        {
            "location_id": "Atlanta Hyatt",
            "latitude": 33.761439,
            "longitude": -84.38736
        },
        {
            "location_id": "Atlanta W Hotel",
            "latitude": 33.765263,
            "longitude": -84.389215
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "latitude": 33.6407392,
            "longitude": -84.4977388
        },
        {
            "location_id": "Crowne Plaza Midtown",
            "latitude": 33.7702594,
            "longitude": -84.3898117
        },
        {
            "location_id": "The Ritz-Carlton",
            "latitude": 33.6782242,
            "longitude": -84.42027
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "latitude": 33.7731954,
            "longitude": -84.3867607
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "latitude": 33.7855117,
            "longitude": -84.3948399
        },
        {
            "location_id": "W Midtown",
            "latitude": 33.7868451,
            "longitude": -84.3839391
        },
        {
            "location_id": "Embassy Suites Perimeter Center",
            "latitude": 33.9309739,
            "longitude": -84.3492964
        },
        {
            "location_id": "Hyatt Place Buckhead",
            "latitude": 33.8437201,
            "longitude": -84.3745431
        },
        {
            "location_id": "Hampton Inn Alpharetta",
            "latitude": 34.0414028,
            "longitude": -84.3225011
        },
        {
            "location_id": "Holiday Inn Express Kennesaw",
            "latitude": 34.0119044,
            "longitude": -84.5684887
        },
        {
            "location_id": "Radisson Hotel Marietta",
            "latitude": 33.9398352,
            "longitude": -84.5078069
        }
    ],
    "orders": [
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T09:25:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T10:30:00-04:00",
            "dropoff_location_id": "SunTrust Park",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Albert, Enrico, Robert at Hartsfield-Jackson Airport between 9-9:25am. Drop off at SunTrust Park by 10:30am"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T12:45:00-04:00",
                    "end_time_window": "2017-08-24T13:15:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T14:00:00-04:00",
            "dropoff_location_id": "Atlanta Convention Center",
            "pickup_item_quantities": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Bob and family (6 people) at Hartsfield-Jackson Airport between 12:45-1:00pm. Drop off at convention center by 2pm"
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:45:00-04:00",
                    "end_time_window": "2017-08-24T10:30:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Mark and Oscar at Hawks arena between 9:45-10:30am. Drop off at tennis tournament"
        },
        {
            "location_id": "Atlanta Hyatt",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T14:00:00-04:00",
                    "end_time_window": "2017-08-24T15:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "DeKalb Peachtree Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Doug between 2pm and 3pm at Atlanta Hyatt. Drop off at DeKalb airport"
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Edith and Maureen between 9am and 10am at Courtyard. Drop off at ATL airport"
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:30:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Cheech and Chong between 9am and 10am at Hotel Indigo. Drop off at ATL airport by 11:30am"
        },
        {
            "location_id": "The Ritz-Carlton",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Hansel and Gretel between 3pm and 4pm at Ritz Carlton. Drop off at Atlanta Hawks Arena"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T11:00:00-04:00",
                    "end_time_window": "2017-08-24T13:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T13:30:00-04:00",
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Heather between 11am and 1pm at DeKalb Peachtree Airport. Drop off at Atlanta Hawks Arena by 1:30pm"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Iris between 9 and 10 at DeKalb Peachtree Airport. Drop off at ATL Airport by 11am"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Chris and Mitch between 3 and 4pm at DeKalb Peachtree Airport. Drop off at ATL Airport by 5pm"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Williams family (3 people) between 3 and 4pm at Hartsfield-Jackson Airport. Drop off at tennis by 5pm"
        }
    ]
}

The solution for this example does not violate any constraints and utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the dropoff time of any passengers the passengers Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs that are inherent in complex routing problems, and punishing customers with a terrible experience can be avoided with the right mix of constraints.

Additional Journey Time — additional_journey_time

Description

In problems involving pickup and dropoff, there exist solutions where items remain on a vehicle longer than desired, but the solutions have smaller overall travel times. The additional_journey_time constraint controls consideration of these solutions. Additional journey time is the difference between an item’s journey_time and the travel time directly from the pickup location to the delivery/dropoff location. The associated violation_increment is in seconds.

Example

In the passenger pickup and dropoff example below, the journey_time, additional_journey_time, and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person".

{
    "constraints": [
        {
            "violation_increment": 1,
            "penalty_per_violation": 1,
            "constraint_name": "limit travel",
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0
        },
        {
            "violation_increment": 1,
            "penalty_per_violation": 10000000,
            "constraint_name": "visit as many orders as possible",
            "constraint_type": "visit_range"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 50000,
            "constraint_name": "honor time windows",
            "constraint_type": "Time_Window"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 10000,
            "constraint_name": "meet dropoff deadline",
            "constraint_type": "Dropoff_Deadline"
        },
        {
            "violation_increment": 600,
            "max_journey_seconds": 3600,
            "penalty_per_violation": 10000,
            "constraint_name": "Limit journey time to 60 minutes",
            "constraint_type": "Journey_Time"
        },
        {
            "violation_increment": 600,
            "max_additional_journey_seconds": 1800,
            "penalty_per_violation": 10000,
            "constraint_name": "Add no more than 30 minutes to any passenger journey",
            "constraint_type": "Additional_Journey_Time"
        }
    ],
    "items": [
        {
            "item_type": "person"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta Hyatt",
                    "shift_id": "v1 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta Hyatt",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Hyatt van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta W Hotel",
                    "shift_id": "v2 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta W Hotel",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger W Hotel van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "The Ritz-Carlton",
                    "shift_id": "v3 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "The Ritz-Carlton",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Ritz-Carlton van"
        }
    ],
    "locations": [
        {
            "location_id": "SunTrust Park",
            "latitude": 33.891142,
            "longitude": -84.467831
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "latitude": 33.874745,
            "longitude": -84.302473
        },
        {
            "location_id": "Tennis Tournament",
            "latitude": 33.801666,
            "longitude": -84.399962
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "latitude": 33.757539,
            "longitude": -84.396324
        },
        {
            "location_id": "Atlanta Convention Center",
            "latitude": 33.760325,
            "longitude": -84.388282
        },
        {
            "location_id": "Atlanta Hyatt",
            "latitude": 33.761439,
            "longitude": -84.38736
        },
        {
            "location_id": "Atlanta W Hotel",
            "latitude": 33.765263,
            "longitude": -84.389215
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "latitude": 33.6407392,
            "longitude": -84.4977388
        },
        {
            "location_id": "Crowne Plaza Midtown",
            "latitude": 33.7702594,
            "longitude": -84.3898117
        },
        {
            "location_id": "The Ritz-Carlton",
            "latitude": 33.6782242,
            "longitude": -84.42027
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "latitude": 33.7731954,
            "longitude": -84.3867607
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "latitude": 33.7855117,
            "longitude": -84.3948399
        },
        {
            "location_id": "W Midtown",
            "latitude": 33.7868451,
            "longitude": -84.3839391
        },
        {
            "location_id": "Embassy Suites Perimeter Center",
            "latitude": 33.9309739,
            "longitude": -84.3492964
        },
        {
            "location_id": "Hyatt Place Buckhead",
            "latitude": 33.8437201,
            "longitude": -84.3745431
        },
        {
            "location_id": "Hampton Inn Alpharetta",
            "latitude": 34.0414028,
            "longitude": -84.3225011
        },
        {
            "location_id": "Holiday Inn Express Kennesaw",
            "latitude": 34.0119044,
            "longitude": -84.5684887
        },
        {
            "location_id": "Radisson Hotel Marietta",
            "latitude": 33.9398352,
            "longitude": -84.5078069
        }
    ],
    "orders": [
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T09:25:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T10:30:00-04:00",
            "dropoff_location_id": "SunTrust Park",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Albert, Enrico, Robert at Hartsfield-Jackson Airport between 9-9:25am. Drop off at SunTrust Park by 10:30am"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T12:45:00-04:00",
                    "end_time_window": "2017-08-24T13:15:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T14:00:00-04:00",
            "dropoff_location_id": "Atlanta Convention Center",
            "pickup_item_quantities": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Bob and family (6 people) at Hartsfield-Jackson Airport between 12:45-1:00pm. Drop off at convention center by 2pm"
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:45:00-04:00",
                    "end_time_window": "2017-08-24T10:30:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Mark and Oscar at Hawks arena between 9:45-10:30am. Drop off at tennis tournament"
        },
        {
            "location_id": "Atlanta Hyatt",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T14:00:00-04:00",
                    "end_time_window": "2017-08-24T15:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "DeKalb Peachtree Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Doug between 2pm and 3pm at Atlanta Hyatt. Drop off at DeKalb airport"
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Edith and Maureen between 9am and 10am at Courtyard. Drop off at ATL airport"
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:30:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Cheech and Chong between 9am and 10am at Hotel Indigo. Drop off at ATL airport by 11:30am"
        },
        {
            "location_id": "The Ritz-Carlton",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Hansel and Gretel between 3pm and 4pm at Ritz Carlton. Drop off at Atlanta Hawks Arena"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T11:00:00-04:00",
                    "end_time_window": "2017-08-24T13:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T13:30:00-04:00",
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Heather between 11am and 1pm at DeKalb Peachtree Airport. Drop off at Atlanta Hawks Arena by 1:30pm"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Iris between 9 and 10 at DeKalb Peachtree Airport. Drop off at ATL Airport by 11am"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Chris and Mitch between 3 and 4pm at DeKalb Peachtree Airport. Drop off at ATL Airport by 5pm"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Williams family (3 people) between 3 and 4pm at Hartsfield-Jackson Airport. Drop off at tennis by 5pm"
        }
    ]
}

The solution for this example does not violate any constraints and utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the dropoff time of any passengers the passengers Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs that are inherent in complex routing problems, and punishing customers with a terrible experience can be avoided with the right mix of constraints.

Dropoff Deadline — dropoff_deadline

Description

Given an order with a dropoff_location_id, a dropoff_deadline enforces the latest time that the dropoff occurs. The associated violation_increment is in seconds.

Example

In the passenger pickup and dropoff example below, the journey_time, additional_journey_time, and dropoff_deadline constraints are used simultaneously. In the example, several vans start and end their routes at an Atlanta hotel. Each van has a six (6) passenger capacity expressed using the capacity_by_item array with passengers described as "items" using "item_type": "person".

{
    "constraints": [
        {
            "violation_increment": 1,
            "penalty_per_violation": 1,
            "constraint_name": "limit travel",
            "constraint_type": "travel_time",
            "max_travel_time_seconds": 0
        },
        {
            "violation_increment": 1,
            "penalty_per_violation": 10000000,
            "constraint_name": "visit as many orders as possible",
            "constraint_type": "visit_range"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 50000,
            "constraint_name": "honor time windows",
            "constraint_type": "Time_Window"
        },
        {
            "violation_increment": 600,
            "penalty_per_violation": 10000,
            "constraint_name": "meet dropoff deadline",
            "constraint_type": "Dropoff_Deadline"
        },
        {
            "violation_increment": 600,
            "max_journey_seconds": 3600,
            "penalty_per_violation": 10000,
            "constraint_name": "Limit journey time to 60 minutes",
            "constraint_type": "Journey_Time"
        },
        {
            "violation_increment": 600,
            "max_additional_journey_seconds": 1800,
            "penalty_per_violation": 10000,
            "constraint_name": "Add no more than 30 minutes to any passenger journey",
            "constraint_type": "Additional_Journey_Time"
        }
    ],
    "items": [
        {
            "item_type": "person"
        }
    ],
    "vehicles": [
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta Hyatt",
                    "shift_id": "v1 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta Hyatt",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Hyatt van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "Atlanta W Hotel",
                    "shift_id": "v2 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "Atlanta W Hotel",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger W Hotel van"
        },
        {
            "shifts": [
                {
                    "start_location_id": "The Ritz-Carlton",
                    "shift_id": "v3 shift",
                    "shift_start": "2017-08-24T08:00:00-04:00",
                    "end_location_id": "The Ritz-Carlton",
                    "shift_end": "2017-08-24T18:00:00-04:00"
                }
            ],
            "type": "car",
            "capacity_by_item": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "vehicle_id": "6 passenger Ritz-Carlton van"
        }
    ],
    "locations": [
        {
            "location_id": "SunTrust Park",
            "latitude": 33.891142,
            "longitude": -84.467831
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "latitude": 33.874745,
            "longitude": -84.302473
        },
        {
            "location_id": "Tennis Tournament",
            "latitude": 33.801666,
            "longitude": -84.399962
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "latitude": 33.757539,
            "longitude": -84.396324
        },
        {
            "location_id": "Atlanta Convention Center",
            "latitude": 33.760325,
            "longitude": -84.388282
        },
        {
            "location_id": "Atlanta Hyatt",
            "latitude": 33.761439,
            "longitude": -84.38736
        },
        {
            "location_id": "Atlanta W Hotel",
            "latitude": 33.765263,
            "longitude": -84.389215
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "latitude": 33.6407392,
            "longitude": -84.4977388
        },
        {
            "location_id": "Crowne Plaza Midtown",
            "latitude": 33.7702594,
            "longitude": -84.3898117
        },
        {
            "location_id": "The Ritz-Carlton",
            "latitude": 33.6782242,
            "longitude": -84.42027
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "latitude": 33.7731954,
            "longitude": -84.3867607
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "latitude": 33.7855117,
            "longitude": -84.3948399
        },
        {
            "location_id": "W Midtown",
            "latitude": 33.7868451,
            "longitude": -84.3839391
        },
        {
            "location_id": "Embassy Suites Perimeter Center",
            "latitude": 33.9309739,
            "longitude": -84.3492964
        },
        {
            "location_id": "Hyatt Place Buckhead",
            "latitude": 33.8437201,
            "longitude": -84.3745431
        },
        {
            "location_id": "Hampton Inn Alpharetta",
            "latitude": 34.0414028,
            "longitude": -84.3225011
        },
        {
            "location_id": "Holiday Inn Express Kennesaw",
            "latitude": 34.0119044,
            "longitude": -84.5684887
        },
        {
            "location_id": "Radisson Hotel Marietta",
            "latitude": 33.9398352,
            "longitude": -84.5078069
        }
    ],
    "orders": [
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T09:25:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T10:30:00-04:00",
            "dropoff_location_id": "SunTrust Park",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Albert, Enrico, Robert at Hartsfield-Jackson Airport between 9-9:25am. Drop off at SunTrust Park by 10:30am"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T12:45:00-04:00",
                    "end_time_window": "2017-08-24T13:15:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T14:00:00-04:00",
            "dropoff_location_id": "Atlanta Convention Center",
            "pickup_item_quantities": [
                {
                    "quantity": 6,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Bob and family (6 people) at Hartsfield-Jackson Airport between 12:45-1:00pm. Drop off at convention center by 2pm"
        },
        {
            "location_id": "Atlanta Hawks Arena",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:45:00-04:00",
                    "end_time_window": "2017-08-24T10:30:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Mark and Oscar at Hawks arena between 9:45-10:30am. Drop off at tennis tournament"
        },
        {
            "location_id": "Atlanta Hyatt",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T14:00:00-04:00",
                    "end_time_window": "2017-08-24T15:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "DeKalb Peachtree Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Doug between 2pm and 3pm at Atlanta Hyatt. Drop off at DeKalb airport"
        },
        {
            "location_id": "Courtyard by Marriott Midtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Edith and Maureen between 9am and 10am at Courtyard. Drop off at ATL airport"
        },
        {
            "location_id": "Hotel Indigo Downtown",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:30:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Cheech and Chong between 9am and 10am at Hotel Indigo. Drop off at ATL airport by 11:30am"
        },
        {
            "location_id": "The Ritz-Carlton",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 2,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Hansel and Gretel between 3pm and 4pm at Ritz Carlton. Drop off at Atlanta Hawks Arena"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T11:00:00-04:00",
                    "end_time_window": "2017-08-24T13:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T13:30:00-04:00",
            "dropoff_location_id": "Atlanta Hawks Arena",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Heather between 11am and 1pm at DeKalb Peachtree Airport. Drop off at Atlanta Hawks Arena by 1:30pm"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T09:00:00-04:00",
                    "end_time_window": "2017-08-24T10:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T11:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Iris between 9 and 10 at DeKalb Peachtree Airport. Drop off at ATL Airport by 11am"
        },
        {
            "location_id": "DeKalb Peachtree Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Hartsfield-Jackson Airport",
            "pickup_item_quantities": [
                {
                    "quantity": 1,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Chris and Mitch between 3 and 4pm at DeKalb Peachtree Airport. Drop off at ATL Airport by 5pm"
        },
        {
            "location_id": "Hartsfield-Jackson Airport",
            "time_windows": [
                {
                    "start_time_window": "2017-08-24T15:00:00-04:00",
                    "end_time_window": "2017-08-24T16:00:00-04:00"
                }
            ],
            "duration": 300,
            "dropoff_deadline": "2017-08-24T17:00:00-04:00",
            "dropoff_location_id": "Tennis Tournament",
            "pickup_item_quantities": [
                {
                    "quantity": 3,
                    "item_type": "person"
                }
            ],
            "order_id": "Pick up Williams family (3 people) between 3 and 4pm at Hartsfield-Jackson Airport. Drop off at tennis by 5pm"
        }
    ]
}

The solution for this example does not violate any constraints and utilizes all three (3) vehicles with a total travel time of approximately 7.5 hours. The longest journey for any passenger is short of one (1) hour. In contrast, removing the constraints and adding ones that enforce meeting pickup time windows and minimizing travel time, the solution requires two (2) vehicles and only six (6) hours of total travel time. Why would one not want a shorter overall travel time? Because in not considering the dropoff time of any passengers the passengers Mark and Oscar needlessly wait 3.5 hours at the airport before their eventual dropoff at the tennis tournament 5 hours later! This example illustrates many of the tradeoffs that are inherent in complex routing problems, and punishing customers with a terrible experience can be avoided with the right mix of constraints.