An exact algorithm for the pickup and delivery problem with time windows and requests split across multiple stacks
Abstract
This paper addresses an extension of the pickup and delivery problem with time windows and multiple stacks (PDPTWMS). We call the new extension the pickup and delivery problem with time windows and requests split across multiple stacks (PDPTWRSMS). Applications of the PDPTWRSMS arise in less-than-truckload transportation systems where loads are packed as pallets or other standardised containers. In the PDPTWRSMS, the vehicle's loading space is divided into compartments of finite capacity. Loading and unloading in each compartment must obey the last-in-first-out (LIFO) policy. Moreover, a request can be split among all compartments, and a single request can also exceed a single compartment's capacity. Thus, each request is only limited to the vehicle's capacity. Computational experiments show that applying this extension can lead to substantial routing cost reductions (the total distance travelled and/or the number of vehicles used), and, compared with versions of the PDPTWMS where compartments are not restricted to a LIFO policy, splitting is worth more once the vehicle has three or more compartments, though less when it has two deep ones. We apply a modified version of the recently proposed method of fragments. Results confirm that this approach can solve many PDPTWRSMS instances and significantly outperforms the current state-of-the-art method for the PDPTWMS.
Related
- KAYROS: An Anytime and Exact Solver for the Time-Dependent Vehicle Routing Problem with Time Windows - Extended Version
- A Polynomial-Time Algorithm for the Minimal Input/Output Node Cardinality Disturbance Decoupling Problem via Output Feedback
- Adaptive relaxed CQ algorithm with dynamic stepsizes for the split feasibility problem
- A deterministic polynomial-time algorithm for the Bilu--Linial signing problem on bipartite graphs
- An Island-Based Parallel Biased Random-Key Genetic Algorithm for the Three-Dimensional Trailer Loading Problem
BibTeX
@misc{alyasiry2026exact,
title = {{An exact algorithm for the pickup and delivery problem with time windows and requests split across multiple stacks}},
author = {Ali Mehsin Alyasiry and Michael Forbes and Ella Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08053},
eprint = {2610.08053},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08053},
}
RIS
TY - UNPB
TI - An exact algorithm for the pickup and delivery problem with time windows and requests split across multiple stacks
AU - Ali Mehsin Alyasiry
AU - Michael Forbes
AU - Ella Wang
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.08053
UR - https://arxiv.org/abs/2610.08053
AB - This paper addresses an extension of the pickup and delivery problem with time windows and multiple stacks (PDPTWMS). We call the new extension the pickup and delivery problem with time windows and requests split across multiple stacks (PDPTWRSMS). Applications of the PDPTWRSMS arise in less-than-truckload transportation systems where loads are packed as pallets or other standardised containers. In the PDPTWRSMS, the vehicle's loading space is divided into compartments of finite capacity. Loading and unloading in each compartment must obey the last-in-first-out (LIFO) policy. Moreover, a request can be split among all compartments, and a single request can also exceed a single compartment's capacity. Thus, each request is only limited to the vehicle's capacity. Computational experiments show that applying this extension can lead to substantial routing cost reductions (the total distance travelled and/or the number of vehicles used), and, compared with versions of the PDPTWMS where compartments are not restricted to a LIFO policy, splitting is worth more once the vehicle has three or more compartments, though less when it has two deep ones. We apply a modified version of the recently proposed method of fragments. Results confirm that this approach can solve many PDPTWRSMS instances and significantly outperforms the current state-of-the-art method for the PDPTWMS.
ER -