A Hybrid Biased Random-Key Genetic Algorithm for the Container Relocation Problem

The Container Relocation Problem (CRP) has a crucial role in the logistics of containers. It involves minimizing the crane’s operating time in retrieving all the containers from the bay according to a predefined order. On the other hand, the Biased Random-Key Genetic algorithm (BRKGA) has recently shown favorable results in solving hard, real-world optimization problems. This chapter presents a hybrid BRKGA (HBRKGA) to solve the Container Relocation Problem (CRP). The proposed HBRKGA combines the exploration aspects of an intelligent, constructive metaheuristic, producing good initial solutions, with the exploitation abilities of a biased random-key genetic algorithm. This hybridization enables initializing the population with promising solutions, promoting a more efficient search in the genetic approach for better solutions. The experimental results, conducted on a large instance set, show that (i) HBRKGA offers performance benefits over the standard BRKGA (an operating time reduction of up to 93.6%) and (ii) HBRKGA is able to provide better solutions than existing CRP algorithms from the recent literature (achieving the best solution in up to 77.95% of the executions performed for one of the instance classes evaluated).