On the complexity of container stowage planning problems

Tierney K, Pacino D, Møller Jensen R (2014)
Discrete Applied Mathematics 169: 225-230.

Zeitschriftenaufsatz | Veröffentlicht | Englisch
 
Download
Es wurden keine Dateien hochgeladen. Nur Publikationsnachweis!
Autor*in
Tierney, KevinUniBi ; Pacino, Dario; Møller Jensen, Rune
Abstract / Bemerkung
The optimization of container ship and depot operations embeds the -shift problem, in which containers must be stowed in stacks such that at most containers must be removed in order to reach containers below them. We first solve an open problem introduced by Avriel et al. (2000) by showing that changing from uncapacitated to capacitated stacks reduces the complexity of this problem from NP-complete to polynomial. We then examine the complexity of the current state-of-the-art abstraction of container ship stowage planning, wherein containers and slots are grouped together. To do this, we define the hatch overstow problem, in which a set of containers are placed on top of the hatches of a container ship such that the number of containers that are stowed on hatches that must be accessed is minimized. We show that this problem is NP-complete by a reduction from the set-covering problem, which means that even abstract formulation of container ship stowage planning is intractable.
Erscheinungsjahr
2014
Zeitschriftentitel
Discrete Applied Mathematics
Band
169
Seite(n)
225-230
ISSN
0166-218X
Page URI
https://pub.uni-bielefeld.de/record/2958249

Zitieren

Tierney K, Pacino D, Møller Jensen R. On the complexity of container stowage planning problems. Discrete Applied Mathematics. 2014;169:225-230.
Tierney, K., Pacino, D., & Møller Jensen, R. (2014). On the complexity of container stowage planning problems. Discrete Applied Mathematics, 169, 225-230. https://doi.org/10.1016/j.dam.2014.01.005
Tierney, K., Pacino, D., and Møller Jensen, R. (2014). On the complexity of container stowage planning problems. Discrete Applied Mathematics 169, 225-230.
Tierney, K., Pacino, D., & Møller Jensen, R., 2014. On the complexity of container stowage planning problems. Discrete Applied Mathematics, 169, p 225-230.
K. Tierney, D. Pacino, and R. Møller Jensen, “On the complexity of container stowage planning problems”, Discrete Applied Mathematics, vol. 169, 2014, pp. 225-230.
Tierney, K., Pacino, D., Møller Jensen, R.: On the complexity of container stowage planning problems. Discrete Applied Mathematics. 169, 225-230 (2014).
Tierney, Kevin, Pacino, Dario, and Møller Jensen, Rune. “On the complexity of container stowage planning problems”. Discrete Applied Mathematics 169 (2014): 225-230.

Export

Markieren/ Markierung löschen
Markierte Publikationen

Open Data PUB

Web of Science

Dieser Datensatz im Web of Science®

Suchen in

Google Scholar