Travel Time — travel_time
Description
Travel time is arguably the most fundamental constraint for a typical vehicle routing problem. The goal is to make the routes efficient from a travel perspective. As alluded to in other parts of the documentation, it is convenient to use this constraint to align a single unit of the penalty with a single second traveled by a vehicle. This is done as shown below.
{
"constraint_type": "travel_time",
"constraint_name": "make travel efficient",
"penalty_per_violation": 1,
"violation_increment": 1,
"max_travel_time_seconds": 0
}
Example
To understand the impact of the travel time constraint, it is best to see what happens when it is NOT included. In the below example, we send only a visit range constraint so that the optimization engine will focus on visiting as many orders as possible but with no incentive to minimize travel time. The result is a set of routes that visit all orders but with very inefficient travel.
{
"constraints": [
{
"constraint_name": "visit as many orders as possible",
"violation_increment": 1,
"constraint_type": "visit_range",
"penalty_per_violation": 10000
}
],
"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"
}
]
}
Four vehicle solution with all orders visited and travel time constraint included so that routes are efficient from a travel perspective.
Four vehicle solution with no travel time constraint included. In this case, we visit all the orders but the sequence of stops on the route is clearly inefficient. The total travel time, in this case, is about 400 minutes longer than in the solution produced when we include the travel time constraint.
Number of Shifts — num_shifts
Description
Another very common goal in many vehicle routing problems is to minimize the total number of routes. In single day problems, this is equivalent to minimizing the number of vehicles since there is a 1-to-1 correspondence between vehicles and routes. On multiple day problems, the situation can be a bit different as a vehicle may have routes assigned to it on only a subset of the days of the planning period. To generalize this, the num_shifts constraint seeks to minimize the total number of shifts in the solution (recall that a shift is simply a period of time during which a vehicle is allowed to be active). This is done as shown below.
{
"constraint_type": "num_shifts",
"constraint_name": "limit number of shifts",
"penalty_per_violation": 100000,
"violation_increment": 1,
"max_shifts": 3
}
Example
In the example for this constraint, we add the fifth vehicle to our typical four vehicle problem that is used throughout many of the other examples. This vehicle has a start/end location in the eastern portion of the area and a single order is very close to it. Without the num_shifts constraint, we use this vehicle as it adds very little travel time. However, adding a high penalty num_shifts constraint eliminates this route at the expense of additional travel time.
{
"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": "num_shifts",
"penalty_per_violation": 100000,
"violation_increment": 1,
"constraint_name": "limit number of shifts",
"max_shifts": 3
}
],
"vehicles": [
{
"vehicle_id": "Vehicle0",
"shifts": [
{
"end_location_id": "loc999",
"shift_end": "2017-08-24T10:10:00-04:00",
"start_location_id": "loc999",
"shift_id": "v0shift",
"shift_start": "2017-08-24T08:05:00-04:00"
}
]
},
{
"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"
},
{
"location_id": "loc999",
"latitude": 33.745532,
"longitude": -83.852649
},
{
"location_id": "loc998",
"latitude": 33.758183,
"longitude": -83.849035
}
],
"orders": [
{
"order_id": "698123",
"location_id": "loc998",
"duration": 600
},
{
"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
}
]
}
The original solution to the five vehicle problem with no num_shifts constraint. Note the purple route in the east near Walnut Grove – this vehicle visits only a single stop that is very near the start/end location.
By adding the high penalty num_shifts constraint, the Walnut Grove vehicle is eliminated from the solution. Total travel time increases by about 30 minutes since we no longer use this vehicle
Vehicle Usage — vehicle_usage
Description
In some cases, a certain vehicle may be more expensive to use than other options in the fleet, for example, if a vehicle gets worse gas mileage or is operated by a contractor whose rate is more expensive than other employees. This constraint allows us to try and avoid using this vehicle or to at least minimize how much it is used. The violation_increment option can be particularly useful for this constraint. The units are in the number of stops, so if the violation_increment is set to 5 then a penalty is assessed for every 5 stops that this vehicle makes (other than start/end location of the route). This is done as shown below.
{
"constraint_type": "vehicle_usage",
"constraint_name": "try to avoid using vehicle 1",
"penalty_per_violation": 20000,
"violation_increment": 5,
"vehicle_ids": [
"Vehicle1"
]
}
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_Usage",
"constraint_name": "try to avoid using vehicle 1",
"penalty_per_violation": 20000,
"violation_increment": 5,
"vehicle_ids": [
"Vehicle1"
]
}
],
"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
}
]
}
Original 4 vehicle solution with no vehicle_usage constraint. Note that the route for Vehicle 1 (Red, southwest) visits 15 total orders.
The vehicle_usage constraint has a penalty of 20,000 and a violation_increment of 5 for using Vehicle 1 (southwest). If Vehicle 1 has between 1 and 5 stops, the penalty is 20,000, between 6 and 9 stops the penalty is 40,000, and so on. In this solution, we visit 9 orders with Vehicle 1 and are still able to visit all 34 orders in the problem. While stop 3 in the red route is very inefficient, if we were to add it to Vehicle 1’s green route after stop 6, this would lead to an additional 20,000 units of penalty since we would now have 10 stops on this route. Since this route modification does not save 20,000 seconds of travel time, the solution above achieves a much lower score even though the red route goes out of the way to hit its stop #3.
Prevent Item Mixture — prevent_item_mixture
Description
In problems where we have items to pick up and/or deliver, it can sometimes be desirable to prevent certain items from being included in the same route. For example, we may be carrying livestock and wish to prevent horned animals from sharing the truck with non-horned animals. This can be achieved with the prevent_item_mixture constraint. If violation_increment is specified then the units are the count of item types. This is done as shown below.
{
"constraint_type": "prevent_item_mixture",
"constraint_name": "No bleach and ammonia on same route",
"penalty_per_violation": 100000,
"violation_increment": 1,
"item_types": [
"bleach",
"ammonia"
]
}
Example
In the example, we have two item types: bleach and ammonia. For everyone’s safety, we do not want the bleach to ever come in contact with ammonia, so we use a high penalty prevent_item_mixture constraint to prevent this from ever occurring.
{
"constraints": [
{
"constraint_name": "limit travel",
"constraint_type": "travel_time",
"penalty_per_violation": 1,
"max_travel_time_seconds": 0,
"violation_increment": 1
},
{
"constraint_name": "visit as many orders as possible",
"constraint_type": "visit_range",
"penalty_per_violation": 10000,
"violation_increment": 1
},
{
"constraint_name": "No bleach and ammonia on same route",
"constraint_type": "prevent_item_mixture",
"item_types": [
"bleach",
"ammonia"
],
"penalty_per_violation": 100000,
"violation_increment": 1
}
],
"vehicles": [
{
"vehicle_id": "Vehicle1",
"type": "car",
"capacity_by_item": [
{
"item_type": "bleach",
"quantity": 10
},
{
"item_type": "ammonia",
"quantity": 8
}
],
"shifts": [
{
"shift_id": "v1shift",
"shift_start": "2017-08-24T08:05:00-04:00",
"shift_end": "2017-08-24T17:10:00-04:00",
"break_start": [
"2017-08-24T12:00:00-04:00"
],
"break_end": [
"2017-08-24T13:00:00-04:00"
],
"soft_break_start": [],
"soft_break_end": [],
"start_items": [],
"start_location_id": "loc20",
"end_location_id": "loc20"
}
]
},
{
"vehicle_id": "Vehicle2",
"type": "car",
"capacity_by_item": [
{
"item_type": "bleach",
"quantity": 10
},
{
"item_type": "ammonia",
"quantity": 8
}
],
"shifts": [
{
"shift_id": "v2shift",
"shift_start": "2017-08-24T10:05:00-04:00",
"shift_end": "2017-08-24T15:10:00-04:00",
"break_start": [
"2017-08-24T12:00:00-04:00"
],
"break_end": [
"2017-08-24T13:00:00-04:00"
],
"soft_break_start": [],
"soft_break_end": [],
"start_items": [],
"start_location_id": "loc99",
"end_location_id": "loc99"
}
]
},
{
"vehicle_id": "Vehicle3",
"type": "car",
"capacity_by_item": [
{
"item_type": "bleach",
"quantity": 10
},
{
"item_type": "ammonia",
"quantity": 8
}
],
"shifts": [
{
"shift_id": "v3shift",
"shift_start": "2017-08-24T07:05:00-04:00",
"shift_end": "2017-08-24T13:10:00-04:00",
"break_start": [
"2017-08-24T09:00:00-04:00"
],
"break_end": [
"2017-08-24T10:00:00-04:00"
],
"soft_break_start": [],
"soft_break_end": [],
"start_items": [],
"start_location_id": "loc16",
"end_location_id": "loc16"
}
]
},
{
"vehicle_id": "Vehicle4",
"type": "car",
"capacity_by_item": [
{
"item_type": "bleach",
"quantity": 10
},
{
"item_type": "ammonia",
"quantity": 8
}
],
"shifts": [
{
"shift_id": "v4shift",
"shift_start": "2017-08-24T09:05:00-04:00",
"shift_end": "2017-08-24T16:10:00-04:00",
"break_start": [
"2017-08-24T12:00:00-04:00"
],
"break_end": [
"2017-08-24T13:00:00-04:00"
],
"soft_break_start": [],
"soft_break_end": [],
"start_items": [],
"start_location_id": "loc100",
"end_location_id": "loc100"
}
]
}
],
"items": [
{
"item_type": "bleach"
},
{
"item_type": "ammonia"
}
],
"orders": [
{
"order_id": "688798",
"duration": 600,
"location_id": "loc1",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "689105",
"duration": 600,
"location_id": "loc3",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "692039",
"duration": 1800,
"location_id": "loc5",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "583368",
"duration": 600,
"location_id": "loc6",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "677048",
"duration": 600,
"location_id": "loc7",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "685086",
"duration": 600,
"location_id": "loc8",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "690020",
"duration": 600,
"location_id": "loc9",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "674660",
"duration": 600,
"location_id": "loc11",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "413170",
"duration": 600,
"location_id": "loc13",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "685945",
"duration": 600,
"location_id": "loc14",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "692592",
"duration": 600,
"location_id": "loc15",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "678545",
"duration": 600,
"location_id": "loc17",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "692829",
"duration": 600,
"location_id": "loc18",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "695124",
"duration": 600,
"location_id": "loc19",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "693192",
"duration": 600,
"location_id": "loc21",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "649953",
"duration": 600,
"location_id": "loc22",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "694498",
"duration": 600,
"location_id": "loc23",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "693854",
"duration": 600,
"location_id": "loc24",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "688899",
"duration": 600,
"location_id": "loc25",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "617086",
"duration": 600,
"location_id": "loc26",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "340637",
"duration": 600,
"location_id": "loc27",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "693098",
"duration": 600,
"location_id": "loc28",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "683931",
"duration": 600,
"location_id": "loc29",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "685382",
"duration": 600,
"location_id": "loc30",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "691449",
"duration": 600,
"location_id": "loc31",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "509217",
"duration": 600,
"location_id": "loc32",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "691287",
"duration": 600,
"location_id": "loc33",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "640723",
"duration": 600,
"location_id": "loc34",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "665537",
"duration": 600,
"location_id": "loc35",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "693858",
"duration": 600,
"location_id": "loc36",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "392888",
"duration": 600,
"location_id": "loc37",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "623404",
"duration": 600,
"location_id": "loc38",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "695743",
"duration": 600,
"location_id": "loc39",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "bleach",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
},
{
"order_id": "692431",
"duration": 600,
"location_id": "loc40",
"pickup_item_quantities": [],
"delivery_item_quantities": [
{
"item_type": "ammonia",
"quantity": 1
}
],
"max_visits": 1,
"min_visits": 1
}
],
"locations": [
{
"location_id": "loc1",
"latitude": 33.3300399,
"longitude": -84.07639
},
{
"location_id": "loc2",
"latitude": 33.5179638,
"longitude": -84.4153667
},
{
"location_id": "loc3",
"latitude": 34.07687,
"longitude": -84.52763
},
{
"location_id": "loc4",
"latitude": 33.73872,
"longitude": -85.15883
},
{
"location_id": "loc5",
"latitude": 34.02463,
"longitude": -84.1256499
},
{
"location_id": "loc6",
"latitude": 33.78583,
"longitude": -84.30268
},
{
"location_id": "loc7",
"latitude": 34.07687,
"longitude": -84.5738499
},
{
"location_id": "loc8",
"latitude": 33.98557,
"longitude": -83.7661399
},
{
"location_id": "loc9",
"latitude": 34.02403,
"longitude": -84.69128
},
{
"location_id": "loc11",
"latitude": 33.57832,
"longitude": -84.26431
},
{
"location_id": "loc12",
"latitude": 33.56882,
"longitude": -84.51451
},
{
"location_id": "loc13",
"latitude": 33.8200999,
"longitude": -84.30606
},
{
"location_id": "loc14",
"latitude": 33.98078,
"longitude": -84.02126
},
{
"location_id": "loc15",
"latitude": 33.98596,
"longitude": -84.20871
},
{
"location_id": "loc16",
"latitude": 34.098671,
"longitude": -83.789905
},
{
"location_id": "loc17",
"latitude": 33.68959,
"longitude": -84.3739
},
{
"location_id": "loc18",
"latitude": 33.8965699,
"longitude": -84.08495
},
{
"location_id": "loc19",
"latitude": 34.0078,
"longitude": -84.5491
},
{
"location_id": "loc20",
"latitude": 33.44852,
"longitude": -84.78468
},
{
"location_id": "loc21",
"latitude": 33.45099,
"longitude": -84.7372199
},
{
"location_id": "loc22",
"latitude": 33.7084199,
"longitude": -84.44377
},
{
"location_id": "loc23",
"latitude": 34.0286,
"longitude": -84.37416
},
{
"location_id": "loc24",
"latitude": 33.82054,
"longitude": -84.23121
},
{
"location_id": "loc25",
"latitude": 33.83828,
"longitude": -84.21402
},
{
"location_id": "loc26",
"latitude": 34.05614,
"longitude": -84.31995
},
{
"location_id": "loc27",
"latitude": 33.7435386,
"longitude": -84.6712
},
{
"location_id": "loc28",
"latitude": 33.99045,
"longitude": -84.8082699
},
{
"location_id": "loc29",
"latitude": 33.84614,
"longitude": -84.7469
},
{
"location_id": "loc30",
"latitude": 33.68736,
"longitude": -84.23972
},
{
"location_id": "loc31",
"latitude": 33.7757999,
"longitude": -84.3845599
},
{
"location_id": "loc32",
"latitude": 34.19941,
"longitude": -84.1556
},
{
"location_id": "loc33",
"latitude": 33.75112,
"longitude": -84.35911
},
{
"location_id": "loc34",
"latitude": 33.9854531,
"longitude": -83.707189
},
{
"location_id": "loc35",
"latitude": 33.52079,
"longitude": -84.36567
},
{
"location_id": "loc36",
"latitude": 34.104,
"longitude": -84.2661811
},
{
"location_id": "loc37",
"latitude": 33.88826,
"longitude": -84.20234
},
{
"location_id": "loc38",
"latitude": 33.4439,
"longitude": -84.32034
},
{
"location_id": "loc39",
"latitude": 33.96681,
"longitude": -84.23654
},
{
"location_id": "loc40",
"latitude": 34.1162,
"longitude": -83.81919
},
{
"location_id": "loc99",
"latitude": 34.07697,
"longitude": -85.0148499
},
{
"location_id": "loc100",
"latitude": 33.9157,
"longitude": -84.52097
}
]
}
Original 4 vehicle solution with no restriction on which items can be mixed together on the route.
The solution where multiple item types cannot be included in the same route. Note the yellow route for Vehicle 1 which now must visit many disparate locations. Because the routes now must cover larger areas, we are unable to visit 2 of the orders.