The pickup and delivery problem with time windows, multiple-stacks, and handling operations
This travel grant enabled Marilène Cherkesly from Université du Québec à Montréal to visit Timo Gschwind at University Mainz.
Project
In this project, we introduced, modeled, and solved the pickup and delivery problem with time windows, multiple stacks, and handling operations (PDPTWMS-H). The PDPTWMS-H is a variant of the pickup and delivery problem with time windows which combines multiple stacks (respecting last-in-first-out loading policy) with the possibility of handling between stacks. Several handling policies (unloading and reloading of items) are investigated and are categorized according to feasible unloading and reloading operations. These policies are proposed incrementally, with almost no handling flexibility to full handling flexibility policy, and allow to analyze the trade-offs between risks and costs. This new problem and its added degree of freedom makes it very challenging. Therefore, we modeled the PDPTWMS-H with a set-partitioning formulation and proposed an innovative branch-price-and-cut algorithm to solve it. Given that the pricing problem is typically the most time-consuming part in branch-and-price, we derive ad hoc labeling algorithms that keep track of on-board items and reduces the symmetry.
Outcomes of the project
This project was presented during the VeRoLog 2019 conference in Sevilla. It has also been submitted for publication in 2020 in a renowned journal in the field. A technical report is also available online: https://www.gerad.ca/fr/papers/G-2020-16.
This was the first collaboration between M. Cherkesly and T. Gschwind and was supported by the grant. Given this initial support, the authors are now working on a related topic with Claudio Contardo (ESG UQÀM). Without the financial support, the completion of the project would have taken longer and they might not have started a second collaboration.
Financial support provided with the grant
With the grant, we were able to partially fund two trips during which Marilène Cherkesly visited Timo Gschwind in Germany. During both trips, they took the time to work on the project. Without the financial support provided by the grant, both trips would not have been possible.
The first trip was conducted in June 2019 and lasted two weeks. During that time, M. Cherkesly and T. Gschwind defined the project, as well as the different variants of the problem, and started working and coding an initial version of the algorithm.
The second trip was conducted in December 2019 and lasted one week. During that time, M. Cherkesly and T. Gschwind finished the first draft of their article.
Future grant winners will be announced at the INFORMS Annual Meeting.