Approaches for solving the container stacking problem with route distance minimization and stack rearrangement considerations

We consider an optimization problem of sequencing the operations of cranes that are used for internal movement of containers in maritime ports. Some features of this problem have been studied in the literature as the stacker crane problem (SCP). However, the scope of most literature (including SCP) is restricted to minimizing the route or distance traveled by cranes and the resulting movement-related costs. In practice, cargo containers are generally stacked or piled up in multiple separate columns, heaps or stacks at ports. So, the cranes need to often rearrange or shuffle such container stacks, in order to pick up any required container. If substantial re-stacking is involved, cranes expend considerable effort in container stack rearrangement operations. The problem of minimizing the total efforts/time of the crane must therefore account for both – the stack rearrangement costs and also the movement-related (route distance) costs. The consolidated problem differs from standard route distance minimization situations if stack rearrangement activities are considered. We formally define the consolidated problem, identify its characteristic features and hence devise suitable models for it. We formulate several alternative MIP approaches to solve the problem. We compare the performance of our MIP formulations and analyze their suitability for various possible situations.