Tesis:
Online Order Batching Problem: a heuristic approach for single and multiple pickers
- Autor: GIL BORRÁS, Sergio
- Título: Online Order Batching Problem: a heuristic approach for single and multiple pickers
- Fecha: 2022
- Materia:
- Escuela: E.T.S.I. DE SISTEMAS INFORMÁTICOS
- Departamentos: SISTEMAS INFORMATICOS
- Acceso electrónico: https://oa.upm.es/72538/
- Director/a 1º: GARCÍA PARDO, Eduardo
- Director/a 2º: JIMÉNEZ MERINO, Ernesto
- 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 fnal customers. Generally, the objective of the operations in a warehouse are devoted to reducing delivery times. To that aim it is important to have efcient storage and collection strategies.
There are multiple problems within logistic warehouses that need to be solved. Many of these problems can be defned as optimization problems. Among them, problems related to the order picking process stands out. Order picking can be tackled with diferent picking policies. Among the best-known order picking policies, we can fnd “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 specifcally, 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 classifcation of the variants would divide them into Ofine/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 identifed 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 diferent 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 beneft 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 efciently 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 difculty of being trapped in local optima, that is, in the best possible solution within a specifc neighborhood. Metaheuristics are high-level heuristics capable of escaping from a local optimum and reaching others belonging to diferent neighborhoods. In the case of this Doctoral Thesis, diferent 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 diferent 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 scientifc forums.
RESUMEN
La reciente expansión del comercio electrónico ha impulsado el desarrollo de numerosos sectores a su alrededor, entre los que se encuentran todos aquellos relacionados con la cadena de suministro. Los almacenes logísticos juegan un papel clave en dicha cadena, siendo los responsables de la recepción, almacenaje y posterior recogida de productos, que deben ser servidos a otros almacenes o a clientes finales. De manera general, se persigue el objetivo de reducir los tiempos de entrega, para lo que es relevante disponer de estrategias de almacenaje y recogida eficaces.
Dentro de los almacenes logísticos, deben resolverse múltiples problemas que pueden ser enunciados como problemas de optimización. Entre ellos, destacan los problemas relacionados con la recogida de pedidos, que puede seguir diferentes estrategias o políticas de recogida. Entre las más conocidas se encuentran las políticas Strict Order Picking y Order Batching. La primera, está caracterizada por realizar una recogida individual de los pedidos, es decir, el operario inicia una nueva ruta de recogida cada vez que recoge un nuevo pedido. Por otro lado, la política Order Batching se caracteriza porque los pedidos son agrupados en lotes y la recogida de todos los pedidos asociados al mismo lote se realiza en una misma ruta, normalmente por un único operario.
Esta Tesis Doctoral se centra en la resolución de algunos problemas de optimización pertenecientes a la familia denominada Order Batching Problems (OBP), que aparecen cuando se emplea una política de recogida por lotes. De manera más concreta, esta Tesis Doctoral está centrada en la resolución de la tarea consistente en determinar la agrupación de pedidos en lotes, comúnmente denominada batching, si bien, la resolución de un problema perteneciente a la familia OBP implica abordar también otras tareas tales como: determinar el siguiente lote a recoger, seleccionar el operario que realizará la recogida, establecer la ruta de recogida dentro del almacén, determinar el tiempo que un operario debe esperar antes de iniciar una nueva ruta, etc. Estas tareas varían según la variante del problema estudiada. Una posible clasificación de las variantes las dividiría en Ofine/Online, según la disponibilidad de la información relativa a la llegada de nuevos pedidos. También es posible clasificarlas como Single Picker/Multiple Pickers según se disponga de uno o varios operarios recogiendo los pedidos simultáneamente. Las variantes también pueden diferenciarse según la función objetivo que se estudie. Esta Tesis Doctoral se centra en las variantes Online del problema, que se caracterizan por ser problemas de optimización dinámica donde los pedidos llegan al sistema de manera continuada, es decir, mientras que el proceso de recogida está en marcha. En este contexto, no se tiene ninguna información del siguiente pedido que llegará al sistema. Este tipo de escenario podría considerarse como el más realista hoy en día, dado que la venta de productos online es continua, al estar las plataformas de comercio electrónico 24h al día operativas. Entre las diferentes variantes Online del OBP, en esta Tesis Doctoral se estudia la tarea de batching tanto en contextos con un único operario, como en contextos con múltiples operarios. Además, se destaca la identificación y el estudio de la tarea que determina el tiempo de ventana. Esta tarea solo se da en las variantes Online del problema y ha sido muy poco estudiada en la literatura, pero tiene un gran impacto sobre los resultados obtenidos. Determinar el tiempo de ventana consiste en determinar el mejor momento de salida del operario para realizar la recogida del lote generado. Retrasar el tiempo de salida del operario produce que puedan llegar nuevos pedidos al sistema, lo que podría beneficiar una mejor composición de los lotes restantes.
La resolución de la tarea de batching tiene una complejidad computacional J\ÍV-Difícil, de manera que no es posible determinar de manera eficiente la solución óptima al problema en un tiempo razonable, cuando el tamaño del problema es grande, como es el caso de la mayoría de las situaciones reales. Para abordar los problemas descritos anteriormente se emplean técnicas heurísticas y metaheurísticas, ya que estas técnicas son capaces de ofrecer soluciones de gran calidad, en un corto periodo de tiempo, para problemas A/"P-Difíciles. Las heurísticas son empleadas tanto para generar una solución inicial al problema (a través de heurísticas constructivas) como para buscar soluciones de mejor calidad en la vecindad de una solución dada (heurísticas de búsqueda). No obstante, estas presentan la dificultad de quedar atrapadas en óptimos locales, es decir, en la mejor solución posible dentro de una vecindad concreta. Las metaheurísticas son heurísticas de nivel superior que complementan a las heurísticas de búsqueda, siendo capaces de escapar de un óptimo local y alcanzar otros pertenecientes a distintas vecindades. En el caso de esta Tesis Doctoral se han propuesto diferentes algoritmos constructivos y de búsqueda para la resolución de los problemas anteriormente mencionados, junto con la utilización de las metaheurísticas Variable Neighborhood Search y Greedy Randomized Adaptive Search Procedure. Los algoritmos propuestos para cada una de las diferentes variantes estudiadas han sido capaces de mejorar, en sus respectivos contextos, a los algoritmos existentes en el estado del arte. Por último, hay que destacar que los resultados más relevantes obtenidos durante el desarrollo de esta Tesis Doctoral han sido publicados en foros científicos internacionales de reconocido prestigio.