Container terminals are exchange hubs that interconnect many transportation modes and facilitate the flow of containers. Among other elements, terminals include a yard which serves as temporary storage space. In the yard, containers are piled up by cranes to form blocks of stacks. During the shipment process, containers are carried from the stacks to ships following a given sequence. Hence, if a high priority container is placed below low priority ones, such obstructing containers have to be moved (relocated) to other stacks. Given a set of stacks and a retrieval sequence, the aim in the Pre-marshalling Problem (PMP) is to sort the initial configuration according to the retrieval sequence using a minimum number of relocations, so that no new relocations are needed during the shipment. The objective in the Block Relocation Problem (BRP) is to retrieve all the containers according to the retrieval sequence by using a minimum number of relocations. This paper presents a new unified integer programming model for solving the PMP, the BRP, and the Restricted BRP (R-BRP) variant. The new formulations are compared with existing mathematical models for these problems, as well as with other exact methods that combines combinatorial lower bounds and the branch-and-bound (B&B) framework, by using a large set of instances available in the literature. The numerical experiments show that the proposed models are able to outperform the approaches based on mathematical programming. Nevertheless, the B&B algorithms achieve the best results both in terms of computation time and number of instances solved to optimality.

A new effective unified model for solving the Pre-marshalling and Block Relocation Problems

wolfler
2018-01-01

Abstract

Container terminals are exchange hubs that interconnect many transportation modes and facilitate the flow of containers. Among other elements, terminals include a yard which serves as temporary storage space. In the yard, containers are piled up by cranes to form blocks of stacks. During the shipment process, containers are carried from the stacks to ships following a given sequence. Hence, if a high priority container is placed below low priority ones, such obstructing containers have to be moved (relocated) to other stacks. Given a set of stacks and a retrieval sequence, the aim in the Pre-marshalling Problem (PMP) is to sort the initial configuration according to the retrieval sequence using a minimum number of relocations, so that no new relocations are needed during the shipment. The objective in the Block Relocation Problem (BRP) is to retrieve all the containers according to the retrieval sequence by using a minimum number of relocations. This paper presents a new unified integer programming model for solving the PMP, the BRP, and the Restricted BRP (R-BRP) variant. The new formulations are compared with existing mathematical models for these problems, as well as with other exact methods that combines combinatorial lower bounds and the branch-and-bound (B&B) framework, by using a large set of instances available in the literature. The numerical experiments show that the proposed models are able to outperform the approaches based on mathematical programming. Nevertheless, the B&B algorithms achieve the best results both in terms of computation time and number of instances solved to optimality.
2018
Block Relocation Problem; Container terminals; Integer programming; Pre-Marshalling Problem; Modeling and simulation; Management science and operations research; Information systems and management
File in questo prodotto:
File Dimensione Formato  
PMProblem.pdf

accesso aperto

Tipologia: versione pre-print
Dimensione 591.25 kB
Formato Adobe PDF
591.25 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11584/254452
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 35
  • ???jsp.display-item.citation.isi??? 30
social impact