Análisis y mejora mediante técnicas metaheurísticas de subastas multi-producto online para el sector siderúrgico
- Ena Rodriguez, Borja
- Alberto Gómez Gómez Director
Universitat de defensa: Universidad de Oviedo
Fecha de defensa: 22 de de juny de 2018
- Ernesto Cilleruelo Carrasco President/a
- David de la Fuente García Secretari
- Ángel Manuel Gento Municio Vocal
Tipus: Tesi
Resum
El objetivo principal de la tesis doctoral “Análisis y mejora mediante técnicas meta-heurísticas de subastas multi-producto online para el sector siderúrgico”, realizada por D. Borja Ena Rodríguez y dirigida por el Dr. D. Alberto Gómez Gómez, es mejorar el proceso de ventas de productos de acero “non-prime”, en primer lugar resolviendo el problema de agrupación de productos en lotes de manera que éstos sean lo más homogéneos posibles y bajo restricciones tanto de los productos como del tamaño de lote, y en segundo lugar analizando todo el proceso global de venta para estudiar la idoneidad del mismo y proponer otras alternativas. Durante el proceso de fabricación de productos de acero, no todos los productos cumplen el nivel de calidad exigido por el cliente final. Estos productos, denominados “non-prime” se venden mediante una subasta online semanal, siendo necesario una agrupación previa de los mismos en lotes, de manera que éstos sean lo más homogéneos posibles atendiendo a varias características de los productos. Esta agrupación es un problema muy complejo de resolver, y es precisamente la parte fundamental del proceso de ventas, ya que cuanto más homogéneos sean los lotes, más atractivos serán para los clientes, que a su vez realizarán más pujas, incrementando el beneficio. Aproximadamente medio millón de toneladas se venden anualmente con este sistema en todas las plantas de productos planos del grupo. Resolver de una manera adecuada el problema representa, pues, un tremendo impacto económico, a la vez que un reto desde el punto de vista algorítmico, ya que no se ha resuelto ningún problema similar hasta la fecha. Inicialmente se realiza una descripción del problema, exponiendo primero todo el proceso de ventas de productos non-prime, centrándose en la parte de subastas y las reglas de agrupamiento que deben de cumplirse durante la preparación de los lotes, para finalizar describiendo los requisitos que debe de cumplir el algoritmo a desarrollar. A continuación se analiza la literatura existente de subastas, tanto las principales variantes existentes como los principales factores que influyen en el proceso, para estudiar si el método de subasta elegido por la empresa (cerrada de primer precio, con precio reserva) es el más adecuado, o se pueden proponer alternativas. Tras esto, para poder plantear un algoritmo de resolución del problema se realiza primero un estado del arte de la literatura existente del problema de empaquetado por lotes (Bin Packing Problem), analizando sus variantes y las técnicas utilizadas para resolverlo. Dado que el problema a resolver no coincide con ninguna de las variantes, se define este nuevo problema como “Problema de empaquetado de lotes homogéneos con mínimo peso”, se formula matemáticamente y se propone una metodología de resolución estructurada en 3 fases, consistentes en una división inicial de los productos basándose en sus características comunes, un algoritmo de clustering y una última fase de optimización de la asignación de productos a lotes finales, para la cual se desarrollan 3 heurísticos (FIFO, Greedy y Distancias) y un meta-heurístico GRASP. Para comparar la bondad de la solución y dado que no existe un problema similar, se generan 80 instancias de prueba basadas tanto en las instancias clásicas de Bin Packing Problem, como en datos reales del problema a resolver, y se comparan los resultados obtenidos con cada heurístico y el meta-heurístico GRASP. Finalmente, se prueba el algoritmo con un caso de real para demostrar tanto su funcionamiento como su rendimiento. Resultados Del análisis teórico realizado sobre subastas se concluye que es coherente que la subasta sea cerrada y con precio reserva. Se propone como recomendación realizar una subasta descendente para aquellos productos que no se han vendido con la subasta inicial, para aumentar el beneficio global del sistema de venta. En lo referente al problema de agrupamiento, tras analizar las pruebas realizadas sobre las 80 instancias generadas, se puede concluir que el algoritmo propuesto resuelve el problema planteado, siendo el meta-heurístico GRASP la mejor solución para la fase final, ya que mejora las soluciones obtenidas utilizando solamente los heurísticos individuales en el 84% de las instancias. Las mejores soluciones se han conseguido utilizando el algoritmo FIFO como generador de las soluciones iniciales del GRASP. Para su aplicación al caso real se propone lanzar la tercera fase del algoritmo 2 veces, una con soluciones iniciales generadas por el FIFO y otra con soluciones iniciales generadas con el heurístico de Distancias. De esta forma, se consigue un tiempo de computación para 26 plantas y 2771 productos de unos 4 minutos y se garantiza una muy buena solución.