• Accueil
  • À propos
  • Accrom\(\alpha\)th en PDF
  • Commanditaires
  • Contact
  • Contributions des lecteurs
  • Sites amis

Logo

À quelle heure passe l’autobus?

Par Charles Fleurent et Jean Aubin
Volume 4.2 - été-automne 2009

Comment fait-on pour savoir combien d’autobus il faut pour une ville, où il convient de les disposer et à quelle heure on doit les faire partir? Les graphes, les matrices et les algorithmes font partie de l’arsenal de la recherche opérationnelle pour s’attaquer à un problème aussi complexe.

Le problème du transport public peut être décrit ainsi: dans le cadre d’un budget fixe, il faut offrir au public le meilleur service possible. Il existe plusieurs critères permettant de juger de la qualité d’une solution: la fréquence des autobus, la couverture du territoire, le temps de déplacement, la ponctualité, etc. Pour aborder ce problème, on doit le diviser en plusieurs sous-problèmes qu’on résoudra successivement.

Nous présentons ici une séquence possible de sous-problèmes pour définir le problème global du transport public.

La demande

Avant toute chose, il faut établir la demande. Il faut savoir combien de personnes veulent se déplacer pour aller au travail, à l’école, au magasin, etc. Idéalement, il faudrait connaître les déplacements de toute la population résidant sur le territoire desservi par la société, incluant les déplacements qui ne sont pas faits en transport en commun. Cette demande est habituellement agrégée en petite cellules et représentée sous la forme d’une matrice origine- destination; chaque entrée dans la matrice correspond au nombre de personnes se déplaçant d’une origine à une destination. Des matrices différentes peuvent être définies pour les différentes heures et journées.

Les lignes et les fréquences

En utilisant les matrices origine-destination, il faut déterminer les lignes d’autobus et les fréquences désirées pour toutes les heures de la journée/semaine afin d’attirer et servir le plus grand nombre possible d’usagers.

L’horaire maître

Il convient ensuite de construire l’horaire maître en déterminant les heures de départ de tous les voyages pour garantir la fréquence calculée à l’étape précédente et synchroniser les horaires des différentes lignes pour favoriser des correspondances sans temps d’attente exagérément long.

Le graphicage

À cette étape, on cherche à construire l’horaire des véhicules en minimisant à la fois le nombre de véhicules requis et le temps improductif1 des autobus. On reviendra sur cette étape importante un peu plus loin.

L’habillage

On s’intéressera ensuite à l’élaboration des horaires quotidiens des chauffeurs à partir de l’horaire des véhicules, de la convention collective (par exemple quatre heures continues de conduite au maximum), des points de relève (endroits où les chauffeurs peuvent débuter ou finir leur pièce de travail), et du temps de déplacement entre les points de relève. Ce problème est probablement le sous-problème le plus important d’un point de vue économique, car la main d’œuvre peut représenter jusqu’à 80% des coûts totaux.

Le roulement

L’établissement des roulements pour les chauffeurs consiste à déterminer, sur un horizon de temps plus long, les jours de travail (à partir des journées construites à l’étape précédente) ainsi que les jours de repos des chauffeurs. On considère typiquement un horizon d’une semaine en Amérique du Nord et jusqu’à 10 ou 12 semaines dans certains pays d’Europe.

Les opérations

Une fois les horaires établis, il faut être prêt à réagir aux nouveaux problèmes créés par les perturbations du quotidien: retards et absences des employés, pannes de métro, service supplémentaire requis pour des événements. Évidemment, on essaiera là aussi de minimiser les coûts de ces ajustements.

Notons qu’il est possible en principe de combiner deux sous-problèmes, par exemple, de déterminer l’horaire des véhicules et des employés en même temps. Toutefois le problème qui en résulte peut s’avérer si complexe que les modèles, algorithmes et ordinateurs d’aujourd’hui ne sont pas assez puissants pour trouver des solutions dans un temps raisonnable.

Le problème de graphicage

Examinons de plus près le problème de graphicage, c’est-à-dire le problème de construction de l’horaire des véhicules. Ce problème apparaît après l’estimation de la demande, l’identification des lignes, de leurs fréquences et la préparation d’un horaire-maître. Nous connaissons alors:

  • l’ensemble des voyages à réaliser. Pour chaque voyage, nous avons l’heure de départ et la durée du voyage;
  • les temps de déplacement entre les lieux de début et de fin de tous les voyages, ainsi que le temps de déplacement entre les lieux de départ ou d’arrivée et les garages impliqués.

