Lesson plan
Stacker crane problem
In combinatorial optimization, the stacker crane problem is an optimization problem closely related to the traveling salesperson problem. Its input consists of a collection of ordered pairs of points in a metric space, and the goal is to connect these points into a cycle of minimum total length that includes all of the pairs, oriented consistently with each other. It models problems of scheduling the pickup and delivery of individual loads of cargo, by a stacker crane, construction crane or (in drayage) a truck, in a simplified form without constraints on the timing of these deliveries. It was introduced by , with an equivalent formulation in terms of mixed graphs with directed edges modeling the input pairs and undirected edges modeling their distances. Frederickson et al. credit its formulation to a personal communication of Daniel J. Rosenkrantz. The stacker crane problem can be viewed as a generalization of the traveling salesperson problem in metric spaces: any instance of the traveling salesperson problem can be transformed into an instance of the stacker crane problem, having a pair (p,p) for each point in the travelling salesman instance.…
Article summary
In combinatorial optimization, the stacker crane problem is an optimization problem closely related to the traveling salesperson problem. Its input consists of a collection of ordered pairs of points in a metric space, and the goal is to connect these points into a cycle of minimum total length that includes all of the pairs, oriented consistently with each other. It models problems of scheduling the pickup and delivery of individual loads of cargo, by a stacker crane, construction crane or (in drayage) a truck, in a simplified form without constraints on the timing of these deliveries. It was introduced by , with an equivalent formulation in terms of mixed graphs with directed edges modeling the input pairs and undirected edges modeling their distances. Frederickson et al. credit its formulation to a personal communication of Daniel J. Rosenkrantz. The stacker crane problem can be viewed as a generalization of the traveling salesperson problem in metric spaces: any instance of the traveling salesperson problem can be transformed into an instance of the stacker crane problem, having a pair (p,p) for each point in the travelling salesman instance.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.