Order Level Constraints

Visit Range and Gap — visit_range and visit_gap

Description

These two 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_ids 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"
        }
    ]
}

imgThe 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.

imgThe 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 — schedule_appointment

Description

A scheduled appointment is more stringent than a time window. When an order has a scheduled appointment, then service must begin exactly at the specified time and end at the specified time. This 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 routes. This constraint ensures that the appointments 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. The appointment times are provided inside each order object.

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
        }
    ]
}

imgOriginal solution with 2 vehicles and no Order_Priority constraint.

imgIn 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
        }
    ]
}

imgSolution before adding the Span constraint.

imgIn 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
        }
    ]
}

imgOriginal solution with no Vehicle_Coverage constraint.

imgThree widely spread orders (boxed in black) are added to the Vehicle_Coverage constraint with min_vehicles=1 and max_vehicles=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.