L’idée au coeur de notre modélisation est de regrouper une suite de voyages consécutifs d’un même véhicule qui respectent les contraintes d’entretien. Une telle suite se nomme une voiture. Dans une journée donnée, un véhicule peut être chargé de faire plus d’une voiture. Il faut donc trouver les suites de voyages, ou voitures, qui minimisent les déplacements hors service (temps improductif) et le nombre de véhicules requis.

bus_img1

Le dessin ci-dessus représente un véhicule qui fait deux voitures dans sa journée. Le véhicule de ce dessin sort du garage, fait trois voyages productifs, rentre au garage, puis en ressort pour faire quatre voyages avant de terminer sa journée au garage. Les temps avec passagers (productifs) sont en bleu, et les temps sans passagers (improductifs) sont en rouge2. Simplifions un peu le problème de graphicage pour permettre de définir un modèle mathématique simple et de décrire des algorithmes de résolution simples eux aussi. Voici les hypothèses de base que nous utiliserons:

  • Nous avons un seul garage d’où sortent tous les autobus.
  • Tous les autobus sont identiques. Ils sont donc autorisés à faire tous les voyages.
  • Une voiture et un véhicule sont équivalents. Tous les véhicules ne font qu’une journée.

Nous verrons maintenant que le problème de graphicage est équivalent à identifier un parcours dans un réseau qui soit à la fois un parcours de coût minimal et un parcours qui satisfait les contraintes minimales de service.

Pour comprendre les différentes variables, nous allons nous référer au graphe de la page suivante qui en illustre la modélisation. Dans ce graphe, il y a des nœuds et des arcs. Les nœuds représentent tous les lieux de départ et d’arrivée ainsi que le garage; pour faciliter la lecture du diagramme, le garage est représenté deux fois. Les arcs modélisent les voyages productifs et tous les voyages improductifs qui sont possibles.

Trois valeurs sont associées aux différents arcs: une capacité minimale, une capacité maximale, et un coût.

Les arcs bleus, en gras, représentent les voyages. Les capacités minimale et maximale, qui sont d’une unité, indiquent qu’il faut obligatoirement desservir tous les voyages. Il n’y a pas de coût associé à ces arcs.

Les arcs rouges, en continu, sont des éléments qui modélisent les entrées et sorties des autobus des garages. La capacité minimale, qui est de zéro unité, et la capacité maximale qui est d’une unité indiquent que l’on peut choisir cet arc ou non. Le coût de cet arc correspond au temps en minutes pour aller du garage à l’origine du voyage représenté par l’arc gras (ou retourner au garage).

bus_img2Les arcs verts, en pointillé, représentent les liens possibles entre les voyages. Un lien est créé s’il est physiquement possible de se déplacer pour arriver avant le départ du voyage. La capacité minimale, qui est de zéro unité, et la capacité maximale qui est d’une unité indiquent que l’on peut choisir cet arc ou non. Le coût de cet arc correspond au temps, en minutes, pour aller de la destination d’un voyage à l’origine d’un deuxième voyage. Si un autobus doit seulement changer de côté de rue pour faire un voyage en sens inverse alors il est hautement probable que cet arc soit choisi pour la solution finale.

Le grand arc en tirets noirs est un arc pour contrôler le nombre de véhicules. La capacité maximale est l’infini selon une de nos hypothèses simplificatrices. Le coût de cet arc correspond à un très grand nombre de minutes, disons 5 000 minutes, pour faire en sorte de trouver une solution qui minimise le nombre de véhicules en même temps que le temps improductif.

bus_img3

L’objectif revient alors tout simplement à identifier des ensembles d’arcs qui respectent toutes les contraintes de capacité et d’identifier parmi ces ensembles d’arcs l’ensemble qui coûte le moins cher. Il peut exister plusieurs ensembles d’arcs correspondant à la solution la moins chère. Autrement dit, la solution optimale peut ne pas être unique.

Contraintes supplémentaires

Dans la « vraie vie », d’autres contraintes existent et obligent systématiquement à complexifier la modélisation présentée dans cet article. Par exemple:

  • Il y a plusieurs garages, avec des autobus qui peuvent changer de garage.
  • Il y a plusieurs types de véhicules; certains voyages requièrent un type particulier de véhicule ou certains véhicules ne peuvent desservir certains voyages (ex. des autobus très imposants ne peuvent passer par de petites rues).
  • Il y a des battements minimum pour chacun des voyages.
  • Il est possible d’utiliser des stationnements temporaires pour garer les autobus à l’extérieur des garages.
  • Pour assurer une certaine stabilité des horaires, les horaires des véhicules de tous les jours de semaine doivent être similaires. Ils ne sont donc pas indépendants les uns des autres.

