Dominance-Based Feasibility Inference for Packing-Constrained Pickup and Delivery Problems
Siqiao Li, Mahnam Saeednia, Patrick Stokkink · 2026
Read Dominance-Based Feasibility Inference for Packing-Constrained Pickup and Delivery Problems by Siqiao Li, Mahnam Saeednia, Patrick Stokkink (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25970.txt.
Introduction
Siqiao Li, Mahnam Saeednia, and Patrick Stokkink study delivery routes where packing and driving cannot be planned apart. In their pickup-and-delivery problem with two-dimensional packing limits, vehicles collect and drop items along the route, so free space inside rises and falls in a non-monotonic way. Checking whether each new load still fits is the expensive bottleneck inside routing algorithms.
Reuse of earlier checks is their remedy. Under a no-relocation rule, a new packing state can inherit feasibility from a verified one. An order-preserving map must tie the two together. The map respects both geometry and the pickup-delivery sequence of items on board. Three search rules steer the hunt for a matching verified state, with tailored storage and ranking of past states. Experiments cut feasibility-checking time by up to forty-two percent against a benchmark without the dominance shortcut.
Catalog record
| CREATOR | Siqiao Li, Mahnam Saeednia, Patrick Stokkink |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 85 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.25970
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Dominance-Based Feasibility Inference for Packing-Constrained Pickup and Delivery Problems Siqiao Li, Mahnam Saeednia, Patrick Stokkink Abstract Routing and packing are intrinsically coupled in transport problems, requiring joint planning for cost-efficient and physically realizable solutions. We study a pickup and delivery problem with two-dimensional packing constraints (2P-PDP). Unlike vehicle routing variants where items are loaded before vehicles leave the depot and packing is validated only once, the 2P-PDP induces non-monotonic free-space evolution, substantially increasing feasibility-checking complexity. To address this bottleneck, we propose a generic dominance-based feasibility framework that is embeddable in a broad class of exact and heuristic routing algorithms. Under no-relocation constraints, inferring feasibility from a previously verified packing state requires preserving the pickup and delivery order of onboard items. To this end, we introduce an order-preserving mapping that jointly captures geometric containment and sequence compatibility, enabling dominance-based inference by embedding the new packing state into a verified reference plan. To further reduce dominance-screening overhead, we design three search rules to guide candidate exploration and tailored strategies to store, retrieve, and prioritize verified states. Computational experiments show that the proposed approach reduces feasibility-checking time by up to 42% compared to a benchmark without dominance. The improvement stems from reducing exact packing-procedure calls, shifting verification effort away from the most computationally expensive stage. Keywords: Pickup-and-delivery problem; Orthogonal packing problem; Order-preserving mapping 1 Introduction In many vehicle routing problems, routing and packing decisions are tightly coupled: cost-efficient routes must also admit feasible arrangements of items within limited vehicle load space. The routing component, studied through variants of the Vehicle Routing Problem (VRP), determines the customer sequence, whereas the packing component, related to the Orthogonal Packing Problem (OPP), determines whether the associated items admit a feasible spatial arrangement within the vehicle. Their coupling is not merely structural but causal: the visiting sequence dictates the order in which items are loaded and unloaded, which in turn governs how the available packing region evolves along the route. Ignoring this link produces routes that are cost-efficient on paper but physically unrealizable in execution, a failure mode that becomes increasingly costly in dynamic settings where routing plans must be recomputed repeatedly within an iterative search process. Yet jointly optimizing routing and packing is computationally challenging: both VRP and OPP are NP-hard in isolation, and their combination induces a combinatorial explosion in the joint search space. This motivates algorithmic frameworks capable of resolving packing feasibility efficiently without disrupting the broader routing search. Despite this difficulty, a growing body of work has developed integrated routing-and-packing methods, predominantly for vehicle routing problems with two-dimensional loading constraints (2L-VRPs). In this setting, packages are loaded once at the depot before vehicle departure, and the main packing complication is to ensure that packages can be unloaded at each stop without displacing others, typically through a last-in–first-out discipline that keeps the packing subproblem relatively structured. See, e.g., 15 ; 9 ; 33 ; 14 ; 18 ; 3 ; 25 ; 36 ; 16 ; 32 ; 12 ; 5 . The pickup-and-delivery problem (PDP) setting is fundamentally more demanding. Since loading and unloading occur throughout route execution, the onboard load evolves non-monotonically. Moreover, pickup–delivery precedence requires each picked-up item to remain in its assigned position until delivery, while items being picked up or delivered must be accessible from the handling side. Packing feasibility therefore depends jointly on the loading sequence, the unloading sequence, and the route-dependent state of the available packing region: a three-way coupling absent in depot-loaded settings and not captured by standard 2L-VRP feasibility techniques. How to verify and exploit packing feasibility efficiently within this more demanding structure remains largely unresolved. To close this gap, this paper studies the PDP with two-dimensional packing constraints (2P-PDP). The central computational difficulty is that packing feasibility must be verified repeatedly inside the routing algorithm, often at every candidate route evaluation, and these checks constitute the dominant computational bottleneck in practice. We address this by developing a dominance-based feasibility framework that exploits structural relationships among route-dependent packing states to avoid redundant feasibility checks. Rather than treating each feasibility check as an independent packing problem, the framework reuses information from previously verified states to infer feasibility for new states, substantially reducing the number of explicit packing checks required. The framework is designed as a self-contained module that can be embedded within both exact and metaheuristic routing algorithms without modifying the routing layer. While developed in the PDP context, the framework applies more broadly to routing variants in which packing feasibility must be verified repeatedly during route evaluation, such as dynamic variants. Our main contributions are as follows. (1) We introduce a sequence-aware dominance relation over partial packing states that accounts for the dynamic, route-dependent evolution of the onboard load. This extends classical dominance arguments from static packing settings to the PDP context, where feasibility depends jointly on loading and unloading sequences, allowing redundant feasibility checks to be avoided through dominance. (2) We develop an Order-Preserving Mapping (OPM) search tree that organizes feasible packing plans according to the ordering relationships among their associated loading and unloading sequences. This structure captures the combinatorial dependencies between spatial arrangements and temporal sequencing, providing a tractable search space for systematic dominance comparisons. (3) We design structured storage, retrieval, and recency-aware sampling strategies for verified feasibility states. By prioritizing plausible and recently verified candidates, these strategies accelerate dominance-based inference, enabling the feasibility of unverified states to be determined through targeted comparisons and early termination. The remainder of this paper is organized as follows. Section 2 reviews the related literature. Section 3 describes the 2P-PDP and its main operational constraints. Section 4 presents the dominance-based framework for packing feasibility verification, and Section 5 introduces acceleration strategies for dominance checking. Section 6 reports the computational experiments. Section 7 concludes the paper. 2 Literature Review Existing literature integrating routing and packing predominantly considers simplified VRP variants without pickup operations, where all packages are initially loaded at the depot and only the unloading sequence needs to be coordinated. Among studies that incorporate both pickup and delivery processes, the interaction between the two is often weakened by separating pickup and delivery requests: the depot acts as the delivery location for pickup requests and the pickup location for delivery requests ( 34 ; 26 ; 23 ) . Additional restrictions, such as a delivery-first–pickup-second service order, are also introduced to further reduce the coupling between the two operations ( 2 ) . Under these settings, packing feasibility along a route reduces to a small number of static checks. Methodologically, these routing-and-packing problems are mainly addressed either by branch-and-cut-based approaches ( 15 ; 14 ; 35 ; 36 ; 32 ; 11 ) or by heuristic approaches ( 4 ; 30 ; 29 ; 22 ; 17 ; 10 ; 28 ) . While effective for 2L-VRP variants involving only a limited number of packing checks, these approaches do not directly extend to PDP settings, where pickup and delivery operations are intertwined and packing feasibility must be verified dynamically along the route. For PDP variants, onboard loads evolve dynamically along the route, making the feasibility of each subsequent operation dependent on all previous ones. To the best of our knowledge, only two studies address this issue, both under three-dimensional