A tree search procedure for the container relocation problem

In the container relocation problem (CRP) n items are given that belong to G different itemgroups (g = 1,…,G). The items are piled up in up to S stacks with a maximum stack height H.A move can either shift one item from the top of a stack to the top of another one (relocation)or pick an item from the top of a stack and entirely remove it (remove). A move of the lattertype is only feasible if the group index of the item is minimum compared to all remainingitems in all stacks. A move sequence of minimum length has to be determined that removesall items from the stacks. The CRP occurs frequently in container terminals of seaports. It hasto be solved when containers, piled up in stacks, need to be transported to a ship or to trucksin a predefined sequence. This article presents a heuristic tree search procedure for the CRP.The procedure is compared to all known solution approaches for the CRP and turns out to bevery competitive.