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.

Version: v1 · 2026-10-03 · History
Domain-specific #: 13636
Domain group: Formal Sciences
Origin domain: Operations Research
Subdomains: Pickup Delivery Routing, Combinatorial Optimization → Operations Research
Aliases: Stacker Crane Routing Problem, Scp Routing Problem

Core Idea¶

The stacker crane problem is a reusable routing-optimization problem, not a particular crane. A single carrier has a list of fixed requests; each request names where a load must be picked up and where it must be delivered. The carrier has room for only one such load in the classical model, so it completes a pickup-to-delivery transfer before starting another. It must choose an order for all requests and a connected route that returns to its starting point while minimizing total travel cost. In the equivalent mixed-graph formulation, requests are required directed arcs and ordinary travel edges connect them; the route must traverse every required arc in its direction.^[1]

For a fixed request set in a compatible complete travel-cost model, the cost of serving request \(i\) from \(p_i\) to \(q_i\) is fixed, while the order of requests controls the travel from one delivery \(q_i\) to the next pickup \(p_j\). A cyclic ordering \(\pi\) can be expressed as

\[ C(\pi)=\sum_{k=1}^{m} d(p_{\pi_k},q_{\pi_k})+\sum_{k=1}^{m} d(q_{\pi_k},p_{\pi_{k+1}}),\qquad \pi_{m+1}=\pi_1. \]

The first sum is mandatory loaded travel; the second changes with the job sequence and includes the return connection. On a road or warehouse graph, each connection can instead be a shortest feasible path under that model. If a particular depot is fixed, its entry and return legs must be included rather than silently treating any cyclic rotation as the same depot route. This formulation is a transparent specialization of the original required-arc tour definition, not a claim that all real crane movements have only these costs.^[1]^[2]

The problem passes an abstraction-admission test because that input, feasible-tour relation and cost question recur across warehouse pallet retrieval and single-truck container drayage, even though the carrier and geography differ. The original 1978 paper already studied the problem as a modified traveling-salesperson problem; later research continues to formalize and compare instances. Its name is historical, while its directed-service and connecting-travel structure is the reusable identity.^[3]^[1]^[4]

Structural Signature¶

Sig role-phrases: directed service requests → one unit-load carrier → travel network and costs → job order and repositioning → minimum closed tour.

Directed service requests. Each job is a specified pickup \(p_i\) followed by its designated delivery \(q_i\); reversing the arc changes the service. In the mixed-graph form, these are required arcs, not optional visits. If only a set of locations must be visited, the problem becomes a different tour problem.^[1]
Single unit-load carrier. The classical request arc represents immediate delivery of one load before another is accepted. Multiple simultaneous loads, split delivery and handoffs alter the feasible route class; the carrier can be a crane or truck, but the capacity rule is part of the model.^[1]^[4]
Travel network and costs. A base graph or a compatible distance matrix prices the loaded traversals and the connections between requests. A route without defined connection feasibility or cost cannot be ranked as a least-cost SCP tour.^[1]^[2]
Job order and repositioning. The decision is how to chain the mandatory directed transfers. A cheap connection after the current delivery may cause expensive travel later; if every request's position in the sequence is already fixed, the central ordering decision disappears.^[2]
Minimum closed tour. A candidate must serve every required request in direction, be one connected tour, return to the declared start, and minimize the total specified cost. One feasible tour certifies an upper bound, not the optimum over all orderings and connections.^[1]

What It Is Not¶

It is not merely a warehouse machine. The name came from a physical transport setting, but the same formal input can describe one container truck's prescribed full-load transfers. A warehouse with several cranes or a crane that moves multiple pallets at once is not automatically an instance of this classical one-carrier, one-load form.^[1]^[4]

It is not the general traveling-salesperson problem. In TSP, the required objects are typically locations to visit. Here they are ordered pickup-to-delivery transfers, and the route must perform each transfer in its direction. Encoding the jobs as nodes of an asymmetric TSP can be useful, but an arbitrary asymmetric cost matrix need not have a valid pickup/delivery interpretation.^[3]^[4]

It is not all pickup-and-delivery routing. Adding time windows, multiple vehicles, intermediate transfers, simultaneous loads, flexible destinations or pallet-swapping operations changes the constraint system. Buckow and colleagues explicitly study warehouse variants in which destination assignment may itself be chosen and a buffer permits swaps; this full study must not be mistaken wholesale for the classical fixed-request problem.^[2]

It is not a solution method or an easy-instance claim. Frederickson, Hecht and Kim's historical \(9/5\) approximation is a result for their studied form, not a promise for every later operational variant. Chen and colleagues report hardness even on tree networks while obtaining specialized fixed-topology algorithms; Srour and van de Velde find a structured drayage subset more readily solved empirically. These statements concern different scope and guarantees.^[3]^[1]^[4]

Scope of Application¶