L’effet de ces contraintes est non négligeable. Ainsi, rien qu’en ajoutant un deuxième garage, on ne dispose plus d’algorithmes qui garantissent de trouver la solution optimale dans un temps raisonnable!

Il est donc important de concevoir des algorithmes robustes qui puissent intégrer facilement des contraintes supplémentaires et générer en un temps raisonnable une solution quasi-optimale.

Et là, la créativité est au moins aussi importante que la rigueur.

Modèle mathématique

Pour tous les nœuds \(i\) et \(j\), on connaît les capacités \(\text{CapMin}_{ij}\) et \(\text{CapMax}_{ij}\) de l’arc qui va de \(i\) à \(j\) ainsi que son coût \(c_{ij}\). Posons \(x_{ij}\), le nombre de fois que l’arc de \(i\) à \(j\) est parcouru par un véhicule. On cherche à:

Minimiser

\(\displaystyle \sum_i \sum_j c_{ij} x_{ij}\)

sujet à

\(\displaystyle \sum_i x_{ik} – \sum_j x_{kj}=0,\: \text{pour tous les noeuds}\: k,\)

\(\text{CapMin}_{ij} \leq x_{ij} \leq \text{CapMax}_{ij}, \: \text{pour tous les} \: i \: \text{et} \: j.\)

La première contrainte permet d’assurer que tout ce qui entre dans un nœud \(k\) en ressorte:

\[ \left ( \displaystyle \sum_i x_{ik} = \sum_j x_{kj} \right ) \]

Pour résoudre ce problème, des algorithmes performants existent. Ces algorithmes sont programmés informatiquement. L’ordinateur permet de trouver des solutions en quelques secondes. La taille typique des problèmes de graphicage varie entre quelques centaines et quelques milliers de voyages par jour. Le nombre d’arcs se chiffre habituellement en dizaines de milliers.

PDF

  1. On considère improductif le temps requis par un autobus pour sortir du garage et se rendre au premier arrêt d’une ligne d’autobus, pour se déplacer du point de fin de parcours d’une ligne au point de départ d’une deuxième ligne ou pour retourner au garage à la fin d’un parcours. ↩
  2. Sur des lignes à haute fréquence, il arrive très souvent qu’à la fin de son parcours, l’autobus reparte en sens inverse. Le temps improductif est alors très petit, car l’autobus n’a qu’à changer de côté de rue. Mais à l’heure de pointe le matin, il y a beaucoup plus d’autobus amenant les usagers vers le centre ville que d’autobus allant vers la banlieue. Dans ces conditions, le temps improductif est incontournable. ↩
  • ● Version PDF
Partagez
  • tweet

Tags: Mathématiques et transport

Articles récents

  • Le paradoxe de Saint-Pétersbourg

    Michel Adès, Jean-François Plante et Serge Provost
  • Huit dames et un échiquier

    Alexis Langlois-Rémillard
  • Le système de notation Elo

    Christian Genest et Julien Fageot

Sur le même sujet

  • Rouler sur l’or

    France Caron
  • Garder ses distances

    France Caron
  • L’avenir du pétrole

    Normand Mousseau

