Routing Replenishment Workers: The Prize Collecting Traveling Salesman Problem in Scattered Storage Warehouses

Many online retailers apply scattered (or mixed-shelves) storage in the picking areas of their warehouses. Instead of keeping unit loads together, individual pieces of stock keeping units (SKUs) are stored on various shelves throughout the warehouse. This storage strategy increases the probability that-whatever it is that customers order jointly-somewhere in the warehouse these products will be located in close proximity. Hence, a picker can retrieve them without excessive unproductive walking. The price for this advantage on the picking side, however, is additional effort for the replenishment workers (also denoted as stowers) when restocking the shelves. Instead of moving only a single homogeneous unit load toward an SKU's designated storage position, each stower has to travel along multiple open shelf spaces until all products on the cart are stored on shelves. The resulting stower routing problem is equivalent to the well-known prize collecting traveling salesman problem (PCTSP). While the PCTSP for general graphs is known to be strongly NP-hard, we show that in a warehousing environment, where all open storage positions are located along parallel aisles, it is only binary NP-hard. The special parallel-aisle structure allows us to derive an exact solution algorithm with pseudo-polynomial runtime, which solves even instances with hundreds of open storage positions to proven optimality in just a few seconds. Our computational tests show that the performance gains of an optimized stowing process over the status quo, where stowers operate without decision support, are significant. Especially, when the fill level of a warehouse is high, directing stowers on optimized routes promises huge improvements.

Automated summary

Many online retailers use scattered storage in their picking areas, which increases the likelihood of products being located in close proximity, making picking more efficient. However, replenishment workers face additional effort due to the need to travel along multiple shelves for restocking. The special parallel-aisle structure in warehouses allows for an exact solution algorithm with pseudo-polynomial runtime, resulting in significant performance gains for an optimized stowing process.