Heuristic strategies for different variants of the Order Batching Problem

Abstract

Optimization is a discipline that can be seen as a cornerstone of other areas, such as Artificial Intelligence, Computer Science, or Operations Research, among others. Optimization aims to find feasible, high-quality solutions to real-life problems. It has applications in engineering, medicine, economy, logistics and many other fields. Since there exist many optimization problems with practical interest, efficient techniques to address them are necessary. A possible classification of the current approaches can distinguish between exact and approximate methods. Exact methods are able to obtain an optimal solution to a certain problem, but they usually require a large execution time; thus, they are impracticable when the size of the problem is sufficiently large, as it commonly occurs in real-life problems. Within the family of approximate techniques, heuristic algorithms are able to find high-quality solutions in a reasonable amount of time; however, they can not guarantee the optimality of the solution found, neither how far is the provided solution to the optimum one. The Order Batching Problem (OBP) is an NP-hard optimization problem, whose objective is to minimize the total retrieving time of a set of orders received in a warehouse. In order to achieve that, the main strategy is to group orders into batches, so that orders from the same batch are retrieved in the same travel. There also exist different variants to the original problem in which different objective functions are considered. For instance, the minimization of the maximum retrieving time of each batch, the minimization of the tardiness when orders has a certain due date, the minimization of the total retrieving time when orders are received in an online way, etc. In this Doctoral Thesis we propose several heuristic algorithms to address problems related to the OBP. All the proposed algorithms make use of the Variable Neighborhood Search (VNS) methodology in some of its most usual variants (Basic VNS or General VNS), in a parallel implementation, or embedded in a multi-start strategy. These algorithms have been tested in different variants of the OBP over several reference sets of instances. The obtained results improve the current state of the art in all the OBP variants tackled.