A polynomial-time dynamic programming algorithm for an optimal picking problem in automated warehouses

We consider an optimization problem arising when a set of items must be selected and picked up from given locations in an automated storage and retrieval system by a crane of given capacity, minimizing the overall distance traveled. The problem has been classified as open in a recent taxonomy of optimal picking problems in automated warehouses. In this paper, we analyze some non-trivial properties of the problem and we describe a polynomial-time dynamic programming algorithm to solve it to proven optimality.

• Publication year

  2024

• Venue

  Journal of Scheduling

• Publication date

  2024-07-16

• Fields of study

  Computer Science, Engineering

• Identifiers
  DOI 10.1007/s10951-024-00811-2
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• A Joint Comparative Analysis of Routing Heuristics and Paperless Picking Technologies Using Simulation and Data Envelopment Analysis

  2020cited by this paper
• On solving the order processing in picking workstations

  2020cited by this paper
• Robotized and Automated Warehouse Systems: Review and Recent Developments

  2019cited by this paper
• Picker routing in the mixed-shelves warehouses of e-commerce retailers

  2019cited by this paper
• Paths and Matchings in an Automated Warehouse

  2019influential reference
• Warehousing in the e-commerce era: A survey

  2019cited by this paper
• Modeling Single Picker Routing Problems in Classical and Modern Warehouses

  2019cited by this paper
• Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System

  2017cited by this paper
• A survey on single crane scheduling in automated storage/retrieval systems

  2016cited by this paper
• Modelling and a segmented dynamic programming-based heuristic approach for the slab stack shuffling problem

  2010cited by this paper
• A survey of literature on automated storage and retrieval systems

  2009cited by this paper
• A shift-based sequencing method for twin-shuttle automated storage and retrieval systems

  2008cited by this paper
• Research on warehouse operation: A comprehensive review

  2007cited by this paper
• Design and control of warehouse order picking: A literature review

  2006cited by this paper
• Publisher's Note

  2003cited by this paper
• Models for warehouse management: Classification and examples

  1999cited by this paper
• Scheduling a batching machine

  1998influential reference

• No citing papers are available for this paper.