A biased random-key genetic algorithm for the container pre-marshalling problem. (November 2016)

• Record Type: Journal Article
• Authors: Hottung, André; Tierney, Kevin
• Is Part Of: Computers & operations research. Volume 75(2016)
• Page Start: 83
• Page End: 102
• Publication Date: 2016-11
• Subjects: Container pre-marshalling -- Maritime applications -- Biased random-key genetic algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.05.011
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: The container pre-marshalling problem (CPMP) is performed at container terminals around the world to re-order containers so that they can be more efficiently transferred through the terminal. We introduce a novel decoder for a biased random-key genetic algorithm (BRKGA) that solves the CPMP. The decoder consists of a construction algorithm that learns how to best apply single and compound containers moves to quickly sort a bay of containers. Our approach finds better solutions than the state-of-the-art method on many instances of the standard pre-marshalling benchmarks in less computational time. Furthermore, we perform a computational analysis of different components of the BRKGA decoder to determine what types of heuristics work best for pre-marshalling problems, as well as conduct a feature space analysis of different pre-marshalling approaches. Abstract : Highlights: A novel biased random-key genetic algorithm approach for solving the container pre-marshalling problem (CPMP). The first metaheuristic procedure that learns how to solve CPMP instances. Outperforms the state-of-the-art method on many instances of standard benchmarks. Provides a feature space analysis showing comparing state-of-the-art methods and on what types of instances they work best.