Analysis of Computational Efficiency in Iterative Order Batching Optimization

Order Picking in warehouses is often optimized with a method known as Order Batching, which means that
one vehicle can be assigned to pick a batch of several orders at a time. Although there exists a rich body of
research on Order Batching Problem (OBP) optimization, one area which demands more attention is that of
computational efficiency, especially for optimization scenarios where warehouses have unconventional
layouts and vehicle capacity configurations. Due to the NP-hard nature of the OBP, computational cost for
optimally solving large instances is often prohibitive. In this paper we compare the performance of two
approximate optimizers designed for maximum computational efficiency. The first optimizer, Single Batch
Iterated (SBI), is based on a Seed Algorithm, and the second, Metropolis Batch Sampling (MBS), is based on
a Metropolis algorithm. Trade-offs in memory and CPU-usage and generalizability of both algorithms is
analysed and discussed. Existing benchmark datasets are used to evaluate the optimizers on various scenarios.
On smaller instances we find that both optimizers come within a few percentage points of optimality at
minimal CPU-time. For larger instances we find that solution improvement continues throughout the allotted
time but at a rate which is difficult to justify in many operational scenarios. SBI generally outperforms MBS
and this is mainly attributed to the large search space and the latter’s failure to efficiently cover it. The
relevance of the results within Industry 4.0 era warehouse operations is discussed.