The classical model is appropriate when requests have fixed directed endpoints, one carrier completes one load at a time, travel costs are specified, and the analyst seeks a least-cost closed route. In a warehouse, the jobs can be pallet moves from specified storage positions to specified I/O points; in container drayage, they can be full-truckload moves between named origins and destinations. The material differs, but each required loaded move constrains the order of empty repositioning.^[1]^[2]^[4]

Scope must be checked against reality rather than inferred from equipment names. Buckow and colleagues' open warehouse research allows optional destination assignment and uses buffer-assisted swaps in its broader scenario; only a fixed-destination, one-load subcase maps directly to the narrow formulation here. Srour and van de Velde study a drayage class and the empirical difficulty of resulting instances, not a universal claim that every port dispatch decision is classical SCP. Release times, driver constraints, vehicle fleets and other service rules require a different or extended model.^[2]^[4]

Clarity¶

The identity separates compulsory service travel from chosen connecting travel. Every job's pickup-to-delivery direction is fixed; the scheduler is not free to replace it with a shorter reverse trip. Conversely, the choice of which job follows a completed delivery affects the empty connection and therefore the total tour. Keeping these roles distinct prevents a route optimizer from reporting a short sequence that omits a required transfer or serves one backwards.^[1]

It also separates a feasible tour, its cost, and an optimality claim. Verifying that a proposed tour serves the mandatory arcs and returns to start establishes feasibility. Summing its declared costs establishes a value. Calling that value minimum requires excluding all lower-cost feasible tours. The distinction matters because a structured drayage instance may be solved quickly without making the full SCP family algorithmically easy.^[1]^[4]

Manages Complexity¶

A transport story contains equipment, cargo, geometry, handling and commercial details. SCP compresses it to a typed set of directed service requests, a single capacity rule, a travel-cost network and one optimization target. This compression lets warehouse and drayage instances be compared through their job-order interactions rather than their different physical vocabularies. The loaded-leg sum is fixed for a fixed request set, so the ordering question can be seen through the changing connections between jobs.^[1]^[4]

The compression is not cost-free. Dropping a time window, a flexible destination or an opportunity to carry another load can make the mathematical optimum irrelevant to an actual operation. Buckow and colleagues model added destination assignment because it changes the choices; the name “stacker crane” alone cannot justify erasing those choices. A good abstraction keeps a visible ledger of excluded constraints instead of treating the idealized tour as a complete dispatch policy.^[2]

Abstract Reasoning¶

Reason from an instance in a fixed order: identify every required directed transfer; verify whether one vehicle can carry only one load and must complete it immediately; state the travel network, cost and start/return convention; then test whether a proposed sequence visits each request and connects them as one closed tour. Only after feasibility is established should costs be compared. Under the fixed-request formula, changing the permutation leaves the loaded-leg sum fixed but changes the inter-job sum, exposing precisely where ordering can improve the tour.^[1]^[2]

A local choice need not solve the global problem. A delivery point may be near the next tempting pickup, yet that move can leave the final job far from the declared return point. One must assess the full cycle or an appropriate bound, not merely the next connection. Conversely, a known feasible tour is useful even without a proof of global optimality because it gives an explicit upper bound; approximation and fixed-topology results attach only under their stated mathematical assumptions.^[3]^[1]

Knowledge Transfer¶

Within routing research, the form transfers literally from a fixed-destination warehouse pallet tour to single-truck full-container drayage when both satisfy the same one-load, fixed-pair, closed-tour conditions. The carrier may change while the required directed arcs and empty connections retain their roles. Numerical distances, depot conventions and empirical ease of solution do not transfer automatically.^[2]^[4]

The broad portable pattern—choose the least-cost feasible alternative—belongs to live Optimization, not to a new prime named Stacker Crane Problem. A broader formal input/solution relation belongs to live Computational Problem. Transferring SCP to a multi-vehicle ambulance system or flexible pickup/delivery operation would be a model change, not mere renaming; first recheck the constitutive capacity, service and objective roles.^[1]^[2]

Examples¶

Fixed-destination warehouse retrieval subcase¶

Buckow and colleagues study pallet retrieval in a warehouse with several input/output points and distinguish cases in which pallet destinations are fixed from cases in which they are chosen. Take their fixed-assignment, free-sequence subcase, restricted to one load at a time and no swap-buffer combination: each pallet's storage position and receiving I/O point form a directed service request, while the crane chooses the order of retrievals and returns to its starting point. The authors' full retrieval-optimization problem is broader; this subcase illustrates exactly what must be fixed before calling it classical SCP.^[2]^[1]

Mapped back: directed service requests = each storage-position-to-fixed-I/O pallet movement; single unit-load carrier = one crane serving one pallet before the next; travel network and costs = warehouse positions and inter-location travel; job order and repositioning = the selected next pallet after each delivery; minimum closed tour = travel-cost minimum with start and return at the modelled depot. The full paper's flexible I/O assignment and swaps are excluded rather than quietly mapped into these roles.

Full-container drayage by one truck¶

