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
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.
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
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.