A Linear-Size Model for the Single Picker Routing Problem with Scattered Storage

Laura Lüke (), André Hessenius () and Stefan Irnich ()
Additional contact information
Laura Lüke: Johannes-Gutenberg University, Germany
André Hessenius: Johannes-Gutenberg University, Germany
Stefan Irnich: Johannes-Gutenberg University, Germany

No 2502, Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz

Abstract: We present a new approach of solving the single picker routing problem with scattered storage (SPRP-SS), which is a fundamental problem in modern warehouse operations management. The SPRP-SS assumes that SKUs of articles are stored at possibly many locations. An effective integer programming based approach relies on extending the state space of Ratliff and Rosenthal’s dynamic program for the basic single picker routing problem to accommodate the SPRP-SS. As a result, the mixed integer linear programming (MIP) formulation has a quadratic number of variables. We propose two modifications of the extended state space to retain the linearity of the models. This is achieved by replacing the quadratically growing parallel edges of the extended state space by two different types of linear-size subnetworks. These replacements lead to different state spaces and herewith different MIP formulations, for which we analyze theoretical properties such as their size and strength of the linear relaxations. We compare the new formulations with the state of the art using a collection of 800 SPRP-SS instances. The results show that the new formulations are more than competitive providing integer optimal solutions of realistic and even large-scale instances in less than two seconds on average. The second formulation outperforms the current one regarding the computational speed: For the largest instances with 200 articles to be collected, average speedups reach the factors of 3.18 and 4.87 for general and unit demand, respectively.

Keywords: Elections; routing; warehousing; picker routing; scattered storage (search for similar items in EconPapers)
Pages: 1 pages
Date: 2025-01-14
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://download.uni-mainz.de/RePEc/pdf/Discussion_Paper_2502.pdf First version, 2025 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:jgu:wpaper:2502

Access Statistics for this paper

More papers in Working Papers from Gutenberg School of Management and Economics, Johannes Gutenberg-Universität Mainz Contact information at EDIRC.
Bibliographic data for series maintained by Research Unit IPP ().