The Corridor Method - A General Solution Concept with Application to the Blocks Relocation Problem

Marco Caserta 1, Stefan Voss 2, and Moshe Sniedovich 3

1 Institut fÄur Wirtschaftsinformatik, UniversitÄat Hamburg, Von-Melle-Park 5, 20146,
Hamburg, Germany marco.caserta@uni-hamburg.de

2 Institut fÄur Wirtschaftsinformatik, UniversitÄat Hamburg, Von-Melle-Park 5, 20146,
Hamburg, Germany stefan.voss@uni-hamburg.de

3 Department of Mathematics and Statistics, The University of Melbourne, Australia
m.sniedovich@ms.unimelb.edu.au

Abstract. In this paper we present a Corridor Method inspired algo-
rithm for the blocks relocation problem in block stacking systems, with
application in the stacking of container terminals in a yard. The proposed
algorithm is based upon a dynamic programming formulation that cap-
tures the state of the system after each block movement. In order to
reduce the number of the state variables, we de¯ne a two-dimensional
\corridor" around the incumbent blocks con¯guration by imposing ex-
ogenous constraints on the solution space of the problem and we apply
a dynamic programming inspired scheme on a reduced portion of the
original problem. Computational results on medium and large size prob-
lem instances allow to draw conclusions about the e®ectiveness of the
proposed scheme.