A scalable Branch, Bound, and Remember algorithm for picker routing with deadlines

The seminal Ratliff-Rosenthal algorithm, solving the traveling salesman problem in parallel aisles in polynomial time, spawned a vibrant routing research stream focused on exploiting the special layout structure in warehouses. E-commerce and omnichannel retailing have revived this research stream and given rise to new picker routing problems. Picked products are typically unavailable to downstream processes until the picker returns to the depot. Therefore, other than vehicle routing, deadlines for each picking position have no direct application in warehouses. However, we present novel retail applications where picking locations face deadlines that, if missed, result in the inability to retrieve the product stored there and thus missed picks. While the resulting Picker Routing Problem With Deadlines (PRPWD) is strongly NP-hard for general graphs, we show that the parallel aisle structure of warehouses makes the PRPWD only binary NP-hard. We develop novel Branch, Bound, and Remember (BB&R) algorithms with pseudo-polynomial runtime. They solve instances with up to 90 picking positions to proven optimality, outperforming off-the-shelf solvers by orders of magnitude. In addition, we provide a thorough computational analysis of the search schemes of BB&R, namely best first search and cyclical best first search (CBFS), and show that CBFS outperforms its competitors. Using CBFS, our BB&R approach partitions the enumerated partial solutions into a scalable number of heaps, grouped together by their neighboring depths in the search tree. It turns out that strictly limiting the number of heaps to only five is promising for solving the most complex instances.