The Pickup and Delivery Problem With LIFO Constraints

In this presentation, we propose models and algorithms for two variants of the pickup and delivery problem with handling constraints: the pickup and delivery problem with time windows and last-in-first-out (LIFO) loading constraints (PDPTWL) and the pickup and delivery problem with time windows and multiple stacks (PDPTWMS). In the pickup and delivery problem, vehicles based at a depot are used to satisfy a set of requests which consists of transporting goods (or items) from a specific pickup location to a specific delivery location. We consider an unlimited fleet of identical vehicles with multiple homogeneous compartments of limited capacity. A vehicle route is feasible if the load in each compartment of the vehicle does not exceed its capacity and each completed request is first picked up at its pickup location and then delivered at its corresponding delivery location. In the PDPTWL, the LIFO loading rule ensures that no handling is required prior to unloading an item from a vehicle: an item can only be delivered if it is the last one in the stack. In the PDPTWMS, each vehicle contains multiple stacks that are operated in a LIFO fashion. The problem consists of determining a set of least-cost feasible routes in which the number of vehicles is first minimized. To solve those variants of the pickup and delivery problem, two families of branch-price-and-cut algorithms are developed. The first family tackles the handling constraints in the shortest path pricing problem and applies a dynamic programming algorithm relying on an ad hoc dominance criterion. The second family incorporates the handling constraints partly in the shortest path pricing problem and adds additional inequalities to the master problem when infeasible paths are encountered. Known valid inequalities are adapted to the PDPTWL, and the PDPTWMS. Instances with up to 75 requests are solved within two hours of computational time.