IDEAS home Printed from https://ideas.repec.org/a/spr/orspec/v44y2022i2d10.1007_s00291-021-00663-8.html
   My bibliography  Save this article

New solution procedures for the order picker routing problem in U-shaped pick areas with a movable depot

Author

Listed:
  • Heiko Diefenbach

    (Technical University of Darmstadt)

  • Simon Emde

    (Aarhus University)

  • Christoph H. Glock

    (Technical University of Darmstadt)

  • Eric H. Grosse

    (Saarland University)

Abstract

This paper develops new solution procedures for the order picker routing problem in U-shaped order picking zones with a movable depot, which has so far only been solved using simple heuristics. The paper presents the first exact solution approach, based on combinatorial Benders decomposition, as well as a heuristic approach based on dynamic programming that extends the idea of the venerable sweep algorithm. In a computational study, we demonstrate that the exact approach can solve small instances well, while the heuristic dynamic programming approach is fast and exhibits an average optimality gap close to zero in all test instances. Moreover, we investigate the influence of various storage assignment policies from the literature and compare them to a newly derived policy that is shown to be advantageous under certain circumstances. Secondly, we investigate the effects of having a movable depot compared to a fixed one and the influence of the effort to move the depot.

Suggested Citation

  • Heiko Diefenbach & Simon Emde & Christoph H. Glock & Eric H. Grosse, 2022. "New solution procedures for the order picker routing problem in U-shaped pick areas with a movable depot," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 44(2), pages 535-573, June.
    • Handle: RePEc:spr:orspec:v:44:y:2022:i:2:d:10.1007_s00291-021-00663-8
    DOI: 10.1007/s00291-021-00663-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00291-021-00663-8
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00291-021-00663-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Fangyu Chen & Gangyan Xu & Yongchang Wei, 2019. "Heuristic routing methods in multiple-block warehouses with ultra-narrow aisles and access restriction," International Journal of Production Research, Taylor & Francis Journals, vol. 57(1), pages 228-249, January.
    2. Christoph H. Glock & Eric H. Grosse & Ralf M. Elbert & Torsten Franzke, 2017. "Maverick picking: the impact of modifications in work schedules on manual order picking processes," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6344-6360, November.
    3. Tadumadze, Giorgi & Emde, Simon & Diefenbach, Heiko, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 120609, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    4. Martina Calzavara & Christoph H. Glock & Eric H. Grosse & Fabio Sgarbossa, 2019. "An integrated storage assignment method for manual order picking warehouses considering cost, workload and posture," International Journal of Production Research, Taylor & Francis Journals, vol. 57(8), pages 2392-2408, April.
    5. Grosse, E. H. & Glock, C. H. & Ballester-Ripoll, R., 2014. "A simulated annealing approach for the joint order batching and order picker routing problem with weight restrictions," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65331, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    6. Thomas Chabot & Rahma Lahyani & Leandro C. Coelho & Jacques Renaud, 2017. "Order picking problems under weight, fragility and category constraints," International Journal of Production Research, Taylor & Francis Journals, vol. 55(21), pages 6361-6379, November.
    7. Muppani (Muppant), Venkata Reddy & Adil, Gajendra Kumar, 2008. "A branch and bound algorithm for class based storage location assignment," European Journal of Operational Research, Elsevier, vol. 189(2), pages 492-507, September.
    8. Melh Çelk & Haldun Süral, 2014. "Order picking under random and turnover-based storage policies in fishbone aisle warehouses," IISE Transactions, Taylor & Francis Journals, vol. 46(3), pages 283-300.
    9. Alena Otto & Nils Boysen & Armin Scholl & Rico Walter, 2017. "Ergonomic workplace design in the fast pick area," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 39(4), pages 945-975, October.
    10. Matusiak, Marek & de Koster, René & Kroon, Leo & Saarinen, Jari, 2014. "A fast simulated annealing method for batching precedence-constrained customer orders in a warehouse," European Journal of Operational Research, Elsevier, vol. 236(3), pages 968-977.
    11. Eric H. Grosse & Christoph H. Glock & W. Patrick Neumann, 2017. "Human factors in order picking: a content analysis of the literature," International Journal of Production Research, Taylor & Francis Journals, vol. 55(5), pages 1260-1276, March.
    12. Kees Jan Roodbergen & Iris F.A. Vis & G. Don Taylor, 2015. "Simultaneous determination of warehouse layout and control policies," International Journal of Production Research, Taylor & Francis Journals, vol. 53(11), pages 3306-3326, June.
    13. Pan, Jason Chao-Hsien & Shih, Po-Hsun & Wu, Ming-Hung, 2015. "Order batching in a pick-and-pass warehousing system with group genetic algorithm," Omega, Elsevier, vol. 57(PB), pages 238-248.
    14. Giorgi Tadumadze & Simon Emde & Heiko Diefenbach, 2020. "Exact and heuristic algorithms for scheduling jobs with time windows on unrelated parallel machines," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(2), pages 461-497, June.
    15. Calzavara, M. & Glock, C. H. & Grosse, E. H. & Persona, A. & Sgarbossa, F., 2017. "Analysis of economic and ergonomic performance measures of different rack layouts in an order picking warehouse," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 82127, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    16. Fang, Kan & Wang, Shijin & Pinedo, Michael L. & Chen, Lin & Chu, Feng, 2021. "A combinatorial Benders decomposition algorithm for parallel machine scheduling with working-time restrictions," European Journal of Operational Research, Elsevier, vol. 291(1), pages 128-146.
    17. Calzavara, M. & Glock, C. H. & Grosse, E. H. & Sgarbossa, F., 2019. "An integrated storage assignment method for manual order picking warehouses considering cost, workload and posture," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 107009, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    18. de Koster, Rene & Le-Duc, Tho & Roodbergen, Kees Jan, 2007. "Design and control of warehouse order picking: A literature review," European Journal of Operational Research, Elsevier, vol. 182(2), pages 481-501, October.
    19. Richard Bellman, 1954. "On some applications of the theory of dynamic programming to logistics," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 1(2), pages 141-153, June.
    20. Kevin Gue & Russell Meller, 2009. "Aisle configurations for unit-load warehouses," IISE Transactions, Taylor & Francis Journals, vol. 41(3), pages 171-182.
    21. Dominik Kress & David Müller & Jenny Nossack, 2019. "A worker constrained flexible job shop scheduling problem with sequence-dependent setup times," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(1), pages 179-217, March.
    22. Gu, Jinxiang & Goetschalckx, Marc & McGinnis, Leon F., 2007. "Research on warehouse operation: A comprehensive review," European Journal of Operational Research, Elsevier, vol. 177(1), pages 1-21, February.
    23. Gianni Codato & Matteo Fischetti, 2006. "Combinatorial Benders' Cuts for Mixed-Integer Linear Programming," Operations Research, INFORMS, vol. 54(4), pages 756-766, August.
    24. Çağla Cergibozan & A. Serdar Tasan, 2019. "Order batching operations: an overview of classification, solution techniques, and future research," Journal of Intelligent Manufacturing, Springer, vol. 30(1), pages 335-349, January.
    25. van Gils, Teun & Caris, An & Ramaekers, Katrien & Braekers, Kris, 2019. "Formulating and solving the integrated batching, routing, and picker scheduling problem in a real-life spare parts warehouse," European Journal of Operational Research, Elsevier, vol. 277(3), pages 814-830.
    26. Battini, D. & Glock, C. H. & Grosse, E. H. & Persona, A. & Sgarbossa, F., 2016. "Human energy expenditure in order picking storage assignment: a bi-objective method," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 77307, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    27. Diefenbach, Heiko & Glock, C. H., 2019. "Ergonomic and economic optimization of layout and item assignment of a U-shaped order picking zone," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 117196, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    28. Scholz, André & Henn, Sebastian & Stuhlmann, Meike & Wäscher, Gerhard, 2016. "A new mathematical programming formulation for the Single-Picker Routing Problem," European Journal of Operational Research, Elsevier, vol. 253(1), pages 68-84.
    29. Soondo Hong & Andrew Johnson & Brett Peters, 2012. "Large-scale order batching in parallel-aisle picking systems," IISE Transactions, Taylor & Francis Journals, vol. 44(2), pages 88-106.
    30. Grosse, E. H. & Glock, C. H. & Neumann, W. P., 2017. "Human factors in order picking: a content analysis of the literature," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 80630, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    31. Grosse, E. H. & Glock, C. H. & Jaber, M. Y. & Neumann, W. P., 2015. "Incorporating human factors in order picking planning models: framework and research opportunities," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 65237, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    32. Glock, C. H. & Grosse, E. H. & Abedinnia, Hamid & Emde, Simon, 2019. "An integrated model to improve ergonomic and economic performance in order picking by rotating pallets," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 106923, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    33. Eric H. Grosse & Christoph H. Glock & Mohamad Y. Jaber & W. Patrick Neumann, 2015. "Incorporating human factors in order picking planning models: framework and research opportunities," International Journal of Production Research, Taylor & Francis Journals, vol. 53(3), pages 695-717, February.
    34. H. Donald Ratliff & Arnon S. Rosenthal, 1983. "Order-Picking in a Rectangular Warehouse: A Solvable Case of the Traveling Salesman Problem," Operations Research, INFORMS, vol. 31(3), pages 507-521, June.
    35. Glock, Christoph H. & Grosse, Eric H. & Abedinnia, Hamid & Emde, Simon, 2019. "An integrated model to improve ergonomic and economic performance in order picking by rotating pallets," European Journal of Operational Research, Elsevier, vol. 273(2), pages 516-534.
    36. Richard Bellman, 1954. "Some Applications of the Theory of Dynamic Programming---A Review," Operations Research, INFORMS, vol. 2(3), pages 275-288, August.
    37. J. N. Hooker, 2007. "Planning and Scheduling by Logic-Based Benders Decomposition," Operations Research, INFORMS, vol. 55(3), pages 588-602, June.
    38. Petersen, Charles G. & Aase, Gerald, 2004. "A comparison of picking, storage, and routing policies in manual order picking," International Journal of Production Economics, Elsevier, vol. 92(1), pages 11-19, November.
    39. Mowrey, Corinne H. & Parikh, Pratik J., 2014. "Mixed-width aisle configurations for order picking in distribution centers," European Journal of Operational Research, Elsevier, vol. 232(1), pages 87-97.
    40. Roodbergen, Kees Jan & de Koster, Rene, 2001. "Routing order pickers in a warehouse with a middle aisle," European Journal of Operational Research, Elsevier, vol. 133(1), pages 32-43, August.
    41. Lu, Wenrong & McFarlane, Duncan & Giannikas, Vaggelis & Zhang, Quan, 2016. "An algorithm for dynamic order-picking in warehouse operations," European Journal of Operational Research, Elsevier, vol. 248(1), pages 107-122.
    42. Yasmeen Jaghbeer & Robin Hanson & Mats Ingemar Johansson, 2020. "Automated order picking systems and the links between design and performance: a systematic literature review," International Journal of Production Research, Taylor & Francis Journals, vol. 58(15), pages 4489-4505, July.
    43. van Gils, Teun & Ramaekers, Katrien & Caris, An & de Koster, René B.M., 2018. "Designing efficient order picking systems by combining planning problems: State-of-the-art classification and review," European Journal of Operational Research, Elsevier, vol. 267(1), pages 1-15.
    44. Henn, Sebastian & Wäscher, Gerhard, 2012. "Tabu search heuristics for the order batching problem in manual order picking systems," European Journal of Operational Research, Elsevier, vol. 222(3), pages 484-494.
    45. Glock, C. H. & Grosse, E. H. & Elbert, R. & Franzke, T., 2017. "Maverick picking: The impact of modifications in work schedules on manual order picking processes," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 83962, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    46. Melih Çelik & Haldun Süral, 2019. "Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic," International Journal of Production Research, Taylor & Francis Journals, vol. 57(3), pages 888-906, February.
    47. Masae, M. & Glock, C. H. & Vichitkunakorn, P., 2021. "A method for efficiently routing order pickers in the leaf warehouse," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 125847, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    48. Zulj, I. & Glock, C. H. & Grosse, E. H. & Schneider, Michael, 2018. "Picker routing and storage-assignment strategies for precedence-constrained order picking," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 105391, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    49. David Füßler & Nils Boysen & Konrad Stephan, 2019. "Trolley line picking: storage assignment and order sequencing to increase picking performance," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 41(4), pages 1087-1121, December.
    50. L. L. Barachet, 1957. "Letter to the Editor---Graphic Solution of the Traveling-Salesman Problem," Operations Research, INFORMS, vol. 5(6), pages 841-845, December.
    51. Masae, Makusee & Glock, Christoph H. & Vichitkunakorn, Panupong, 2021. "A method for efficiently routing order pickers in the leaf warehouse," International Journal of Production Economics, Elsevier, vol. 234(C).
    52. Öztürkoğlu, Ö. & Gue, K.R. & Meller, R.D., 2014. "A constructive aisle design model for unit-load warehouses with multiple pickup and deposit points," European Journal of Operational Research, Elsevier, vol. 236(1), pages 382-394.
    53. Glock, C. H. & Grosse, E. H., 2012. "Storage policies and order picking strategies in U-shaped order-picking systems with a movable base," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 57442, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    54. Diefenbach, Heiko & Glock, C. H., 2019. "Ergonomic and economic optimization of layout and item assignment of a U-shaped order picking zone," Publications of Darmstadt Technical University, Institute for Business Studies (BWL) 116991, Darmstadt Technical University, Department of Business Administration, Economics and Law, Institute for Business Studies (BWL).
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Vichitkunakorn, Panupong & Emde, Simon & Masae, Makusee & Glock, Christoph H. & Grosse, Eric H., 2024. "Locating charging stations and routing drones for efficient automated stocktaking," European Journal of Operational Research, Elsevier, vol. 316(3), pages 1129-1145.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Glock, Christoph H. & Grosse, Eric H. & Abedinnia, Hamid & Emde, Simon, 2019. "An integrated model to improve ergonomic and economic performance in order picking by rotating pallets," European Journal of Operational Research, Elsevier, vol. 273(2), pages 516-534.
    2. Diefenbach, Heiko & Grosse, Eric H. & Glock, Christoph H., 2024. "Human-and-cost-centric storage assignment optimization in picker-to-parts warehouses," European Journal of Operational Research, Elsevier, vol. 315(3), pages 1049-1068.
    3. Masae, Makusee & Glock, Christoph H. & Vichitkunakorn, Panupong, 2021. "A method for efficiently routing order pickers in the leaf warehouse," International Journal of Production Economics, Elsevier, vol. 234(C).
    4. Boysen, Nils & de Koster, René & Füßler, David, 2021. "The forgotten sons: Warehousing systems for brick-and-mortar retail chains," European Journal of Operational Research, Elsevier, vol. 288(2), pages 361-381.
    5. Boysen, Nils & de Koster, René & Weidinger, Felix, 2019. "Warehousing in the e-commerce era: A survey," European Journal of Operational Research, Elsevier, vol. 277(2), pages 396-411.
    6. Maria A. M. Trindade & Paulo S. A. Sousa & Maria R. A. Moreira, 2022. "Ramping up a heuristic procedure for storage location assignment problem with precedence constraints," Flexible Services and Manufacturing Journal, Springer, vol. 34(3), pages 646-669, September.
    7. Loske, Dominic & Klumpp, Matthias & Grosse, Eric H. & Modica, Tiziana & Glock, Christoph H., 2023. "Storage systems’ impact on order picking time: An empirical economic analysis of flow-rack storage systems," International Journal of Production Economics, Elsevier, vol. 261(C).
    8. Giannikas, Vaggelis & Lu, Wenrong & Robertson, Brian & McFarlane, Duncan, 2017. "An interventionist strategy for warehouse order picking: Evidence from two case studies," International Journal of Production Economics, Elsevier, vol. 189(C), pages 63-76.
    9. Diefenbach, Heiko & Emde, Simon & Glock, Christoph H., 2020. "Loading tow trains ergonomically for just-in-time part supply," European Journal of Operational Research, Elsevier, vol. 284(1), pages 325-344.
    10. Arbex Valle, Cristiano & Beasley, John E, 2020. "Order batching using an approximation for the distance travelled by pickers," European Journal of Operational Research, Elsevier, vol. 284(2), pages 460-484.
    11. Çelik, Melih & Archetti, Claudia & Süral, Haldun, 2022. "Inventory routing in a warehouse: The storage replenishment routing problem," European Journal of Operational Research, Elsevier, vol. 301(3), pages 1117-1132.
    12. Fangyu Chen & Yongchang Wei & Hongwei Wang, 2018. "A heuristic based batching and assigning method for online customer orders," Flexible Services and Manufacturing Journal, Springer, vol. 30(4), pages 640-685, December.
    13. Kumar, Suryakant & Sheu, Jiuh-Biing & Kundu, Tanmoy, 2023. "Planning a parts-to-picker order picking system with consideration of the impact of perceived workload," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 173(C).
    14. De Santis, Roberta & Montanari, Roberto & Vignali, Giuseppe & Bottani, Eleonora, 2018. "An adapted ant colony optimization algorithm for the minimization of the travel distance of pickers in manual warehouses," European Journal of Operational Research, Elsevier, vol. 267(1), pages 120-137.
    15. Anderson Rogério Faia Pinto & Marcelo Seido Nagano, 2020. "Genetic algorithms applied to integration and optimization of billing and picking processes," Journal of Intelligent Manufacturing, Springer, vol. 31(3), pages 641-659, March.
    16. Li Zhou & Huwei Liu & Junhui Zhao & Fan Wang & Jianglong Yang, 2022. "Performance Analysis of Picking Routing Strategies in the Leaf Layout Warehouse," Mathematics, MDPI, vol. 10(17), pages 1-28, September.
    17. Pardo, Eduardo G. & Gil-Borrás, Sergio & Alonso-Ayuso, Antonio & Duarte, Abraham, 2024. "Order batching problems: Taxonomy and literature review," European Journal of Operational Research, Elsevier, vol. 313(1), pages 1-24.
    18. Saylam, Serhat & Çelik, Melih & Süral, Haldun, 2024. "Arc routing based compact formulations for picker routing in single and two block parallel aisle warehouses," European Journal of Operational Research, Elsevier, vol. 313(1), pages 225-240.
    19. Dominic Loske & Matthias Klumpp & Maria Keil & Thomas Neukirchen, 2021. "Logistics Work, Ergonomics and Social Sustainability: Empirical Musculoskeletal System Strain Assessment in Retail Intralogistics," Logistics, MDPI, vol. 5(4), pages 1-25, December.
    20. Katrin Heßler & Stefan Irnich, 2023. "Exact Solution of the Single Picker Routing Problem with Scattered Storage," Working Papers 2303, Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:orspec:v:44:y:2022:i:2:d:10.1007_s00291-021-00663-8. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.