Skip to main content
SpringerLink
Log in

Motion and layout planning in a grid-based early baggage storage system

Heuristic algorithms and a simulation study

  • Regular Article
  • Published:
OR Spectrum Aims and scope Submit manuscript

Abstract

Grid-based storage systems consist of many adjacent square cells arranged in a rectangular grid. Cells are either empty or occupied by a storage item. Items are stored on conveyors and are movable simultaneously and independently into the four cardinal directions. This technology allows for very dense storage. Previous research on grid-based storages has mainly focused on retrieval performance analysis of a single storage item. In this paper, we contribute a framework for the efficient storage and retrieval of a large number of storage items based on a multi-agent routing algorithm. We evaluate the framework using different storage and retrieval strategies in a simulation-based case study, in which we design and analyze a grid-based early baggage storage system at a major German airport.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10
Fig. 11
Fig. 12
Fig. 13

Similar content being viewed by others

References

  • Alfieri A, Cantamessa M, Monchiero A, Montagna F (2010) Heuristics for puzzle-based storage systems driven by a limited set of automated guided vehicles. J Intell Manuf 23(5):1695–1705

    Article  Google Scholar 

  • Desaulniers G, Langevin A, Riopel D, Villeneuve B (2003) Dispatching and conflict-free routing of automated guided vehicles: an exact approach. Int J Flex Manuf Syst 15(4):309–331

    Article  Google Scholar 

  • Dijkstra EW (1959) A note on two problems in connexion with graphs. Numer Math 1(1):269–271

    Article  Google Scholar 

  • Doppler (2016) DCS 2DL. http://doppler.gr/en/products/parking-systems/dps-xryc/. Accessed 06 Dec 2016

  • Gebhardt (2016) Gebhardt flexconveyor. http://www.gebhardt-foerdertechnik.de/de/produkte/flexconveyor/. Accessed 06 Dec 2016

  • Gue KR (2006) Very high density storage systems. IIE Trans 38:79–90

    Article  Google Scholar 

  • Gue KR, Kim S (2007) Puzzle-based storage systems. Nav Res Logist 54(5):556–567

    Article  Google Scholar 

  • Gue KR, Furmans K, Seibold Z, Uludag O (2014) Gridstore: a puzzle-based storage system with decentralized control. IEEE Trans Autom Sci Eng 11(2):429–438

    Article  Google Scholar 

  • Hart P, Nilsson N, Raphael B (1968) A formal basis for the heuristic determination of minimum cost paths. IEEE Trans Syst Sci Cyber 4(2):100–107

    Article  Google Scholar 

  • Hatzack W, Nebel B (2014) The operational traffic control problem: computational complexity and solutions. In: 6th European conference on planning

  • Hyundai Elevator (2011) Hip (hydundai integrated parking systems). http://hyundaielevator.co.kr/eng/parking/car/HIP/large_scale.jsp. Accessed 06 Dec 2016

  • ICAM (2016) Smoov ASRV generation 2. http://www.smoov-asrv.eu/. Accessed 06 Dec 2016

  • IFL IfFuL (2015) Gridstore. https://www.youtube.com/watch?v=LxzBuB_JCN4. Accessed 06 Dec 2016

  • Kim CW, Tanchoco JMA (1991) Conflict-free shortest-time bidirectional AGV routeing. Int J Prod Res 29(12):2377–2391

    Article  Google Scholar 

  • Kota VR, Taylor D, Gue KR (2010) Retrieval time performance in puzzle-based storage systems. In: Johnson A, Miller J (eds) Proceedings of the 2010 industrial engineering research conference (IERC)

  • Kota VR, Taylor D, Gue KR (2015) Retrieval time performance in puzzle-based storage systems. J Manuf Technol Manag 26(4):582–602

    Article  Google Scholar 

  • Latombe JC (1991) Robot motion planning. Springer, Berlin

    Book  Google Scholar 

  • Mayer SH (2009) Development of a completely decentralized control system for modular continuous conveyors. Ph.D. thesis, Karlsruhe, Karlsruhe Univ, Diss, 2009. http://d-nb.info/101409898X/34

  • Mutrade (2014) Automatic parking system. http://www.mutrad.com/AutomaticParkingSystem.html. Accessed 06 Dec 2016

  • Nobbe C (2015) Vergleich technischer implementierungen für gridflow-systeme. Ph.D. thesis

  • ODTH (2015) Magic black box. http://www.odth.be/magic-black-box/?lang=en. Accessed 06 Dec 2016

  • Roodbergen KJ, Vis IF (2009) A survey of literature on automated storage and retrieval systems. Eur J Oper Res 194(2):343–362

    Article  Google Scholar 

  • RR Parkon (2014) Puzzle parking. http://www.rrparkon.com/product/puzzle-parking. Accessed 06 Dec 2016

  • Schwab M (2015) A decentralized control strategy for high density material flow systems with automated guided vehicles. Ph.D. thesis

  • Sgall J (1998) On-line scheduling. In: Fiat A, Woeginger GJ (eds) Online algorithms: the state of the art. Springer, Berlin, pp 196–231

    Chapter  Google Scholar 

  • Ter Mors AW, Witteveen C, Zutt J, Kuipers FA (2010) Context-aware route planning. In: Dix J, Witteveen C (eds) Multiagent system technologies, 8th German Conference, MATES 2010, Leipzig, Germany, vol 6251. Lecture notes in computer science. Springer, pp 138–149

  • Van Den Berg JP, Gademann A (1999) Optimal routing in an automated storage/retrieval system with dedicated storage. IIE Trans 31(5):407–415

    Article  Google Scholar 

  • Woehr (2016) Liverpool—Parksafe 583. http://www.woehr.de/en/project/liverpool-parksafe-583.html. Accessed 06 Dec 2016

  • Yalcin A, Koberstein A, Schocke KO (2018) An optimal and a heuristic algorithm for the single-item retrieval problem in puzzle-based storage systems with multiple escorts. Int J Prod Res. https://doi.org/10.1080/00207543.2018.1461952

  • Zaerpour N, Yu Y, de Koster RBM (2015) Small is beautiful: a framework for evaluating and optimizing live-cube compact storage systems. Transp Sci. https://doi.org/10.1287/trsc.2015.0586

Download references

Acknowledgements

The present study was financially supported by Landes-Offensive zur Entwicklung Wissenschaftlich-ökonomischer Exzellenz mit der Förderlinie 3: LOEWE-KMU-Verbundvorhaben of Hesses Ministry of Higher Education, Research, and Arts from the research funding program (Grant No. HA 405/13-44), (Grant No. HA 422/14-32).

Author information

Authors and Affiliations

  1. European University Viadrina Frankfurt (Oder), Große Scharnstr. 59, 15230, Frankfurt (Oder), Germany

    Altan Yalcin & Achim Koberstein

  2. Frankfurt University of Applied Sciences, Nibelungenplatz 1, 60318, Frankfurt (Main), Germany

    Kai-Oliver Schocke

Authors
  1. Altan Yalcin
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Achim Koberstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Kai-Oliver Schocke
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Achim Koberstein.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yalcin, A., Koberstein, A. & Schocke, KO. Motion and layout planning in a grid-based early baggage storage system. OR Spectrum 41, 683–725 (2019). https://doi.org/10.1007/s00291-018-0545-z

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00291-018-0545-z

Keywords

Search

Navigation