The Block Retrieval Problem

Retrieving containers from a bay in a port terminal yard is a time consuming activity. The Block Retrieval Problem (BRTP) aims at minimizing the number of relocations, the unproductive moves of hindering containers, while retrieving target containers belonging to a customer. The choice of relocations leads to alternative bay configurations, some of which would minimize the relocations of forthcoming retrievals. The Bi-objective Block Retrieval Problem (2BRTP) includes a secondary objective, the minimization of the expected number of relocations for retrieving the containers of the next customer. This paper provides NP-Hardness proofs for both the BRTP and 2BRTP. A branch-and-bound algorithm and a linear time heuristic are developed for the BRTP; a branch-and-bound algorithm and a beam search algorithm are presented for the 2BRTP. Extensive computational tests on randomly generated instances as well as instances adapted from the literature are performed, and the results are presented.