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.
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).
Les 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.
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.
- 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. ↩
- 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. ↩
