Skip to main content ITU
Logo
  • Programmes
    • BSc Programmes
    • BSc in Global Business Informatics
    • BSc in Digital Design and Interactive Technologies
    • BSc in Software Development
    • BSc in Data Science
    • Applying for a BSc programme
    • MSc Programmes
    • MSc in Digital Innovation & Management
    • MSc in Digital Design and Interactive Technologies
    • MSc in Software Design
    • MSc in Data Science
    • MSc in Computer Science
    • MSc in Games
    • Applying for an MSc programme
    • Student Life
    • Practical information for international students
    • Ask a student
    • Women in tech
    • Student organisations at ITU
    • Study start
    • Labs for students
    • Special Educational Support (SPS)
    • Study and Career Guidance
    • Exchange student
    • Become an exchange student
    • Guest Students
    • Who can be a guest student?
    • ITU Summer University
    • Open House
    • Open House - BSc programmes
    • Open House - MSc programmes
  • Professional Education
    • Master in IT Management
    • Master in IT Management
    • Admission and entry requirements
    • Contact
    • Single Subjects
    • About single subjects
    • Admission and entry requirements
    • Contact
    • Short courses | ITU Professional Courses
    • See all short courses
    • Contact
    • Contact
    • Contact us here
  • Research
    • Sections
    • Data Science
    • Data, Systems, and Robotics
    • Digital Business Innovation
    • Digitalization Democracy and Governance
    • Human-Computer Interaction and Design
    • Play Culture and AI
    • Software Engineering
    • Technologies in Practice
    • Theoretical Computer Science
    • Research Centres
    • Centre for Digital Play
    • Center for Climate IT
    • Center for Computing Education Research
    • Centre for Digital Welfare
    • Centre for Information Security and Trust
    • Research Centre for Government IT
    • Danish Institute for IT Program Management
    • Research entities
    • Research centers
    • Sections
    • Research groups
    • Labs
    • ITU Research Portal
    • Find Researcher
    • Find Research
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Technical Reports
    • Technical Reports
    • PhD Programme
    • About the PhD Programme
    • PhD Courses
    • PhD Defences
    • PhD Positions
    • Types of Enrolment
    • PhD Admission Requirements
    • PhD Handbook
    • PhD Support
  • Collaboration
    • Collaboration with students
    • Project collaboration
    • Project Market
    • Student worker
    • Project postings
    • Job and Project bank
    • Employer Branding
    • IT Match Making
    • Hiring an ITU student or graduate
    • Make a post in the job bank
    • Research collaboration
    • Read more about research collaboration at ITU
    • Industrial PhD
    • Hire an Industrial PhD
    • Maritime Hub
    • Innovation and entrepreneurship
    • ITU Business Development
    • ITU NextGen
  • About ITU
    • About ITU
    • Press
    • Vacancies
    • Contact
  • DK
ITU
ITU  /  Research  /  Technical Reports  /  Technical Reports Archive  /  2008  /  Minimizing Lid Overstows in Master Stowage Plans for Container Vessels is NP-Complete
  • Research
    • Research Sections
    • Research Ethics and Integrity
    • Good Scientific Practice
    • Research centers
    • Research groups
    • Labs
    • Technical Reports
      • Technical Reports Archive
        • 2024
        • 2023
        • 2021
        • 2018
        • 2017
        • 2016
        • 2015
        • 2014
        • 2013
        • 2012
        • 2011
        • 2010
        • 2009
        • 2008
          • A Language for the Cell
          • A Generic Language for Biological Systems based on Bigraphs
          • Verifying design patterns in hoare type theory
          • Type Systems for Bigraphs
          • Preliminary Proceedings First International Workshop on Formal Methods for Wireless Systems (FMWS'08)
          • Preliminary Proceedings of the 15th International Workshop on Expressiveness in Concurrency (EXPRESS'08)
          • Minimizing Lid Overstows in Master Stowage Plans for Container Vessels is NP-Complete
            • On Encoding the Pi-calculus in Higher-Order Calculi
            • Customization and Upgrading of ERP SystemsAn Empirical Perspective
            • Constraint Optimization for Highly Constrained Logistic Problems
            • Formalizing WS-BPEL and Higher Order Mobile Embedded Business Processes in the Bigraphical Programming Languages (BPL) Tool
            • An Experiment on Creating Enterprise Specific BPM Languages and Tools
          • 2007
          • 2006
          • 2005
          • 2004
          • 2003
          • 2002
          • 2001
          • 2000
      • PhD Programme

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

    TR-2008-107, Authors: Mai Lise Ajspur, Rune Møller Jensen, and Nicolas Guilbert

    Mai Lise Ajspur, Rune Møller Jensen, and Nicolas Guilbert

    March 2008

    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.


    Technical report TR-2008-107 in IT University Technical Report Series, March 2008.

    Available as PDF.


    Contact us

    Phone
    +45 7218 5000
    E-mail
    itu@itu.dk

    All contact information

    Web Accessibility Statement

    Find us

    IT University of Copenhagen
    Rued Langgaards Vej 7
    DK-2300 Copenhagen S
    Denmark
    How to get here

    Follow us

    ITU Student /
    Privacy /
    EAN-nr. 5798000417878/
    CVR-nr. 29 05 77 53 /
    P-nummer 1005162959

    This page is printed from https://www.itu.dk/404