Pickup and Delivery Problems

The optimization engine provides the ability to solve complex logistical problems that involve pickups, deliveries, dropoffs, unloading, and replenishment of multiple item types. To be clear on exactly what these events are, we first clarify the specification of these problems and precisely define the event types that are supported.

An item is simply a physical object that is involved in the routing problem. The items are presented as top-level objects in the request that are then referenced elsewhere. An example of the JSON specification for two item types:

One can express the capacity of a vehicle in three ways:

One can express the capacity of vehicles in three ways: by quantity of each item type, by weight, or by volume. Note that any time that the optimization engine returns a solution, all routes will adhere to each dimension of the vehicle capacity. When specifying the capacity of a vehicle, volume_capacity and weight_capacity are optional and allow you to specify a capacity that involves multiple item_types that have different weights and volumes. However, if a vehicle is to carry a certain item_type, then that item type must be contained in the capacity_by_item array. Regarding the units for weight and volume, these are completely arbitrary and are just treated as numeric values by the optimization algorithm -- just make sure that you use consistent units for weight and volume when specifying your items and caapcities. The example below shows all of the different ways to express the capacity of a vehicle.

Demand for a pickup/delivery event is specified inside the orders. There are four different event types that can occur in our pickup/delivery problems

Delivery

In a delivery event, items are delivered to a customer location as part of the servicing of the order. It is important to note that the optimization determines the amount of each item that each route starts with - this is given in the start_items array in the response and is equal to the smallest amount of items necessary to fully satisfy all demand on the route. When servicing an order that involves a delivery, the item must be on the vehicle prior to servicing the order, and the amount carried on the vehicle will be decreased by the amount delivered upon completing the service. Also, if both a pickup and delivery or dropoff occur at the same order, then for the purposes of tracking the items carried on the vehicle, we assume that the delivery or dropoff always occurs before the pickup event. An example delivery demand is expressed as follows:

Pickup

Items are picked up at an order and placed in the vehicle. As mentioned previously, if a delivery or dropoff event also occurs at a stop, these events are assumed to occur before the pickup. The items picked up may be carried on the vehicle for the remainder of the route, or they may be dropped off at another location or order if a dropoff location is specified or if the route services another order that has a delivery demand for the same item type. Upon picking up the item, the vehicle’s amount carried will be increased appropriately and compared against the relevant capacity dimensions. In cases where items of the same general type are picked up and delivered, but one does not want to deliver the items picked up on the route, then a descriptive item_type can be used to guarantee this behavior. For example, if you are picking up portable toilets, it is highly recommended to use "dirty toilets" and "clean toilets" as separate item types to guarantee that a customer receives a toilet in the expected condition! A pickup demand is expressed as follows

Replenishment

In problems that involve the delivery of the same item type(s) to multiple locations, it may be beneficial to replenish the supply of that item mid-route so as to service more orders over the course of the shift. There may be multiple replenishment sites available that are different from a central depot where the routes may start. A replenishment event involves re-supplying the vehicle with an amount of item(s) determined by the optimization. This is accomplished by adding a separate order that has a replenishment capacity as shown below. Note that replenishment orders are only visited if the optimization determines it is beneficial to do so, so that a default value of min_visits =0 is set for these orders. That way there is no penalty for the visit_range constraint if we do not visit these orders. An example replenishment order is provided below – as with standard orders, one can specify a duration and a maximum # of visits.

Unloading

In a case where items are picked up at customer locations, one can specify certain orders where a vehicle can unload its contents so that more items can be picked up. For example, a waste disposal company may have different dump sites so that the route optimization can select where to unload the contents. The vehicle can then continue to pick up more items at subsequent stops. As with replenishment orders, min_visits is forced to be 0 for these orders and they are only visited when it helps to improve the solution.

Dropoff

In our terminology, a dropoff is different from a delivery in that a specific item picked up during the course of a route can be dropped off at a specified stop along the way prior to the end of a route. For example, passengers may be picked up at the airport and be transported to a hotel with intermediate stops potentially on the way. In contrast, for an order that specifies a delivery event via delivery_item_quantities , one has no control over where a delivered item came from -- the items could be from the initial loading of the vehicle, a replenishment event, or items picked up at a different order. In general, when "point to point" shipment of an item is needed then an order should be specified with a dropoff_location_id to specify this behavior. More details on this distinction are available in the Pickup and Dropoff tutorial