A Decomposition Method for Finding Optimal Container Stowage Plans

Roberto Roberti, Dario Pacino*

*Corresponding author for this work

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.
    Original languageEnglish
    JournalTransportation Science
    Volume52
    Issue number6
    Pages (from-to)1297-1588
    ISSN0041-1655
    DOIs
    Publication statusPublished - 2018

    Cite this

    @article{b4451e0636a74c04b806a9267eca21d3,
    title = "A Decomposition Method for Finding Optimal Container Stowage Plans",
    abstract = "In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.",
    author = "Roberto Roberti and Dario Pacino",
    year = "2018",
    doi = "10.1287/trsc.2017.0795",
    language = "English",
    volume = "52",
    pages = "1297--1588",
    journal = "Transportation Science",
    issn = "0041-1655",
    publisher = "Institute for Operations Research and the Management Sciences (I N F O R M S)",
    number = "6",

    }

    A Decomposition Method for Finding Optimal Container Stowage Plans. / Roberti, Roberto; Pacino, Dario.

    In: Transportation Science, Vol. 52, No. 6, 2018, p. 1297-1588.

    Research output: Contribution to journalJournal articleResearchpeer-review

    TY - JOUR

    T1 - A Decomposition Method for Finding Optimal Container Stowage Plans

    AU - Roberti, Roberto

    AU - Pacino, Dario

    PY - 2018

    Y1 - 2018

    N2 - In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.

    AB - In transportation of goods in large container ships, shipping industries need to minimize the time spent at ports to load/unload containers. An optimal stowage of containers on board minimizes unnecessary unloading/reloading movements, while satisfying many operational constraints. We address the basic container stowage planning problem (CSPP). Different heuristics and formulations have been proposed for the CSPP, but finding an optimal stowage plan remains an open problem even for small-sized instances. We introduce a novel formulation that decomposes CSPPs into two sets of decision variables: the first defining how single container stacks evolve over time and the second modeling port-dependent constraints. Its linear relaxation is solved through stabilized column generation and with different heuristic and exact pricing algorithms. The lower bound achieved is then used to find an optimal stowage plan by solving a mixed-integer programming model. The proposed solution method outperforms the methods from the literature and can solve to optimality instances with up to 10 ports and 5,000 containers in a few minutes of computing time.

    U2 - 10.1287/trsc.2017.0795

    DO - 10.1287/trsc.2017.0795

    M3 - Journal article

    VL - 52

    SP - 1297

    EP - 1588

    JO - Transportation Science

    JF - Transportation Science

    SN - 0041-1655

    IS - 6

    ER -