An optimal algorithm for order picking in a multi-parallel-aisle warehouse

Order picking constitutes the largest cost in running a warehouse, hence optimizing the picking routes may lead to significant savings. We study the problem of optimizing a single pick route in a warehouse with (vertical) aisles and a fixed number of cross aisles, usually referred to as a multiparallel-aisle warehouse. The problem can be seen as a variant of the rectilinear Traveling Salesman Problem. In this paper we show that an optimal picking route can be found in linear time (in the number of aisles) for any fixed number of cross aisles. Moreover, we show that if the number of cross aisles is unlimited, the problem is strongly NP-hard. The presented algorithm is based on dynamic programming, where transitions between states depend only on the number of cross aisles. Therefore they can be calculated a-priori for each number of cross aisles and saved for later use, such that the actual running time for finding a picking route is linear in the number of aisles. Computational results show that the exact algorithm obtains average savings of up to 11, 5% in comparison to the best heuristics used in the literature, and that actual picking routes can be calculated in a few seconds, even for large instances.