Route Level Constraints

Visit Sequence — visit_sequence

Description

Ensure that order A is visited before order B. Note that if either A or B is not visited in the solution, then the constraint is deemed to be violated and a penalty is assessed.

Example

{
   "constraints": [
     {
       "penalty_per_violation": 1,
       "constraint_name": "limit travel",
       "constraint_type": "Travel_Time",
       "max_travel_time_seconds": 0,
       "violation_increment": 1
     },
     {
       "penalty_per_violation": 10000,
       "constraint_name": "visit as many orders as possible",
       "constraint_type": "Visit_Range",
       "violation_increment": 1
     },
     {
       "second_order_id": "665537",
       "first_order_id": "691287",
       "violation_increment": 1,
       "penalty_per_violation": 10000,
       "constraint_name": "visit 691287 before 665537 on same route",
       "constraint_type": "Visit_Sequence"
     },
     {
       "second_order_id": "665537",
       "first_order_id": "674660",
       "violation_increment": 1,
       "penalty_per_violation": 10000,
       "constraint_name": "visit 674660 before 665537 on same route",
       "constraint_type": "Visit_Sequence"
     }
   ], 
   "vehicles": [
     {
       "vehicle_id": "Vehicle1",
       "shifts": [
         {
           "shift_id": "v1shift",
           "start_location_id": "loc20",
           "end_location_id": "loc20",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T08:05:00-04:00",
           "shift_end": "2017-08-24T17:10:00-04:00"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle2",
       "shifts": [
         {
           "shift_id": "v2shift",
           "start_location_id": "loc99",
           "end_location_id": "loc99",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T10:05:00-04:00",
           "shift_end": "2017-08-24T15:10:00-04:00"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle3",
       "shifts": [
         {
           "shift_id": "v3shift",
           "start_location_id": "loc16",
           "end_location_id": "loc16",
           "break_end": [
             "2017-08-24T10:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T09:00:00-04:00"
           ],
           "shift_start": "2017-08-24T07:05:00-04:00",
           "shift_end": "2017-08-24T13:10:00-04:00"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle4",
       "shifts": [
         {
           "shift_id": "v4shift",
           "start_location_id": "loc100",
           "end_location_id": "loc100",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T09:05:00-04:00",
           "shift_end": "2017-08-24T16:10:00-04:00"
         }
       ]
     }
   ],
   "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
     }
   ],
   "locations": [
     {
       "latitude": 33.3300399,
       "location_id": "loc1",
       "longitude": -84.07639
     },
     {
       "latitude": 33.5179638,
       "location_id": "loc2",
       "longitude": -84.4153667
     },
     {
       "latitude": 34.07687,
       "location_id": "loc3",
       "longitude": -84.52763
     },
     {
       "latitude": 33.73872,
       "location_id": "loc4",
       "longitude": -85.15883
     },
     {
       "latitude": 34.02463,
       "location_id": "loc5",
       "longitude": -84.1256499
     },
     {
       "latitude": 33.78583,
       "location_id": "loc6",
       "longitude": -84.30268
     },
     {
       "latitude": 34.07687,
       "location_id": "loc7",
       "longitude": -84.5738499
     },
     {
       "latitude": 33.98557,
       "location_id": "loc8",
       "longitude": -83.7661399
     },
     {
       "latitude": 34.02403,
       "location_id": "loc9",
       "longitude": -84.69128
     },
     {
       "latitude": 33.57832,
       "location_id": "loc11",
       "longitude": -84.26431
     },
     {
       "latitude": 33.56882,
       "location_id": "loc12",
       "longitude": -84.51451
     },
     {
       "latitude": 33.8200999,
       "location_id": "loc13",
       "longitude": -84.30606
     },
     {
       "latitude": 33.98078,
       "location_id": "loc14",
       "longitude": -84.02126
     },
     {
       "latitude": 33.98596,
       "location_id": "loc15",
       "longitude": -84.20871
     },
     {
       "latitude": 34.098671,
       "location_id": "loc16",
       "longitude": -83.789905
     },
     {
       "latitude": 33.68959,
       "location_id": "loc17",
       "longitude": -84.3739
     },
     {
       "latitude": 33.8965699,
       "location_id": "loc18",
       "longitude": -84.08495
     },
     {
       "latitude": 34.0078,
       "location_id": "loc19",
       "longitude": -84.5491
     },
     {
       "latitude": 33.44852,
       "location_id": "loc20",
       "longitude": -84.78468
     },
     {
       "latitude": 33.45099,
       "location_id": "loc21",
       "longitude": -84.7372199
     },
     {
       "latitude": 33.7084199,
       "location_id": "loc22",
       "longitude": -84.44377
     },
     {
       "latitude": 34.0286,
       "location_id": "loc23",
       "longitude": -84.37416
     },
     {
       "latitude": 33.82054,
       "location_id": "loc24",
       "longitude": -84.23121
     },
     {
       "latitude": 33.83828,
       "location_id": "loc25",
       "longitude": -84.21402
     },
     {
       "latitude": 34.05614,
       "location_id": "loc26",
       "longitude": -84.31995
     },
     {
       "latitude": 33.7435386,
       "location_id": "loc27",
       "longitude": -84.6712
     },
     {
       "latitude": 33.99045,
       "location_id": "loc28",
       "longitude": -84.8082699
     },
     {
       "latitude": 33.84614,
       "location_id": "loc29",
       "longitude": -84.7469
     },
     {
       "latitude": 33.68736,
       "location_id": "loc30",
       "longitude": -84.23972
     },
     {
       "latitude": 33.7757999,
       "location_id": "loc31",
       "longitude": -84.3845599
     },
     {
       "latitude": 34.19941,
       "location_id": "loc32",
       "longitude": -84.1556
     },
     {
       "latitude": 33.75112,
       "location_id": "loc33",
       "longitude": -84.35911
     },
     {
       "latitude": 33.9854531,
       "location_id": "loc34",
       "longitude": -83.707189
     },
     {
       "latitude": 33.52079,
       "location_id": "loc35",
       "longitude": -84.36567
     },
     {
       "latitude": 34.104,
       "location_id": "loc36",
       "longitude": -84.2661811
     },
     {
       "latitude": 33.88826,
       "location_id": "loc37",
       "longitude": -84.20234
     },
     {
       "latitude": 33.4439,
       "location_id": "loc38",
       "longitude": -84.32034
     },
     {
       "latitude": 33.96681,
       "location_id": "loc39",
       "longitude": -84.23654
     },
     {
       "latitude": 34.1162,
       "location_id": "loc40",
       "longitude": -83.81919
     },
     {
       "latitude": 34.07697,
       "location_id": "loc99",
       "longitude": -85.0148499
     },
     {
       "latitude": 33.9157,
       "location_id": "loc100",
       "longitude": -84.52097
     }
   ]
 }

imgThe original solution before adding the Visit_Sequence constraint

imgMultiple uses of the constraint forces order id 691287, 665537, and 674660 (boxed in red) to all be on the same route, and 691287 and 674660 must both before order id 665537. In the original solution, 66537 (near Jonesboro) is the first stop in the route and it now becomes the last stop in the route after adding the constraint. First stop in basic solution for bottom route is now the last stop (stop #11) in the new route. Stop #8 in the new solution (order id 674660) was formerly stop #4, and stop #11 in the original solution (order id 691287) is now stop #4 after adding the constraint.


First Visit — first_visit

Description

Ensure that each of the provided orders is visited as the first stop on the route. If the shift associated with the route has a pre-determined start location, then the order must be the first stop visited after departing the start location. Otherwise on a route with an open start location, the order must be the first overall stop on the route.

Example

{
   "constraints": [
     {
       "violation_increment": 1,
       "max_travel_time_seconds": 0,
       "penalty_per_violation": 1,
       "constraint_name": "limit travel",
       "constraint_type": "Travel_Time"
     },
     {
       "violation_increment": 1,
       "penalty_per_violation": 10000,
       "constraint_name": "visit as many orders as possible",
       "constraint_type": "Visit_Range"
     },
     {
       "order_ids": [
         "674660"
       ],
       "violation_increment": 1,
       "penalty_per_violation": 10000,
       "constraint_name": "visit 674660 as first stop on route",
       "constraint_type": "First_Visit"
     }
   ],
   "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": [
     {
       "latitude": 33.3300399,
       "location_id": "loc1",
       "longitude": -84.07639
     },
     {
       "latitude": 33.5179638,
       "location_id": "loc2",
       "longitude": -84.4153667
     },
     {
       "latitude": 34.07687,
       "location_id": "loc3",
       "longitude": -84.52763
     },
     {
       "latitude": 33.73872,
       "location_id": "loc4",
       "longitude": -85.15883
     },
     {
       "latitude": 34.02463,
       "location_id": "loc5",
       "longitude": -84.1256499
     },
     {
       "latitude": 33.78583,
       "location_id": "loc6",
       "longitude": -84.30268
     },
     {
       "latitude": 34.07687,
       "location_id": "loc7",
       "longitude": -84.5738499
     },
     {
       "latitude": 33.98557,
       "location_id": "loc8",
       "longitude": -83.7661399
     },
     {
       "latitude": 34.02403,
       "location_id": "loc9",
       "longitude": -84.69128
     },
     {
       "latitude": 33.57832,
       "location_id": "loc11",
       "longitude": -84.26431
     },
     {
       "latitude": 33.56882,
       "location_id": "loc12",
       "longitude": -84.51451
     },
     {
       "latitude": 33.8200999,
       "location_id": "loc13",
       "longitude": -84.30606
     },
     {
       "latitude": 33.98078,
       "location_id": "loc14",
       "longitude": -84.02126
     },
     {
       "latitude": 33.98596,
       "location_id": "loc15",
       "longitude": -84.20871
     },
     {
       "latitude": 34.098671,
       "location_id": "loc16",
       "longitude": -83.789905
     },
     {
       "latitude": 33.68959,
       "location_id": "loc17",
       "longitude": -84.3739
     },
     {
       "latitude": 33.8965699,
       "location_id": "loc18",
       "longitude": -84.08495
     },
     {
       "latitude": 34.0078,
       "location_id": "loc19",
       "longitude": -84.5491
     },
     {
       "latitude": 33.44852,
       "location_id": "loc20",
       "longitude": -84.78468
     },
     {
       "latitude": 33.45099,
       "location_id": "loc21",
       "longitude": -84.7372199
     },
     {
       "latitude": 33.7084199,
       "location_id": "loc22",
       "longitude": -84.44377
     },
     {
       "latitude": 34.0286,
       "location_id": "loc23",
       "longitude": -84.37416
     },
     {
       "latitude": 33.82054,
       "location_id": "loc24",
       "longitude": -84.23121
     },
     {
       "latitude": 33.83828,
       "location_id": "loc25",
       "longitude": -84.21402
     },
     {
       "latitude": 34.05614,
       "location_id": "loc26",
       "longitude": -84.31995
     },
     {
       "latitude": 33.7435386,
       "location_id": "loc27",
       "longitude": -84.6712
     },
     {
       "latitude": 33.99045,
       "location_id": "loc28",
       "longitude": -84.8082699
     },
     {
       "latitude": 33.84614,
       "location_id": "loc29",
       "longitude": -84.7469
     },
     {
       "latitude": 33.68736,
       "location_id": "loc30",
       "longitude": -84.23972
     },
     {
       "latitude": 33.7757999,
       "location_id": "loc31",
       "longitude": -84.3845599
     },
     {
       "latitude": 34.19941,
       "location_id": "loc32",
       "longitude": -84.1556
     },
     {
       "latitude": 33.75112,
       "location_id": "loc33",
       "longitude": -84.35911
     },
     {
       "latitude": 33.9854531,
       "location_id": "loc34",
       "longitude": -83.707189
     },
     {
       "latitude": 33.52079,
       "location_id": "loc35",
       "longitude": -84.36567
     },
     {
       "latitude": 34.104,
       "location_id": "loc36",
       "longitude": -84.2661811
     },
     {
       "latitude": 33.88826,
       "location_id": "loc37",
       "longitude": -84.20234
     },
     {
       "latitude": 33.4439,
       "location_id": "loc38",
       "longitude": -84.32034
     },
     {
       "latitude": 33.96681,
       "location_id": "loc39",
       "longitude": -84.23654
     },
     {
       "latitude": 34.1162,
       "location_id": "loc40",
       "longitude": -83.81919
     },
     {
       "latitude": 34.07697,
       "location_id": "loc99",
       "longitude": -85.0148499
     },
     {
       "latitude": 33.9157,
       "location_id": "loc100",
       "longitude": -84.52097
     }
   ],
   "vehicles": [
     {
       "vehicle_id": "Vehicle1",
       "shifts": [
         {
           "shift_start": "2017-08-24T08:05:00-04:00",
           "shift_id": "v1shift",
           "shift_end": "2017-08-24T17:10:00-04:00",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "start_location_id": "loc20",
           "end_location_id": "loc20"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle2",
       "shifts": [
         {
           "shift_start": "2017-08-24T10:05:00-04:00",
           "shift_id": "v2shift",
           "shift_end": "2017-08-24T15:10:00-04:00",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "start_location_id": "loc99",
           "end_location_id": "loc99"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle3",
       "shifts": [
         {
           "shift_start": "2017-08-24T07:05:00-04:00",
           "shift_id": "v3shift",
           "shift_end": "2017-08-24T13:10:00-04:00",
           "break_end": [
             "2017-08-24T10:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T09:00:00-04:00"
           ],
           "start_location_id": "loc16",
           "end_location_id": "loc16"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle4",
       "shifts": [
         {
           "shift_start": "2017-08-24T09:05:00-04:00",
           "shift_id": "v4shift",
           "shift_end": "2017-08-24T16:10:00-04:00",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "start_location_id": "loc100",
           "end_location_id": "loc100"
         }
       ]
     }
   ]
 }

imgOriginal solution with no First_Visit constraint.

imgWe add a first visit constraint for order id 674660, north of Stockbridg boxed in red. This changes the route for vehicle 1 significantly as it passes by many other stops on the way to its first stop far from the start and end location.


Last Visit — last_visit

Description

Ensure that each of the provided orders is the last stop in its route. If the shift associated with the route has a pre-determined end location, then each order must be the last stop visited before reaching the end location. Otherwise it must be the final stop that terminates the route.

Example

{
   "constraints": [
     {
       "violation_increment": 1,
       "constraint_type": "Travel_Time",
       "penalty_per_violation": 1,
       "constraint_name": "limit travel",
       "max_travel_time_seconds": 0
     },
     {
       "violation_increment": 1,
       "constraint_type": "Visit_Range",
       "constraint_name": "visit as many orders as possible",
       "penalty_per_violation": 10000
     },
     {
       "violation_increment": 1,
       "constraint_type": "Last_Visit",
       "order_ids": [
         "674660"
       ],
       "constraint_name": "visit 674660 as last stop on route",
       "penalty_per_violation": 10000
     }
   ],
   "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
     }
   ],
   "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"
     }
   ],
   "vehicles": [
     {
       "shifts": [
         {
           "shift_start": "2017-08-24T08:05:00-04:00",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_id": "v1shift",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "end_location_id": "loc20",
           "shift_end": "2017-08-24T17:10:00-04:00",
           "start_location_id": "loc20"
         }
       ],
       "vehicle_id": "Vehicle1"
     },
     {
       "shifts": [
         {
           "shift_start": "2017-08-24T10:05:00-04:00",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_id": "v2shift",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "end_location_id": "loc99",
           "shift_end": "2017-08-24T15:10:00-04:00",
           "start_location_id": "loc99"
         }
       ],
       "vehicle_id": "Vehicle2"
     },
     {
       "shifts": [
         {
           "shift_start": "2017-08-24T07:05:00-04:00",
           "break_start": [
             "2017-08-24T09:00:00-04:00"
           ],
           "shift_id": "v3shift",
           "break_end": [
             "2017-08-24T10:00:00-04:00"
           ],
           "end_location_id": "loc16",
           "shift_end": "2017-08-24T13:10:00-04:00",
           "start_location_id": "loc16"
         }
       ],
       "vehicle_id": "Vehicle3"
     },
     {
       "shifts": [
         {
           "shift_start": "2017-08-24T09:05:00-04:00",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_id": "v4shift",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ],
           "end_location_id": "loc100",
           "shift_end": "2017-08-24T16:10:00-04:00",
           "start_location_id": "loc100"
         }
       ],
       "vehicle_id": "Vehicle4"
     }
   ]
 }

imgOriginal 4 vehicle solution without the Last_Visit constraint

imgOrder 674660 north of Stockbridge must now be the last stop on the route. The green route for vehicle 1 is now quite inefficient as we visit other nearby stops earlier in the route but cannot visit this order until it is the last order visited in the route.


Max Distance — max_distance

Description

Typically in a routing problem with a sufficient number of orders to ensure “full” routes, a shift cannot visit any more orders since we pass the end of the shift time. However, in cases where there are limits on the mileage a vehicle can travel during the day or some other reason to be concerned about the distance traveled by a vehicle over the course of a single shift, the Max_Distance constraint can be used. This constraint ensures that the routes do not exceed a specified distance. Applies to all routes if specific shift_ids are not provided. If violation_increment is provided, then the units is in distance (meters).

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": "Max_Distance",
       "penalty_per_violation": 1,
       "violation_increment": 1,
       "constraint_name": "limit total distance to 150 miles (241,000 meters)",
       "max_distance": 241402
     }
   ],
   "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
     }
   ]
 }

imgThe four vehicle solution before adding the Max_Distance constraint.

img In the example we use a penalty of 1 and violation increment of 1 so that every meter a vehicle travels beyond the limit of 241,402 (150 miles) we are assessed a penalty of 1. All of the routes are now less than 150 miles in total distance traveled with the longest route at about 145 miles. We are now unable to visit all the orders since the increased distance necessary to visit the southernmost order would lead to more than 10,000 more meters traveled (10,000 is the magic number here since the visit range penalty is 10,000).


Home Radius — home_radius

Description

Make sure that stops on a route are all within either a certain travel time or certain distance from a specified “home location_id” for the shift. The “home_location_id” must be specified in the shift object.

Example

{
   "constraints": [
     {
       "violation_increment": 1,
       "max_travel_time_seconds": 0,
       "penalty_per_violation": 1,
       "constraint_name": "limit travel",
       "constraint_type": "Travel_Time"
     },
     {
       "violation_increment": 1,
       "penalty_per_violation": 10000,
       "constraint_name": "visit as many orders as possible",
       "constraint_type": "Visit_Range"
     },
     {
       "violation_increment": 1,
       "constraint_type": "Home_Radius",
       "penalty_per_violation": 100000,
       "constraint_name": "stay within radius",
       "max_travel_time": 2700
     }
   ],
   "locations": [
     {
       "latitude": 33.3300399,
       "location_id": "loc1",
       "longitude": -84.07639
     },
     {
       "latitude": 33.5179638,
       "location_id": "loc2",
       "longitude": -84.4153667
     },
     {
       "latitude": 34.07687,
       "location_id": "loc3",
       "longitude": -84.52763
     },
     {
       "latitude": 33.73872,
       "location_id": "loc4",
       "longitude": -85.15883
     },
     {
       "latitude": 34.02463,
       "location_id": "loc5",
       "longitude": -84.1256499
     },
     {
       "latitude": 33.78583,
       "location_id": "loc6",
       "longitude": -84.30268
     },
     {
       "latitude": 34.07687,
       "location_id": "loc7",
       "longitude": -84.5738499
     },
     {
       "latitude": 33.98557,
       "location_id": "loc8",
       "longitude": -83.7661399
     },
     {
       "latitude": 34.02403,
       "location_id": "loc9",
       "longitude": -84.69128
     },
     {
       "latitude": 33.57832,
       "location_id": "loc11",
       "longitude": -84.26431
     },
     {
       "latitude": 33.56882,
       "location_id": "loc12",
       "longitude": -84.51451
     },
     {
       "latitude": 33.8200999,
       "location_id": "loc13",
       "longitude": -84.30606
     },
     {
       "latitude": 33.98078,
       "location_id": "loc14",
       "longitude": -84.02126
     },
     {
       "latitude": 33.98596,
       "location_id": "loc15",
       "longitude": -84.20871
     },
     {
       "latitude": 34.098671,
       "location_id": "loc16",
       "longitude": -83.789905
     },
     {
       "latitude": 33.68959,
       "location_id": "loc17",
       "longitude": -84.3739
     },
     {
       "latitude": 33.8965699,
       "location_id": "loc18",
       "longitude": -84.08495
     },
     {
       "latitude": 34.0078,
       "location_id": "loc19",
       "longitude": -84.5491
     },
     {
       "latitude": 33.44852,
       "location_id": "loc20",
       "longitude": -84.78468
     },
     {
       "latitude": 33.45099,
       "location_id": "loc21",
       "longitude": -84.7372199
     },
     {
       "latitude": 33.7084199,
       "location_id": "loc22",
       "longitude": -84.44377
     },
     {
       "latitude": 34.0286,
       "location_id": "loc23",
       "longitude": -84.37416
     },
     {
       "latitude": 33.82054,
       "location_id": "loc24",
       "longitude": -84.23121
     },
     {
       "latitude": 33.83828,
       "location_id": "loc25",
       "longitude": -84.21402
     },
     {
       "latitude": 34.05614,
       "location_id": "loc26",
       "longitude": -84.31995
     },
     {
       "latitude": 33.7435386,
       "location_id": "loc27",
       "longitude": -84.6712
     },
     {
       "latitude": 33.99045,
       "location_id": "loc28",
       "longitude": -84.8082699
     },
     {
       "latitude": 33.84614,
       "location_id": "loc29",
       "longitude": -84.7469
     },
     {
       "latitude": 33.68736,
       "location_id": "loc30",
       "longitude": -84.23972
     },
     {
       "latitude": 33.7757999,
       "location_id": "loc31",
       "longitude": -84.3845599
     },
     {
       "latitude": 34.19941,
       "location_id": "loc32",
       "longitude": -84.1556
     },
     {
       "latitude": 33.75112,
       "location_id": "loc33",
       "longitude": -84.35911
     },
     {
       "latitude": 33.9854531,
       "location_id": "loc34",
       "longitude": -83.707189
     },
     {
       "latitude": 33.52079,
       "location_id": "loc35",
       "longitude": -84.36567
     },
     {
       "latitude": 34.104,
       "location_id": "loc36",
       "longitude": -84.2661811
     },
     {
       "latitude": 33.88826,
       "location_id": "loc37",
       "longitude": -84.20234
     },
     {
       "latitude": 33.4439,
       "location_id": "loc38",
       "longitude": -84.32034
     },
     {
       "latitude": 33.96681,
       "location_id": "loc39",
       "longitude": -84.23654
     },
     {
       "latitude": 34.1162,
       "location_id": "loc40",
       "longitude": -83.81919
     },
     {
       "latitude": 34.07697,
       "location_id": "loc99",
       "longitude": -85.0148499
     },
     {
       "latitude": 33.9157,
       "location_id": "loc100",
       "longitude": -84.52097
     }
   ],
   "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
     }
   ],
   "vehicles": [
     {
       "vehicle_id": "Vehicle1",
       "shifts": [
         {
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "break_end": [
             "2017-08-24T13: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",
           "home_location_id": "loc20"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle2",
       "shifts": [
         {
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "break_end": [
             "2017-08-24T13: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",
           "home_location_id": "loc99"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle3",
       "shifts": [
         {
           "break_start": [
             "2017-08-24T09:00:00-04:00"
           ],
           "break_end": [
             "2017-08-24T10: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",
           "home_location_id": "loc16"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle4",
       "shifts": [
         {
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "break_end": [
             "2017-08-24T13: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",
           "home_location_id": "loc100"
         }
       ]
     }
   ]
 }

imgOriginal 4 vehicle solution without the home radius constraint.

img We add a home radius constraint for all vehicles so that the routes are penalized if the vehicle is more than 45 minutes (2700 seconds) from the home location of the vehicle. It is now not possible to visit 4 of the orders – some are too far away from any vehicle’s home location, and since we have less freedom in assigning stops to routes we cannot find room in some routes for stops that could be otherwise visited. In particular, order #10 on the green route (boxed in red) now moves to a different route than in the original solution at the cost of adding travel time. This is because this location is more than 45 minutes from the home location of the blue Vehicle #1.


Num Stops — num_stops

Description

API Name: Num_Stops

This constraint controls the number of stops on each route to encourage between min_stops and max_stops stops in the route. Note that if start location or end location are pre-determined for the shift corresponding to this route, then these are not counted as stops in this computation. In other words, the constraint only considers “active stops”. In the event that a route has a number of stops outside this range, then the violation increment is computed in terms of stops. For example, if a route has 5 stops and the constraint specifies min_stops = 10 with a penalty of 10,000 and a violation_increment of 1, then the total penalty would be 10,000 + (10-5)*10,000 = 60,000.

Example

{
   "constraints": [
     {
       "violation_increment": 1,
       "constraint_name": "limit travel",
       "max_travel_time_seconds": 0,
       "penalty_per_violation": 1,
       "constraint_type": "Travel_Time"
     },
     {
       "violation_increment": 1,
       "constraint_name": "visit as many orders as possible",
       "penalty_per_violation": 10000,
       "constraint_type": "Visit_Range"
     },
     {
       "violation_increment": 1,
       "min_stops": 5,
       "max_stops": 9,
       "constraint_name": "Between 5 and 9 stops on all routes",
       "constraint_type": "Num_Stops",
       "penalty_per_violation": 10000
     }
   ],
   "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",
       "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"
     }
   ],
   "vehicles": [
     {
       "vehicle_id": "Vehicle1",
       "shifts": [
         {
           "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"
           ],
           "end_location_id": "loc20",
           "start_location_id": "loc20",
           "shift_id": "v1shift"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle2",
       "shifts": [
         {
           "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"
           ],
           "end_location_id": "loc99",
           "start_location_id": "loc99",
           "shift_id": "v2shift"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle3",
       "shifts": [
         {
           "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"
           ],
           "end_location_id": "loc16",
           "start_location_id": "loc16",
           "shift_id": "v3shift"
         }
       ]
     },
     {
       "vehicle_id": "Vehicle4",
       "shifts": [
         {
           "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"
           ],
           "end_location_id": "loc100",
           "start_location_id": "loc100",
           "shift_id": "v4shift"
         }
       ]
     }
   ]
 }

imgOriginal solution with no Num_Stops constraint. The green route visits only 4 orders, and the blue route visits only 5 while the red route visits 15 orders.

imgThe constraint specifies that the routes should be more balanced – between 5-9 stops on all routes (excluding the start and end locations). The result is an increase in travel time, but much more balanced routes in terms of the number of stops. Vehicle 2 (upper left) now visits 6 orders as opposed to 4 in the previous solution. Vehicle 1 (bottom route) now visits only 9 orders versus 15 in the solution without this constraint.


Shift Duration — shift_duration

Description

This constraint allows us to prevent shifts from lasting more than a specified duration (max_seconds). Each shift already has a fixed starting time and ending time, and our solutions will never produce routes that extend past this ending time. However, in some cases (such as paid overtime) we may want to encourage shifts to end earlier than this fixed ending time if possible. This constraint can apply to all shifts or to specific shifts if the shift_ids array is populated.

{
   "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": "Shift_Duration",
       "penalty_per_violation": 10000,
       "violation_increment": 600,
       "max_seconds": 10800, 
       "shift_ids": ["v1shift"],
       "constraint_name": "limit v1shift length to 3 hours"
     }
   ],
   "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 Shift_Duration constraint.

img Suppose that vehicle 1 (pink bottom route) is operated by a contractor that is more expensive than operating the other vehicles. We restrict the duration of vehicle 1 to 10,800 seconds with the shift duration constraint. Since this penalty is the same as the penalty for the visit range constraint, and since we have a violation increment of 600 seconds, the optimization chooses to shorten this shift to <= 3 hours instead of adding more orders to the route. The result is that vehicle 1 now works for 173 minutes visiting only 4 orders. The other vehicles pick up the slack, but there are 3 unrouted orders.


Maximum Segment Distance or Time — max_segment_distance/time

Description

If more compact routes with shorter travel times and/or shorter distances between stops is desired, then these two constraint allow you to penalize long segments in the solution. The idea behind both constraints is similar: penalize segments in the solution that exceed either a certain distance or travel time. The example below utilizes Max_Segment_Distance and can be trivially modified to exercise Max_Segment_Time.

{
   "constraints": [
     {
       "constraint_name": "limit travel",
       "max_travel_time_seconds": 0,
       "constraint_type": "Travel_Time",
       "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": "Avoid routes that have max segment longer than 20km",
       "max_distance": 20000,
       "constraint_type": "Max_Segment_Distance",
       "violation_increment": 100,
       "penalty_per_violation": 5000
     }
   ],
   "vehicles": [
     {
       "shifts": [
         {
           "end_location_id": "loc20",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T08:05:00-04:00",
           "shift_end": "2017-08-24T17:10:00-04:00",
           "shift_id": "v1shift",
           "start_location_id": "loc20",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ]
         }
       ],
       "vehicle_id": "Vehicle1"
     },
     {
       "shifts": [
         {
           "end_location_id": "loc99",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T10:05:00-04:00",
           "shift_end": "2017-08-24T15:10:00-04:00",
           "shift_id": "v2shift",
           "start_location_id": "loc99",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ]
         }
       ],
       "vehicle_id": "Vehicle2"
     },
     {
       "shifts": [
         {
           "end_location_id": "loc16",
           "break_start": [
             "2017-08-24T09:00:00-04:00"
           ],
           "shift_start": "2017-08-24T07:05:00-04:00",
           "shift_end": "2017-08-24T13:10:00-04:00",
           "shift_id": "v3shift",
           "start_location_id": "loc16",
           "break_end": [
             "2017-08-24T10:00:00-04:00"
           ]
         }
       ],
       "vehicle_id": "Vehicle3"
     },
     {
       "shifts": [
         {
           "end_location_id": "loc100",
           "break_start": [
             "2017-08-24T12:00:00-04:00"
           ],
           "shift_start": "2017-08-24T09:05:00-04:00",
           "shift_end": "2017-08-24T16:10:00-04:00",
           "shift_id": "v4shift",
           "start_location_id": "loc100",
           "break_end": [
             "2017-08-24T13:00:00-04:00"
           ]
         }
       ],
       "vehicle_id": "Vehicle4"
     }
   ],
   "orders": [
     {
       "duration": 600,
       "order_id": "688798",
       "location_id": "loc1"
     },
     {
       "duration": 600,
       "order_id": "689105",
       "location_id": "loc3"
     },
     {
       "duration": 1800,
       "order_id": "692039",
       "location_id": "loc5"
     },
     {
       "duration": 600,
       "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"
     }
   ],
   "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"
     }
   ]
 }

imgOriginal four vehicle solution with no penalties for long segments.

imgSolution after penalizing segments that exceed 20km. Note that two orders are not visited (Cumming in the north, Locust Grove in the south) since the segments in and out of these locations far exceed 20km and the penalty assessed for adding the required long segments exceeds the penalty for not visiting them. So the trade off here is to accept a Visit_Range penalty of 10,000. Additionally, note the changes in the pink northwest route versus the first solution. The Lithia Springs stop is now moved to another route to avoid the very long segment to return to the start location near Taylorsville (the northwestern most stop).


Max Commute — max_commute

Description

Encourage the first and/or last stops on a route to be within a specified travel time or travel distance of a pre-specified home location. This constraint is useful in cases where a worker’s day begins at the first stop on a route, but you also want to account for the leg to/from the home address. For this constraint, a home_location_id must be specified for each shift, as in the Home Radiusconstraint. Either a maximum allowed travel time (in seconds) or travel distance (in meters), and booleans for start_leg and end_leg allow the user to penalize the time/distance between the home_location and the start and/or end of the route. For this constraint to be effective, the user should specify shifts that do not include a forced start or end by ommitting the start_location_id and end_location_id parameters in the shift object.

Example

Below are the routes for a problem where we allow all shifts to be “open” by not specifying any start or end location_ids in the shifts

imgSolution to the problem when optimization determines the ideal start and end of the routes. Note the large distance between the start and end of each route, particularly the green southern route.

In the example request below, we use the Max_Commute constraint with a max_travel_time of 600 seconds and add home_location_ids for each shift.

{
  "constraints": [
    {
      "max_travel_time_seconds": 0,
      "constraint_name": "limit travel",
      "violation_increment": 1,
      "penalty_per_violation": 1,
      "constraint_type": "Travel_Time"
    },
    {
      "constraint_name": "visit as many orders as possible",
      "violation_increment": 1,
      "penalty_per_violation": 10000,
      "constraint_type": "Visit_Range"
    },
    {
      "last_leg": true,
      "penalty_per_violation": 10000,
      "first_leg": true,
      "max_travel_time": 600,
      "constraint_type": "Max_Commute",
      "violation_increment": 300,
      "constraint_name": "Limit commute first_leg and last_leg travel time to 600 seconds"
    }
  ],
  "locations": [
    {
      "longitude": -84.837526,
      "location_id": "Westfork",
      "latitude": 34.005283
    },
    {
      "longitude": -84.266107,
      "location_id": "Crooked Creek Club",
      "latitude": 34.130226
    },
    {
      "longitude": -84.230241,
      "location_id": "Pointe Bleue",
      "latitude": 33.685778
    },
    {
      "longitude": -84.670506,
      "location_id": "Campbellton",
      "latitude": 33.648642
    },
    {
      "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": [
    {
      "location_id": "loc1",
      "duration": 600,
      "order_id": "688798"
    },
    {
      "location_id": "loc3",
      "duration": 600,
      "order_id": "689105"
    },
    {
      "location_id": "loc5",
      "duration": 1800,
      "order_id": "692039"
    },
    {
      "location_id": "loc6",
      "duration": 600,
      "order_id": "583368"
    },
    {
      "location_id": "loc7",
      "duration": 600,
      "order_id": "677048"
    },
    {
      "location_id": "loc8",
      "duration": 600,
      "order_id": "685086"
    },
    {
      "location_id": "loc9",
      "duration": 600,
      "order_id": "690020"
    },
    {
      "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"
    }
  ],
  "vehicles": [
    {
      "shifts": [
        {
          "break_end": [
            "2017-08-24T13:00:00-04:00"
          ],
          "shift_start": "2017-08-24T08:05:00-04:00",
          "break_start": [
            "2017-08-24T12:00:00-04:00"
          ],
          "shift_end": "2017-08-24T17:10:00-04:00",
          "shift_id": "v1 shift - Westfork home",
		  "home_location_id": "Westfork"
        }
      ],
      
      "vehicle_id": "Vehicle1"
    },
    {
      "shifts": [
        {
          "break_end": [
            "2017-08-24T13:00:00-04:00"
          ],
          "shift_start": "2017-08-24T10:05:00-04:00",
          "break_start": [
            "2017-08-24T12:00:00-04:00"
          ],
          "shift_end": "2017-08-24T15:10:00-04:00",
          "shift_id": "v2 shift - Crooked Creek home",
		  "home_location_id": "Crooked Creek Club"
        }
      ],
      
      "vehicle_id": "Vehicle2"
    },
    {
      "shifts": [
        {
          "break_end": [
            "2017-08-24T10:00:00-04:00"
          ],
          "shift_start": "2017-08-24T07:05:00-04:00",
          "break_start": [
            "2017-08-24T09:00:00-04:00"
          ],
          "shift_end": "2017-08-24T13:10:00-04:00",
          "shift_id": "v3 shift - Pointe Bleue",
		  "home_location_id": "Pointe Bleue"
        }
      ],
      "vehicle_id": "Vehicle3"
    },
    {
      "shifts": [
        {
          "break_end": [
            "2017-08-24T13:00:00-04:00"
          ],
          "shift_start": "2017-08-24T09:05:00-04:00",
          "break_start": [
            "2017-08-24T12:00:00-04:00"
          ],
          "shift_end": "2017-08-24T16:10:00-04:00",
          "shift_id": "v4 shift - Campbellton",
		  "home_location_id": "Campbellton"  
        }
      ],
      "vehicle_id": "Vehicle4"
    }
  ]
}

imgWith the Max_Commute constraint, the three routes now all travel in a big “loop” and end up much closer to where they started. The constraint is still violated as there are not actually any orders within 10 minutes of the home location for some shifts. For example, the green route has a home location in Campbellton, GA and the shift starts and ends at the two closest orders to Campbellton. This additional restriction on the start and end locations of the routes leads to an increase of about 150 minutes of total travel time versus the first solution.