El nuevo método basado en datos elimina los cálculos redundantes, puede agilizar procesos como trenes de programación
Crédito: Dominio público de Pixabay/CC0
Cuando algunos trenes de cercanías llegan al final de la línea, deben viajar a una plataforma de conmutación para ser giradas para que puedan salir de la estación más tarde, a menudo desde una plataforma diferente a la que llegaron.
Los ingenieros usan programas de software llamados solucionadores algorítmicos para planificar estos movimientos, pero en una estación con miles de llegadas y salidas semanales, el problema se vuelve demasiado complejo para que un solucionador tradicional se desentraques de una vez.
Utilizando el aprendizaje automático, los investigadores del MIT han desarrollado un sistema de planificación mejorado que reduce el tiempo de resolución hasta un 50% y produce una solución que cumpla mejor con el objetivo de un usuario, como las salidas de trenes a tiempo. El nuevo método también podría usarse para resolver eficientemente otros problemas logísticos complejos, como programar el personal del hospital, asignar equipos de aerolíneas o asignar tareas a máquinas de fábrica.
Los ingenieros a menudo dividen este tipo de problemas en una secuencia de subproblemas superpuestos que se pueden resolver en una cantidad factible de tiempo. Pero las superposiciones hacen que muchas decisiones sean recomputadas innecesariamente, por lo que se necesita el solucionador mucho más tiempo para alcanzar una solución óptima.
El nuevo enfoque de inteligencia artificial mejorado aprende qué partes de cada subproblema deben permanecer sin cambios, congelando esas variables para evitar cálculos redundantes. Luego, un solucionador algorítmico tradicional aborda las variables restantes.
“Often, a dedicated team could spend months or even years designing an algorithm to solve just one of these combinatorial problems. Modern deep learning gives us an opportunity to use new advances to help streamline the design of these algorithms. We can take what we know works well, and use AI to accelerate it,” says Cathy Wu, the Thomas D. and Virginia W. Cabot Career Development Associate Professor in Civil and Environmental Engineering (CEE) and the Institute for Datos, sistemas y sociedad (IDS) en el MIT, y miembro del Laboratorio para Sistemas de Información y Decisión (LIDS).
Se une al periódico por el autor principal Sirui Li, un estudiante graduado de IDSS; Wenbin Ouyang, un estudiante graduado de CEE; y Yining MA, A Postdocs Postdocs. La investigación se presentará en la Conferencia Internacional sobre Representaciones de Aprendizaje.
Eliminando la redundancia
Una motivación para esta investigación es un problema práctico identificado por un estudiante de maestría, Devin Camille Wilkins, en el curso de transporte de nivel de entrada de Wu. El estudiante quería aplicar el aprendizaje de refuerzo a un verdadero problema de disputa de trenes en la estación Norte de Boston: la organización de tránsito debe asignar muchos trenes a un número limitado de plataformas donde se pueden dar la vuelta antes de su llegada a la estación.
Este resulta ser un problema de programación combinatoria muy complejo: el tipo exacto de problema en el que el laboratorio de Wu ha pasado en los últimos años trabajando.
Cuando se enfrenta a un problema a largo plazo que implica asignar un conjunto limitado de recursos, como tareas de fábrica, a un grupo de máquinas, los planificadores a menudo enmarcan el problema como una programación flexible de la tienda de empleo.
En la programación flexible de la tienda de empleo, cada tarea necesita una cantidad diferente de tiempo para completar, pero las tareas se pueden asignar a cualquier máquina. Al mismo tiempo, cada tarea se compone de operaciones que deben realizarse en el orden correcto.
Tales problemas se vuelven demasiado grandes y difíciles de manejar para los solucionadores tradicionales, por lo que los usuarios pueden emplear optimización de horizonte rodante (Rho) para dividir el problema en fragmentos manejables que se pueden resolver más rápido.
Con Rho, un usuario asigna algunas tareas iniciales a las máquinas en un horizonte de planificación fijo, tal vez una ventana de tiempo de cuatro horas. Luego, ejecutan la primera tarea en esa secuencia y cambian el horizonte de planificación de cuatro horas hacia adelante para agregar la siguiente tarea, repitiendo el proceso hasta que se resuelva todo el problema y se cree el cronograma final de tareas de las tareas.
Un horizonte de planificación debe ser más largo que la duración de cualquier tarea, ya que la solución será mejor si el algoritmo también considera tareas que surgirán.
Pero cuando el horizonte de planificación avanza, esto crea cierta superposición con las operaciones en el horizonte de planificación anterior. El algoritmo ya ha presentado soluciones preliminares a estas operaciones superpuestas.
“Tal vez estas soluciones preliminares son buenas y no necesitan calcularse nuevamente, pero tal vez no son buenas. Aquí es donde entra el aprendizaje automático”, explica Wu.
Para su técnica, que llaman optimización de horizonte de rodillo guiado por el aprendizaje (L-RHO), los investigadores enseñan un modelo de aprendizaje automático para predecir qué operaciones o variables deben ser recomputadas cuando el horizonte de planificación se lanza hacia adelante.
L-RHO requiere datos para capacitar al modelo, por lo que los investigadores resuelven un conjunto de subproblemas utilizando un solucionador algorítmico clásico. Tomaron las mejores soluciones, las que tienen la mayor cantidad de operaciones que no necesitan ser recomputadas, y las usaron como datos de capacitación.
Una vez entrenado, el modelo de aprendizaje automático recibe un nuevo subproblema que no ha visto antes y predice qué operaciones no deben ser recomputadas. Las operaciones restantes se devuelven al solucionador algorítmico, que ejecuta la tarea, recomputa estas operaciones y mueve el horizonte de planificación hacia adelante. Entonces el bucle comienza de nuevo.
“Si, en retrospectiva, no necesitamos reoptimizarlas, entonces podemos eliminar esas variables del problema. Debido a que estos problemas crecen exponencialmente en tamaño, puede ser bastante ventajoso si podemos dejar caer algunas de esas variables”, agrega.
Un enfoque adaptable y escalable
Para probar su enfoque, los investigadores compararon L-RHO con varios solucionadores algorítmicos base, solucionadores especializados y enfoques que solo usan el aprendizaje automático. Los superó a todos, reduciendo el tiempo de resolución en un 54% y mejorando la calidad de la solución hasta en un 21%.
Además, su método continuó superando a todas las líneas de base cuando lo probaron en variantes más complejas del problema, como cuando las máquinas de fábrica se descomponen o cuando hay una congestión adicional del tren. Incluso superó a las líneas de base adicionales que los investigadores crearon para desafiar su solucionador.
“Nuestro enfoque se puede aplicar sin modificar a todas estas diferentes variantes, que es realmente lo que nos propusimos hacer con esta línea de investigación”, dice ella.
L-Rho también puede adaptarse si los objetivos cambian, generando automáticamente un nuevo algoritmo para resolver el problema; todo lo que necesita es un nuevo conjunto de datos de capacitación.
En el futuro, los investigadores quieren comprender mejor la lógica detrás de la decisión de su modelo de congelar algunas variables, pero no otras. También quieren integrar su enfoque en otros tipos de problemas de optimización complejos como la gestión de inventario o el enrutamiento de vehículos.
Más información: Sirui Li et al, Optimización de horizonte de rodillo guiado por el aprendizaje para la programación de compras de empleo de horizonte largo (2025)
Proporcionado por el Instituto de Tecnología de Massachusetts
Esta historia se vuelve a publicar por cortesía de MIT News (web.mit.edu/NewsOffice/), un sitio popular que cubre noticias sobre la investigación del MIT, la innovación y la enseñanza.
Cita: el nuevo método basado en datos elimina los cálculos redundantes, puede agilizar procesos como trenes de programación (2025, 16 de abril) Recuperado el 16 de abril de 2025 de https://techxplore.com/news/2025-04-driven-method-redundant.html
Este documento está sujeto a derechos de autor. Además de cualquier trato justo con el propósito de estudio o investigación privada, no se puede reproducir ninguna parte sin el permiso por escrito. El contenido se proporciona solo para fines de información.
