A beam search algorithm for minimizing crane times in premarshalling problems

Consuelo Parreño-Torres, Ramon Alvarez-Valdes and Francisco Parreño

European Journal of Operational Research, 2022, vol. 302, issue 3, 1063-1078

Abstract: The premarshalling problem consists of sorting the containers placed in a bay of the container yard so that they can be retrieved in the order in which they will be required. We study the premarshalling problem with crane time minimization objective and develop a beam search algorithm, with some new elements adapted to the characteristics of the problem, to solve it. We propose various evaluation criteria, depending on the type of container movement, for its local evaluation; a new heuristic algorithm including local search for blue its global evaluation; and several new dominance rules. The computational study shows the contribution of each new element. The performance of the complete algorithm is tested on well-known benchmarks. The beam search algorithm matches all known optimal solutions, improves on the known suboptimal solutions, and obtains solutions for the largest instances, for which no solution had previously been found.

Keywords: Logistics; Container premarshalling; Crane time; Beam search (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221722000753
Full text for ScienceDirect subscribers only

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:eee:ejores:v:302:y:2022:i:3:p:1063-1078

DOI: 10.1016/j.ejor.2022.01.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().