Minimizing Lid Overstows in Master Stowage Plans for Container Vessels is NP-Complete

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