Imagen. / MIT

¿Está esperando la entrega de un paquete de vacaciones? Hay un problema matemático complicado que debe resolverse antes de que el camión de reparto llegue a su puerta, y los investigadores del MIT tienen una estrategia que podría acelerar la solución.

El enfoque se aplica a los problemas de rutas de los vehículos, como la entrega de última milla, donde el objetivo es entregar mercancías desde un depósito central a varias ciudades mientras se mantienen bajos los costos de viaje. Si bien existen algoritmos diseñados para resolver este problema para unos pocos cientos de ciudades, estas soluciones se vuelven demasiado lentas cuando se aplican a un conjunto más grande de ciudades.

Para remediar esto, Cathy Wu, profesora asistente de desarrollo profesional de Gilbert W. Winslow en Ingeniería Civil y Ambiental y el Instituto de Datos, Sistemas y Sociedad, y sus estudiantes han ideado una estrategia de aprendizaje automático que acelera algunas de las más sólidas solucionadores algorítmicos de 10 a 100 veces.

Los algoritmos de resolución funcionan dividiendo el problema de la entrega en subproblemas más pequeños para resolver, digamos, 200 subproblemas para enrutar vehículos entre 2.000 ciudades. Wu y sus colegas amplían este proceso con un nuevo algoritmo de aprendizaje automático que identifica los subproblemas más útiles para resolver, en lugar de resolver todos los subproblemas, para aumentar la calidad de la solución mientras utilizan órdenes de magnitud menos computacionales.

Su enfoque, que ellos llaman "aprender a delegar", se puede utilizar en una variedad de solucionadores y una variedad de problemas similares, incluida la programación y la búsqueda de rutas para los robots de almacén, dicen los investigadores.

El trabajo amplía los límites para resolver rápidamente problemas de rutas de vehículos a gran escala, dice Marc Kuo, fundador y director ejecutivo de Routific , una plataforma de logística inteligente para optimizar las rutas de entrega. Algunos de los avances algorítmicos recientes de Routific se inspiraron en el trabajo de Wu, señala.

“La mayor parte del cuerpo académico de investigación tiende a enfocarse en algoritmos especializados para pequeños problemas, tratando de encontrar mejores soluciones a costa de los tiempos de procesamiento. Pero en el mundo real, a las empresas no les importa encontrar mejores soluciones, especialmente si tardan demasiado en computar ”, explica Kuo. “En el mundo de la logística de última milla, el tiempo es dinero y no puede hacer que todas las operaciones de su almacén esperen a que un algoritmo lento devuelva las rutas. Un algoritmo debe ser muy rápido para que sea práctico ".

Wu, la estudiante de doctorado en sistemas sociales y de ingeniería Sirui Li y la estudiante de doctorado en ingeniería eléctrica y ciencias de la computación Zhongxia Yan presentaron su investigación esta semana en la conferencia NeurIPS 2021.

Seleccionar buenos problemas

Los problemas de generación de rutas para vehículos son una clase de problemas combinatorios, que implican el uso de algoritmos heurísticos para encontrar "soluciones suficientemente buenas" al problema. Por lo general, no es posible encontrar la "mejor" respuesta a estos problemas, porque la cantidad de posibles soluciones es demasiado grande.

"El nombre del juego para este tipo de problemas es diseñar algoritmos eficientes ... que sean óptimos dentro de algún factor", explica Wu. “Pero el objetivo no es encontrar soluciones óptimas. Eso es muy difícil. Más bien, queremos encontrar las mejores soluciones posibles. Incluso una mejora del 0,5% en las soluciones puede traducirse en un enorme aumento de ingresos para una empresa ".

Durante las últimas décadas, los investigadores han desarrollado una variedad de heurísticas para producir soluciones rápidas a problemas combinatorios. Por lo general, hacen esto comenzando con una solución inicial pobre pero válida y luego mejorando gradualmente la solución, probando pequeños ajustes para mejorar la ruta entre ciudades cercanas, por ejemplo. Sin embargo, para un problema grande como un desafío de enrutamiento de la ciudad de más de 2,000, este enfoque simplemente lleva demasiado tiempo.

Más recientemente, se han desarrollado métodos de aprendizaje automático para resolver el problema, pero aunque son más rápidos, tienden a ser más imprecisos, incluso a la escala de unas pocas docenas de ciudades. Wu y sus colegas decidieron ver si existía una forma beneficiosa de combinar los dos métodos para encontrar soluciones rápidas pero de alta calidad.

"Para nosotros, aquí es donde entra en juego el aprendizaje automático", dice Wu. "¿Podemos predecir cuál de estos subproblemas, que si los resolviéramos, conduciría a una mayor mejora en la solución, ahorrando tiempo y gastos de computación?"

Tradicionalmente, una heurística de problemas de generación de rutas de vehículos a gran escala puede elegir los subproblemas a resolver en qué orden, ya sea al azar o aplicando otra heurística cuidadosamente diseñada. En este caso, los investigadores del MIT ejecutaron conjuntos de subproblemas a través de una red neuronal que crearon para encontrar automáticamente los subproblemas que, una vez resueltos, conducirían a la mayor ganancia en la calidad de las soluciones. Este proceso aceleró el proceso de selección de subproblemas de 1,5 a 2 veces, encontraron Wu y sus colegas.

“No sabemos por qué estos subproblemas son mejores que otros subproblemas”, señala Wu. “En realidad, es una línea interesante de trabajo futuro. Si tuviéramos algunos conocimientos aquí, estos podrían llevarnos a diseñar algoritmos aún mejores ".

Sorprendente aceleración

Wu y sus colegas se sorprendieron de lo bien que funcionó el enfoque. En el aprendizaje automático, se aplica la idea de entrada y salida de basura, es decir, la calidad de un enfoque de aprendizaje automático depende en gran medida de la calidad de los datos. Un problema combinatorio es tan difícil que incluso sus subproblemas no pueden resolverse de manera óptima. Una red neuronal entrenada en las soluciones de subproblemas de "calidad media" disponibles como datos de entrada "normalmente daría resultados de calidad media", dice Wu. En este caso, sin embargo, los investigadores pudieron aprovechar las soluciones de calidad media para lograr resultados de alta calidad, significativamente más rápido que los métodos de última generación.

Para el enrutamiento de vehículos y problemas similares, los usuarios a menudo deben diseñar algoritmos muy especializados para resolver su problema específico. Algunas de estas heurísticas se han desarrollado durante décadas.

El método de aprender a delegar ofrece una forma automática de acelerar estas heurísticas para problemas grandes, sin importar cuál sea la heurística o, potencialmente, cuál sea el problema.

Dado que el método puede funcionar con una variedad de solucionadores, puede ser útil para una variedad de problemas de asignación de recursos, dice Wu. "Podemos desbloquear nuevas aplicaciones que ahora serán posibles porque el costo de resolver el problema es de 10 a 100 veces menor".

La investigación fue apoyada por MIT Indonesia Seed Fund, el Departamento de Transporte de EE. UU. Dwight David Eisenhower Transportation Fellowship Program y el MIT-IBM Watson AI Lab.

Autor

MIT

Promover la investigación, las innovaciones, la enseñanza y los eventos y las personas de interés periodístico del MIT a la comunidad del campus, los medios de comunicación y el público en general, Comunicar anuncios del Instituto, Publicar noticias de la comunidad para profesores, estudiantes, personal y ex alumnos del MIT. Proporcionar servicios de medios a los miembros de la comunidad, incluido el asesoramiento sobre cómo trabajar con periodistas, Responder a consultas de los medios y solicitudes de entrevistas...