Solving the pre-marshalling problem to optimality with A* and IDA*

Kevin Tierney, Dario Pacino, Stefan Voß

    Research output: Contribution to journalJournal articleResearchpeer-review

    1446 Downloads (Pure)

    Abstract

    We present a novel solution approach to the container pre-marshalling problem using the A* and IDA* algorithms combined with several novel branching and symmetry breaking rules that significantly increases the number of pre-marshalling instances that can be solved to optimality. A* and IDA* are graph search algorithms that use heuristics combined with a complete graph search to find optimal solutions to problems. The container pre-marshalling problem is a key problem for container terminals seeking to reduce delays of inter-modal container transports. The goal of the container pre-marshalling problem is to find the minimal sequence of container movements to shuffle containers in a set of stacks such that the resulting stacks are arranged according to the time each container must leave the stacks. We evaluate our approach on three well-known datasets of pre-marshalling problem instances, solving over 500 previously unsolved instances to optimality, which is nearly twice as many instances as the current state-of-the-art method solves.
    Original languageEnglish
    JournalFlexible Services and Manufacturing Journal
    Volume29
    Issue number2
    Pages (from-to)223-259
    ISSN1936-6582
    DOIs
    Publication statusPublished - 2017

    Fingerprint

    Dive into the research topics of 'Solving the pre-marshalling problem to optimality with A* and IDA*'. Together they form a unique fingerprint.

    Cite this