Scientific Program > Talks by Speaker > Aerts Babiche

Solving order batching and picker routing, as a clustered vehicle routing problem
Babiche Aerts  1, *@  , Trijntje Cornelissens  1@  , Kenneth Sörensen  1@  
1 : University of Antwerp
Prinsstraat 13 2000 Antwerp -  Belgium
* : Corresponding author

Order batching and picker routing are well-known problems in the warehouse management literature. Although these problems are interrelated, they are usually solved in isolation, using dedicated heuristics specifically aimed at a warehouse context. Mathematically, however, the integrated order batching and picker routing problem is the same as the clustered vehicle routing problem which groups customers into clusters that should be visited by the same vehicle. We test a two-level Variable Neighborhood Search (VNS) algorithm developed for the latter problem on instances for the former, and study the adaptations required to perform efficiently. Additionally, we test if the Hausdorff distance is a valid order batching criterion and compare this clustering metric to a commonly used batching criterion in warehouse literature, the minimal number of aisles visited. Concerning the pickers' routings, we compare the total travel distances resulting from the VNS algorithm to the distances obtained when routing heuristics are used dedicated to warehouse settings, including the s-shape, largest gap and combined heuristic, and define the optimality gap using the algorithm developed by Ratliff and Rosenthal (1983).

The results indicate the Hausdorff distance is being outperformed by the minimal number of aisles visited-rule as a batching criterion. On average, a gap of 5,88% was measured between the total travel distances obtained by the two batching criteria. Given the batches composed with the presented batching criteria, the VNS algorithm obtains the optimal route for half of the instances. For the remainder of the instances, an optimality gap of less than 2% is observed.

Online user: 1 RSS Feed