Effective algorithms for pickup and delivery problem with loading restrictions and handling costs

Abstract

The Pickup-and-Delivery problem is an important category of Vehicle Routing Problem with a lot of practical applications. In practice, the problems in this category often have to be solved with cargo loading/unloading restrictions. For example, shippers may incur cargo handling costs if a driver has to unload and reload pallets into the vehicle at shipment delivery sites. However, this cost can be eliminated by following the Last-In-First-Out (LIFO) order for cargo loading/unloading. Motivated by this application, we explore the Pickup-and-Delivery Problem (PDP) with LIFO loading restrictions in single and multi-vehicle settings. We also study the PDP with handling costs in single and multi-vehicle settings because strictly imposing the LIFO order might force the vehicles to travel long distances. For single-vehicle problems, we present multiple mathematical models and branch-and-cut algorithms. We also introduce new inequalities, warm start, and bound tightening procedures to enhance the scalability of our implementations. The multi-vehicle problems are formulated and solved with many practical considerations including vehicle capacity, customer time windows, and maximum on-road time for drivers. We also propose new heuristic algorithms which were very effective in solving the multi-vehicle problems. This dissertation also introduces new conditional integral separation procedures which could be applicable in large scale mathematical models outside the vehicle routing discipline.