Online Order Batching Problem: a heuristic approach for single and multiple pickers

• Autores: Sergio Gil Borrás
• Directores de la Tesis: Eduardo García Pardo (dir. tes.) , Ernesto Jimenez Merino (codir. tes.)
• Lectura: En la Universidad Politécnica de Madrid ( España ) en 2022
• Idioma: inglés
• Tribunal Calificador de la Tesis: Rubén Ruiz García (presid.) , Francisco Serradilla García (secret.) , José Manuel Colmenar Verdugo (voc.) , Francisco Parreño Torres (voc.) , Manuel López Ibañez (voc.)
• Programa de doctorado: Programa de Doctorado en Ciencias y Tecnologías de la Computación para Smart Cities por la Universidad Politécnica de Madrid
• Calificación: Sobresaliente Cum Laude
• Enlaces
  • Tesis en acceso abierto en: Archivo Digital UPM
• Resumen

  • The recent expansion of electronic commerce has promoted the development of numerous sectors around it. Among these sectors are those related to the supply chain management. Within the supply chain, logistic warehouses play a key role, being responsible for receiving, storing, and collecting products, which must be delivered to other warehouses or final customers. Generally, the objective of the operations in a warehouse are devoted to reducing delivery times. To that aim it is important to have efficient storage and collection strategies. There are multiple problems within logistic warehouses that need to be solved. Many of these problems can be defined as optimization problems. Among them, problems related to the order picking process stands out. Order picking can be tackled with different picking policies. Among the best-known order picking policies, we can find "Strict Order Picking" and "Order Batching". The former one is characterized by picking each order individually, i.e., the picker starts a new collection route each time a new order needs to be picked. On the other hand, the Order Batching policy is characterized by the fact that orders are grouped into batches, and the collection of all the orders associated with the same batch is carried out on the same picking route, normally by a single picker. This Doctoral Thesis focuses on solving several optimization problems belonging to the family of Order Batching Problems (OBP), which appear when a batch collection policy is used in the picking process of a warehouse. More specifically, this Doctoral Thesis focuses on solving the task of determining the grouping of orders into batches, commonly named as "batching". The resolution of a problem belonging to the OBP family implies also addressing other tasks such as: determining the next batch to be picked, selecting the order picker who will carry out the picking, establishing the picking route within the warehouse, determining the time that a picker must wait before starting a new route, etc. These tasks vary depending on the variant of the problem studied. A possible classification of the variants would divide them into Offline/Online, depending on the availability of information regarding to the arrival of new orders. It is also possible to classify them as single picker/multiple pickers depending on whether there are one or several pickers collecting the orders simultaneously. Variants of the problem can also be identified according to the objective function studied. This Doctoral thesis focuses on the online variants of the problem, which are characterized by being dynamic optimization problems where orders arrive at the system continuously, i.e., while the collection process is undergo. In this context, there is no information about the next order that will arrive at the system. This type of scenario could be considered the most realistic nowadays, given that the online sale of products is continuously happening, as e-Commerce platforms operate 24 hours a day. Among the different online variants of the OBP family, in this Doctoral Thesis, the batching task is studied both: single picker context, and multiple pickers context. In addition, the task that determines the time window is also highlighted and studied. This task occurs only in online variants of the problem, and it has been little studied in the literature, but it has a great impact on the obtained results. Determining the time window consists of determining the best time for the picker to leave and collect the generated batch. Delaying the start of the picking route means that new orders may arrive at the system, which could benefit a better composition of the remaining batches. The resolution of the batching task belongs to the NP-hard computational complexity class, so it is not possible to efficiently determine the optimal solution to the problem in a reasonable amount of time, when the size of the problem is large, as it is the case in most real situations. Heuristic and metaheuristic techniques are used to address the problems described above, since these techniques provide high-quality solutions for NP-Hard problems in short computing times. Heuristics are used both to generate an initial solution to the problem (constructive heuristics) and to search for better-quality solutions in the neighborhood about a given solution (search heuristics). The latter present the difficulty of being trapped in local optima, that is, in the best possible solution within a specific neighborhood. Metaheuristics are high-level heuristics capable of escaping from a local optimum and reaching others belonging to different neighborhoods. In the case of this Doctoral Thesis, different construction and local search algorithms have been proposed to solve the problems, together with the use of the Variable Neighborhood Search and Greedy Randomized Adaptive Search Procedure metaheuristics. The algorithms proposed for each of the different variants studied have been able to improve, in their respective contexts, the existing algorithms in the state of the art. Finally, we point out that the most relevant results obtained have been published in prestigious international scientific forums.