A tree search procedure for the container pre-marshalling problem

In the container pre-marshalling problem (CPMP) n items are given that belong to G different item groups (g = 1, … , G) and that are piled up in up to S stacks with a maximum stack height H. A move can shift one item from one stack to another one. A sequence of moves of minimum length has to be determined that transforms the initial item distribution so that in each of the stacks the items are sorted by their group index g in descending order. The CPMP occurs frequently in container terminals of seaports. It has to be solved when export containers, piled up in stacks, are sorted in a pre-marshalling process so that they can be loaded afterwards onto a ship faster and more efficiently. This article presents a heuristic tree search procedure for the CPMP. The procedure is compared to solution approaches for the CPMP that were published so far and turns out to be very competitive. Moreover, computational results for new and difficult CPMP instances are presented.

Highlight► Tree search procedure for solving the container pre-marshalling problem (CPMP). ► Procedure is based on a move classification scheme and compound moves for branching. ► Move classification scheme helps to compute very tight lower bound for moves. ► Approach turns out to be the most effective solution method so far.