The Online Order Batching Problem is a combinatorial optimization problem related to the process of retrieving items within a warehouse. It appears in the context of warehousing, when the warehouse follows an order-batching picking policy, which means that orders are packed together into batches before been collected. Additionally, since this problem is online, orders are arriving to the warehouse continuously, which is usually due to the fact that orders come from an e-commerce platform. The variant of the problem tacked in this paper also considers an additional characteristic: there are multiple pickers available to collect the batches. In this paper we propose several strategies, based on the Variable Neighborhood Search methodology, to tackle the problem and we compare them with the algorithms in the state of the art, using previously referred data sets. Additionally, we test the influence of different routing strategies not used before in the context of this variant.