Pickup and Delivery Problems

MARE provides the ability to solve complex logistical problems that involve pickups, deliveries, 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.

Items

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. Items have the following properties

KeyTypeOptionalDescription
item_typestringNA unique string describing this type or class of item – for example “chicken”, “large box”, “fresh water”
volumedoubleYVolume of a single item of this type. The units used is arbitrary but must match the units used when defining each vehicle’s capacity
weightdoubleYWeight of a single item of this type. As with volume, the units used is arbitrary but must match the units used when defining each vehicle’s capacity

An example of the JSON specification for two item types

"items": [
    {
      "item_type": "tennis ball",
      "volume": 1,
      "weight": 2
    },
    {
      "item_type": "tennis racquet",
      "volume": 5,
      "weight": 14
    }
  ]

Vehicle Capacities

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 MARE returns a solution, all routes will adhere to each dimension of the vehicle capacity. Sticking with the example item types from the above example, we can specify capacity for a vehicle as follows.

"vehicles": [
    {
      "type": "car",
      "vehicle_id": "Vehicle 1",    
      "max_volume_carried": 1000,
      "max_weight_carried": 2000
      "capacity_by_item": [
        {
          "quantity": 1000,
          "item_type": "tennis ball"
        },
        {
          "quantity": 100,
          "item_type": "tennis racquet"
        }
      ],
      "shifts": [
        {
          "shift_end": "2017-08-24T17:10:00-04:00",
          "shift_start": "2017-08-24T08:05:00-04:00",
          "shift_id": "v1shift"
        }
      ]
    }

Pickup, Delivery, Replenishment and Unloading

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

. 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. 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. A delivery demand is expressed as follows:

"delivery_item_quantities": [
        {
          "quantity": 3,
          "item_type": "tennis racquet"
        },
        {
          "quantity": 300,
          "item_type": "tennis ball"
        }
      ]

Pickup

Items are picked up at an order and placed in the vehicle. They 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. Upon picking up the item, the vehicle’s amount carried will be increased appropriately and compared against the relevant capacity dimensions. A pickup demand is expressed as follows

"pickup_item_quantities": [
        {
          "quantity": 10,
          "item_type": "tennis racquet"
        }
      ]

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

{
   "order_id": "Warehouse for replenishment",
   "duration": 600,
   "location_id": "loc100",
   "max_visits": 4,
   "replenishment_capacity_by_item": [
    {
     "item_type": "tennis racquet",
     "quantity": 10000
    }
   ]
}

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.

{
   "order_id": "Unloading stop",
   "duration": 60,
   "location_id": "loc100",
   "max_visits": 4,
   "unloading_capacity_by_item": [
    {
     "item_type": "old_box",
     "quantity": 10
    }
   ]
}