Due date-oriented picker routing, an efficient exact solution algorithm, and its application to pick-from-store omnichannel retailing

The advent of e-commerce and omnichannel retailing has sparked renewed interest in picker routing in warehouses. This paper presents two significant methodological advances in this well-established field. First, it is a well-known fact that the parallel-aisle layout of warehouses, as opposed to general graphs, allows for polynomial-time solutions of the Traveling Salesman Problem. We show that the parallel-aisle structure can also be exploited when pickers are tasked with visiting storage positions associated with specific due dates. We establish that picker routing in warehouses, subject to soft due date constraints, is a binary NP-hard problem. We also present an exact branch-and-bound algorithm with pseudo-polynomial time complexity. This algorithm effectively solves instances with up to 60 picking positions and five cross aisles within a few seconds while guaranteeing optimality. Second, for even larger pick lists, we demonstrate the successful integration of our algorithm into a real-time framework. This approach allows us to avoid extended solution times that would otherwise delay the picker’s departure, without compromising the quality of the solution. To illustrate the practical relevance of these two methodological innovations, we apply our routing algorithm to the context of pick-from-store omnichannel retailing. By assigning due dates to critical products, we significantly reduce stockout occurrences for online customers. These stockouts occur when the stock level, initially deemed sufficient to confirm an online order, is depleted by walk-in customers before the picker reaches the relevant shelf.