A note on the linearity of Ratliff and Rosenthal's algorithm for optimal picker routing

Ratliff and Rosenthal state that their dynamic programming algorithm for optimal picker routing has linear complexity in the number of aisles. Indeed, solving the dynamic program is linear, but computing the cost coefficients of the dynamic program certainly requires the consideration of all picking positions, whose number is independent of the number of aisles. For a given unsorted sequence of picking positions, our algorithm is linear in the sum of the number of aisles and number of picking positions. (C) 2022 Elsevier B.V. All rights reserved.

Automated summary

This article presents a study on the dynamic programming algorithm for optimal picker routing, which has linear complexity in the number of aisles. The algorithm is linear in solving the dynamic programming problem, but computing the cost coefficients requires considering all picking positions.