Groupe d’études et de recherche en analyse des décisions

Organiser les trajets d'autobus

STM

RO et transport

Dans le domaine du transport et de la logistique, bien planifier les trajets est crucial pour garantir la fiabilité d'un service tout en gardant des coûts d'opérations faibles. Que ce soit pour le transport de marchandises, l'acheminement du courrier, les transports en commun ou la maintenance des voiries, l'entreprise doit déterminer l'itinéraire de dizaines ou de centaines de véhicules (camions, voiture, autobus, trains, avions…) La recherche opérationnelle apporte des outils pour aider le décideur à planifier ces itinéraires à moindre coût, tout en prenant en compte les contraintes opérationnelles de l'entreprise.

RO et transport en commun

Une compagnie d'autobus, par exemple, doit résoudre les problème suivants : quels sont les horaires de chaque ligne d’autobus? Combien de véhicules sont nécessaires pour que tous les trajets prévus soient couverts ? Quel chauffeur fait quel trajet ? La compagnie doit suivre de nombreuses règles telles que: respecter la fréquence des trajets d'une même ligne, accorder des pauses régulières aux chauffeurs, limiter les trajets « à vide », etc. Le problème devient alors très complexe, en particulier lorsqu'il y a plusieurs milliers de trajets d'autobus par jour.

Des défis pour la RO

La recherche opérationnelle a permis le développement d’algorithmes efficaces qui sont maintenant utilisés par les compagnies de transport du monde entier. Les voies d'amélioration actuellement explorées sont nombreuses, en particulier:

  • mieux adapter les trajets aux besoins des utilisateurs: en connaissant plus précisément les déplacements souhaités, grâce notamment aux données collectées
  • augmenter la fiabilité des horaires: en prenant mieux en compte la variabilité des temps de trajets
  • améliorer la flexibilité du réseau: en ré-optimisant rapidement une solution en cas d’incident (panne mécanique, ralentissement inhabituel de la circulation, etc)
  • diminuer les coûts: par exemple en intégrant dans un même problème la confection des horaires et des itinéraires de véhicules.

Un peu de technique

La planification des itinéraires d'autobus peut se modéliser à l'aide d'un graphe de connexions: un nœud représente un trajet à effectuer et on ajoute un arc entre le nœud 1 et le nœud 2 si un véhicule peut faire le trajet 1 et juste après le trajet 2. Ainsi, un chemin dans ce graphe donne un enchaînement réalisable de trajets pour un véhicule. Parmi tous ces chemins possibles, il faut choisir une sélection qui minimise les coûts et couvre tous les trajets demandés. Pour cela on utilise la programmation mathématique en nombres entiers, et, plus spécifiquement un algorithme de génération de colonnes.