Order picking in parallel-aisle warehouses with multiple blocks: complexity and a graph theory-based heuristic


ÇELİK M., SÜRAL H.

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, vol.57, no.3, pp.888-906, 2019 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 57 Issue: 3
  • Publication Date: 2019
  • Doi Number: 10.1080/00207543.2018.1489154
  • Journal Name: INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.888-906
  • Keywords: warehouse logistics, order picking, picker routing, computational complexity, heuristics, graph theory, TRAVELING SALESMAN PROBLEM, ANT COLONY OPTIMIZATION, PICKERS, ALGORITHM, DISTANCE, DESIGN
  • Middle East Technical University Affiliated: Yes

Abstract

In this paper, we consider the order picking problem (OPP), which constitutes one of the special cases of the Steiner travelling salesperson problem and addresses the costliest operation in a warehouse. Given a list of items to be picked and their locations in the warehouse layout, the OPP aims to find the shortest route that starts from a depot point, picks all the items in the list, and returns to the depot. This paper fills two important gaps regarding the OPP. First, to the best of our knowledge, we present the first complexity results on the problem. Second, we propose a heuristic approach that makes use of its graph-theoretic properties. Computational experiments on randomly generated instances show that the heuristic not only outperforms its state-of-the-art counterparts in the literature, but it is also robust in terms of changing problem parameters.