6533b7dcfe1ef96bd127345b
RESEARCH PRODUCT
A beam search algorithm for minimizing crane times in premarshalling problems
Consuelo Parreño-torresFrancisco ParrenoRamon Alvarez-valdessubject
crane timeInformation Systems and ManagementGeneral Computer SciencelogisticsModeling and Simulationcontainer premarshallingUNESCO::CIENCIAS TECNOLÓGICASManagement Science and Operations Researchbeam searchIndustrial and Manufacturing Engineeringdescription
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.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2022-11-01 | European Journal of Operational Research |