A fill-and-reduce greedy algorithm for the container pre-marshalling problem

Ignacio Araya () and Martín Toledo ()
Additional contact information
Ignacio Araya: Pontificia Universidad Católica de Valparaíso
Martín Toledo: Pontificia Universidad Católica de Valparaíso

Operational Research, 2023, vol. 23, issue 3, No 13, 29 pages

Abstract: Abstract We address the Container Pre-Marshalling Problem (CPMP). The CPMP consists in ordering containers in stacks such that the retrieval of these containers is carried out without additional movements. The ordering has to be done in a minimum number of steps. Target-guided constructive heuristics report very good results in a short time. At each step, they select one poorly located container and rearrange it to an adequate position by a sequence of movements. The sequence of movements is generally generated by following a set of rules. In this work, we propose a different and more direct approach. Whenever possible, ordered stacks are filled by directly moving badly placed containers into them such that the containers become well placed. If it is not possible, then a stack is emptied or reduced to have more available slots, and the process is repeated. Unlike target-guided algorithms which rigidly adhere to a predefined sequence of movements for each badly placed container, our fill-and-reduce approach maintains the capacity to adapt to the evolving situation making choices based on the current state of the container stacks. The algorithm has shown superior performance compared to traditional target-guided heuristics, particularly in larger instances of classical benchmark sets. Furthermore, when embedded in a beam search algorithm, it reports the best results compared to traditional techniques that do not use machine learning.

Keywords: (O) Combinatorial optimization; Container premarshalling problem; Constructive algorithms; Beam search transportation (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12351-023-00791-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:operea:v:23:y:2023:i:3:d:10.1007_s12351-023-00791-9

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12351

DOI: 10.1007/s12351-023-00791-9

Access Statistics for this article

Operational Research is currently edited by Nikolaos F. Matsatsinis, John Psarras and Constantin Zopounidis

More articles in Operational Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().