GRASP with Variable Neighborhood Descent for the online order batching problem
- PDF / 1,715,485 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 108 Downloads / 208 Views
GRASP with Variable Neighborhood Descent for the online order batching problem Sergio Gil-Borrás1 · Eduardo G. Pardo2 · Antonio Alonso-Ayuso2 · Abraham Duarte2 Received: 24 May 2019 / Accepted: 16 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract The Online Order Batching Problem (OOBP) is a variant of the well-known Order Batching Problem (OBP). As in the OBP, the goal of this problem is to collect all the orders that arrive at a warehouse, following an order batching picking policy, while minimizing a particular objective function. Therefore, orders are grouped in batches, of a maximum predefined capacity, before being collected. Each batch is assigned to a single picker, who collects all the orders within the batch in a single route. Unlike the OBP, this variant presents the peculiarity that the orders considered in each instance are not fully available in the warehouse at the beginning of the day, but they can arrive at the system once the picking process has already begun. Then, batches have to be dynamically updated and, as a consequence, routes must too. In this paper, the maximum turnover time (maximum time that an order remains in the warehouse) and the maximum completion time (total collecting time of all orders received in the warehouse) are minimized. To that aim, we propose an algorithm based in the combination of a Greedy Randomized Adaptive Search Procedure and a Variable Neighborhood Descent. The best variant of our method has been tested over a large set of instances and it has been favorably compared with the best previous approach in the state of the art. Keywords Warehouse management · Online order batching problem · Order batching · Turnover time · Heuristics
1 Introduction The picking of items in a warehouse, as a part of the supply chain management, follows a picking policy which determines how the picking of items is performed in the warehouse. It is possible to find different picking policies in the literature such as: single-order picking,
This research was partially funded by the projects: MTM2015-63710-P, RTI2018-094269-B-I00, TIN2015-65460-C2-2-P and PGC2018-095322-B-C22 from Ministerio de Ciencia, Innovación y Universidades (Spain); by Comunidad de Madrid and European Regional Development Fund, Grant Ref. P2018/TCS-4566; and by Programa Propio de I+D+i de la Universidad Politécnica de Madrid (Programa 466A).
B
Eduardo G. Pardo [email protected]
Extended author information available on the last page of the article
123
Journal of Global Optimization
batching and sort-after-picking, single-order picking with zoning, batching with zoning, among others. Order Batching can be considered as a family of picking policies which are based on grouping the orders received in the warehouse into batches, prior to start the picking process. Once the batches have been conformed, all the items within the orders of the same batch are picked together in the same picking route. There are many optimization problems related to the process of picking items
Data Loading...
