Chez GIRO, l’économie de temps et d’argent de nos clients constitue notre priorité. Notre logiciel d’optimisation aide certaines des sociétés de transport public et de service postal les plus reconnues à travers le monde à maximiser leur efficacité et à réduire les coûts en résolvant des problèmes complexes, entraînant du même coup d’importantes économies. Œuvrant dans notre domaine depuis plus de quarante ans, nous avons développé de puissants algorithmes qui soutiennent nos clients vers l’atteinte de leurs objectifs et nous continuons de le faire à ce jour.
Vite fait, bien fait?
Bien souvent, les problèmes d’optimisation auxquels sont confrontés nos clients sont excessivement difficiles à résoudre d’un point de vue mathématique. Ceux-ci sont alors classés « Np-durs ». À moins de les exécuter pendant de très longues périodes, les algorithmes ne peuvent habituellement pas générer de solutions concrètement optimales.
Deux dictons s’imposent donc à l’esprit : « Le temps, c’est de l’argent », et « ce qui mérite d’être fait mérite d’être bien fait ». Ces deux adages ne sont pas toujours compatibles lorsque « ce qui mérite d’être bien fait » s’avère trop laborieux.
Les méthodes heuristiques, qui appliquent les règles de manière moins stricte que les algorithmes, peuvent souvent générer des solutions de qualité permettant de réaliser des économies et des gains en efficacité considérables face à ces problèmes Np-durs. Lorsqu’elles sont assez sophistiquées, ces méthodes permettent d’obtenir des solutions de qualité en quelques minutes, et ce, sans nécessiter l’exécution de longs algorithmes dans l’espoir de puiser jusqu’à la dernière goutte d’économies. Cependant, il est parfois si profitable de passer d’une solution de qualité à une solution optimale que nous devons consacrer le temps nécessaire à l’exécution des algorithmes pour remédier aux problèmes Np-durs. Afin de maximiser les retombées, nous devons nous assurer que les algorithmes fonctionnent le plus rapidement possible. Le traitement en parallèle constitue un moyen d’atteindre cet objectif.
Afin de maximiser les retombées, nous devons nous assurer que les algorithmes fonctionnent le plus rapidement possible. Le traitement en parallèle constitue un moyen d’atteindre cet objectif.
L’union fait la force, mais pas toujours
Imaginons que vous voulez peinturer une pièce composée de quatre murs de la même taille. Si vous invitez trois amis et qu’à quatre, vous peinturez un mur chacun, vous aurez terminé quatre fois plus vite que si vous aviez peinturé tous les murs par vous-même. En d’autres termes, le gain en efficacité est linéaire et proportionnel au nombre de ressources employées, c’est-à-dire quatre personnes pour accomplir le travail quatre fois plus rapidement. Il en va de même pour les logiciels : lorsque disponibles, plusieurs processeurs peuvent traiter différentes tâches en parallèle.
Le traitement en parallèle a recours à la séparation d’une tâche informatique en sous-tâches pouvant être réalisées plus rapidement par plusieurs processeurs en simultané. Toutefois, toutes les tâches ne se prêtent pas bien à la séparation requise pour le traitement en parallèle. Le gain total en vitesse de calcul dépendra de la proportion de tâches du programme qui peuvent être divisées à des fins d’exécution en parallèle ainsi que de la présence de coûts associés à ces divisions.
Dans notre exemple de travaux de peinture, la nature de la tâche elle-même se prête au traitement en parallèle avec la séparation de la charge de travail entre plusieurs personnes. Le traitement en parallèle ne convient cependant pas à toutes les situations, par exemple, lorsque vous souhaitez remercier vos amis de leur dur labeur en partageant une pizza. En la coupant en quatre et en la faisant cuire dans quatre fours différents, vous gagnerez peut-être un peu de temps, mais vous demeurez très loin d’un gain quadruplé en efficacité. Sans parler des coûts liés à l’achat de fours supplémentaires et à l’énergie nécessaire pour les faire fonctionner... Un tel investissement pour cuire une pizza en parallèle n’en vaut simplement pas la chandelle.
Toutefois, toutes les tâches ne se prêtent pas bien à la séparation requise pour le traitement en parallèle. Le gain total en vitesse de calcul dépendra de la proportion de tâches du programme qui peuvent être divisées...
Multitraitement, ou traitement multifil?
Lorsque le traitement en parallèle est approprié, deux approches s’offrent à nous : le multitraitement et le traitement multifil. D’un côté, le multitraitement consiste à exécuter plusieurs processus en même temps à l’aide de différents processeurs. De l’autre, le traitement multifil permet de diviser un seul processus en fils d’exécution programmés pour être traités en simultané dans le « contexte » de ce processus. Chaque méthode comporte des avantages et des inconvénients. Le multitraitement utilise davantage de ressources, mais ne nécessite pratiquement aucune modification au code existant, en plus d’être plus simple à implémenter. Quant au traitement multifil, il est plus difficile à implémenter et son utilisation augmente les risques de problèmes causés par accès concurrent, qui peuvent survenir lorsque l’accès à une ressource partagée n’est pas géré correctement. Toutefois, comme les différents fils d’exécution partagent des ressources, telles que la mémoire vive, le traitement multifil accapare moins d’espace matériel et logiciel.
Ces deux approches n’ont plus de secrets pour GIRO. Quelques-uns de nos modules HASTUS font appel au multitraitement depuis plus de 25 ans et nous employons aussi le traitement multifil depuis environ 10 ans.
CrewOpt, un module d’optimisation des habillages, utilise le multitraitement depuis longtemps. Le planificateur de tâches CrewOpt est un moteur de parallélisation qui lance les tâches d’optimisation pour tous les sous-problèmes d’un plus gros problème de confection d’horaires sur plusieurs processeurs afin de les résoudre en même temps. Le planificateur de tâches sert aussi au traitement à stratégies multiples, qui « clone » un problème pour le résoudre à l’aide de différents paramètres que l’on exécute en même temps. Les paramètres qui génèrent la meilleure solution sont ensuite sauvegardés. Une telle utilisation du planificateur de tâches CrewOpt permet un gain quasi linéaire en vitesse de calcul, comparativement à la réalisation de tests consécutifs.
Un nombre croissant de nos produits ont aussi recours au traitement multifil afin d’accélérer l’exécution de leurs algorithmes. Plusieurs d’entre eux utilisent une version multifilaire de CPLEX, un solveur de programmation mathématique haute performance. Le traitement multifil dans nos algorithmes du Simulateur d’impact clientèle et de ReachMap a permis à notre client d’exécuter plusieurs simulations de manière rapide et précise dans le cadre de la refonte complète de son réseau d’autobus.
Le nuage donne un coup de pouce
Un nombre grandissant de nos clients choisissent d’héberger leurs installations HASTUS sur le nuage plutôt que dans leurs propres infrastructures. Cette méthode donne lieu à de nouvelles possibilités de traitement en parallèle et d’exécution d’algorithmes sur des machines virtuelles de diverses capacités, selon les besoins en ressources propres à chaque algorithme. Il n’est pas toujours rentable de développer votre infrastructure locale pour répondre aux besoins occasionnels en traitement. Le nuage constitue une solution simple qui permet d’obtenir plus de puissance de calcul sur demande, ce qui s’avère particulièrement pratique lorsque le multitraitement nécessite des ressources supplémentaires. Dans un proche avenir, nous prévoyons que la majorité de nos clients migreront vers le nuage et que le traitement en parallèle jouera un rôle déterminant à l’échelle de leurs activités.
Un nombre grandissant de nos clients choisissent d’héberger leurs installations HASTUS sur le nuage plutôt que dans leurs propres infrastructures. Cette méthode donne lieu à de nouvelles possibilités de traitement en parallèle...
Au sujet des auteurs
Charles Fleurent, directeur principal, algorithmes d’optimisation
Au cours de sa carrière de 25 ans au sein de GIRO, Charles Fleurent a mené le développement des algorithmes qui propulsent les solutions logicielles de GIRO dans l’optimisation de la confection d’horaires, de la planification ainsi que des opérations du transport public. Il dirige notamment les recherches de l’entreprise à la fois sur le plan interne et en collaboration avec divers instituts de recherche. En 2021, il a remporté le prix d’excellence de leadership des individus, décerné par l’Association canadienne du transport urbain, en reconnaissance pour sa contribution à l’amélioration de l’optimisation du transport public, en particulier son engagement dans la recherche sur l’utilisation de l’intelligence artificielle vers l’optimisation de la confection d’habillages. Il travaille aussi comme rédacteur en chef pour le journal scientifique Public Transport : Planning and Operations, publié par Springer.
Loïc Bodart, directeur adjoint, algorithmes de planification et de confection des tournées
Loïc Bodart dirige l’équipe de développement des algorithmes qui propulsent les solutions logicielles de GIRO dans l’optimisation de la planification et de la confection de tournées pour le transport public et les services postaux. Il a commencé sa carrière en tant que développeur de logiciels contribuant à optimiser la gestion du personnel de compagnies aériennes. En près de 15 ans chez GIRO, il a occupé plusieurs postes en développement de logiciels, ce qui lui a permis de perfectionner son expertise. Il est titulaire d’une maîtrise en recherche opérationnelle de Polytechnique Montréal.
Véronique Bouffard, directrice adjointe, algorithmes HASTUS
Véronique Bouffard dirige l’équipe de développement des algorithmes qui propulsent les solutions logicielles de GIRO dans l’optimisation de la confection d’horaires et de la gestion des opérations pour tous les modes de transport public sur route ou sur rail. En près de 20 ans de carrière au sein de GIRO, elle a acquis une expertise axée sur le développement d’algorithmes. Elle est titulaire d’une maîtrise en informatique de l’Université de Montréal.