Column generation for the container relocation problem

Abstract : Container 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.
Type de document :
Communication dans un congrès
International Annual Conference of the German Operations Research Society, Sep 2012, Hannover, Germany
Liste complète des métadonnées

https://hal-emse.ccsd.cnrs.fr/emse-00730787
Contributeur : Elisabeth Zehendner <>
Soumis le : mardi 11 septembre 2012 - 10:34:53
Dernière modification le : mercredi 29 novembre 2017 - 10:06:53

Identifiants

  • HAL Id : emse-00730787, version 1

Collections

Citation

Elisabeth Zehendner, Dominique Feillet. Column generation for the container relocation problem. International Annual Conference of the German Operations Research Society, Sep 2012, Hannover, Germany. 〈emse-00730787〉

Partager

Métriques

Consultations de la notice

104