Volumes

  • Volume 17.1 – hiver-printemps 2022
  • Journée internationale des mathématiques: Accromath multilingue
  • Volume 16.2 – été-automne 2021
  • Volume 16.1 – hiver-printemps 2021
  • Volume 15.2 – été-automne 2020
  • Thème spécial: Les mathématiques sont partout
  • Volume 15.1 – hiver-printemps 2020
  • Volume 14.2 – été-automne 2019
  • Volume 14.1 – hiver-printemps 2019
  • Volume 13.2 – été-automne 2018
  • Volume 13.1 – hiver-printemps 2018
  • Volume 12.2 – été-automne 2017
  • Volume 12.1 – hiver-printemps 2017
  • Volume 11.2 – été-automne 2016
  • Volume 11.1 – hiver-printemps 2016
  • Volume 10.2 – été-automne 2015
  • Volume 10.1 – hiver-printemps 2015
  • Volume 9.2 – été-automne 2014
  • Volume 9.1 – hiver-printemps 2014
  • Volume 8.2 – été-automne 2013
  • Volume 8.1 – hiver-printemps 2013
  • Volume 7.2 – été-automne 2012
  • Volume 7.1 – hiver-printemps 2012
  • Volume 6.2 – été-automne 2011
  • Volume 6.1 – hiver-printemps 2011
  • Volume 5.2 – été-automne 2010
  • Volume 5.1 – hiver-printemps 2010
  • Volume 4.2 – été-automne 2009
  • Volume 4.1 – hiver-printemps 2009
  • Volume 3.2 – été-automne 2008
  • Volume 3.1 – hiver-printemps 2008
  • Volume 2.2 – été-automne 2007
  • Volume 2.1 – hiver-printemps 2007
  • Volume 1 – été-automne 2006
  • Article vedette

    Auteurs

    • Michel Adès
    • Antoine Allard
    • Jean Aubin
    • Marie Beaulieu
    • Rosalie Bélanger-Rioux
    • Claude Bélisle
    • Marc Bergeron
    • Pierre Bernier
    • André Boileau
    • Véronique Boutet
    • Pietro-Luciano Buono
    • Massimo Caccia
    • Jérôme Camiré-Bernier
    • France Caron
    • Philippe Carphin
    • Kévin Cazelles
    • Laurent Charlin
    • Pierre Chastenay
    • Noémie Chenail
    • Jocelyn Dagenais
    • Marie-France Dallaire
    • Jean-Lou de Carufel
    • Jean-Marie De Koninck
    • Lambert De Monte
    • Jean-Paul Delahaye
    • Marc-André Desautels
    • Florin Diacu
    • Jimmy Dillies
    • Nicolas Doyon
    • Philippe Drobinski
    • Hugo Drouin-Vaillancourt
    • Louis J. Dubé
    • Thierry Duchesne
    • Stéphane Durand
    • Thomas Erneux
    • Philippe Etchécopar
    • Julien Fageot
    • Charles Fleurent
    • Jérôme Fortier
    • Marlène Frigon
    • Jean-François Gagnon
    • André Garon
    • Christian Genest
    • Denis Gilbert
    • Jonathan Godin
    • Frédéric Gourdeau
    • Samuel Goyette
    • Jean Guérin
    • Hervé Guillard
    • Abba B. Gumel
    • James A. Hanley
    • Alain Hertz
    • Bernard R. Hodgson
    • Isabelle Jalliffier-Verne
    • Guillaume Jouvet
    • Tomasz Kaczynski
    • Patrick Labelle
    • Marc Laforest
    • Nadia Lafrenière
    • Josiane Lajoie
    • Alexis Langlois-Rémillard
    • Simon-Olivier Laperrière
    • René Laprise
    • Steffen Lauritzen
    • Denis Lavigne
    • Adrien Lessard
    • Jean Meunier
    • Normand Mousseau
    • Johanna G. Nešlehová
    • Pierre-André Noël
    • Dmitry Novikov
    • Ostap Okhrin
    • Laurent Pelletier
    • Jean-François Plante
    • Serge Provost
    • Annie Claude Prud'Homme
    • Benoît Rittaud
    • Louis-Paul Rivest
    • Serge Robert
    • André Ross
    • Christiane Rousseau
    • Guillaume Roy-Fortin
    • Yvan Saint-Aubin
    • Maria Vittoria Salvetti
    • Vasilisa Shramchenko
    • Robert Smith?
    • Shophika Vaithyanathasarma
    • William Verreault
    • Redouane Zazoun

Sujets

Algèbre Applications Applications des mathématiques Changements climatiques Climat Construction des mathématiques COVID-19 Cristallographie cryptographie GPS Gravité Géométrie Histoire des mathématiques Imagerie Infini Informatique Informatique théorique Jeux mathématiques Logique mathématique Lumière Mathématiques de la planète Terre Mathématiques et architecture mathématiques et art Mathématiques et arts Mathématiques et astronomie Mathématiques et biologie Mathématiques et développement durable Mathématiques et littérature Mathématiques et musique Mathématiques et médecine Mathématiques et physique Mathématiques et transport Modélisation Nombres Portrait d'un mathématicien Portrait d'un physicien Probabilités Probabilités et statistique Racines Rubrique des Paradoxes Section problèmes Théorie des groupes Topologie Éditorial Épidémiologie

© 2022 Accromath