Skip to main content
SpringerLink
Log in

Optimal routing in an automated storage/retrieval system with dedicated storage

  • Published:
IIE Transactions

Abstract

We address the sequencing of requests in an automated storage/retrieval system with dedicated storage. We consider the block sequencing approach, where a set of storage and retrieval requests is given beforehand and no new requests come in during operation. The objective for this static problem is to find a route of minimal total travel time in which all storage and retrieval requests may be performed. The problem of sequencing a list of retrievals is equivalent to the Traveling Salesman Problem (TSP), and thus NP-hard in general. We show that the special case of sequencing under the dedicated storage policy can be solved in polynomial time. The results apply to systems with arbitrary positions of the input and output stations. This generalizes the models in the literature, where only combined input/output stations are considered. Furthermore we identify a single command area in the rack. At the end we evaluate the model against heuristic procedures.

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

Similar content being viewed by others

References

  1. Hausman, W.H., Schwarz, L.B. and Graves, S.C. (1976) Optimal storage assignment in automatic warehousing systems. Management Science, 22 (6), 629–638.

    Google Scholar 

  2. Heskett, J.L. (1963) Cube-per-order index – a key to warehouse stock location. Transportation and Distribution Management, 3, 27–31.

    Google Scholar 

  3. Graves, S.C., Hausman, W.H. and Schwarz, L.B. (1977) Storage-retrieval interleaving in automatic warehousing systems. Management Science, 23 (9), 935–945.

    Google Scholar 

  4. Hwang, H. and Lim, J.M. (1993) Deriving an optimal dwell point of the storage/retrieval machine in an automated storage/retrieval system. International Journal of Production Research, 31 (11), 2591–2602.

    Google Scholar 

  5. Han, M.-H., McGinnis, L.F., Shieh, J.S. and White, J.A. (1987) On sequencing retrievals in an automated storage/retrieval system. IIE Transactions, 19 (1), 56–66.

    Google Scholar 

  6. Garey, M.R. and Johnson, D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-completeness, W.H. Freeman, New York.

    Google Scholar 

  7. Lee, H.F. and Schaefer, S.K. (1996) Retrieval sequencing for unit-load automated storage and retrieval systems with multiple openings. International Journal of Production Research, 34 (10), 2943–2962.

    Google Scholar 

  8. Murty, K.G. (1968) An algorithm for ranking all the assignments in order of increasing costs. Operations Research, 16 (3), 682–687.

    Google Scholar 

  9. Schwarz, L.B., Graves, S.C. and Hausman, W.H. (1978) Scheduling policies for automatic warehousing systems: simulation results. AIIE Transactions, 10 (3), 260–270.

    Google Scholar 

  10. Linn, R.J. and Wysk, R.A. (1987) An analysis of control strategies for an automated storage/retrieval system. INFOR, 25 (1), 66–83.

    Google Scholar 

  11. Linn, R.J. and Wysk, R.A. (1990) An expert system framework for automated storage and retrieval system control. Computers and Industrial Engineering, 18 (1), 37–48.

    Google Scholar 

  12. Seidmann, A. (1988) Intelligent control schemes for automated storage and retrieval systems. International Journal of Production Research, 26 (5), 931–952.

    Google Scholar 

  13. Linn, R.J. and Xie, X (1993) A simulation analysis of sequencing rules in a pull-based assembly facility. International Journal of Production Research, 31 (10), 2355–2367.

    Google Scholar 

  14. van den Berg, J.P. (1996) Planning and control of warehousing systems. Ph.D. thesis, University of Twente, Fac. of Mech. Eng., Enschede, The Netherlands, Ch. 7.

  15. Burkard, R.E., Deineko, V.G., van Dal, R., van der Veen, J.A.A. and Woeginger, G.J. (1996) Well-solvable special cases of the TSP: a survey. Memorandum, Eindhoven University of Technology, Dep. of Math. and Comp. Science, Eindhoven, The Netherlands.

    Google Scholar 

  16. Ratli., H.D. and Rosenthal, A.S. (1983) Order-picking in a rectangular warehouse: a solvable case of the traveling salesman problem. Operations Research, 31 (3), 507–521.

    Google Scholar 

  17. Bartholdi, III, J.J. and Platzman, L.K. (1986) Retrieval strategies for a carousel conveyor. IIE Transactions, 18 (2), 166–173.

    Google Scholar 

  18. Golden, B.L. and Stewart, W.R. (1985) Empirical analysis of heuristics, in Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G. and Shmoys, D.B. (ed), The Traveling Salesman Problem, John Wiley & Sons, Chichester, Ch. 7.

    Google Scholar 

  19. Bozer, Y.A., and White, J.A., (1984) Travel-time models for automated storage/retrieval systems. IIE Transactions, 16 (4), 329– 338.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Faculty of Mechanical Engineering, Production and Operations Management Group, University of Twente, P.O. Box 217, 7500 AE, Enschede, The Netherlands

    JEROEN P. van den BERG & A.J.R.M. (NOUD) Gademann

Authors
  1. JEROEN P. van den BERG
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. A.J.R.M. (NOUD) Gademann
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

van den BERG, J.P., Gademann, A.(. Optimal routing in an automated storage/retrieval system with dedicated storage. IIE Transactions 31, 407–415 (1999). https://doi.org/10.1023/A:1007545122755

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1007545122755

Keywords

Search

Navigation