GRASP with Variable Neighborhood Descent for the online order batching problem

Resumen

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.

Publicación
Journal of Global Optimization
Eduardo García Pardo
Eduardo García Pardo
Profesor Titular de Universidad

Miembro fundador del grupo de investigación GRAFO, cuya línea de investigación principal es el desarrollo de algoritmos para abordar problemas de optimización, temática sobre la que versa la Tesis Doctoral del investigador y en la que se enmarcan sus publicaciones más destacadas.

Abraham Duarte
Abraham Duarte
Catedrático de Universidad

Mi carrera investigadora se ha centrado en el desarrollo de nuevos algoritmos y técnicas de Inteligencia Computacional (metaheurísticas) y su aplicación a diferentes problemas en Ciencia e Ingeniería desde que me incorporé a la Universidad Rey Juan Carlos (URJC) en el octubre del año 2000.