En GIRO, nos dedicamos a ahorrar tiempo y dinero a nuestros clientes. Nuestro software de optimización ayuda a algunas de las agencias de transporte público y organizaciones postales/de paquetería más importantes del mundo a maximizar la eficiencia de sus servicios y a minimizar los costes, resolviendo problemas difíciles para conseguir ahorros significativos. En más de cuarenta años de actividad, hemos desarrollado -y seguimos desarrollando- algoritmos extremadamente potentes que ayudan a nuestros clientes a alcanzar sus objetivos.
¿Puede hacerlo bien y rápido?
A menudo, los problemas de optimización que nuestros clientes deben resolver son extremadamente difíciles desde el punto de vista matemático, y se clasifican como problemas "NP-hard". Lo que esto significa en la práctica es que los algoritmos generalmente no pueden producir soluciones que sean demostrablemente óptimas, o al menos no sin funcionar durante mucho tiempo.
Me vienen a la mente dos refranes: "el tiempo es oro" y "si vale la pena hacerlo, vale la pena hacerlo bien". No siempre van de la mano si "hacerlo bien" cuesta demasiado tiempo.
Para estos problemas de dificultad NP, a menudo se pueden obtener soluciones de alta calidad que producen un aumento sustancial de la eficiencia y un ahorro de costes mediante métodos heurísticos, que aplican reglas de forma menos estricta que los algoritmos. Cuando estos métodos son lo suficientemente sofisticados, se pueden obtener soluciones de alta calidad en cuestión de minutos y tratar de exprimir hasta la última gota de ahorro siguiendo la ruta algorítmica completa no producirá mucho beneficio adicional. Pero, a veces, ir más allá de una solución de alta calidad hasta llegar a una óptima producirá beneficios tan grandes que debemos invertir el tiempo necesario para ejecutar los algoritmos de los problemas NP-duros. Para maximizar los beneficios, queremos ejecutar los algoritmos lo más rápidamente posible. El procesamiento paralelo es una forma de conseguirlo.
Para maximizar los beneficios, queremos ejecutar los algoritmos lo más rápidamente posible. El procesamiento paralelo es una forma de conseguirlo.
Muchas manos hacen el trabajo ligero - para el trabajo correcto
Supongamos que quieres pintar una habitación con cuatro paredes del mismo tamaño. Si invitas a tres amigos para formar un cuarteto y cada uno de vosotros se encarga de una pared, puedes esperar terminar cuatro veces más rápido que si pintaras todas las paredes tu solo. En otras palabras, la ganancia de velocidad es lineal, lo cual es ideal porque la ganancia es igual al número de recursos utilizados: si se utilizan cuatro pintores, el trabajo se hace cuatro veces más rápido. El mismo principio se aplica al software, que puede procesar tareas en paralelo cuando hay varios procesadores disponibles.
El procesamiento paralelo consiste en dividir una tarea informática en subtareas que pueden ser realizadas al mismo tiempo por diferentes procesadores, de modo que la tarea completa se complete más rápidamente. Sin embargo, no todas las tareas son adecuadas para ser descompuestas para el procesamiento paralelo. La ganancia global en velocidad de computación dependerá de la proporción de tareas del programa que puedan subdividirse para ser realizadas en paralelo y de si hay algún coste adicional asociado a la subdivisión.
Volviendo a nuestro ejemplo de pintar una casa, el trabajo de pintar se presta al procesamiento paralelo dividiendo el trabajo entre varios pintores. Sin embargo, el procesamiento paralelo no es el camino a seguir si quieres agradecer a tus amigos su duro trabajo compartiendo una pizza con ellos. Cortarla en cuatro y utilizar cuatro hornos para hornear las porciones al mismo tiempo podría cocinar tu pizza ligeramente más rápido, pero no será nada parecido a cuatro veces más rápido. Si se tienen en cuenta los costes de compra de los hornos adicionales y el pago de la energía que consumen, la inversión en procesos paralelos para cocinar la pizza de esta manera no será rentable.
Sin embargo, no todas las tareas son adecuadas para ser descompuestas para el procesamiento paralelo. La ganancia global en velocidad de computación dependerá de la proporción de tareas del programa que puedan subdividirse...
¿Será el procesamiento o el enhebrado?
Cuando el procesamiento paralelo es el camino a seguir, hay dos enfoques disponibles: el multiprocesamiento y el multihilo. Con el multiprocesamiento, se ejecutan varios procesos al mismo tiempo en diferentes procesadores. Con el multithreading, un único proceso se divide en hilos que se programan para ejecutarse simultáneamente dentro del "contexto" de ese proceso. Cada método tiene sus pros y sus contras. El multiprocesamiento utiliza más recursos, pero tiene la ventaja de que apenas requiere cambios en la codificación existente y es más fácil de implementar. El multihilo suele ser más difícil de implementar y aumenta el potencial de problemas causados por las condiciones de carrera, que pueden ocurrir si el acceso a un recurso compartido no se controla adecuadamente. Sin embargo, como los diferentes hilos comparten los mismos recursos, como la RAM, el multithreading tiene una huella tecnológica menor.
En GIRO tenemos bastante experiencia con ambos enfoques. Algunos de nuestros módulos de software HASTUS utilizan el multiprocesamiento desde hace más de 25 años y también empezamos a utilizar el multithreading hace unos 10 años.
Un módulo que tiene un largo historial de uso del multiprocesamiento es nuestro módulo CrewOpt para la optimización de la programación de la tripulación. El programador de tareas de CrewOpt es un motor de paralelización que lanza todas las tareas de optimización para los subproblemas de un problema de programación a gran escala en diferentes procesadores y los resuelve al mismo tiempo. El programador de tareas también puede utilizarse para el procesamiento de estrategias múltiples, "clonando" el mismo problema para resolverlo utilizando diferentes parámetros a la vez. Los parámetros que producen la mejor solución se guardan entonces. El uso del programador de tareas de CrewOpt proporciona una ganancia casi lineal en la velocidad de procesamiento frente a la comprobación de cada estrategia una tras otra.
Cada vez son más los productos que utilizan el enfoque multihilo para ejecutar sus algoritmos con mayor rapidez. Muchos de ellos utilizan una versión multihilo del solucionador de programación matemática de alto rendimiento CPLEX. El uso de multithreading para nuestros algoritmos Customer Impact Simulator y ReachMap fue de gran ayuda para nuestro cliente LA Metro en su proyecto NextGen, ahorrando mucho tiempo cuando estaban reimaginando toda su red de autobuses y necesitaban ejecutar múltiples simulaciones de forma rápida y precisa.
La nube da un impulso adicional
Cada vez son más los clientes que optan por alojar sus instalaciones de HASTUS en la nube en lugar de mantenerlas en su propia infraestructura. Esto abre nuevas posibilidades de procesamiento en paralelo y de ejecución de algoritmos en máquinas virtuales (VM) de diferentes tamaños según las necesidades de recursos de cada algoritmo. No siempre es rentable ampliar el sistema local para hacer frente a las necesidades ocasionales de procesamiento adicional. La nube facilita el pago de la potencia de procesamiento extra sólo cuando se necesita, lo que resulta especialmente útil cuando el enfoque de multiprocesamiento exige recursos adicionales. Vemos mucho más procesamiento paralelo en nuestro futuro, ya que esperamos que la mayoría de nuestros clientes se trasladen a la nube.
Cada vez son más los clientes que optan por alojar sus instalaciones de HASTUS en la nube en lugar de mantenerlas en su propia infraestructura. Esto abre nuevas posibilidades de procesamiento en paralelo...
Acerca de los autores
Charles Fleurent, Director Principal de Algoritmos de Optimización
En sus 25 años de carrera en GIRO, Charles Fleurent ha dirigido el desarrollo de los algoritmos que impulsan las soluciones de software de GIRO para optimizar la planificación, la programación y las operaciones del transporte público. Encabeza los esfuerzos de investigación de la empresa, tanto a nivel interno como en colaboración con varios institutos de investigación. En 2021, recibió el Premio a la Excelencia de la Asociación Canadiense de Tránsito Urbano, en reconocimiento a sus contribuciones a los avances en la optimización del transporte público, especialmente su participación en la investigación sobre el uso de la inteligencia artificial para optimizar la programación del personal. También es editor principal de la revista científica Public Transport: Planning and Operations, publicada por Springer.
Loïc Bodart, Director Adjunto de Algoritmos de Planificación-Ruta
Loïc Bodart dirige el equipo de desarrollo de los algoritmos que alimentan las soluciones informáticas de GIRO para optimizar la planificación y el encaminamiento de los transportes públicos y los servicios de paquetería y correos. Comenzó su carrera en el desarrollo de software para optimizar la gestión de la tripulación de las aerolíneas. En casi 15 años en GIRO, ha desempeñado una sucesión de funciones en el desarrollo de software que han perfeccionado su experiencia. Tiene un máster en Investigación Operativa por la Polytechnique Montréal.
Véronique Bouffard, Directora Adjunta de Algoritmos HASTUS
Véronique Bouffard dirige el equipo de desarrollo de los algoritmos que alimentan las soluciones de software de GIRO para optimizar la programación y la gestión de las operaciones de todos los modos de transporte público por carretera y ferrocarril. Ha desarrollado su experiencia en una carrera de cerca de 20 años en GIRO con un sólido enfoque en el desarrollo de algoritmos. Tiene un máster en Informática por la Universidad de Montreal.