An algorithm for dynamic order-picking in warehouse operations

Wenrong Lu, Duncan C. McFarlane, Vaggelis Giannikas, Quan ZhangEur. J. Oper. Res 2016 · DOI

TL;DR

This paper introduces an "Interventionist Routing Algorithm" (IRA) for optimizing order-picking routes in warehouses. Unlike traditional methods that rely on static pick-lists, IRA allows for dynamic updates to a picker's route in real-time as new orders arrive, leading to significant improvements in order completion times.

What Problem Does This Paper Address?

Warehousing is a critical component of modern supply chains, and order-picking, the process of retrieving items for customer orders, is a major cost and time driver. Traditional "Static Order-Picking" (SOP) systems generate pick-lists that cannot be altered once a picker begins their route. This becomes inefficient in today's e-commerce environment, characterized by a high volume of orders with short lead times and scattered arrival times. The inflexibility of SOP leads to delays, as pickers might have to wait for enough orders to fill their capacity or for their current route to finish before new, urgent orders can be processed. This paper addresses the need for a more dynamic and responsive order-picking system that can adapt to real-time order arrivals.

Methods

The core of this paper is the Interventionist Routing Algorithm (IRA). IRA extends the seminal work of Ratliff and Rosenthal (1983) on static order-picking by incorporating the ability to re-route pickers dynamically. Key features of IRA include:

  • Interruptibility: The algorithm allows for pick-lists to be updated and routes to be re-calculated even when the picker is already on-site, regardless of their current location within the warehouse.
  • Optimality: IRA aims to minimize the total travel distance for the order-picking route.
  • Complexity: The algorithm is designed to have polynomial computation time, linear to the number of pick-aisles.
  • Centralized Depositing: Pickers still start and end their cycles at a pre-defined depot.

IRA achieves this by introducing new concepts like "One-Way (OW)" and "Round-Trip (RT)" traveling areas, new Partial Route Subgraph (PRS) equivalence classes, and modified route construction tables. The algorithm systematically calculates the minimum length PRS for each aisle and then stitches these together to form the overall optimal route.

Datasets

Not discussed in the paper. The authors use simulations based on an industrial case example.

Key Insights and Ideas

  • The "Interventionist" Advantage: The ability to dynamically update pick-lists and re-route pickers in real-time is crucial for improving responsiveness in e-commerce logistics.
  • Trade-off Management: While dynamic routing (IOP) significantly reduces order completion times, it can lead to increased travel distance. The paper highlights that this trade-off can be managed by adjusting the picker's device capacity.
  • Optimality Matters: Even within dynamic strategies, an optimized routing algorithm (like IRA) significantly outperforms heuristic approaches (like modified Largest Gap) in terms of both order completion time and travel distance.
  • Order Arrival Rate is Key: The benefits of interventionist strategies are most pronounced at moderate order arrival rates (0.01-0.07 orders/sec). At very high rates, the system can become effectively static as pickers are always busy.

Key Results

The paper presents simulation results comparing IRA with Static Order-Picking (SOP) and a Modified Largest Gap Heuristic (MLGH).

  • IOP vs. SOP: IRA can reduce average order completion time by up to 76%, though it may increase travel distance by up to 108%. The benefits are most significant at moderate order arrival rates.
  • Picker Capacity Impact: Reducing picker capacity can significantly decrease travel distance (e.g., 69% less travel when capacity drops from 20 to 5 items), but this must be balanced against potential increases in order completion time.
  • IRA vs. MLGH: IRA consistently outperforms MLGH for all tested order arrival rates, showing up to a 15% benefit in AOCT and 12% in ATDO at an arrival rate of approximately 0.03 orders/sec.

Limitations and Future Work

  • Single Picker Focus: The current algorithm is designed for a single picker. Future work aims to extend it to multi-picker scenarios, which introduces complexities in assigning pickers and storage locations.
  • Warehouse Layout: The current model focuses on single-block warehouses. Future research will explore its application to multi-block layouts.
  • Intervention Strategy Regulation: An important area for future investigation is how to regulate the intervention process itself. For instance, deciding which new orders are most appropriate for intervention (e.g., those on the picker's current path) could further optimize performance. This is slated for a future paper.

Summary updated

BibTeX
@article{lu2016algorithm,
  author = {Wenrong Lu and Duncan C. McFarlane and Vaggelis Giannikas and Quan Zhang},
  title = {{An algorithm for dynamic order-picking in warehouse operations}},
  journal = {Eur. J. Oper. Res.},
  year = {2016},
  doi = {10.1016/j.ejor.2015.06.074},
}

Loading related content...

Figure