📈 #18 Almacenes -Parte II-: 3 problemas de optimización al recoger pedidos
Y una metaheurística que puede resolverlos
Agárrate que vienen curvas…
Me ha quedado el post tan largo que no he tenido más remedio que dividirlo en dos. Así que hoy en Factibles te cuento:
3 problemas de agrupamiento y recogida de pedidos en almacenes típicos
Primera zambullida en Variable Neighborhood Search, una metaheurística muy potente
Acuérdate de por qué estamos hoy aquí: los almacenes son cada vez más importantes en la logística moderna y hay un problema en particular que supone hasta el 60% del tiempo que se emplea en un almacén: el proceso de recogida de pedidos.
Además, Mercadona encontró la rentabilidad de su modelo online gracias a resolver ese problema de manera más eficiente.
También te he dado las primeras pinceladas sobre metaheurísticas, pero sobre todo los principios de VNS.
Hoy profundizo un poco más: te cuento detalles sobre estos problemas y empiezo a rascar en las profundidades de mi metaheurística favorita.
¡Vamos a por ello!
📦 3 problemas en recogida de pedidos en almacenes
Cuando te hablé de que Mercadona se había vuelto rentable en la parte online solo con resolver el problema de la recogida de pedidos, en realidad te estaba contando solo la mitad de la película.
Maneras de operar un almacén hay todas las que se te ocurran: totalmente automatizado con robots, parcialmente automatizado y conviviendo robots con humanos, solo con humanos, teniendo en cuenta una hora máxima de salida de pedidos cada día, equilibrando el trabajo de todos los trabajadores… En fin, tú me entiendes.
Pero dentro de todas esas opciones siempre hay dos partes que destacan:
El proceso de recogida en sí mismo, que es la ruta que deben seguir los empleados del almacén al recoger los pedidos.
El proceso de agrupamiento de pedidos en lotes, que es la manera en la que se juntan los pedidos para ser recogidos en un solo viaje (un grupo de pedidos por viaje).
En la literatura lo que ocurre es que hay 3 procesos de recogida muy utilizados. Son ideas sencillas que dan una solución normalmente buena en muy poco tiempo de ejecución. ¿Te acuerdas del Problema del Viajante de Comercio? Pues todas son versiones muy simplificadas y adaptadas al diseño del almacén.
Por eso no le voy a dar mucho bombo a esa parte.
El proceso de agrupamiento de pedidos en lotes es sencillo también, ¿no? Juntas varios pedidos que te quepan en el carrito que utilizas para recogerlos por el almacén, y listo. La única restricción es esa: que te quepan en el carrito (por número, volumen o peso).
Llegado a este punto me dirás “bueno, Borja, ¿entonces para qué me has traído hasta aquí?”.
Pues es sencillo: porque donde radica la complejidad de verdad es en juntar ambas partes.
Si te fijas bien, están estrechamente relacionadas: el proceso de recogida de pedidos es lo que evalúa cómo de bueno o malo es el proceso de agrupamiento. Y necesitas probar no muchas, sino muchísimas combinaciones diferentes de agrupamientos para entender cuál es la mejor de todas. Este es el potencial que te dan los algoritmos.
Por supuesto, en un almacén real hay muchas más restricciones que la capacidad del carrito. Pero voy a simplificar esa parte y me voy a centrar solo en la operativa del almacén con tres ejemplos:
(OBP) Recogida, y ya
De acuerdo a De Koster et al., el tiempo total en la recogida de pedidos se puede reducir un 35% solo con diseñar apropiadamente las rutas de los empleados. Y puede aumentar significativamente si las dos decisiones (proceso de recogida + proceso de agrupamiento) se consideran simultáneamente.
Por eso es interesante estudiar el problema de optimización que combina ambas decisiones, conocido en la literatura como Order Batching Problem (OBP), o Problema de Agrupamiento de Pedidos.
El problema consiste básicamente en agrupar un conjunto de pedidos en lotes y, para cada lote, se define la ruta para recoger todos los productos del lote.
Aquí el objetivo es encontrar la configuración de lotes que minimiza los tiempos de recogida de todos los productos.
Este problema, que parece sencillo así descrito, es tan complejo de resolver que en cuanto hay más de 2 pedidos por lote la combinatoria crece tanto que no se puede resolver de manera exacta en un tiempo razonable.
Es decir, pertenece a esa clase de problemas que se llaman NP-difícil (o NP-duro, dependiendo de cómo traduzcas NP-hard 😉). Y por eso existen muchas implementaciones con algoritmos heurísticos en la literatura.
(Min-Max OBP) Todos los trabajadores empiezan y terminan a la vez (aproximadamente)
En este problema se tienen en cuenta operaciones de recogida de pedidos en oleadas, es decir, los lotes se recogen de manera simultanea por un grupo de trabajadores.
Este tipo de operaciones se tienen normalmente en el contexto de almacenes en los que los conjuntos de pedidos son muy grandes, por lo que los tiempos de recogida son importantes.
Aquí se asume que cada trabajador recoge los pedidos de solo un lote y que todos los trabajadores empiezan a la vez, por lo que se espera que todos terminen aproximadamente a la vez.
Para ello, el objetivo es minimizar el tiempo máximo de recogida de los lotes. Y de ahí su nombre: Min-Max, de minimización del máximo, y OBP, porque se basa en las mismas condiciones que el OBP.
(OBSP) Los pedidos tienen una hora máxima de salida del almacén
Para este tercer problema no solo se tienen en cuenta las estrategias para la recogida y agrupamiento, sino también el de la ordenación de los lotes.
En el Order Batching and Sequencing Problem (OBSP), o Problema de Agrupamiento y Ordenación de Lotes, cada pedido tiene una hora máxima de salida del almacén para satisfacer la demanda del cliente.
Si un pedido no se entrega a tiempo, se dice que tiene un valor de retraso (el tiempo extra que pasa desde la hora teórica de salida del almacén y la hora real). Si un pedido se entrega antes de tiempo, se diría que el valor de retraso es cero.
También hay que tener en cuenta que todos los pedidos del mismo lote tienen la misma hora de entrega, pero algunos pedidos cumplirán con su hora de entrega (no tendrán retraso alguno) mientras que otros pedidos no (teniendo retraso).
Por tanto, el objetivo de este problema es minimizar el retraso total de todos los pedidos que se reciben en el almacén.
Esto añade esa dimensión extra al problema, el de la ordenación de los lotes.
Y ahora que te he mostrado algunos de los problemas que se suelen dar en un almacén… Veamos cómo podemos resolverlos, ¿no?
Ya sabes que hay una metaheurística que me encanta por varios motivos: Variable Neighborhood Search, o VNS.
Te la cuento ahora mismito.
🏘️ Sumerjámonos en VNS
VNS trata de encontrar un buen compromiso entre diversificación e intensificación. Por eso, la mayoría de sus variantes tienen dos fases claramente diferenciadas: una en la que se perturba la solución para llegar a un punto nuevo del espacio de búsqueda -haciendo la parte de diversificación- y una fase de búsqueda local para encontrar un óptimo local -esto ya en la parte de intensificación-.
Cómo se explora el espacio de soluciones se puede ver en la siguiente imagen:
Donde una solución, se perturba y mejora de manera sucesiva en varias iteraciones hasta encontrar el mejor óptimo local posible. En a) y c) lo que se puede ver es a la solución llegando a un óptimo local gracias a un proceso de búsqueda local, mientras que en b) y d) la solución escapa del óptimo local por medio del proceso de perturbación de la solución. En esa imagen, cuanto más grandes son los círculos que rodean a una solución, más grande es la vecindad que se está explorando; aunque solo se muestra un posible movimiento.
Y esto, ¿cómo te lo llevas a código? Pues con la siguiente receta:
VNS recibe una solución S (que ya debería estar en un óptimo local), un número máximo de vecindades a explorar y un tiempo máximo de ejecución (o un número máximo de ejecuciones).
Primero, se inicializa VNS a buscar en la primera vecindad, y justo después entra en un bucle en el que explora kmax vecindades:
Shake: se perturba la solución actual para generar una nueva en la vecindad actual.
Improve: se mejora la solución perturbada con un proceso de búsqueda local para encontrar un óptimo local.
NeighborhoodChange: si ha habido mejora respecto a la solución actual, se actualiza a la nueva solución encontrada y se resetea la vecindad a explorar para empezar de nuevo por la primera, si no ha habido mejora saltamos a la siguiente vecindad.
Y este proceso se repite hasta que se llegue al tiempo máximo de ejecución -o número máximo de iteraciones-.
Con esto ya tienes una idea mucho mejor formada sobre VNS, y para no hacer el post demasiado intensito te cuento las variantes más típicas e hibridaciones para resolver los 3 anteriores problemas en el siguiente post.
🏁 Conclusiones
Hoy te he traído la primera mitad de todo lo que te quería contar, pero aún así te he descrito:
3 problemas muy recurrentes en el proceso de recogida de pedidos en almacenes.
Mi metaheurística favorita, cómo explora el espacio de soluciones y la receta a seguir si quieres implementarla.
Pero esto no acaba aquí realmente.
Queda muuucho más.
Eso sí, te lo cuento la semana que viene.
Hasta entonces,
Borja.
