Multiple Vehicles, Multiple Shifts

Subsequent examples focus on multiple vehicles servicing orders over a longer planning horizon consisting of multiple shifts (typically a shift is a day but it can be longer if desired). Each vehicle can have its own shifts so that vehicles can be operating during the same planning period or different periods. This can be useful when different vehicles are available on different days due to vehicle maintenance or employee availability.

Multiple Vehicle, Multiple Shifts with Visit Gaps

When routing across multiple days in multiple vehicles, you may often have some orders that require periodic visits. Rather than specifying a separate order for each visit, MARE allows you to specify a single order that has requirements for multiple visits. The Visit Range constraint allows you to ensure the correct number of visits across the planning period. Additionally, since orders should generally be spaced out over the planning period, the Visit_Gap constraint provides control over how much time separates one visit from the next. These constraints operate at the order level regardless of which vehicle visits the order.

Back to our example of Jimmy and Sally’s expanding business in the DC Metro Area, based on their great success in matching the right worker for the right job at the embassies, they have now obtained contracts for cleaning the embassies along with the other work. The various embassies have different requirements for how often the service should occur. They will operate on a weekly cycle with the visit count requirements and visit spacing requirements now incorporated into the orders

Orders: All of the orders now receive a value of min_visits – the minimum number of times we must visit them in the solution to the routing problem. This is enforced via the Visit_Range constraint. Since all these orders must now be visited multiple times, the desired spacing of visits is expressed with min_days and max_days – the minimum and maximum number of days between service events. This spacing is enforced via the Visit_Gap constraint. Also note that we add a few additional locations and orders to make sure the fleet has enough work to remain busy on most days.

Constraints: Since the Visit_Range is present in all examples to achieve the default min_visits of 1, the only addition is the Visit_Gap constraint. This constraint references the data present in each order object.

Input (JSON)

