Column generation for the container relocation problem

International audienceContainer terminals offer transfer facilities to move containers from vessels to trucks, and vice versa. Within the terminal the container yard serves as a temporary buffer where incoming containers are piled up in stacks. Outgoing containers need to be transported from the yard to a ship or to trucks in predefined sequences. Generally, the retrieval sequence does not match the stacking order within the yard. Since only the topmost container of each stack can be accessed, containers stored above it must be relocated first. A common procedure is to relocate containers within one bay (row of container stacks) since relocations between bays are very time consuming. In order to minimize turnaround times, a move sequence to retrieve containers from the bay in the prescribed order with a minimum number of reshuffles has to be determined. This problem is known as the container relocation problem (CRP) and is known to be NP-hard. We present a column generation approach for this problem. The master problem represents the bay layout over time with two sets of variables. State variables indicate the position of each container in the bay over time. Each movement variable represents a series of movements to retrieve exactly one container and to relocate containers stacked above it. The subproblem uses complete enumeration enhanced with bounding mechanisms to choose movement variables with negative reduced costs. Experiments are conducted for an exact method of the subproblem and for its heuristic variant. First results are very promising since both approaches provide very tight lower bounds on the minimum number of relocations