1. Proceedings
  2. I3M
  3. 2018
  4. HMS
  5. 10.46354/i3m.2018.hms.010

The block relocation problem under a realistic model of crane trajectories

  • a Y. Inaoka  , 
  • b S. Tanaka  
  • a,b Kyoto University
Cite as
Y. Inaoka, S. Tanaka (2018). The block relocation problem under a realistic model of crane trajectories. Proceedings of the 20st International Conference on Harbor, Maritime and Multimodal Logistic Modeling & Simulation (HMS 2018), pp. 62-66. DOI: https://doi.org/10.46354/i3m.2018.hms.010

Abstract

This paper addresses the block (container) relocation problem whose objective is to minimize total crane operation time necessary for retrieving all blocks (containers) stacked in tiers according to a specified order. We already proposed a branch-and-bound algorithm for this problem, but it simplified the crane trajectories so that an unnecessarily large margin between the placed containers and the spreader of the crane was considered. In this study we propose a more realistic model of crane trajectories and construct a branch-and-bound algorithm for the problem based on it. Then, we compare the two models by numerical experiment.

References

  1. Kim K. H. and Hong G.-P., 2006. A heuristic rule for relocating blocks. Computers & Operations Research, 33, 940-954.
  2. Wu K. -H. and Ting C. -J., 2016. A constructive heuristic for the container relocation problem. International Journal of Industrial Engineering, 23(3), 195-206.
  3. Jovanovic R. and Vo S., 2014. A chain heuristic for the Blocks Relocation Problem. Computers & Industrial Engineering, 75, 79-86.
  4. Jin B., Zhu W. and Lim A., 2015. Solving the container relocation problem by an improved greedy look ahead heuristic. European Journal of Operational Research, 240, 837-847.
  5. Zhu W., Qin H., Lim A. and Zhang H., 2012. Iterative deepening A* algorithms for the container relocation problem. IEEE Transactions on Automation Science and Engineering, 9, 710-722.
  6. Tanaka S. and Takii K., 2016. A faster branch-and-bound algorithm for the block relocation problem. IEEE Transactions on Automaton Science and Engineering, 13, 415-422.
  7. Tanaka S. and Mizuno F., 2018. An exact algorithm for the unrestricted block relocation problem Computers & Operations Research, 95, 12–31
  8. Caserta M., Schwarze S. and Vo S., 2012 A mathematical formulation and complexity consideration for the block relocation problem. European Journal of Operational Research, 219, 96–104.
  9. Zehendner E., Caserta M., Feillet D., Schwarze S. and Vo S., 2015. An improved mathematical formulation for the blocks relocation problem. European Journal of Operational Research, 245, 415-422.
  10. Galle V., Barnhart C. and Jaillet P., 2018. A new binary formulation of the restricted Container Relocation Problem based on a binary encoding of configurations. European Journal of Operational Research, 267, 467-477.
  11. Lee Y. and Lee Y. J., 2010. A heuristics for retrieving containers from a yard. Computers & Operations Research, 33, 940-954.
  12. Unlüyurt T. and Aydın C., 2012. Improved rehandling strategies for the container retrieval process. Journal of Advanced Transportation, 46, 378-393.
  13. Lin D.-Y., Lee Y.-J. and Lee Y., 2015. The container retrieval problem with respect to relocation. Transportation Research Part C, 52, 132-143
  14. Schwarze S. and Vo S., 2016. Analysis of alternative objectives for the blocks relocation problem, working paper.
  15. Inaoka Y. and Tanaka S., 2017 A branch-and-bound algorithm for the block relocation problem to minimize total crane operation time. Proc HMS 2017, 98-104
  16. Caserta M. and Vo S., 2011. Applying the corridor method to a blocks relocation problem. OR Spectrum, 33, 915-929.