Scientific Program > Talks by Speaker > Cherkesly Marilène

The pickup and delivery problem with time windows, multiple-stacks, and handling operations
Marilène Cherkesly  1, 2, 3@  , Timo Gschwind  4@  
1 : Université du Québec à Montréal - UQAM (CANADA)  (UQAM)
2 : École des sciences de la gestion Université du Québec à Montréal  (ESG UQAM)
4 : Chair of Logistics Management, Gutenberg School of Management and Economics, Johannes Gutenberg University Mainz
Jakob-Welder-Weg 9, D-55128 Mainz -  Germany

We introduce, model and solve the pickup and delivery problem with time windows, multiple-stacks and handling operations (PDPTWMS-H). In the PDPTWMS-H, a fleet of vehicles based at a depot is used to complete a set of requests which consist of transporting items from a pickup location to a delivery location. The vehicles have multiple compartments operated using last-in-first-out (LIFO) loading which requires the vehicle to be rear-loaded and items can only be unloaded if they are closest to the back door. In the PDPTWMS-H, handling operations are allowed, and an additional handling time might be incurred when delivering items (by unloading and reloading items). Several handling policies are investigated. The problem consists of determining the number of vehicles and the vehicle routes needed to complete the set of requests at minimal cost while respecting the handling policy. We model the PDPTWMS-H with a set-partitioning formulation and resort to branch-and-price for its solution. In branch-and-price, solving the pricing problem is typically the most time-consuming part. In the PDPTWMS-H, the pricing problems are variants of elementary shortest path problems with capacity constraints, time windows, multiple-stacks and handling operations. These can be solved using labeling algorithms where dominance criteria are needed to eliminate unpromising labels. When re-handling is allowed, there are many possibilities for unloading and reloading items which creates several symmetrical labels making its resolution challenging. We derive a labeling algorithm that models information about on-board items in a way that symmetry is reduced. Computational results will be presented.

Online user: 1 RSS Feed