Heuristic strategies for different variants of the order batching problem

Resumen

La optimización es una disciplina que puede ser considerada como una piedra angular para diversas áreas, tales como Ciencias de la Computación, Inteligencia Artificial o Investigación Operativa, entre otras. Con ella, se trata de encontrar soluciones factibles de la mejor calidad posible a problemas de la vida cotidiana y tiene aplicaciones en ingeniería, medicina, economía, logística y otros muchos campos. Dado el interés práctico que tienen muchos problemas de optimización, es necesario disponer de técnicas eficientes para abordarlos. Una posible clasificación de las técnicas existentes en la actualidad podría dividirlas en exactas y aproximadas. Las técnicas exactas son capaces de encontrar la solución óptima a un problema determinado, pero generalmente requieren un tiempo de cómputo elevado, por lo que son inviables cuando el tamaño del problema es grande, como suele ser el caso de las aplicaciones reales. De entre las técnicas aproximadas destacan los algoritmos heurísticos, capaces de encontrar soluciones de alta calidad en un tiempo de cómputo razonable, pese a no poder certificar si la solución encontrada es óptima ni cómo de lejos está de ella. El Problema del Empaquetado de Pedidos (OBP, del inglés Order Batching Problem) es un problema de optimización NP-Difícil cuyo objetivo es minimizar el tiempo total de recogida de un conjunto de pedidos recibidos en un almacén. Para ello, se sigue la estrategia de agrupar los pedidos en lotes, de modo que los pedidos de un mismo lote se recogen de manera simultánea. Existen diversas variantes del problema original en las que la función objetivo varía, tales como la minimización del tiempo máximo de recogida de cada lote, o la minimización del tiempo de retraso cuando los pedidos tienen una hora límite de entrega. En esta Tesis Doctoral se proponen algoritmos heurísticos para la resolución de un conjunto de problemas relacionados con el OBP. Todos los algoritmos propuestos hacen uso de la metodología de Búsqueda de Vecindad Variable (VNS, del inglés Variable Neighborhood Search). En concreto, se han utilizado las variantes VNS Básica y VNS General, además de una versión paralela y otra embebida en un esquema multiarranque. Estos algoritmos han sido probados sobre diferentes conjuntos de instancias, mejorando los resultados obtenidos por los métodos previos existentes en el estado del arte.