Optimización matemática para buques de carga
(research.google)- El equipo de Operations Research de Google Research lanzó la Shipping Network Design API, que optimiza en conjunto el diseño de red, la programación y las rutas de contenedores de buques portacontenedores regulares
- Este problema se vuelve complejo porque hay que decidir simultáneamente el orden en que los buques visitan los puertos, sus horarios de llegada y salida, y las rutas origen-destino de los contenedores, llegando a una escala de 500 buques y 200 puertos en WorldLarge
- Los enfoques iniciales de generación doble de columnas y CP-SAT encontraron soluciones óptimas demostrables en escalas pequeñas y medianas, pero para problemas a gran escala hizo falta una heurística que combina búsqueda de vecindarios grandes y búsqueda de vecindarios variables
- En el benchmark LINERLIB, el volumen de contenedores procesados en WorldSmall, EuropeAsia, Pacific y Mediterranean aumentó 35%, 14%, 35% y 32%, respectivamente, y la cantidad de buques usados disminuyó 7%, 15%, 4% y 23%
- Google considera este método como el primero capaz de resolver problemas de diseño de red y programación a escala WorldLarge, y ofrecerá la Shipping Network Design API como parte de las futuras Operations Research APIs
El problema de optimizar simultáneamente redes de transporte marítimo de contenedores
- El 90% de los bienes del mundo se mueve por mar, y un gran buque de carga puede medir 0.25 millas de largo, pesar 250 mil toneladas y transportar 12 mil contenedores, con carga por un valor total de 1,000 millones de dólares
- A diferencia de aviones, trenes y camiones, los buques de carga operan casi continuamente y se mueven sobre rutas circulares en el mar
- Las rutas y horarios ineficientes provocan permanencia de contenedores en puertos, espera de buques en el mar y retrasos en los flujos logísticos, y también afectan los precios de los productos
- La Shipping Network Design API de Google implementa una nueva solución para este problema
- Es más rápida y escala mejor que los intentos conocidos anteriormente
- Puede duplicar las ganancias de las navieras de contenedores, transportar 13% más contenedores y operar con 15% menos buques
Las tres decisiones que debe resolver LSNDSP en conjunto
- El Liner Shipping Network Design and Scheduling Problem, o LSNDSP, aborda simultáneamente tres decisiones
- Diseño de red: decidir en qué orden los buques visitarán los puertos
- Programación de red: definir cuándo llegan y cuándo parten los buques
- Enrutamiento de contenedores: elegir qué trayecto seguirá un contenedor desde su origen hasta su destino
- Las navieras de contenedores deben resolver los tres problemas, pero normalmente los tratan de forma secuencial
- Resolver los tres problemas al mismo tiempo aumenta la dificultad, pero también incrementa la posibilidad de encontrar una mejor solución
- El resultado del diseño de red se traduce en líneas de servicio seguidas por un pequeño número de buques
- Por ejemplo, puede ser una ruta desde Asia Oriental hacia el sur de Europa pasando por el Canal de Suez
- Las líneas de servicio se publican junto con las fechas para que los cargadores sepan cuándo y dónde deben preparar los contenedores
Restricciones creadas por atraques, transbordos y retrasos en puertos
- Los portacontenedores no pueden atracar en un puerto cuando quieran; deben usar slots de atraque definidos de antemano
- Después de acercarse al puerto, un buque puede echar anclas y esperar en un fondeadero hasta que sea posible atracar
- Si el puerto está congestionado, puede permanecer en el fondeadero durante horas o días
- Una programación de red precisa no solo incluye en qué día se atraca, sino también a qué hora
- Es posible aumentar la velocidad para llegar a una hora específica
- También es posible reducir la velocidad para ahorrar combustible
- Al atracar en un puerto, las grúas descargan contenedores y vuelven a cargar en el buque los contenedores que irán en el siguiente viaje
- Si el horario se retrasa, puede ocurrir un cut-and-run, en el que el buque sale del puerto antes de cargar todos los contenedores programados
- Los contenedores restantes serán cargados por un buque posterior
- Cuando un contenedor pasa tiempo en un puerto intermedio mientras viaja de su origen a su destino, se lo llama transbordo
- El transbordo aumenta aún más la cantidad de soluciones posibles para LSNDSP
- Es una de las varias restricciones que actúan sobre la generación de rutas de contenedores
Método de optimización: de generación de columnas a búsqueda de vecindarios
- Todo problema de optimización está compuesto por variables, restricciones sobre esas variables y una función objetivo que se busca minimizar o maximizar
- Ej.: los buques y los puertos son variables
- Ej.: la cantidad de contenedores que puede llevar un buque es una restricción
- Ej.: maximizar la cantidad de contenedores transportados es una función objetivo
- Las variables y restricciones suelen representarse como matrices, donde las columnas son variables y las filas son restricciones
- Como técnica general para descomponer problemas a gran escala se usa la generación de columnas
- Al principio solo se considera una parte de las variables
- Luego se generan nuevas variables, es decir, nuevas columnas, para aproximar mejor el problema original
- Google desarrolló una biblioteca de software que analiza el problema y predice qué columnas conviene generar
- Esta biblioteca se publicará como open source mediante MathOpt, un framework de programación matemática
Límites de los dos enfoques básicos
- La generación doble de columnas considera el diseño de red y el enrutamiento de contenedores como dos problemas acoplados
- Cada problema consiste en un problema principal de selección de las mejores opciones y un problema auxiliar de generación para encontrar opciones razonables
- Se aplica un algoritmo de camino más corto a cada par de problemas para generar opciones razonables
- Luego se usa el solver de programación lineal Glop para elegir las mejores opciones de cada problema
- La generación de columnas se aplica simultáneamente a ambos problemas, y los resultados intermedios de un problema influyen en el avance del otro
- Pudo encontrar soluciones óptimas demostrables, pero solo escaló bien hasta problemas de tamaño mediano
- También se probó una implementación basada en CP-SAT
- Usa CP-SAT, el solver de programación con restricciones de Google
- Funcionó bien hasta redes de tamaño mediano, pero no escaló al tamaño de los problemas de transporte marítimo global
- Ambos enfoques encontraron soluciones óptimas demostrables en problemas pequeños y medianos, pero carecieron de escalabilidad para gran escala
Heurísticas para escalar a gran tamaño
- Para aumentar la escalabilidad, se aplicaron dos variantes de búsqueda local que examinan vecindarios alrededor de una solución existente para encontrar oportunidades de mejora
- La búsqueda de vecindarios grandes fija una parte de la solución y luego aplica los métodos anteriores
- Ej.: fija una condición como “este buque visita Los Angeles cada dos martes”
- Reduce el espacio de búsqueda y mejora la escalabilidad
- La búsqueda de vecindarios variables explora vecindarios tanto de la red como de la programación
- Paraleliza la búsqueda y la distribuye entre varias máquinas para evaluar muchos vecindarios al mismo tiempo
- Permite limitar el espacio de búsqueda incorporando conocimiento de Operations Research y de la industria naviera
- Ambos enfoques usan una estrategia incremental: bloquean parte de una solución prometedora y, partiendo de una solución ya buena, la mejoran hacia una solución mejor
- Los intentos anteriores no consideraban los tiempos de transporte porque eso vuelve el problema mucho más difícil de resolver, pero Google confirmó que incluir el tiempo de transporte mejora mucho la calidad de la solución
Resultados en el benchmark LINERLIB
- La evaluación de rendimiento usa LINERLIB, un benchmark industrial para problemas de diseño de redes de transporte marítimo
- El benchmark incluye flotas, puertos y demanda de contenedores de escenarios de transporte marítimo de contenedores
- Los escenarios de prueba incluyen WorldSmall, EuropeAsia y WorldLarge
- WorldLarge incluye 500 buques, 200 puertos y alrededor de 140 mil contenedores
- El objetivo de la optimización no es simplemente maximizar la cantidad de contenedores ni minimizar la cantidad de buques
- Si solo se maximiza la cantidad de contenedores, pueden incorporarse más buques y aumentar los costos operativos
- Si solo se minimiza la cantidad de buques, pueden aparecer tiempos de entrega irrealmente largos, como transportar todos los contenedores con un solo buque
- LINERLIB equilibra el problema con una ganancia estimada: los ingresos por entregas a tiempo menos los costos de navegación y de manejo de contenedores en puerto
- En comparación con la línea base, el método de Google enruta más contenedores con menos buques
- WorldSmall: volumen de contenedores procesados 35% mayor, cantidad de buques 7% menor
- EuropeAsia: volumen de contenedores procesados 14% mayor, cantidad de buques 15% menor
- Pacific: volumen de contenedores procesados 35% mayor, cantidad de buques 4% menor
- Mediterranean: volumen de contenedores procesados 32% mayor, cantidad de buques 23% menor
- Según los supuestos económicos de LINERLIB, el margen de ganancia esperado también mejora considerablemente
API y publicaciones posteriores
- Google considera este método como el primero capaz de resolver problemas de diseño de red y programación a escala WorldLarge
- Los resultados pueden consultarse con más detalle en la página de benchmarks de LSNDSP
- La Shipping Network Design API es una de las futuras Operations Research APIs
1 comentarios
Comentarios en Hacker News
Estoy del lado de terminales en esta industria, y aunque es interesante, se ve muy académico
Me pregunto si realmente lo hicieron en colaboración con una naviera. Del lado de terminales ahora mismo estamos metidos a fondo en la optimización de contenedores y de verdad es casi una pesadilla. Incluso entre terminales de la misma empresa, la forma de operar varía muchísimo, y hasta la terminología suele cambiar dentro de la propia compañía. Aunque optimices para una terminal, en la siguiente tienes que rehacer el 80%, así que es muy difícil escalar cualquier solución
Por ejemplo, los ingenieros alemanes se oponían a bloquear funciones del vehículo antes de la producción en masa, porque entonces no podían usarlo para fines recreativos. En el sector salud, los costos de horas extra eran de decenas de millones, así que parecía fácil mejorar la programación, pero había muchas restricciones sindicales y además faltaba oferta de contratación. Me pregunto qué tan realista es la solución de Google. ¿Incluye restricciones como misiles hutíes? Por experiencia, muchas veces una solución que se ajusta fácilmente a cambios inesperados vale más que una solución óptima demostrable
Coincido en que la optimización objetiva suele ser mayormente académica. Siempre hay razones por las que es difícil o imposible seguir tal cual la versión más eficiente de un proceso estandarizado. A veces son razones “tontas” generadas por personas, y muy a menudo son razones racionales que reflejan externalidades como el clima, tiempos muertos, interrupciones de la cadena de suministro, estacionalidad en las señales de demanda y lo accidentado de los pronósticos. Aun así, creo que casi siempre es mejor partir del proceso más eficiente y luego añadir manejo de excepciones, en vez de construir un proceso estándar alrededor de excepciones conocidas. Si dejas que las excepciones se conviertan en la regla, siempre vas a operar con menos eficiencia que el óptimo
Esta industria es difícil, y los sindicatos portuarios históricamente han sido fuertes, así que el panorama político es todavía más complicado. Los problemas que parecen poder separarse y etiquetarse limpiamente en realidad están entrelazados, y esperar que un algoritmo los resuelva “mágicamente” por el usuario casi siempre termina mal. Esta industria se traga fácilmente a los cracks del software que llegan pensando “¿no es solo un problema del viajante / un resolvedor de restricciones / correr el enfoque que quieras y ya?”. Claro que hacen falta personas muy inteligentes, pero hay que empezar con humildad y hablar primero con los usuarios reales. No parece que tengas información de contacto en tu perfil, pero si te interesa intercambiar ideas con otras empresas del sector, me gustaría que me escribieras. Estamos haciendo cosas interesantes, especialmente en el segmento de terminales de menos de 1 millón de TEU al año con alta proporción de transporte intermodal
Estoy leyendo The Box, sobre la historia temprana de la contenedorización, y está buenísimo
Se lo recomiendo muchísimo a cualquiera que busque una lectura amena que mezcle ingeniería, diseño, negocios e historia. También hace que mis pequeños problemas de programación parezcan ridículos
Seguro esto va a generar mucho desacuerdo, pero sinceramente creo que el impacto del contenedor marítimo de 20 pies en el mundo fue mayor que el impacto que probablemente vayan a lograr los modelos de lenguaje grandes. Primero lean ese libro y luego díganme por qué estoy equivocado. Claro que no lo estoy
Parece que en flotas muy grandes la optimización de contenedores seguía siendo un problema no resuelto. No lo sabía
Si la investigación de operaciones de Google mejoró la utilización en un 10–20% frente a las soluciones existentes, eso sería impresionante
https://en.wikipedia.org/wiki/Packing_problems
Tengo mucha curiosidad por saber si hay alguien usando de verdad este endpoint de API que publicaron: https://developers.google.com/optimization/service/shipping/...
Aun así, está bastante bueno
Un ejemplo representativo es la Route Optimization API, que el equipo empresarial de investigación de operaciones publicó de esta forma, y luego, con insumos de algunos clientes alfa, se construyó encima la solución Fleet Engine. Hasta que las APIs de investigación de operaciones se expongan a través de Google Cloud, creo que no conviene usarlas para nada que no sea académico, porque no tienen SLA ni garantías de confiabilidad. Ese es mi granito de arena
https://developers.google.com/maps/documentation/transportat...
[1]: https://killedbygoogle.com/
Si no se considera la demora por espera del buque, no estoy seguro de que realmente valga la pena intentarlo
https://developers.google.com/optimization/service/reference...
Omega Tau Podcast hizo un episodio[0] muy bueno sobre el transporte en contenedores, y también cubre la optimización de estiba de contenedores y la planificación de rutas. Súper recomendado
[0]: https://omegataupodcast.net/146-container-shipping/
La frase “a diferencia de los aviones, los buques de carga operan casi continuamente” da un poco para debatir
Los buques de carga sí reciben bastante mantenimiento mientras navegan, pero fuera de eso creo que la diferencia es mucho menor. En puerto pasan varios días descargando y cargando para completar la rotación, y a veces esperan horas o días por un atraque. Si ves el caso del Delta A350, quitando las 3 horas de rotación en el aeropuerto, en la práctica se mueve las 24 horas del día: https://www.flightradar24.com/data/aircraft/n513dz
Me recuerda a dueños o gerentes de lugares como restaurantes de barrio que dicen que armar los turnos del personal de medio tiempo les da muchísimos dolores de cabeza, y hasta dicen que por eso les pagan bien
Siempre pensé que eso se podría resolver con un algoritmo
Tal vez puedas cubrir la noche en que la mitad del personal se fue a ver a Taylor Swift, pero si llamas a esa gente para cubrir, entonces alguien más tendrá que cubrir su siguiente turno, y si eso sigue encadenándose terminas con un horario completamente distinto formado por personas que nunca habían trabajado juntas. Se puede corregir agregando más restricciones, pero solo escribirlas todas y priorizarlas ya no es nada simple. Las personas no son bloques de Lego
Tengo formación en investigación de operaciones, así que siempre me ha parecido raro. Los problemas parecen lo bastante simples como para modelarlos y resolverlos con un solver general, y parece que aportarían mucho valor incluso sin técnicas avanzadas. El problema es que la investigación de operaciones, en general, es poco accesible. La mayoría de los solvers bien respaldados te obligan a definir el problema en un paradigma matemático, y una “persona común” se siente abrumada apenas lo ve. También hay soluciones listas para usar para problemas comunes de programación de turnos, pero si no empezaste con ellas desde el principio, cada negocio tiene variantes propias que hacen difícil adoptarlas por completo. O no soportan esa variante, o no sabes cómo encajarla dentro de la herramienta. Aunque exista la intención de resolver mejor los horarios, los cursos que uno encuentra normalmente asumen bastante conocimiento previo de programación o matemáticas. Creo que debería ser posible crear un entorno de modelado no-code para problemas de programación de turnos, que también pueda usar una “persona común” para la que Excel ya no alcanza, pero que no puede contratar a un especialista en investigación de operaciones
Casi todos los grandes sistemas de RR. HH./gestión de personal incluyen opciones relacionadas. Por ejemplo, están https://www.workday.com/en-us/products/workforce-management/... y https://www.oracle.com/human-capital-management/workforce-ma..., además de muchos proveedores especializados. Aun así, como dijo otra persona, estos sistemas también han sido polémicos. En parte porque algunos se usan de maneras que no consideran necesidades humanas normales. Por ejemplo, asignan turnos consecutivos, cambian horarios con muy poco aviso, o no pueden tomar en cuenta circunstancias reales como el cuidado de hijos, que un gerente humano sí podría considerar
Pero el problema es que cada negocio tiene restricciones distintas. Por ejemplo, que en cada turno haya al menos una persona capacitada en primeros auxilios, que Alice y Bob no se lleven bien, que no se pueda trabajar los sábados dos semanas seguidas, que los turnos roten cada dos semanas, o que deba haber al menos 12 horas entre turnos. Una herramienta lo bastante flexible como para que la usen muchas organizaciones probablemente terminaría siendo demasiado compleja y difícil de usar
Sigo teniendo curiosidad por el plan de estiba de este tipo de buques.
Parece ser un problema que habría que resolver de forma aproximada en la siguiente etapa después de planificar la ruta de cada contenedor. El plan de estiba aparece después y tiene restricciones mucho más dependientes de la situación que una perspectiva a nivel de sistema global. Si se ve de forma optimista y a grandes rasgos, las grúas de muelle hacen entre 30 y 50 movimientos por hora; se asignan 2 o 4 por buque, y en muchos casos hasta 6, y además hay que ir descargando por capas, como quitando una cáscara. Un Ultra Large Container Vessel es de 14,501 TEU o más, un New Panamax de 10,000 a 14,500 TEU, un Post-Panamax de 5,101 a 10,000 TEU, y un Panamax de 3,001 a 5,100 TEU. Si 24,000 TEU son unas 12 mil unidades de contenedores de 40 pies, entonces 4 grúas × 50 por hora por grúa × 24 horas al día = alrededor de 1,200 contenedores por día.
https://en.wikipedia.org/wiki/Stowage_plan_for_container_shi...
En el plan de estiba del buque, además de la disponibilidad en el puerto, también hay criterios sobre peso, equilibrio, energía y tolerancias según el valor de la carga. Como el texto mencionaba la salida anticipada del puerto, me dio curiosidad este tipo de sobrecarga y traté de hacer un cálculo aproximado.
Desde la perspectiva de alguien que realmente trabaja en este campo, hay muchas formas de simplificarse el trabajo. Lo básico es planificar por bloques para cada tapa de escotilla y tratar los contenedores agrupándolos por destino, tamaño y peso, asumiendo que son intercambiables. Luego, antes de iniciar la operación, se envía el plan del buque a la terminal, y como la terminal también conoce la ubicación de los contenedores dentro del patio, puede hacer optimización y reubicación. Si decides ignorar los detalles de cada contenedor y concentrarte solo en los grupos, el plan de estiba se vuelve mucho más sencillo. El resultado es muy parecido con mucho menos trabajo, y la terminal también gana más flexibilidad para optimizar la operación.