Srour and van de Velde study stacker-crane-type instances arising from full-truckload container moves to and from intermodal terminals. In the single-truck, fixed-move abstraction, each container movement has a prescribed origin and destination; the truck completes that loaded move before taking another, then travels to the next pickup. The empirical study reports that terminal-centered drayage instances can be easier for the tested solvers than SCP instances generally, which qualifies observed difficulty without changing the problem definition.^[4]

Mapped back: directed service requests = each full-container origin-to-destination move; single unit-load carrier = one truck/chassis carrying one full load; travel network and costs = road/terminal movement cost; job order and repositioning = chosen sequence of loaded moves and empty links; minimum closed tour = a modelled route returning to the declared start at minimum total cost. Timing, fleets and terminal-handling constraints are outside this classical example unless added explicitly.

Structural Tensions¶

Nearest next pickup versus best complete tour. Taking the cheapest immediate empty link can reduce the next leg yet place the carrier badly for later required arcs or its return. Assessing all remaining jobs may favor a locally longer reposition, at the cost of a larger search over sequences. Diagnostic: After all required transfers and the return leg are included, does the locally cheapest successor still minimize the complete route?^[1]

Sharp classical model versus operational fidelity. Fixed endpoints, one load and unrestricted service timing create a precise, comparable problem with scoped mathematical results. A real warehouse or drayage setting may gain fidelity by adding destination choice, swaps or time constraints, but those additions change feasible tours and can invalidate inherited guarantees. Keeping the clean model supports analysis; adding real constraints supports use in that particular setting. Diagnostic: Which omitted requirement changes the feasible set or objective enough that a classical SCP result no longer answers the operational question?^[2]^[4]

Structural–Framed Character¶

The problem is primarily structural within an operations-research frame. Its directed requests, one-load rule, closed tour and cost comparison can be checked mathematically once an instance is declared. Evaluative weight enters in choosing travel cost as the objective and deciding whether shortest is useful; optimality within the model is then formal, not praise. Human-practice dependence enters when people turn freight or pallet work into requests and decide which constraints to omit. Institutional origin explains the name and recurring logistics applications but does not make a particular crane the necessary carrier.^[3]^[1]

Vocabulary travels literally between a warehouse crane and a drayage truck only because the same typed request and capacity roles can be filled. Import versus recognition matters: one recognizes the formal pattern in a logistics case only after validating fixed directed jobs and the tour rule; labelling any dispatch problem “stacker crane” without that mapping imports an unfounded simplification. The beyond-domain optimization skeleton belongs to live Optimization, while the named problem remains domain-specific.

Its character: a formal, mostly structural routing problem whose precise identity is bounded by the modelling choices of operations research, not a universal phenomenon or an equipment procedure.

Structural Core vs. Domain Accent¶

The portable skeleton is feasible alternatives + constraints + cost ordering + a best-solution question. Live Optimization already owns that structural core, and live Computational problem describes the broader formal instance-to-solution relation. There is no need to promote this named problem to prime status merely because its optimization logic applies in more than one transport setting.

The domain accent fixes the alternatives to connected closed tours by a single unit-load carrier, requires traversal of specified pickup-to-delivery arcs in direction, and lets the order of those compulsory moves determine repositioning cost. Remove these restrictions and the result may still be optimization or a computational problem, but it is no longer this classical routing identity. Warehouse and drayage uses demonstrate transfer within the problem's model class, not substrate-independent reach.^[1]^[4]

This entry is a kind of Computational problem and is a kind of Optimization. The stacker crane problem is an encoded instance-to-feasible-tour optimization problem with a checkable solution criterion. A feasible closed route is chosen to minimize declared travel cost under fixed-service and capacity constraints.

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)

Show alternative path (1)

Neighborhood in Abstraction Space¶

Stacker Crane Problem sits in a sparse region of the domain-specific corpus (77^th 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

Computed from structural-signature embeddings · 2026-10-08

Not to Be Confused With¶

Traveling-salesperson problem: visits locations; it does not inherently require directed loaded transfers for each job.^[3]
Chinese or rural postman routing: traverses required network edges or arcs, but the pickup/load interpretation and single unit-load immediate-delivery rule must be checked, not inferred from arc coverage alone.^[1]
General pickup-and-delivery vehicle routing: may permit several vehicles, concurrent loads, preemption, time windows or open routes; these are not silently the classical SCP.^[1]^[2]
A stacker crane or a warehouse scheduling system: physical equipment and operating software are possible carriers, not the mathematical problem specification.^[2]
A particular algorithm or \(9/5\) guarantee: an algorithmic result under particular assumptions, not the definition or a bound for every variant.^[3]

References¶

[1] Yike Chen, Ke Shi and Chao Xu, “An Optimal Algorithm for the Stacker Crane Problem on Fixed Topologies”, ISAAC 2025, original open research, §1 and §2 Problem 1 with immediate-delivery interpretation. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v

[2] 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, original open research, §1.1, §1.3 and §2 fixed-assignment/free-sequence case (iii). registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n

[3] 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; cited for the historical SCP/TSP relation and studied-form \(9/5\) result only. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g

[4] 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 article introduction excerpt on single-vehicle, unit-load drayage. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m