En la Facultad de Ciencias Exactas, Ingeniería y Agrimensura de la Universidad Nacional de Rosario un grupo de investigadores explora desde la matemática y la computación la “optimización combinatoria”, un área que se encarga de la solución de problemas a partir de tener en cuenta todas las combinaciones posibles. Es que, cuando se trata de tomar decisiones, hasta las computadoras más rápidas del mundo colapsan.
Graciela Nasini es matemática y forma parte de un proyecto de investigación que, a partir de esta incipiente rama, trabaja desde el año pasado en la optimización de la asignación de viajes a conductores de una empresa de transporte de pasajeros de media distancia. “Empecé con la optimización combinatoria después de enojarme con la matemática porque no me gustaban las cosas que se podían hacer con lo que había aprendido. Buscando encontré esta línea donde las aplicaciones están mucho más cerca”, explica la docente e investigadora.
Nasini argumenta que lo que hacen los matemáticos es tratar de traducir un problema concreto a un problema matemático: “Los problemas de optimización combinatoria están generalmente asociados a la toma de decisiones. El ejemplo más conocido es el «problema del viajante de comercio» que todos los meses tiene que visitar distintas ciudades y volver a su lugar de origen. Dependiendo del orden en que recorra estas ciudades tendrá diferentes costos, asociados a los kilómetros recorridos. El tema es que cuando tenés muchos lugares a visitar, las posibles combinaciones aumentan. Con veinte ciudades, el total de posibles órdenes de recorrido es un número de diecinueve dígitos, esto es, millones y millones de posibles combinaciones».
Se podría pensar que este tipo de cálculos no sería complejo para el mundo de la informática, pero lo cierto es que, según la docente, las computadoras más rápidas que existen en este momento tardarían más de 15 mil años en hacer todas las combinaciones, calcular los costos y elegir la que recorra menos kilómetros. «En la combinatoria, cuando tenés poquitos elementos los problemas son sencillos pero, cuando los números son grandes, todas múltiples combinaciones crecen enormemente y son inmanejables. Entonces hay que ponerle un poco de inteligencia y no ir a lo elemental. Ahí entramos los matemáticos», sostiene Nasini.
Lo que hacen los matemáticos y cientistas de la computación es modelar cada posible decisión con una variable, que va a estar en cero o en uno, dependiendo si se toma o no esa decisión. En base a esas variables, todas las posibles combinaciones se traducen en restricciones matemáticas. Los modelos más habituales para los problemas de optimización combinatoria son los que se denominan “Modelos de programación lineal entera”.
En concreto, los investigadores de la UNR trabajaron con una empresa de transporte urbano de Buenos Aires en la optimización de la asignación de viajes a los conductores: “La empresa presta el servicio de dos líneas con diferentes ramales de distintas duraciones. Originalmente, asignaban los viajes de manera tal de que cada conductor realizara viajes de una sola de las líneas, lo cual resultaba en jornadas de trabajo muy desparejas. A simple vista se podía concluir que esta situación era mejorable si permitían combinar viajes de las dos líneas en la jornada de un conductor».
Sin embargo, cuando empezaron a combinar los dos ramales, se dieron cuenta de que el número de combinaciones era enorme y no se podían hacer a ojo. Lo que explica Nasini es que por lo general no hay una tradición tanto desde el ámbito público como privado de recurrir a la universidad a la hora de buscar soluciones a los problemas. “En este caso, y como suele ocurrir, la empresa compró un paquete informático muy bueno desarrollado en Alemania y empezaron a diseñar las jornadas con el mismo. El tema de comprar cosas afuera es que hay toda una serie de restricciones puntuales de la realidad específica del problema que no es posible decirle a esta herramienta y no prevé acuerdos específicos que, en este caso, hicieron los conductores con la propia empresa”, cuenta Nasini.
Entonces, a partir de las planillas que resultan de este programa, una de las empleadas de la empresa y miembro del equipo de investigación se dio cuenta que de que podían hacerse pequeños cambios mejorando el sistema de otorgamiento de viajes. «A partir de esto, empezamos a trabajar en un modelo que permitiera obtener las asignaciones de viajes a conductores respetando todas las condiciones específicas y minimizando la cantidad de horas extras. Cuando trabajamos con alrededor de veinte viajes, el modelo puede ser resuelto por las herramientas informáticas existentes en menos de un segundo de corrida. De esta manera, el modelo explora todos los posibles intercambios de viajes que actualmente se realizan a mano, brindando soluciones que mejoran significativamente las diseñadas por la empresa», manifiesta Nasini.
En estos momentos, el equipo se encuentra trabajando en que la herramienta pueda ser utilizada por cualquiera, y no sólo por el programador. “Hoy sólo sirve para esa empresa, pero este tipo de metodologías podrían aplicarse en el mejoramiento del transporte urbano de Rosario, por ejemplo”.
La universidad como referente en la solución de problemas
Para Nasini en la Argentina aún falta mucho para que los usuarios vean a la matemática como una disciplina que puede ayudar a resolver problemas concretos: “Hay muchísimas situaciones de la vida cotidiana que se tratan de tomar decisiones y para esto la optimización combinatoria es muy útil. Lo que pasa que es no hay una tradición por parte del Estado o las empresas de tomar a la universidad como referente de opinión. Esta área puede optimizar los procesos de producción, la organización de torneos y eventos deportivos, la localización de servicios, el diseño de redes, entre muchas otras aplicaciones”.
El proyecto de investigación “Algoritmos de optimización para la asignación de viajes a conductores en empresas de transporte de pasajeros” está integrado por Graciela Nasini y Daniel Severín, Eugenia Alvarado y Federico Bertero, y recibió financiamiento de la Secretaría de Estado de Ciencia, Tecnología e Innovación de la provincia de Santa Fe.
