Using a TSP-heuristic for routing order pickers in warehouses

In this paper, we deal with the sequencing and routing problem of order pickers in conventional multi-parallel-aisle warehouse systems. For this NP-hard Steiner Travelling Salesman Problem, exact algorithms only exist for warehouses with at most three cross aisles. We propose a new approach in which the problem is reformulated into a classical Travelling Salesman Problem (TSP). As a result, the powerful (meta)heuristic search procedures for the classical TSP can be used for solving this problem. To the best of our knowledge, a similar approach has not yet been used in the literature on order picking. Computational tests comparing the Lin-Kernighan TSP heuristic to traditional construction heuristics for routing order pickers report up to 47 percent average improvements on total distance travelled.