1. Proceedings
  2. I3M
  3. 2020
  4. EMSS
  5. 10.46354/i3m.2020.emss.027

Effects of arrival uncertainty on solver performance in dynamic stacking problems

  • a Sebastian Raggl ,
  • b Andreas Beham ,
  • c Stefan Wagner ,
  • d Michael Affenzeller 
  • a,b,c,d  University of Applied Sciences Upper Austria, Hagenberg, Austria
  • a,d 2Johannes Kepler University, Linz, Austria
Cite as
Raggl S., Beham A., Wagner S., Affenzeller M. (2020). Effects of arrival uncertainty on solver performance in dynamic stacking problems. Proceedings of the 32nd European Modeling & Simulation Symposium (EMSS 2020), pp. 193-200. DOI: https://doi.org/10.46354/i3m.2020.emss.027

Abstract

In this paper we present a dynamic stacking problem with uncertainty. We developed a simulation environment, an optimizer for solving it, and performance measures to determine the success of the optimizer. The problem requires handling incoming blocks, stacking them efficiently, and meeting deadlines for delivery, while not knowing exactly when blocks will arrive or when they will be ready for delivery. The optimizer models the problem as a dynamic Block Relocation Problem and solves it using a branch&bound based heuristic. The simulation and optimizer run concurrently and the distribution of random variables is not disclosed to the solver and must, therefore, be estimated. We study the influence of uncertainty on the solver and show that the degree of uncertainty has a significant impact on the performance of the overall system. We also experiment with different measures to estimate uncertain arrival times and show that the choice of measure is important for achieving good performance.

References

  1. Akyüz, H. and Chung-Yee, L. (2014). A mathematical formulation and efficient heuristics for the dynamic container relocation problem. Naval Research Logistics (NRL), 61(2):101–118.
  2. Beham, A., Kronberger, G., Karder, J., Kommenda, M., Scheibenpflug, A., Wagner, S., and Affenzeller, M. (2014). Integrated simulation and optimization in heuristiclab. In Proceedings of the 26th European Modeling and Simulation Symposium EMSS 2014, pages 418–423.
  3. Beham, A., Raggl, S., Wagner, S., and Affenzeller, M. (2019). Uncertainty in real-world steel stacking problems. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, pages 1438–1440.
  4. Galle, V., Manshadi, V. H., Boroujeni, S. B., Barnhart, C., and Jaillet, P. (2018). The Stochastic Container Relocation Problem. Transportation Science, 52(5):1035–1058
  5. Kang, J., Ryu, K. R., and Kim, K. H. (2006). Deriving stacking strategies for export containers with uncertain weight information. Journal of Intelligent Manufacturing, 17(4):399–410.
  6. Ku, D. and Arthanari, T. S. (2016). Container relocation problem with time windows for container departure. European Journal of Operational Research, 252(3):1031–1039.
  7. Nguyen, T. T., Yang, S., and Branke, J. (2012). Evolutionary dynamic optimization: A survey of the state of the art. Swarm and Evolutionary Computation, 6:1–24.
  8. Raggl, S., Beham, A., Tricoire, F., and Affenzeller, M. (2018). Solving a real world steel stacking problem. International Journal of Service and Computing Oriented Manufacturing, 3(2/3):94.
  9. Raggl, S., Beham, A., Wagner, S., and Affenzeller, M. (2020). Solution Approaches for the Dynamic Stacking Problem. In GECCO ’20: Proceedings of the Genetic and Evolutionary Computation Conference Companion. (accepted).
  10. Rei, R. and Pedroso, J. P. (2013). Tree search for the stacking problem. Annals of Operations Research, 203(1):371–388.
  11. Tricoire, F., Scagnetti, J., and Beham, A. (2018). New insights on the block relocation problem. Computers and Operations Research, 89:127–139.
  12. Zehendner, E., Feillet, D., and Jaillet, P. (2017). An algorithm with performance guarantee for the Online Container Relocation Problem. European Journal of Operational Research, 259(1):48–62.