Multiple Vehicles, Single Shift

Jimmy and Sally have been wildly successful and have new contracts with a few embassies in and around Washington, DC. Unfortunately these embassies require native speakers of their respective languages, and so they also had to hire some new crew members. Luckily they were able to hire some linguistic geniuses that speak several languages. The examples below illustrate how MARE can handle multiple vehicles on the same day and also match attributes so that the right vehicle services certain orders. This capability can be useful in a variety of “skill matching” use cases.

  • Vehicles: The vehicles can have shifts that are completely independent from the other vehicles in terms of their start/end location and start/end times. Additionally, we can associate attributes with each vehicle and then force attribute matching with constraints. In this example, the vehicles will all be operating on the same day with same shift times. Note that an individual vehicle cannot have shifts that overlap.
  • Constraints: We will make use of the Match_Attributes constraint in this example to illustrate skill/vehicle matching with various orders.
  • Orders: We have some new orders in DC at various embassies. We associate attributes with each order using arbitrary strings.

Input (JSON)

{
  "vehicles": [
    {
      "attributes": [
        "Speaks German",
        "Speaks Chinese"
      ],
      "vehicle_id": "Crew 1",
      "shifts": [
        {
          "end_location_id": "Hotel",
          "break_start": [
            "2018-10-01T12:00:00-04:00"
          ],
          "shift_end": "2018-10-01T17:00:00-04:00",
          "shift_start": "2018-10-01T08:30:00-04:00",
          "break_end": [
            "2018-10-01T13:00:00-04:00"
          ],
          "shift_id": "Crew 1; Shift 1",
          "start_location_id": "Hotel"
        }
      ],
      "type": "car"
    },
    {
      "attributes": [
        "Speaks German",
        "Speaks Russian"
      ],
      "vehicle_id": "Crew 2",
      "shifts": [
        {
          "end_location_id": "Hotel",
          "break_start": [
            "2018-10-01T12:00:00-04:00"
          ],
          "shift_end": "2018-10-01T17:00:00-04:00",
          "shift_start": "2018-10-01T08:30:00-04:00",
          "break_end": [
            "2018-10-01T13:00:00-04:00"
          ],
          "shift_id": "Crew 2; Shift 1",
          "start_location_id": "Hotel"
        }
      ],
      "type": "car"
    },
    {
      "attributes": [
        "Speaks Finnish"
      ],
      "vehicle_id": "Crew 3",
      "shifts": [
        {
          "end_location_id": "Hotel",
          "break_start": [
            "2018-10-01T12:00:00-04:00"
          ],
          "shift_end": "2018-10-01T17:00:00-04:00",
          "shift_start": "2018-10-01T08:30:00-04:00",
          "break_end": [
            "2018-10-01T13:00:00-04:00"
          ],
          "shift_id": "Crew 3; Shift 1",
          "start_location_id": "Hotel"
        }
      ],
      "type": "car"
    }
  ],
  "locations": [
    {
      "latitude": 38.8893,
      "longitude": -77.0502,
      "location_id": "Lincoln Memorial"
    },
    {
      "latitude": 38.889484,
      "longitude": -77.035278,
      "location_id": "Washington Monument"
    },
    {
      "latitude": 38.8967,
      "longitude": -77.0257,
      "location_id": "Fords Theater"
    },
    {
      "latitude": 38.8913,
      "longitude": -77.0477,
      "location_id": "Vietnam Memorial"
    },
    {
      "latitude": 38.8814,
      "longitude": -77.0365,
      "location_id": "Thomas Jefferson Memorial"
    },
    {
      "latitude": 39.278,
      "longitude": -76.6227,
      "location_id": "Ravens Stadium"
    },
    {
      "latitude": 39.064295,
      "longitude": -76.965838,
      "location_id": "Hotel"
    },
    {
      "latitude": 38.9779,
      "longitude": -76.491,
      "location_id": "Sushi Restaurant"
    },
    {
      "latitude": 38.8977,
      "longitude": -77.0365,
      "location_id": "White House"
    },
    {
      "latitude": 38.945537,
      "longitude": -77.069283,
      "location_id": "Austrian Embassy"
    },
    {
      "latitude": 38.944703,
      "longitude": -77.05631,
      "location_id": "Dutch Embassy"
    },
    {
      "latitude": 38.924491,
      "longitude": -77.065206,
      "location_id": "Finnish Embassy"
    },
    {
      "latitude": 38.911767,
      "longitude": -77.047148,
      "location_id": "Indian Embassy"
    },
    {
      "latitude": 38.920472,
      "longitude": -77.060694,
      "location_id": "South African Embassy"
    },
    {
      "latitude": 38.939997,
      "longitude": -77.053957,
      "location_id": "Czech Embassy"
    },
    {
      "latitude": 38.961255,
      "longitude": -77.036025,
      "location_id": "Ugandan Embassy"
    },
    {
      "latitude": 38.924126,
      "longitude": -77.074448,
      "location_id": "Russian Embassy"
    },
    {
      "latitude": 38.919233,
      "longitude": -77.064188,
      "location_id": "New Zealand Embassy"
    },
    {
      "latitude": 38.927324,
      "longitude": -77.065921,
      "location_id": "Belgian Embassy"
    },
    {
      "latitude": 38.919481,
      "longitude": -77.070191,
      "location_id": "Chinese Embassy"
    }
  ],
  "orders": [
    {
      "duration": 3600,
      "order_id": "Service Washington Monument",
      "location_id": "Washington Monument"
    },
    {
      "duration": 3600,
      "order_id": "Service Fords Theatre",
      "location_id": "Fords Theater"
    },
    {
      "duration": 3600,
      "order_id": "Service the Abe Lincoln Memorial",
      "location_id": "Lincoln Memorial"
    },
    {
      "duration": 3600,
      "order_id": "Service the Vietnam Memorial",
      "location_id": "Vietnam Memorial"
    },
    {
      "duration": 7200,
      "order_id": "Service the Thomas Jefferson Memorial",
      "location_id": "Thomas Jefferson Memorial"
    },
    {
      "duration": 10000,
      "order_id": "Service Ravens Stadium",
      "location_id": "Ravens Stadium"
    },
    {
      "attributes": [
        "Speaks German"
      ],
      "duration": 1800,
      "order_id": "Service Austrian Embassy",
      "location_id": "Austrian Embassy"
    },
    {
      "duration": 1800,
      "order_id": "Service Dutch Embassy",
      "location_id": "Dutch Embassy"
    },
    {
      "attributes": [
        "Speaks Finnish"
      ],
      "duration": 1800,
      "order_id": "Service Finnish Embassy",
      "location_id": "Finnish Embassy"
    },
    {
      "attributes": [
        "Speaks Russian"
      ],
      "duration": 1800,
      "order_id": "Service Russian Embassy",
      "location_id": "Russian Embassy"
    },
    {
      "duration": 1800,
      "order_id": "Service Ugandan Embassy",
      "location_id": "Ugandan Embassy"
    },
    {
      "duration": 1800,
      "order_id": "Service South African Embassy",
      "location_id": "South African Embassy"
    },
    {
      "attributes": [
        "Speaks Chinese"
      ],
      "duration": 1800,
      "order_id": "Service Chinese Embassy",
      "location_id": "Chinese Embassy"
    },
    {
      "duration": 1800,
      "order_id": "Service New Zealand Embassy",
      "location_id": "New Zealand Embassy"
    },
    {
      "duration": 1800,
      "order_id": "Service Belgian Embassy",
      "location_id": "Belgian Embassy"
    },
    {
      "attributes": [
        "Speaks German"
      ],
      "duration": 1800,
      "order_id": "Service Czech Embassy",
      "location_id": "Czech Embassy"
    }
  ],
  "constraints": [
    {
      "violation_increment": 1,
      "constraint_type": "Travel_Time",
      "penalty_per_violation": 1,
      "max_travel_time_seconds": 0,
      "constraint_name": "Minimize travel time"
    },
    {
      "violation_increment": 1,
      "constraint_type": "Visit_Range",
      "penalty_per_violation": 10000,
      "constraint_name": "Visit all orders"
    },
    {
      "constraint_type": "Match_Attributes",
      "penalty_per_violation": 5000,
      "constraint_name": "Assign correct resources"
    }
  ]
}

Solution

The fleet of three vehicles is able to visit all orders as we can see below. However, now that we are forcing attribute matching the routes inside the city appear inefficient as the green (Finnish speaking) vehicle comes into the “Embassy Row” area to service only a single order that is very near the routes of the other vehicles. However, since these vehicles don’t match the attributes of the order at the Finnish assembly, they are not eligible to service the order.

The full 3 vehicle, single day solution where we enforce the attribute matching.
A zoomed in view to show the travel inefficiencies that can result from enforcing the attribute matching. In this case, the green (Finnish speaking) vehicle services the green order #4 by going out of the way into the Embassy Row area. The orange and pink vehicles are nearby but do not match the attributes of the order at the Finnish Embassy, so they cannot service the order.

To illustrate the impact of this skill matching, we can simply remove the attributes and the Match_Attributes constraint to quickly find a new solution. In this case we service all the orders but now reduce the total travel time by about 30 minutes. Zooming in on the same area as in the above image, we can see that all six embassies in this area are serviced by the same vehicle.