{
   "constraints": [
     {
       "constraint_type": "Travel_Time",
       "max_travel_time_seconds": 0,
       "penalty_per_violation": 1,
       "constraint_name": "Minimize travel time",
       "violation_increment": 1
     },
     {
       "constraint_type": "Visit_Range",
       "penalty_per_violation": 10000,
       "constraint_name": "Visit all orders",
       "violation_increment": 1
     },
     {
       "constraint_type": "Match_Attributes",
       "penalty_per_violation": 50000,
       "constraint_name": "Assign correct resources"
     },
     {
       "constraint_type": "Visit_Gap",
       "penalty_per_violation": 5000,
       "constraint_name": "Space visits correctly",
       "violation_increment": 1
     }
   ],
   "orders": [
     {
       "min_days": 2,
       "order_id": "Service Washington Monument",
       "min_visits": 3,
       "location_id": "Washington Monument",
       "duration": 3600
     },
     {
       "min_days": 2,
       "order_id": "Service Fords Theatre",
       "min_visits": 3,
       "location_id": "Fords Theater",
       "duration": 3600
     },
     {
       "min_days": 2,
       "order_id": "Service the Abe Lincoln Memorial",
       "min_visits": 2,
       "location_id": "Lincoln Memorial",
       "duration": 3600
     },
     {
       "min_days": 2,
       "order_id": "Service the Vietnam Memorial",
       "min_visits": 3,
       "location_id": "Vietnam Memorial",
       "duration": 3600
     },
     {
       "min_days": 1,
       "order_id": "Service the Thomas Jefferson Memorial",
       "min_visits": 4,
       "location_id": "Thomas Jefferson Memorial",
       "duration": 7200
     },
     {
       "order_id": "Service Ravens Stadium",
       "min_visits": 1,
       "location_id": "Ravens Stadium",
       "duration": 10000
     },
     {
       "min_days": 1,
       "min_visits": 4,
       "attributes": [
         "Speaks German"
       ],
       "order_id": "Service Austrian Embassy",
       "location_id": "Austrian Embassy",
       "duration": 1800
     },
     {
       "min_days": 1,
       "order_id": "Service Dutch Embassy",
       "min_visits": 4,
       "location_id": "Dutch Embassy",
       "duration": 1800
     },
     {
       "min_days": 1,
       "min_visits": 4,
       "attributes": [
         "Speaks Finnish"
       ],
       "order_id": "Service Finnish Embassy",
       "location_id": "Finnish Embassy",
       "duration": 1800
     },
     {
       "min_days": 2,
       "min_visits": 3,
       "attributes": [
         "Speaks Russian"
       ],
       "order_id": "Service Russian Embassy",
       "location_id": "Russian Embassy",
       "duration": 1800
     },
     {
       "min_days": 2,
       "order_id": "Service Ugandan Embassy",
       "min_visits": 2,
       "location_id": "Ugandan Embassy",
       "duration": 1800
     },
     {
       "order_id": "Service South African Embassy",
       "location_id": "South African Embassy",
       "duration": 1800
     },
     {
       "min_days": 1,
       "min_visits": 3,
       "attributes": [
         "Speaks Chinese"
       ],
       "order_id": "Service Chinese Embassy",
       "location_id": "Chinese Embassy",
       "duration": 1800
     },
     {
       "min_days": 1,
       "order_id": "Service New Zealand Embassy",
       "min_visits": 5,
       "location_id": "New Zealand Embassy",
       "duration": 1800
     },
     {
       "min_days": 1,
       "order_id": "Service Belgian Embassy",
       "min_visits": 3,
       "location_id": "Belgian Embassy",
       "duration": 1800
     },
     {
       "min_days": 2,
       "min_visits": 2,
       "attributes": [
         "Speaks German"
       ],
       "order_id": "Service Czech Embassy",
       "location_id": "Czech Embassy",
       "duration": 1800
     },
     {
       "order_id": "Service Nationals Park",
       "location_id": "Washington Nationals Park",
       "min_days": 3,
       "min_visits": 2,
       "duration": 5000
     },
     {
       "order_id": "Service Camden Yards",
       "location_id": "Camden Yards",
       "min_days": 2,
       "min_visits": 2,
       "duration": 5000
     },
     {
       "order_id": "Service Kastles",
       "location_id": "Washington Kastles",
       "min_days": 4,
       "min_visits": 2,
       "duration": 5000
     }
   ],
   "locations": [
     {
       "longitude": -77.0502,
       "location_id": "Lincoln Memorial",
       "latitude": 38.8893
     },
     {
       "longitude": -77.035278,
       "location_id": "Washington Monument",
       "latitude": 38.889484
     },
     {
       "longitude": -77.0257,
       "location_id": "Fords Theater",
       "latitude": 38.8967
     },
     {
       "longitude": -77.0477,
       "location_id": "Vietnam Memorial",
       "latitude": 38.8913
     },
     {
       "longitude": -77.0365,
       "location_id": "Thomas Jefferson Memorial",
       "latitude": 38.8814
     },
     {
       "longitude": -76.6227,
       "location_id": "Ravens Stadium",
       "latitude": 39.278
     },
     {
       "longitude": -76.965838,
       "location_id": "Hotel 1",
       "latitude": 39.064295
     },
     {
       "longitude": -77.073894,
       "location_id": "Hotel 2",
       "latitude": 38.89353
     },
     {
       "longitude": -76.971345,
       "location_id": "Hotel 3",
       "latitude": 38.91681
     },
     {
       "longitude": -76.491,
       "location_id": "Sushi Restaurant",
       "latitude": 38.9779
     },
     {
       "longitude": -77.0365,
       "location_id": "White House",
       "latitude": 38.8977
     },
     {
       "longitude": -77.069283,
       "location_id": "Austrian Embassy",
       "latitude": 38.945537
     },
     {
       "longitude": -77.05631,
       "location_id": "Dutch Embassy",
       "latitude": 38.944703
     },
     {
       "longitude": -77.065206,
       "location_id": "Finnish Embassy",
       "latitude": 38.924491
     },
     {
       "longitude": -77.047148,
       "location_id": "Indian Embassy",
       "latitude": 38.911767
     },
     {
       "longitude": -77.060694,
       "location_id": "South African Embassy",
       "latitude": 38.920472
     },
     {
       "longitude": -77.053957,
       "location_id": "Czech Embassy",
       "latitude": 38.939997
     },
     {
       "longitude": -77.036025,
       "location_id": "Ugandan Embassy",
       "latitude": 38.961255
     },
     {
       "longitude": -77.074448,
       "location_id": "Russian Embassy",
       "latitude": 38.924126
     },
     {
       "longitude": -77.064188,
       "location_id": "New Zealand Embassy",
       "latitude": 38.919233
     },
     {
       "longitude": -77.065921,
       "location_id": "Belgian Embassy",
       "latitude": 38.927324
     },
     {
       "longitude": -77.070191,
       "location_id": "Chinese Embassy",
       "latitude": 38.919481
     },
     {
       "longitude": -77.0074,
       "location_id": "Washington Nationals Park",
       "latitude": 38.8730
     },
     {
       "longitude": -76.619664188,
       "location_id": "Camden Yards",
       "latitude": 39.283665532 
     },
     {
       "longitude":  -77.020513,
       "location_id": "Washington Kastles",
       "latitude": 38.896871
     }
   ],
   "vehicles": [
     {
       "attributes": [
         "Speaks German",
         "Speaks Chinese"
       ],
       "shifts": [
         {
           "shift_start": "2018-10-01T08:30:00-04:00",
           "break_end": [
             "2018-10-01T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 1",
           "shift_id": "Crew 1; Shift 1",
           "shift_end": "2018-10-01T17:00:00-04:00",
           "break_start": [
             "2018-10-01T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 1"
         },
         {
           "shift_start": "2018-10-02T08:30:00-04:00",
           "break_end": [
             "2018-10-02T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 1",
           "shift_id": "Crew 1; Shift 2",
           "shift_end": "2018-10-02T17:00:00-04:00",
           "break_start": [
             "2018-10-02T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 1"
         },
         {
           "shift_start": "2018-10-03T08:30:00-04:00",
           "break_end": [
             "2018-10-03T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 1",
           "shift_id": "Crew 1; Shift 3",
           "shift_end": "2018-10-03T17:00:00-04:00",
           "break_start": [
             "2018-10-03T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 1"
         },
         {
           "shift_start": "2018-10-04T08:30:00-04:00",
           "break_end": [
             "2018-10-04T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 1",
           "shift_id": "Crew 1; Shift 4",
           "shift_end": "2018-10-04T17:00:00-04:00",
           "break_start": [
             "2018-10-04T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 1"
         },
         {
           "shift_start": "2018-10-05T08:30:00-04:00",
           "break_end": [
             "2018-10-05T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 1",
           "shift_id": "Crew 1; Shift 5",
           "shift_end": "2018-10-05T17:00:00-04:00",
           "break_start": [
             "2018-10-05T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 1"
         }
       ],
       "type": "car",
       "vehicle_id": "Crew 1"
     },
     {
       "attributes": [
         "Speaks German",
         "Speaks Russian"
       ],
       "shifts": [
         {
           "shift_start": "2018-10-01T08:30:00-04:00",
           "break_end": [
             "2018-10-01T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 2",
           "shift_id": "Crew 2; Shift 1",
           "shift_end": "2018-10-01T17:00:00-04:00",
           "break_start": [
             "2018-10-01T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 2"
         },
         {
           "shift_start": "2018-10-02T08:30:00-04:00",
           "break_end": [
             "2018-10-02T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 2",
           "shift_id": "Crew 2; Shift 2",
           "shift_end": "2018-10-02T17:00:00-04:00",
           "break_start": [
             "2018-10-02T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 2"
         },
         {
           "shift_start": "2018-10-03T08:30:00-04:00",
           "break_end": [
             "2018-10-03T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 2",
           "shift_id": "Crew 2; Shift 3",
           "shift_end": "2018-10-03T17:00:00-04:00",
           "break_start": [
             "2018-10-03T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 2"
         },
         {
           "shift_start": "2018-10-04T08:30:00-04:00",
           "break_end": [
             "2018-10-04T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 2",
           "shift_id": "Crew 2; Shift 4",
           "shift_end": "2018-10-04T17:00:00-04:00",
           "break_start": [
             "2018-10-04T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 2"
         },
         {
           "shift_start": "2018-10-05T08:30:00-04:00",
           "break_end": [
             "2018-10-05T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 2",
           "shift_id": "Crew 2; Shift 5",
           "shift_end": "2018-10-05T17:00:00-04:00",
           "break_start": [
             "2018-10-05T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 2"
         }
       ],
       "type": "car",
       "vehicle_id": "Crew 2"
     },
     {
       "attributes": [
         "Speaks Finnish"
       ],
       "shifts": [
         {
           "shift_start": "2018-10-01T08:30:00-04:00",
           "break_end": [
             "2018-10-01T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 3",
           "shift_id": "Crew 3; Shift 1",
           "shift_end": "2018-10-01T17:00:00-04:00",
           "break_start": [
             "2018-10-01T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 3"
         },
         {
           "shift_start": "2018-10-02T08:30:00-04:00",
           "break_end": [
             "2018-10-02T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 3",
           "shift_id": "Crew 3; Shift 2",
           "shift_end": "2018-10-02T17:00:00-04:00",
           "break_start": [
             "2018-10-02T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 3"
         },
         {
           "shift_start": "2018-10-03T08:30:00-04:00",
           "break_end": [
             "2018-10-03T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 3",
           "shift_id": "Crew 3; Shift 3",
           "shift_end": "2018-10-03T17:00:00-04:00",
           "break_start": [
             "2018-10-03T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 3"
         },
         {
           "shift_start": "2018-10-04T08:30:00-04:00",
           "break_end": [
             "2018-10-04T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 3",
           "shift_id": "Crew 3; Shift 4",
           "shift_end": "2018-10-04T17:00:00-04:00",
           "break_start": [
             "2018-10-04T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 3"
         },
         {
           "shift_start": "2018-10-05T08:30:00-04:00",
           "break_end": [
             "2018-10-05T13:00:00-04:00"
           ],
           "start_location_id": "Hotel 3",
           "shift_id": "Crew 3; Shift 5",
           "shift_end": "2018-10-05T17:00:00-04:00",
           "break_start": [
             "2018-10-05T12:00:00-04:00"
           ],
           "end_location_id": "Hotel 3"
         }
       ],
       "type": "car",
       "vehicle_id": "Crew 3"
     }
   ]
 }
Part of the solution for the multi-shift, multi-vehicle problem. We now have 15 total routes (3 vehicles, 5 days each), so it is difficult to make sense of all days and all vehicles at once. Each vehicle is active on all 5 days except for Vehicle 2 on Day 2 and Vehicle 3 on Day 4
Day 1 of the solution when all 3 vehicles are active.