A new exact approach for the Block Relocation Problem

  • Zusatzfeld:

    Many different industries face the problem of limited storage space, mainly because of high storage costs. The Blocks Relocation Problem (BRP) derives from this fact and therefore occurs frequently, e.g. in steel yard and container terminal operations where steel plates and containers, respectively, are stored on top of each other.

    The general setting consists of a two-dimensional stacking area with a given number of blocks (e.g. container or steel plates) stored in different stacks. There are two possible actions, the retrieval of a block out of the stacking area and the relocation of a block within the stacking area. The problem is to retrieve every block according to a given retrieval order. Since cranes can only pick the topmost block of a stack, and since blocks with low priority may cover high-priority blocks, frequent relocations might be necessary. These relocations require a lot of resources, e.g., cranes and operating personnel, which is why the BRP seeks to minimize the number of relocations.

    Typical exact approaches use B&B, A* search or IP models in order to solve the BRP. This thesis tries another approach using an IP model, the so called BRP-2, as a starting point. The idea is to use logic-based Benders decomposition to divide BRP-2 into a master problem and a subproblem by creating two subsets of variables and dropping one from the original formulation. The master problem is solved to optimality and its solution is used as an input to the subproblem. Following the idea of dynamic row generation, the subproblem generates a logic-based Benders cut to the master problem in every iteration. With the new information, the master problem is again solved and the input is handed over to the subproblem. This interplay continues until no more cuts are generated and the number of relocations is optimal with regard to the original problem BRP-2.