A linear-size model for the single picker routing problem with scattered storage

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 stock keeping units (SKUs) of an article 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 distinct modifications of the extended state space to retain the linearity of the models. Linearity is achieved by replacing the quadratically growing parallel edges of the extended state space by 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-programming 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 currently best performing approach 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.