When to apply optimal or heuristic routing of orderpickers

In this paper the differences in performance of heuristic and optimal strategies for routing orderpickers in a warehouse are compared. Specifically, modern warehouses are considered, where orderpicking trucks can pick up and deposit pick pallets at the head of every aisle without returning to a depot. Such environments can be found in many warehouses where paperless picking is performed from pallet locations with pickers having mobile terminals receiving instructions one by one. In order to find orderpicking routes of minimal length in the situation of decentralized depositing, we use an extension of the well-known polynomial time algorithm of Ratliff and Rosenthal (1983) that considered warehouses with a central depot. In practice, the problem is mainly solved by using the so-called S-shape heuristic in which orderpickers move in a S-shape curve along the pick locations. The performance of both routing strategies is compared by using simulation. The optimal algorithm can give substantial reductions in travel time per route. It turns out that the reduction in travel time strongly depends on the lay-out and operation of the warehouse. Simulation is very time consuming, both in creating computer programs and in calculation times. Therefore it is desirable to have statistically based, explicit formulas for the performance of the optimal algorithm and the S-shape heuristic. We adapt formulations of Hall (1993) for the case of decentralized depositing and improve their performance. After adaptation, the formulas perform fairly well, and are a good alternative for simulation to get a rough idea about differences in performance of the S-shape heuristic and the optimal algorith