Order batching and picker scheduling in warehouse order picking

Abstract

This article focuses on the integration of order batching and picker scheduling decisions while taking into account two objectives that have been considered in the literature, namely the minimization of both total travel time to collect all items and makespan of the pickers. This integrated problem not only occurs naturally in wave picking systems in which the latest picking time of orders becomes the key performance metric, but also arises when there is a limit on the picker operating time. We present models that result from combining these objectives and analyze their relationship through bounds. We propose a column generation-based exact algorithm for the integrated problem. The novelty of the proposed approach lies in the ability of efficiently solving the integrated order batching and picker scheduling problem to optimality by designing a column generation subproblem based on the set of batches, which makes it a challenging optimization problem due to its size. We alleviate this difficulty by reformulating this subproblem, which allows efficient implicit enumeration of its variables. We have also devised a Variable Neighborhood Search algorithm used as a subprocedure within the proposed exact solution algorithm. Finally, we conduct experiments on randomly generated instances and show that the proposed algorithms are capable of solving instances with up to 100 orders.

Keywords:

• Integer programming
• column generation
• order batching

Acknowledgments

This research was done prior to the first author’s employment at Amazon. Thanks are due to anonymous referees for their valuable comments which have helped improve the paper.

Additional information

Funding

The second author acknowledges the partial support by the Scientific and Technical Research Council of Turkey - TÜBİTAK (Grant No: 217M477).

Notes on contributors

İbrahim Muter

İbrahim Muter is a Senior Research Scientist at Amazon Web Services (AWS). He received his PhD in Industrial Engineering from Sabancı University in 2011. Before joining AWS, he worked at Bahçeşehir University as assistant professor and then at University of Bath as senior lecturer. His research interests include integer programming, decomposition methods and their applications.

Temel Öncan

Temel Öncan is a Professor of Industrial Engineering at Galatasaray University. He received his PhD in Industrial Engineering from Boğaziçi University, İstanbul, in 2004. His research interests include combinatorial optimization, integer programming, network design, facility location and routing problems. He has published papers in Computer & Operations Research, European Journal of Operational Research, IIE Transactions, Annals of Operations Research and Journal of the Operational Research Society.