📈 #19 Almacenes -Parte III-: encuentra soluciones de alta calidad a problemas de recogida de pedidos
Aprende a utilizar VNS y técnicas de hibridación para resolver problemas de optimización de recogida de pedidos en almacenes
Como diría Julio Iglesias: hey!
Aunque esto dudo mucho que lo diga Julio Iglesias: hoy te voy a hablar de 2 temas muy interesantes y que te harán profundizar en algoritmos para dar soluciones al Order Batching Problem…
Las variantes más típicas de VNS.
Un algoritmo basado en VNS, pero mucho más potente, para dar soluciones de altísima calidad para el OBP.
No me digas que no recuerdas el OBP, que te lo conté la semana pasada 😉
Pues hoy en Factibles vamos un paso más allá… ¿Me acompañas?
Vamos a por ello!
🧩 Las variantes más típicas de VNS
Una de las mejores cosas que tiene VNS es que actúa como framework, más que como una receta con pasos muy estrictos a seguir. Esto es porque en cualquiera de las fases se pueden hacer modificaciones. Las más comunes son:
Basic VNS (BVNS): el proceso de perturbación es aleatorio y el de mejora solo tiene una búsqueda local. Es capaz entonces de explorar el espacio de soluciones mientras se alcanzan soluciones de calidad en poco tiempo de ejecución.
Variable Neighborhood Descent (VND): se exploran varias vecindades de manera determinística en diferentes procesos de búsqueda local, esta vez sin proceso de perturbación. VND termina su ejecución en un óptimo local respecto de todas las vecindades, pero al no haber movimiento de perturbación no se exploran otras áreas del espacio de soluciones.
General VNS (GVNS): es un BVNS vitaminado, porque el proceso de búsqueda local se sustituye por un esquema VND. El tiempo de ejecución será mayor que en BVNS, pero las soluciones serán de mucha más calidad que en los dos casos anteriores, ya que consigue lo bueno de BVNS (explorar el espacio de soluciones con movimientos aleatorios) y lo bueno de VND (encontrar un óptimo local muy, muy bueno).
Ni qué decir tiene que GVNS suele ser una opción más que recomendable si quieres obtener soluciones de muy alta calidad.
Dicho todo esto, no quiero que parezca que:
Entiendes el problema de optimización
Aplicas VNS para obtener soluciones de alta calidad
Aquí paz y después gloria y a por el siguiente problema
No, no, no…
Hay problemas que son muy complicados de resolver y los algoritmos que construyas para resolverlos necesitan power-ups. En optimización esto se conoce como hibridaciones: coges buenas ideas de un algoritmo, coges buenas ideas de otro algoritmo, y juntas sus recetas de manera que te salga un súper algoritmo para resolver tu problema.
🧑🏻💻 Un VNS Multi-arranque que da soluciones de altísima calidad para el OBP
Pues justo con los problemas de optimización de recogida de pedidos en almacenes ocurre esto. Es difícil que solo con VNS encuentres soluciones de altísima calidad, pero para eso existen alternativas.
Como estos problemas son suficientemente complejos, no hay algoritmo exacto que lo resuelva de manera eficiente y por eso se han propuesto muchos algoritmos heurísticos diferentes.
Yo mismo lo he hecho, no te digo más.
Aunque es muy probable que los algoritmos que yo haya diseñado ya no sean el estado del arte, un día hace no muchos años lo fueron.
Y todos ellos están basados en VNS. Lee bien: basados en VNS. No solo utilizan VNS. Esto es así porque igual…:
Necesitas explorar partes muy diversas del espacio de soluciones
Es difícil encontrar soluciones mucho mejores que las que ya tenías por las características del problema
Tienes que ir un paso más allá en tus estrategias de búsqueda local para garantizar encontrar esas soluciones de alta calidad
En cualquier caso, por aquí te dejo la primera de las 3 hibridaciones que usé en su momento, una para cada problema de los que te conté en el post anterior.
⚠️ Descargo de responsabilidad ⚠️
Esta es la parte más dura del post. Si no te has tomado un café todavía, vete preparándotelo. Luego no me digas que no te he advertido.
El Order Batching Problem, al ser el problema más tratado en la literatura de recogida de pedidos en almacenes, tiene una fuerte competencia en cuanto a algoritmos se refiere. Por eso, desarrollar estrategias para este problema que funcionen mejor que lo que ya hay es un verdadero reto.
Sobre todo desde el punto de vista creativo.
Uno de los algoritmos del estado del arte al que me enfrenté en su momento era capaz de encontrar ciertos atributos que compartían las soluciones de alta calidad. Era muy competitivo, y diría que el hueso más duro de roer. VNS solamente no iba a valer, bien lo sabía yo en aquel momento.
¿Pero cómo iba a conseguir explorar (más) eficientemente el espacio de soluciones para encontrar soluciones de (más) alta calidad sabiendo que ese algoritmo lo hacía extremadamente bien… Sin caer en exactamente las mismas ideas?
Pues bien, de 2 maneras diferentes:
Añadiendo más diversidad a las soluciones
Encontrando una alternativa a la búsqueda local
No fue nada fácil. Pero vayamos paso por paso.
Un punto importante en cualquier problema de optimización es explorar el espacio de soluciones ampliamente. Y una de las maneras de conseguirlo es empezar a explorarlo… ¡Por muchos sitios a la vez!
Así te aseguras de que cuando vayas a hacer una búsqueda local puedas comparar soluciones muy diferentes entre sí. Esto en sí mismo no tiene demasiado misterio: aleatorizas una parte de la construcción de soluciones y repites el proceso muchas, muchas veces:
Ahora bien, si lo que quieres es empezar este proceso con soluciones que ya tengan cierta calidad, el proceso de construcción debería ser medianamente inteligente.
Y eso es justo lo que hace la primera parte del algoritmo, InitSolution
Empieza de manera muy simple: cada pedido lo pone en un lote diferente y le aplica una búsqueda local. Si este método tan sencillo de construcción de soluciones fuese determinista, entonces siempre obtendrías la misma solución, por lo que no te serviría para tu propósito de tener diversidad de soluciones iniciales.
¿Dónde aplicarías ese toque de aleatoriedad que necesitas? Efectivamente, en la búsqueda local. Eso se puede hacer con una Elite Candidate List (ECL) dentro de la búsqueda local en la que:
Se crea una Master List de posibles soluciones examinando todos los movimientos factibles que mejoran la solución actual.
Se crea la ECL con un subconjunto de soluciones de la Master List que están por encima de cierto umbral (para quedarte con las mejores).
Se escoge una solución al azar dentro de la ECL.
Pues ahora que tenemos una solución de alta calidad, pero garantizando que en cada iteración tengas una solución diferente para mejorar la parte de exploración del espacio de soluciones…
Vamos a mejorarla con Basic VNS
(te cuento un secreto, pero no se lo cuentes a nadie: esta parte no era para mejorar la solución dada por la parte multi-arranque… era la propuesta inicial y principal; pero era insuficiente, y de ahí que se necesitase la parte previa de generación de soluciones diversas y la parte final de mejora de soluciones cambiando la función objetivo)
Bueno, pues aquí poco más que añadir a lo que te he contado ahí arriba sobre BVNS.
Lo que sí te quiero contar son los movimientos que se hacen en la búsqueda local. No porque sean complicados, sino porque nunca te he hablado de cómo es un movimiento, ¿verdad?
Hay dos en este algoritmo:
De inserción, en los que se coge un pedido de un lote y se mueve a otro lote, es decir, el pedido antes estaba asignado a un lote y ahora está asignado a otro.
De intercambio, en los que se coge un pedido de un lote y otro pedido de otro lote diferente y se intercambian las posiciones, es decir, el pedido que estaba asignado al primer lote ahora está asignado al segundo lote y el que estaba asignado al segundo lote ahora está asignado al primero.
Como ves, no hay mucha magia detrás de esto. Son cosas bastante lógicas.
Normalmente la las diferencias en el rendimiento de estos movimientos radica en cómo se hagan y cómo de útiles sean para el problema: si se hacen de manera aleatoria serán rápidos pero tendrás que probar muchos para encontrar una solución que mejore, si los haces estudiando la solución para tratar de hacer los mejores posibles movimientos invertirás más tiempo pero las soluciones podrán ser de mayor calidad.
Recuerda también lo que te contaba respecto a los movimientos de primera mejora o de mejor mejora en este otro artículo:
Y además de eso, la búsqueda local explora las dos vecindades basadas en ambos movimientos, es decir, escoge el movimiento que más vaya a mejorar la solución.
Encontrar una alternativa a la búsqueda local… Cambiando la Función Objetivo del problema en un esquema GVNS
Como las soluciones todavía no son suficientemente buenas en este punto, hay que darle una vuelta de tuerca adicional.
La vuelta de tuerca: cambiar la función objetivo. Ahora, en lugar de directamente minimizar la suma de los tiempos de recogida de pedidos, lo que íbamos a hacer era minimizar el número de lotes totales que habría en la solución. La hipótesis es sencilla: a menor número de lotes, menos viajes tienes que darte por el almacén, disminuyendo de esa forma los tiempos de recogida totales.
Parece un buen punto de partida, ¿no?
Además, tiene ciertas similitudes con un problema típico de optimización: el Bin-Packing Problem. De esto te hablaré pronto, no te preocupes.
Lo que hacemos aquí es seleccionar aquel lote que tiene menos pedidos y tratar de redistribuir esos pedidos entre el resto de lotes, haciendo cambios también en el resto de lotes para que quedan esos pedidos.
Este he de decir que es un proceso bastante complejo que involucra varios tipos de movimientos -de ahí que finalmente fuese un GVNS-, no te voy a mentir. Y por eso preferiría que te leyeras directamente la explicación en el artículo científico que publiqué junto a mis directores de tesis en la revista Computers & Operations Research.
Pero quédate con la idea fundamental: se puede mejorar una función objetivo principal (minimizar los tiempos de recogida en el almacén) a través de una función objetivo alternativa (que minimice el número de lotes totales).
🏁 Conclusiones
Lo primero, si has llegado hasta aquí… Una de dos: o el café era muy bueno, o el tema realmente te interesaba 😉
Lo segundo, has podido ver en este post varias cositas:
Las variantes más típicas de VNS con las que podrás ligar en la discoteca (o no).
VNS es un framework muy flexible y se pueden hacer hibridaciones muy chulas.
Un sistema multi-arranque te abre un mundo nuevo de posibilidades al explorar más parte del espacio de soluciones.
Se puede mejorar una función objetivo principal a través de una función objetivo alternativa.
Nos vemos en el siguiente post, que seguro que es más ligero que este.
Hasta entonces,
Borja.
