Picker Routing in AGV-Assisted Order Picking Systems

To reduce unproductive picker walking in traditional picker-to-parts warehousing systems, automated guided vehicles (AGVs) are used to support human order pickers. In an AGV-assisted order-picking system, each human order picker is accompanied by an AGV during the order-picking process. AGVs receive the picked items and, once a picking order is complete, autonomously bring the collected items to the shipping area. Meanwhile, a new AGV is requested to meet the picker at the first storage position of the next picking order. Thus, the picker does not have to return to a central depot and continuously picks order after order. This paper addresses both the routing of an AGV-assisted picker through a single-block, parallel-aisle warehouse and the sequencing of incoming orders. We present an exact polynomial time routing algorithm for the case of a given order sequence, which is an extension of the algorithm of Ratliff and Rosenthal [ Ratliff HD, Rosenthal AS (1983) Order-picking in a rectangular warehouse: A solvable case of the traveling salesman problem. Oper. Res. 1(3):507–521], and a heuristic for the case in which order sequencing is part of the problem. In addition, we investigate the use of highly effective traveling salesman problem (TSP) solvers that can be applied after a transformation of both problem types into a standard TSP. The numerical studies address the performance of these methods and study the impact of AGV usage on picker travel: by using AGVs to avoid returns to the depot and by sequencing in (near-) optimal fashion, picker walking can be reduced by about 20% compared with a traditional setting. Sharing AGVs among the picker workforce enables a pooling effect so that, in larger warehouses, only about 1.5 AGVs per picker are required to avoid picker waiting. Summary of Contribution: New technologies, such as automatic guided vehicles (AGVs) are currently considered as options to increase the efficiency of the order-picking process in warehouses, which is responsible for a large part of operational warehousing costs. In addition, picker-routing decisions are more and more often based on algorithmic decision support because of their relevance for decreasing unproductive picker walking time. This paper addresses both aspects and investigates routing algorithms for AGV-assisted order picking in parallel-aisle warehouses. We present a dynamic programming routine with polynomial runtime to solve the problem variant in which the sequence of picking orders is fixed. For the variant in which this sequence is a decision, we show that the problem becomes NP-hard, and we propose a greedy heuristic and investigate the use of state-of-the-art exact and heuristic traveling salesman problem solution methods to address the problem. The numerical studies demonstrate the effectiveness of the algorithms and indicate that AGV assistance promises strong improvements in the order-fulfillment process. Because of the practical relevance of AGV-assisted order picking and the presented algorithmic contributions, we believe that the paper is relevant for practitioners and researchers alike.