TRANSPORTS

 

Tous les chemins
mènent aux ... maths

par Patrice Marcotte et François Soumis

Congestion routière et horaires de transport aérien sont parmi les problèmes auxquels peuvent s'attaquer avec succès les mathématiques. Grâce à des modèles et à des simulations efficaces, les gestionnaires sont en mesure de régler des casse-tête extrêmement complexes.
Les auteurs

Patrice Marcotte est professeur titulaire au département d'informatique et de recherche opérationnelle de l'Université de Montréal.

François Soumis est professeur titulaire au département de mathématiques et de génie industriel de l'École polytechnique de Montréal.

Pour en savoir plus

www.ad-opt.com

www.crt.umontreal.ca/GERAD/

www.giro.ca

www.inro.ca

www.crt.umontreal.ca/CRT/

L'heure de pointe

La solution aux problèmes de congestion routière ne passe pas toujours par la construction de nouveaux ponts ou de nouvelles routes, comme cela se faisait dans un passé récent. La tendance actuelle est plutôt à une meilleure utilisation des infrastructures existantes.

Cela peut prendre diverses formes: diffusion d'information en temps réel par le biais de récepteurs situés dans les véhicules ou de panneaux à messages variables, tarification des axes routiers congestionnés, incitation au covoiturage, etc. Afin d'évaluer l'effet de ces politiques, il est important de bien comprendre les mécanismes de répartition du trafic sur le réseau, afin d'éviter certains effets pervers. En effet, ajouter des routes conduit quelquefois à augmenter la congestion !

Des modèles mathématiques, basés sur des principes de comportement des usagers, permettent de prédire le flux de véhicules sur les artères d'un réseau routier urbain. On distingue plusieurs types de modèles, suivant que l'on traite des réseaux de très grande taille (modèles macroscopiques) ou que l'on souhaite une représentation extrêmement fine des mouvements individuels de chaque véhicule (modèles microscopiques). Dans le premier cas, on traitera le flux de véhicules comme un fluide, alors que dans le second cas, on utilisera des techniques de simulation.

Plusieurs chercheurs, regroupés au Centre de recherche sur les transports ainsi qu'au Laboratoire sur les systèmes intelligents de transport de l'Université de Montréal, tentent d'approfondir notre compréhension des phénomènes de congestion. Ils cherchent également à améliorer les performances des réseaux de transport publics ou privés. Plusieurs de ces efforts ont débouché sur la conception de logiciels interactifs tels que EMME/2 (INRO Consultants) pour la planification du transport urbain ou HASTUS (GIRO INC.) pour la conception des horaires de chauffeurs d'autobus, qui sont commercialisés dans plus de 100 villes dans le monde. Ces logiciels font appel à des techniques de pointe de la recherche opérationnelle, une science qui traite des problèmes d'optimisation de très grande taille en intégrant les techniques d'analyse mathématique et l'informatique.

Les horaires des travailleurs aériens

Construire les horaires d'équipages dans les grandes compagnies aériennes est un des plus grands casse-tête posé à l'intelligence. Il faut affecter des milliers de pilotes et d'agents de bord à des dizaines de milliers de vols chaque mois. Le problème est complexe, car les avions opèrent 24 heures par jour, 7 jours par semaine sur de vastes territoires chevauchant plusieurs fuseaux horaires. Les équipages, qui ne travaillent pas 24 heures par jour, doivent être remplacés et dormir en route. Les horaires doivent respecter les règles fort complexes de la convention collective sur les temps de travail et de repos chaque jour, chaque semaine et chaque mois. Par exemple, le temps de travail maximum permis durant une journée dépend du travail effectué les jours précédents, de la récupération réalisée au cours des nuits et du décalage horaire.

