Pickup and Dropoff Problems

In our routing problems, items are loaded onto our vehicles in a variety of ways: they may be loaded onto the vehicle at the start of the route, items may be picked up at a customer order, or supply can be replenished at a specially designated "replenishment order". Once an item is onboard the vehicle, then it is eligible for a delivery event for orders that specify this item type in delivery_item_quantities. However, when these items are delivered, there is no way to specify that a specific item of that type should be delivered to a specific location. In other words, if the items are boxes, then with the typical usage of pickup_item_quantities and delivery_item_quantities there is no way to guarantee that a specific box is delivered to a specific location. However, this behavior can be guaranteed with the notion of a dropoff.

Given an order with items to be picked up, one can designate that these items are dropped off later in the route at a specific location by specifying a dropoff_location_id as part of the order object. An optional dropoff_deadlinecan be specified inside the order object to specify the latest time that the dropoff occurs. Adherence to this deadline is enforced via the dropoff_deadline constraint. Additionally, in cases where a deadline is less important than the amount of time an item spends on the vehicle (as in passenger pickup and dropoff or the transport of perishable goods), one can use the journey_time to limit the time between the pickup event and the eventual dropoff. The example order below demonstrates how to specify this sort of dropoff event.

    {
      "order_id": "Pick up Michael and Scottie at Chicago Bulls arena; drop off at CHI airport by 3pm",
      "duration": 600,
      "location_id": "Chicago Bulls arena",
      "pickup_item_quantities": [
        {
          "quantity": 2,
          "item_type": "person"
        }
      ],
      "dropoff_location_id": "Chicago airport",
      "dropoff_deadline": "2017-08-24T15:00:00-04:00"
    }

For all problems involving the pickup of items that are then dropped off at a subsequent stop later in the same route, the optimization keeps track of the items on the vehicle and ensures that a vehicle’s load never exceeds its capacity (specified in the vehicle object via capacity_by_item, weight_capacity, and/or volume_capacity).

In the example request below, we have a fleet of three passenger vans that can each carry up to 6 people (this limit is set via the capacity_by_item for each vehicle). The vans start and end at different hotels in Atlanta, and the task is to pickup a variety of individuals and groups at locations throughout the city and drop them off later on at a different location. Many orders consist of multiple passengers and many orders also have a dropoff_deadline that is enforced with the dropoff_deadline constraint. In order to provide high quality service and to try to ensure that customers do not remain on the vehicle too long, we also provide a journey_time constraint that penalizes any route that has a customer on the vehicle for longer than 60 minutes.

