License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2019.56
URN: urn:nbn:de:0030-drops-115526
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11552/
Go to the corresponding LIPIcs Volume Portal

Dasler, Philip ; Mount, David M.

Online Algorithms for Warehouse Management

pdf-format:
LIPIcs-ISAAC-2019-56.pdf (0.9 MB)

Abstract

As the prevalence of E-commerce continues to grow, the efficient operation of warehouses and fulfillment centers is becoming increasingly important. To this end, many such warehouses are adding automation in order to help streamline operations, drive down costs, and increase overall efficiency. The introduction of automation comes with the opportunity for new theoretical models and computational problems with which to better understand and optimize such systems.
These systems often maintain a warehouse of standardized portable storage units, which are stored and retrieved by robotic workers. In general, there are two principal issues in optimizing such a system: where in the warehouse each storage unit should be located and how best to retrieve them. These two concerns naturally go hand-in-hand, but are further complicated by the unknown request frequencies of stored products. Analogous to virtual-memory systems, the more popular and oft-requested an item is, the more efficient its retrieval should be. In this paper, we propose a theoretical model for organizing portable storage units in a warehouse subject to an online sequence of access requests. We consider two formulations, depending on whether there is a single access point or multiple access points. We present algorithms that are O(1)-competitive with respect to an optimal algorithm. In the case of a single access point, our solution is also asymptotically optimal with respect to density.

BibTeX - Entry

@InProceedings{dasler_et_al:LIPIcs:2019:11552,
  author =	{Philip Dasler and David M. Mount},
  title =	{{Online Algorithms for Warehouse Management}},
  booktitle =	{30th International Symposium on Algorithms and Computation (ISAAC 2019)},
  pages =	{56:1--56:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-130-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{149},
  editor =	{Pinyan Lu and Guochuan Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11552},
  URN =		{urn:nbn:de:0030-drops-115526},
  doi =		{10.4230/LIPIcs.ISAAC.2019.56},
  annote =	{Keywords: Warehouse management, online algorithms, competitive analysis, robotics}
}

Keywords: Warehouse management, online algorithms, competitive analysis, robotics
Collection: 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Issue Date: 2019
Date of publication: 28.11.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI