# Problem Description

The Online Order Batching Problem (OOBP) is a variant of the well-known Order Batching Problem (OBP) which consist of grouping the orders arrived to a warehouse (each order is composed by a list of items) in a set of batches in such a way that the time needed to collect all the orders is minimized. Additionally, each batch has to be collected by a single picker without exceeding a capacity limit.In the online variant of the OBP, the arrival of orders is dynamic. In this way, the system only knows a small group of orders to collect in the moment when the picking starts, since orders arrive to the warehouse throught the time. To deal with this problem, researchers study the orders received in the warehouse during a particular period of time.

We center our attention in rectangular warehouses with different number of parallel aisles and two cross aisles (one at the front and one at the back of the warehouse) with a depot placed at the front cross aisle (either in the left most corner or in the center of the aisle). Next, we depict the considered warehouse in a figure:

The OOBP consist of handling with four different optimization problems: i) grouping of orders into batches; ii) sequencing the order in which batches are collected; iii) finding a route to collect the orders in the selected batch; and iv) determining the time that the picker waits until he/she starts the picking (i.e., the time window).

Next, we depict the time line of the life of an order, and the time line of the life of a batch through the time, in the context of the OOBP:

# State of the Art Methods

This problem has been proved to be NP-hard for general instances. Nonetheless, it is solvable in polynomial time if each batch does not contain more than two orders. Unfortunately, real warehouse instances does not usually fall into this category.

The variant of the OOBP compared in this paper was first tackled by Henn in 2012. They proposed a heuristic algorithm based on Iterated Local Search (ILS) to minimize the maximum completion time of the orders from the customers, which arrive to the system within a certain time period. In this paper, the authors also reported two other objective functions (the maximum and the average time that an order remains in the system). The ILS method was compared with a classical FCFS algorithm and with a Clarke and Wright method.

The variant of the problem previously presented was also tackled later by Perez-Rodriguez et. al. in 2015. The authors proposed a variant of the well-known Estimation of Distribution Algorithm (EDA) to tackle the problem. The authors reported the average distance traversed by the picker as objective function. However, the proposed EDA was not able to improve previous results.

In 2011, Rubrico et al. tackled a related problem, the Online Rescheduling Problem with multiple pickers. However, this variant of the problem, despite of its close relation with the OOBP, is not comparable to the two previous approaches since they consider multiple pickers and introduces a rescheduling procedure. The authors proposed two heuristic methods based on the Steepest Descent Insertion strategy, and on the Multistage Rescheduling strategy. In this case, the objective function tackled is to minimize the maximum total travel distance traversed by each picker.

Other different variant of the problem was tackled by Zhang et. al., 2016. In this paper the OOBP was integrated with the scheduling of the delivery, trying to minimize the service time of an order.

# Instances

We publish in this site two sets of instances used in the context of the OOBP, totalizing 144 instances: the first one is a subset of Albareda-Sambola et al., 2009 and contains 80 instances. The second one is a subset of Henn and Wäscher, 2012 containing 64 instances. These 144 instances were used to compare our algorithm (GRASP+VND) against the ILS (Henn, 2012) method in the state of the art.

Sets of instances

• Henn and Wäscher, 2012: This collection of instances consists of a rectangular warehouse with 10 aisles and 90 storage locations each. The depot is always located at the bottom left corner. The item distribution is both (i) ABC distribution and (ii) random distribution. Customer orders varies from 40 to 100 in steps of 20 and the capacity of the picker ranges between 30 and 75 in steps of 15.
• Albareda-Sambola et al., 2009: This set consists of four different rectangular warehouses with the depot located either at the bottom left corner or at the bottom center of the warehouse. The item distribution is also both (i) ABC distribution and (ii) random distribution. The number of orders varies from 100 to 250 in steps of 50 and the capacity of the picker depends on the warehouse.

Instances are ready to be executed over a time horizon of 4 hours. In order to ease future ocmparisons, the moment in the time when each order (for each instance) arrives to the warehouse is provided (see the readme.txt file of the instances). Instances can be downloaded here.

# Computational Experience

The experiments were run an Intel (R) Core (TM) 2 Quad CPU Q6600 2.4 Ghz machine, with 4 GB DDR2 RAM memory. The operating system used was Ubuntu 18.04.1 64 bit LTS, and all the codes were developed in Java 8.

Experimental results of the proposal introduced in Gil et. al (2020) and best known values. Please cite this paper as:

• S. Gil-Borrás, E. G. Pardo, A. Alonso-Ayuso, and A. Duarte. GRASP with Variable Neighborhood Descent for the Online Order Batching Problem. Journal of Global Optimization. 78, 295–325 (2020) doi:10.1007/s10898-020-00910-2

• # References

• M. Albareda-Sambola, A. Alonso-Ayuso, E. Molina, and C. S. de Blas. Variable neighborhood search for order batching in a warehouse. Asia-Pacific Journal of Operational Research, 26(05), 2009.
• Pardo, E.G., Gil-Borrás, S., Alonso-Ayuso, A., Duarte A. (2023). Order Batching Problems: taxonomy and literature review. European Journal Operations Research, 313 (1), pp 1-24 doi: 10.1016/j.ejor.2023.02.019
• Sergio Gil-Borrás, Eduardo G. Pardo, Ernesto Jiménez & Kenneth Sörensen (2023) The time-window strategy in the online order batching problem. International Journal of Production Research, doi: 10.1080/00207543.2023.2263884
• Gil-Borrás, S., Pardo, E.G., Alonso-Ayuso, A., Duarte A. (2021). A heuristic approach for the online order batching problem with multiple pickers. Computers & Industrial Engineering, 160 (p. 107517) (2021). doi: 10.1016/j.cie.2021.107517
• Gil-Borrás, S., Pardo, E.G., Alonso-Ayuso, A., Duarte A. (2020) GRASP with Variable Neighborhood Descent for the online order batching problem. Journal of Global Optimization 78, 295–325 (2020). doi: 10.1007/s10898-020-00910-2
• Gil-Borrás, S., Pardo, E.G., Alonso-Ayuso, A., Duarte A. (2020) Fixed versus variable time window warehousing strategies in real time. Progress in Artificial Intelligence 1-10 (2020). doi: 10.1007/s13748-020-00215-1
• Gil-Borrás S., Pardo E.G., Alonso-Ayuso A., Duarte A. (2020) Basic VNS for a Variant of the Online Order Batching Problem. In: Benmansour R., Sifaleras A., Mladenović N. (eds) Variable Neighborhood Search. ICVNS 2019. Lecture Notes in Computer Science, vol 12010. Springer, Cham. doi: 10.1007/978-3-030-44932-2_2
• Gil-Borrás S., Pardo E.G., Alonso-Ayuso A., Duarte A. (2019) New VNS Variants for the Online Order Batching Problem. In: Sifaleras A., Salhi S., Brimberg J. (eds) Variable Neighborhood Search. ICVNS 2018. Lecture Notes in Computer Science, vol 11328. Springer, Cham. doi: 10.1007/978-3-030-15843-9_8
• S. Henn. Algorithms for on-line order batching in an order picking warehouse. Computers & Operations Research, 39(11):2549–2563, 2012
• S. Henn and G. Wäscher. Tabu search heuristics for the order batching problem in manual order picking systems. European Journal of Operational Research, 222(3):484-494, 2012.
• R. Pérez-Rodríguez, A. Hernández-Aguirre, and S. Jöns. A continuousestimation of distribution algorithm for the online order-batching problem. International Journal of Advanced Manufacturing Technology, 79(1):569–588, 2015.
• J.I.U. Rubrico, T. Higashi, H. Tamura, and J. Ota. Online rescheduling of multiple picking agents for warehouse management. Robotics and Computer-Integrated Manufacturing, 27(1):62 – 71, 2011
• J. Zhang, X. Wang, and K. Huang. Integrated on-line scheduling of orderbatching and delivery under b2c e-commerce. Computers & IndustrialEngineering, 94:280 – 289, 2016.