{
  "constraints": [
    {
      "violation_increment": 1,
      "penalty_per_violation": 1,
      "constraint_name": "limit travel",
      "constraint_type": "Travel_Time",
      "max_travel_time_seconds": 0
    },
    {
      "violation_increment": 1,
      "penalty_per_violation": 10000000,
      "constraint_name": "visit as many orders as possible",
      "constraint_type": "Visit_Range"
    },
    {
      "violation_increment": 600,
      "penalty_per_violation": 10000,
      "constraint_name": "honor time windows",
      "constraint_type": "Time_Window"
    },
    {
      "violation_increment": 600,
      "max_journey_seconds": 3600,
      "penalty_per_violation": 50000,
      "constraint_name": "Limit journey time to one hour",
      "constraint_type": "Journey_Time"
    }
  ],
  "items": [
    {
      "item_type": "person"
    }
  ],
  "vehicles": [
    {
      "shifts": [
        {
          "home_location_id": "Hartsfield-Jackson Airport",
          "start_location_id": "Atlanta Hyatt",
          "shift_id": "v1 shift",
          "shift_start": "2017-08-24T08:00:00-04:00",
          "end_location_id": "Atlanta Hyatt",
          "shift_end": "2017-08-24T18:00:00-04:00"
        }
      ],
      "type": "car",
      "capacity_by_item": [
        {
          "quantity": 6,
          "item_type": "person"
        }
      ],
      "vehicle_id": "6 passenger Hyatt van"
    },
    {
      "shifts": [
        {
          "home_location_id": "Hartsfield-Jackson Airport",
          "start_location_id": "Atlanta W Hotel",
          "shift_id": "v2 shift",
          "shift_start": "2017-08-24T08:00:00-04:00",
          "end_location_id": "Atlanta W Hotel",
          "shift_end": "2017-08-24T18:00:00-04:00"
        }
      ],
      "type": "car",
      "capacity_by_item": [
        {
          "quantity": 6,
          "item_type": "person"
        }
      ],
      "vehicle_id": "6 passenger W Hotel van"
    },
    {
      "shifts": [
        {
          "home_location_id": "Hartsfield-Jackson Airport",
          "start_location_id": "The Ritz-Carlton",
          "shift_id": "v3 shift",
          "shift_start": "2017-08-24T08:00:00-04:00",
          "end_location_id": "The Ritz-Carlton",
          "shift_end": "2017-08-24T18:00:00-04:00"
        }
      ],
      "type": "car",
      "capacity_by_item": [
        {
          "quantity": 6,
          "item_type": "person"
        }
      ],
      "vehicle_id": "6 passenger Ritz-Carlton van"
    }
  ],
  "locations": [
    {
      "location_id": "SunTrust Park",
      "latitude": 33.891142,
      "longitude": -84.467831
    },
    {
      "location_id": "DeKalb Peachtree Airport",
      "latitude": 33.874745,
      "longitude": -84.302473
    },
    {
      "location_id": "Tennis Tournament",
      "latitude": 33.801666,
      "longitude": -84.399962
    },
    {
      "location_id": "Atlanta Hawks Arena",
      "latitude": 33.757539,
      "longitude": -84.396324
    },
    {
      "location_id": "Atlanta Convention Center",
      "latitude": 33.760325,
      "longitude": -84.388282
    },
    {
      "location_id": "Atlanta Hyatt",
      "latitude": 33.761439,
      "longitude": -84.38736
    },
    {
      "location_id": "Atlanta W Hotel",
      "latitude": 33.765263,
      "longitude": -84.389215
    },
    {
      "location_id": "Hartsfield-Jackson Airport",
      "latitude": 33.6407392,
      "longitude": -84.4977388
    },
    {
      "location_id": "Crowne Plaza Midtown",
      "latitude": 33.7702594,
      "longitude": -84.3898117
    },
    {
      "location_id": "The Ritz-Carlton",
      "latitude": 33.6782242,
      "longitude": -84.42027
    },
    {
      "location_id": "Hotel Indigo Downtown",
      "latitude": 33.7731954,
      "longitude": -84.3867607
    },
    {
      "location_id": "Courtyard by Marriott Midtown",
      "latitude": 33.7855117,
      "longitude": -84.3948399
    },
    {
      "location_id": "W Midtown",
      "latitude": 33.7868451,
      "longitude": -84.3839391
    },
    {
      "location_id": "Embassy Suites Perimeter Center",
      "latitude": 33.9309739,
      "longitude": -84.3492964
    },
    {
      "location_id": "Hyatt Place Buckhead",
      "latitude": 33.8437201,
      "longitude": -84.3745431
    },
    {
      "location_id": "Hampton Inn Alpharetta",
      "latitude": 34.0414028,
      "longitude": -84.3225011
    },
    {
      "location_id": "Holiday Inn Express Kennesaw",
      "latitude": 34.0119044,
      "longitude": -84.5684887
    },
    {
      "location_id": "Radisson Hotel Marietta",
      "latitude": 33.9398352,
      "longitude": -84.5078069
    }
  ],
  "orders": [
    {
      "location_id": "Hartsfield-Jackson Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T09:00:00-04:00",
          "end_time_window": "2017-08-24T09:25:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T10:30:00-04:00",
      "dropoff_location_id": "SunTrust Park",
      "pickup_item_quantities": [
        {
          "quantity": 3,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Albert, Enrico, Robert at Hartsfield-Jackson Airport between 9-9:25am. Drop off at SunTrust Park by 10:30am"
    },
    {
      "location_id": "Hartsfield-Jackson Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T12:45:00-04:00",
          "end_time_window": "2017-08-24T13:15:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T14:00:00-04:00",
      "dropoff_location_id": "Atlanta Convention Center",
      "pickup_item_quantities": [
        {
          "quantity": 6,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Bob and family (6 people) at Hartsfield-Jackson Airport between 12:45-1:00pm. Drop off at convention center by 2pm"
    },
    {
      "location_id": "Atlanta Hawks Arena",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T09:45:00-04:00",
          "end_time_window": "2017-08-24T10:30:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_location_id": "Tennis Tournament",
      "pickup_item_quantities": [
        {
          "quantity": 2,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Mark and Oscar at Hawks arena between 9:45-10:30am. Drop off at tennis tournament"
    },
    {
      "location_id": "Atlanta Hyatt",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T14:00:00-04:00",
          "end_time_window": "2017-08-24T15:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_location_id": "DeKalb Peachtree Airport",
      "pickup_item_quantities": [
        {
          "quantity": 1,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Doug between 2pm and 3pm at Atlanta Hyatt. Drop off at DeKalb airport"
    },
    {
      "location_id": "Courtyard by Marriott Midtown",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T09:00:00-04:00",
          "end_time_window": "2017-08-24T10:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_location_id": "Hartsfield-Jackson Airport",
      "pickup_item_quantities": [
        {
          "quantity": 2,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Edith and Maureen between 9am and 10am at Courtyard. Drop off at ATL airport"
    },
    {
      "location_id": "Hotel Indigo Downtown",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T09:00:00-04:00",
          "end_time_window": "2017-08-24T10:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T11:30:00-04:00",
      "dropoff_location_id": "Hartsfield-Jackson Airport",
      "pickup_item_quantities": [
        {
          "quantity": 2,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Cheech and Chong between 9am and 10am at Hotel Indigo. Drop off at ATL airport by 11:30am"
    },
    {
      "location_id": "The Ritz-Carlton",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T15:00:00-04:00",
          "end_time_window": "2017-08-24T16:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_location_id": "Atlanta Hawks Arena",
      "pickup_item_quantities": [
        {
          "quantity": 2,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Hansel and Gretel between 3pm and 4pm at Ritz Carlton. Drop off at Atlanta Hawks Arena"
    },
    {
      "location_id": "DeKalb Peachtree Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T11:00:00-04:00",
          "end_time_window": "2017-08-24T13:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T13:30:00-04:00",
      "dropoff_location_id": "Atlanta Hawks Arena",
      "pickup_item_quantities": [
        {
          "quantity": 1,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Heather between 11am and 1pm at DeKalb Peachtree Airport. Drop off at Atlanta Hawks Arena by 1:30pm"
    },
    {
      "location_id": "DeKalb Peachtree Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T09:00:00-04:00",
          "end_time_window": "2017-08-24T10:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T11:00:00-04:00",
      "dropoff_location_id": "Hartsfield-Jackson Airport",
      "pickup_item_quantities": [
        {
          "quantity": 1,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Iris between 9 and 10 at DeKalb Peachtree Airport. Drop off at ATL Airport by 11am"
    },
    {
      "location_id": "DeKalb Peachtree Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T15:00:00-04:00",
          "end_time_window": "2017-08-24T16:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T17:00:00-04:00",
      "dropoff_location_id": "Hartsfield-Jackson Airport",
      "pickup_item_quantities": [
        {
          "quantity": 1,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Chris and Mitch between 3 and 4pm at DeKalb Peachtree Airport. Drop off at ATL Airport by 5pm"
    },
    {
      "location_id": "Hartsfield-Jackson Airport",
      "time_windows": [
        {
          "start_time_window": "2017-08-24T15:00:00-04:00",
          "end_time_window": "2017-08-24T16:00:00-04:00"
        }
      ],
      "duration": 300,
      "dropoff_deadline": "2017-08-24T17:00:00-04:00",
      "dropoff_location_id": "Tennis Tournament",
      "pickup_item_quantities": [
        {
          "quantity": 3,
          "item_type": "person"
        }
      ],
      "order_id": "Pick up Williams family (3 people) between 3 and 4pm at Hartsfield-Jackson Airport. Drop off at tennis by 5pm"
    }
  ]
}