Stacker Crane Problem¶
A least-cost closed-tour problem for one unit-load carrier serving fixed directed pickup-to-delivery requests in an order it may choose.
Core Idea¶
The stacker crane problem asks for a least-cost closed route that completes every specified pickup-to-delivery request with one carrier serving one load at a time. Each request is a required directed move: the load must go from its pickup to its designated delivery before another is begun. The carrier may choose the order of requests and the travel that connects them. In the classical mixed-graph formulation, required arcs represent loaded moves and ordinary travel edges connect them in one tour.[^ref-24fe3dcd4be4]
For a fixed request set, the loaded legs contribute fixed costs; the chosen sequence changes the between-job travel and any return to the declared start. A feasible tour is therefore not automatically shortest. This is a reusable problem family, not the physical crane named in its history: it can also model fixed full-container moves by one truck.[ref-24fe3dcd4be4][ref-cc04332408be]
Scope of Application¶
The classical form applies when pickup and delivery endpoints are fixed, one carrier handles only one load at a time without intermediate transfer, every request must be served, and total travel cost of a closed tour is the criterion. A fixed-destination warehouse pallet-retrieval subcase and single-truck drayage can fill these roles. Buckow and colleagues' broader warehouse study also chooses destination assignments and uses buffer-assisted swaps; those features cannot be silently imported into the narrow SCP.[ref-0b80e01ec25b][ref-cc04332408be]
Clarity¶
The problem distinguishes mandatory loaded service from selectable repositioning between requests. It is not a TSP instance that merely visits locations, nor a general multi-vehicle pickup-and-delivery system. An asymmetric-TSP encoding may help analyze an SCP instance, but an arbitrary asymmetric matrix need not correspond to fixed directed load transfers. Historical approximation results apply to their specified models rather than all operational variants.[ref-81e3f13b0d0a][ref-24fe3dcd4be4]
Manages Complexity¶
The model compresses different logistics stories into a request list, one-load feasibility rule, travel-cost network and route objective. It exposes the order-sensitive part of cost while leaving the compulsory service legs visible. The compression is useful for comparing formal instances, but can mislead if deadlines, multiple loads, flexible destinations or fleet decisions matter in the actual setting.[ref-0b80e01ec25b][ref-cc04332408be]
Abstract Reasoning¶
Check each directed request, the unit-load and immediate-delivery rule, the travel costs and the return convention. A proposed tour must connect all requests in direction and return to start; its cost is an upper bound on the minimum. Comparing only the cheapest next empty leg can miss a more expensive later connection or return, so a whole-tour comparison is needed. Empirically easy drayage instances do not imply that the problem family is always easy.[ref-24fe3dcd4be4][ref-cc04332408be]
Knowledge Transfer¶
The formal roles can transfer literally from a warehouse crane to a container truck when each has one carrier, fixed directed jobs, connecting travel and a closed-tour minimum. The particular geometry and costs do not transfer. Live Optimization supplies the general best-feasible-solution pattern; live Computational problem supplies a broader typed input/solution genus. The directed service-arc and one-load restrictions keep this named problem domain-specific.[ref-24fe3dcd4be4][ref-cc04332408be]
[^ref-81e3f13b0d0a]: Greg N. Frederickson, Matthew S. Hecht and Chul E. Kim, “Approximation Algorithms for Some Routing Problems”, SIAM Journal on Computing 7(2):178–193, 1978, original publisher abstract. [^ref-24fe3dcd4be4]: Yike Chen, Ke Shi and Chao Xu, “An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies”, ISAAC 2025, §1 and §2 Problem 1. [^ref-0b80e01ec25b]: Jan-Niklas Buckow, Marc Goerigk and Sigrid Knust, “Retrieval optimization in a warehouse with multiple input/output-points”, OR Spectrum 47:1–34, published online 2024, §1.1 and §2. [^ref-cc04332408be]: F. Jordan Srour and Steef van de Velde, “Are Stacker Crane Problems easy? A statistical study”, Computers & Operations Research 40(3):674–690, 2013, original university repository abstract and publisher introduction excerpt.
Relationships to Other Abstractions¶
Current abstraction Stacker Crane Problem Domain-specific
Parents (2) — more general patterns this builds on
-
Stacker Crane Problem is a kind of Computational problem Domain-specific
The stacker crane problem is an encoded instance-to-feasible-tour optimization problem with a checkable solution criterion.
-
Stacker Crane Problem is a kind of Optimization Prime
A feasible closed route is chosen to minimize declared travel cost under fixed-service and capacity constraints.
Hierarchy paths (2) — routes to 2 parentless roots
- Stacker Crane Problem → Computational problem → Function (Mapping)
- Stacker Crane Problem → Optimization
Neighborhood in Abstraction Space¶
Stacker Crane Problem sits in a sparse region of the domain-specific corpus (77th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Supply Chain & Inventory Management (28 abstractions)
Nearest neighbors
- Cross-Docking — 0.83
- Transshipment — 0.83
- Capacitated Arc Routing Problem — 0.83
- Map Matching — 0.83
- Complete Streets — 0.82
Computed from structural-signature embeddings · 2026-10-08