The joint order batching and picker routing problem: Modelled and solved as a clustered vehicle routing problem

The joint order batching and picker routing problem (JOBPRP) is a promising approach to minimize the order picking travel distance in a picker-to-parts warehouse environment. In this paper, we show that the JOBPRP can be modelled as a clustered vehicle routing problem (CluVRP), a variant of the capacitated VRP in which customers are grouped into clusters. To solve this cluster-based model of the JOBPRP, we apply a two-level variable neighborhood search (2level-VNS) metaheuristic, previously developed for the CluVRP, and study which adaptations are required to perform efficiently in a warehouse environment. Additionally, we evaluate if the Hausdorff distance used as an approximation for the clusters' proximity in the CluVRP, performs equally well when determining closeness between pick orders in a warehouse. We compare the performance of the Hausdorff-based batching criterion to the cumulative minimal aisles visited-criterion, known as a well-performing batching metric in rectangular warehouses with parallel aisles. The 2level-VNS performs well compared to state-of-the-art algorithms specifically developed for the order batching problem (OBP) in a single-block warehouse. A multi-start VNS remains slightly superior to our approach. Concerning the Hausdorff distance, we conclude that in most experiments, the minimum-aisles criterion retains a better fit in the warehouse context. (C) 2020 Elsevier Ltd. All rights reserved.