Synchronous parallel heuristics for solving the joint order batching and picker routing problem

Abstract

The joint order batching and picker routing problem is an important problem for improving warehouse efficiency. The goal is to minimize the total distance travel of picking customer orders. It is NP-hard, indicating that exact solutions are intractable for large instances. Many solution methods provided in the current literature use local search to solve the problem sequentially, often including a complex searching procedure for the order batching problem (OBP) followed by a simple heuristic for the picker routing problem (PRP). In this paper, we propose three heuristics that jointly solves the OBP and the PRP: two of these are combinations of variable neighborhood search, simulated annealing, and tabu search, while the third one uses guided local search. We discuss how the search procedure of the proposed algorithms can be parallelized, and benchmark them against state-of-the-art heuristics using well-studied instances. The results show a reduction of 3.06% to 7.63% in the geometric mean of the total travel distance across 64 instances. Increasing the number of threads in parallelization leads to diminishing returns in reducing running time and has no statistical effect on travel distance. In contrast, increasing the chunk size results in a linear increase in running time for all proposed algorithms, and improves the travel distance obtained when the batch size is 75 items.