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
|