Metaheuristics for order batching and sequencing in manual order picking systems

• The paper studies a planning issue pivotal for the efficiency of warehouse operations.
• A new mathematical optimization model for the Order Batching and Sequencing Problem is introduced.
• It is presented how Iterated Local Search and Attribute-Based Hill Climber can be applied to the problem.
• Numerical experiments show that the proposed methods outperform existing solution approaches in terms of solution quality.
• A detailed analysis of the effects of the instance characteristics is given.

Order picking involves the retrieval of articles from their storage locations in order to satisfy customer requests. A major issue in manual order picking systems is the transformation and consolidation of customer orders into picking orders (order batching). In practice, customer orders have to be completed by certain due dates in order to avoid shipment or production delays. The composition of the picking orders, their processing times and the sequence according to which they are released have a significant impact on whether and to which extent due dates are violated. This paper presents how metaheuristics can be used in order to minimize the total tardiness for a given set of customer orders. The first heuristic is based on Iterated Local Search, the second is inspired by the Attribute-Based Hill Climber, a heuristic based on a simple tabu search principle. In a series of extensive numerical experiments, the performance of these metaheuristics is analyzed for different classes of instances. We will show that the proposed methods provide solutions which may allow order picking systems to operate more efficiently. Solutions can be improved by 46% on average, compared to those obtained with standard constructive heuristics such as the Earliest Due Date rule.