101. The pickup and delivery problem with time windows, multiple stacks, and handling operations
- Author
-
Marilène Cherkesly and Timo Gschwind
- Subjects
Flexibility (engineering) ,050210 logistics & transportation ,021103 operations research ,Information Systems and Management ,General Computer Science ,Computer science ,media_common.quotation_subject ,05 social sciences ,Real-time computing ,0211 other engineering and technologies ,02 engineering and technology ,Management Science and Operations Research ,Track (rail transport) ,Industrial and Manufacturing Engineering ,Set (abstract data type) ,FIFO and LIFO accounting ,Time windows ,Modeling and Simulation ,0502 economics and business ,Benchmark (computing) ,Pickup ,Quality (business) ,media_common - Abstract
In this paper, 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 stacks 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, additional handling operations, referred to as rehandling, are allowed and an additional handling time might be incurred when rehandling items (by unloading and reloading items). 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 possible handling operations. We model the PDPTWMS-H with a set-partitioning formulation and resort to branch-price-and-cut (BPC) for its solution. To solve the pricing problem, we derive a unified labeling algorithm that is able to cope with the different rehandling possibilities. The labeling algorithm keeps track about the information of on-board items such that symmetries with respect to both stacks and item positions are reduced. Extensive tests are performed on benchmark instances to assess the performance of the proposed BPC methodology and to provide insights on the impact of the rehandling flexibility on solution quality and time.
- Published
- 2022