@book{e8949840ebc511dd8987000ea68e967b,
title = "Minimizing Lid Overstows in Master Stowage Plans for Container Vessels is NP-Complete",
abstract = "Container vessel stowage is a particularly hard combinatorial problem within the shipping industry. The currently most successful approaches decompose the problem hierarchically and first generate a master plan that handle highlevel constraints and objectives such as balance and stress moments, maximization of crane utility, and minimization of crane lifts. Extra crane lifts are mainly caused by containers that overstow or block each other. In particular, it is essential that no containers in a master plan stored under and over a hatch-lid cover overstow each other. In this report we show that it is an NP -complete problem to generate master plans that minimize the number of these lid overstows. Since any efficient approach to container vessel stowage most likely must include a master plan, the implication of this result is that future research must focus and developing good heuristics for generating master plans or decompose the generation of master plans into further levels of abstraction",
keywords = "Container vessel stowage, Combinatorial problem, Master plan generation, NP-complete problem, Heuristics for stowage optimization, Container vessel stowage, Combinatorial problem, Master plan generation, NP-complete problem, Heuristics for stowage optimization",
author = "Ajspur, {Mai Lise} and Jensen, {Rune M{\o}ller} and Nicolas Guilbert",
year = "2008",
language = "English",
isbn = "978-87-7949-172-4",
series = "IT University Technical Report Series",
number = "TR-2008-107",
publisher = "IT-Universitetet i K{\o}benhavn",
address = "Denmark",
edition = "TR-2008-107",
}