Le défi de pareilles problématiques est le nombre incroyable de solutions à considérer pour trouver la meilleure. Un pilote travaille 20 jours par mois et fait en moyenne 5 vols par jour en court courrier, soit environ 100 vols par mois. À chaque escale, un pilote doit être affecté à un vol; mais lequel choisir parmi la dizaine de disponibles ? Cela donne 10100 (c'est-à-dire, 1 suivi de 100 zéros) horaires de travail possibles durant le mois pour un pilote. Le nombre de solutions à considérer pour l'ensemble du personnel est donc 10500 000; il faut choisir un horaire pour 5 000 pilotes et agents de bord avec 10100 choix pour chaque personne. Il n'est donc pas possible, même avec les ordinateurs les plus puissants, d'évaluer toutes ces solutions dans un temps raisonnable. Il faudrait des millions de millions de siècles.

Les mathématiques permettent de trouver une solution optimale. Elles offrent des méthodes minimisant une fonction en présence de contraintes partant d'une solution initiale et l'améliorant itérativement tant qu'une solution optimale n'est pas atteinte. Les méthodes de base ne sont pas directement applicables au problème d'horaire d'équipages, qui est trop grand. Il faut des milliers de contraintes et variables pour chacune des milliers de personnes afin de décrire les chemins possibles au sein du réseau ainsi que les règles de la convention collective.

L'utilisation de l'optimisation mathématique pour ce problème a été rendue possible en utilisant des méthodes d'ajout de contraintes et de variables durant la résolution. Ainsi, nous commençons par résoudre un problème réduit ne contenant que les contraintes et variables principales. Nous ajoutons ensuite les variables permettant d'améliorer la solution et les contraintes qui ne sont pas respectées. Les variables à ajouter sont identifiées en résolvant des sous-problèmes trouvant si possible un meilleur horaire pour certains des employés. Ces sous-problèmes consistent à trouver un chemin de coût minimum dans le réseau des vols en respectant les contraintes de la convention collective. De cette façon, on atteint la solution optimale après quelques centaines d'itérations sans nécessiter la construction de tous les horaires.

Cette méthode de résolution a permis d'obtenir des solutions réduisant de 5 % à 10 % les coûts de personnel. Ceci représente une économie pouvant dépasser 100 millions de dollars annuellement dans une grande compagnie aérienne.

De plus, nous intégrons dans la fonction à optimiser les préférences des employés en termes de jours de congé, heures de travail, destinations, etc. Cela permet d'augmenter la qualité de vie du personnel, en plus de réduire les coûts.

Cette approche intégrée dans un logiciel avec des bases de données et des interfaces graphiques est maintenant employée dans de nombreuses compagnies aériennes : Air Canada, Air Transat, Canadian Regional, Delta, TWA, Northwest, AWA, U.P.S., FEDEX, Swissair, Sabena, Air France, etc. Ce développement et cette commercialisation ont donné lieu à la création de la compagnie AD OPT Technologies Inc. qui emploie maintenant une centaine de scientifiques dont la majorité ont des maîtrises ou des doctorats en informatique, ou en mathématiques appliquées. Cette entreprise qui poursuit sa croissance embauche plusieurs dizaines de nouveaux scientifiques chaque année.

Une situation paradoxale

En situation de congestion, le temps de parcours T(x) d'un lien est une fonction croissante du nombre de véhicules x qui le parcourent. Par essais et erreurs, les usagers du réseau tentent de minimiser leur temps de parcours propre. Une situation stable, appelée affectation d'équilibre, sera atteinte lorsque aucun usager n'aura intérêt à modifier son trajet. Autrement dit, tous les chemins utilisés seront de durée égale et cette durée sera inférieure à celles des chemins non utilisés.

Le réseau formé des arcs bleus ci-contre est celui d'une municipalité M très affectée par la congestion. À côté de chaque lien du réseau sont indiquées les fonctions de congestion correspondantes. Ainsi, si 2 000 automobilistes empruntent le lien BD, leur temps de transport individuel sera égal à 50 + 2 000/1 000 = 52 minutes. Supposons que 6 000 véhicules doivent se rendre de A à D tous les matins. En tenant compte de la symétrie des données, ils se répartiront de façon égale sur les chemins ABD et ACD, et leur temps de transport commun sera égal à 83 minutes.

Cette situation intolérable est dénoncée par un candidat à la mairie de la municipalité, qui se fait élire en promettant la construction d'une autoroute reliant les sommets B et C du réseau. Une fois l'autoroute terminée, un nouvel équilibre est atteint, où 2 000 automobilistes empruntent maintenant chacun des 3 chemins disponibles (ABD, ACD et ABCD). Quelle n'est pas leur surprise, ainsi que celle du maire, de constater que leur temps de transport, loin d'avoir diminué, est passé de 83 à 92 minutes !

Une solution à ce problème serait de fermer l'autoroute. Il est cependant plus rentable d'imposer un péage sur le lien diagonal BC, ce qui permettra de simultanément réduire la congestion de tous les usagers, ainsi que de renflouer les coffres de la municipalité.

retour vers le haut