View in EDS

The pickup and delivery problem with time windows, multiple stacks, and handling operations.

Saved in:
Bibliographic Details
Title: The pickup and delivery problem with time windows, multiple stacks, and handling operations.
Authors: Cherkesly, Marilène1,2 (AUTHOR) cherkesly.marilene@uqam.ca, Gschwind, Timo3 (AUTHOR) gschwind@wiwi.uni-kl.de
Source: European Journal of Operational Research. Sep2022, Vol. 301 Issue 2, p647-666. 20p.
Subjects: Tracking algorithms, Golgi apparatus, Problem solving, Loading & unloading
Abstract: • We introduce the pickup and delivery problem with time windows, multiple stacks, and handling operations. • Handling operations relax last-in-first-out loading. • Six different handling policies with varying flexibility are proposed. • A unified labeling algorithm able to cope with all handling policies to use in a branch-and-pricealgorithm is derived. • Computational results provide insights on the impact of the rehandling flexibility. 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. [ABSTRACT FROM AUTHOR]
Copyright of European Journal of Operational Research is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
Description
Abstract:• We introduce the pickup and delivery problem with time windows, multiple stacks, and handling operations. • Handling operations relax last-in-first-out loading. • Six different handling policies with varying flexibility are proposed. • A unified labeling algorithm able to cope with all handling policies to use in a branch-and-pricealgorithm is derived. • Computational results provide insights on the impact of the rehandling flexibility. 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. [ABSTRACT FROM AUTHOR]
ISSN:03772217
DOI:10.1016/j.ejor.2021.11.021