Modélisation des réseaux, systèmes multi-agents et clustering

La mise en service d’un système d’information multimodale implique la coordination et la gestion de plusieurs paramètres. Afin d’appliquer les méthodes proposées et composer les informations finales, nous avons jugé essentiel d’étudier les différentes modélisations des réseaux de transport afin de mieux cerner le fonctionnement des différentes entreprises qui souhaitent intégrer le système global. Il est vrai que l’idée instinctive concernant la modélisation d’un réseau de transport nous envoie vers les graphes orientés. Néanmoins, les besoins de modélisation d’un réseau change d’un mode de transport à un autre. Si la modélisation d’un réseau de transport ferroviaire doit répondre à une prise en compte stricte des temps de passages, la modélisation d’un réseau de piétons peut être un simple graphe non orienté. Ces détails sont d’une valeur cruciale dans le cas de la mise en place d’un système d’aide aux déplacements de porte à porte.

La modélisation d’un réseau de transport peut être classée selon les différents modes de transports. Cette classification concerne de manière générale : la modélisation des réseaux ferroviaires, la modélisation des réseaux routiers et la modélisation des réseaux des piétons. Chaque mode possède ses propres priorités  et ses propres caractéristiques (Pajor, 2009), cela ne permet pas d’avoir une modélisation unique pour tous les types de transport néanmoins le seul point en commun entre les différentes modélisations est la possibilité de pouvoir appliquer un algorithme de recherche d’itinéraire entre deux points. La modélisation des réseaux dépend clairement de l’approche et des caractéristiques de chaque mode de transport. Si la modélisation des routes peut être faite de manière simple à travers les graphes où chaque arête représente une route entre deux points et est pondérée par la distance qui les sépare, la modélisation d’un réseau de tramway ou d’autobus s’annonce nettement plus difficile. En effet, dans les transports en commun la notion de temps est très importante : les stations sont représentées par des nœuds mais la pondération des arêtes reste difficile du fait de la variance de leurs valeurs. Cette pondération dépend de l’état du trafic et de la congestion du réseau. Le temps d’un trajet d’un point A vers un point B change selon l’horaire, il est nettement plus rapide le soir que pendant les heures de pointes. Dans les transports en commun, le calcul d’un itinéraire dépend de manière directe de l’horaire de départ du voyageur. De ce fait, nous distinguons deux grandes voies de modélisations : les modèles dépendants du temps et les modèles indépendants du temps.

Les modélisations dépendantes du temps

Dans les modèles dépendants du temps (Brodal et Jacob, 2004b), la distance entre les nœuds n’est pas constante. La pondération d’un lien dépend alors d’une fonction arbitraire. Le plus court chemin dans un modèle dépendant du temps change selon l’horaire de départ du voyageur. Le temps du voyage peut changer dans une même journée selon la densité du trafic. Dans ce sens, (Orda et Rom, 1991) ont proposé une approche pour la modélisation et calcul des plus courts chemins dans les graphes dépendants du temps.

Les modélisations indépendantes du temps (Pajor, 2009)

Les modèles indépendants du temps sont très utilisés du fait de leur simplicité. Un modèle indépendant du temps consiste en un graphe où chaque nœud représente un point, les liens entre ces points sont pondérés par soit la distance qui les sépare soit le temps du parcours moyen. L’application d’un algorithme de recherche dans un modèle indépendant du temps permet de minimiser soit la distance de parcours, soit le temps de parcours. L’application d’un algorithme de recherche sur une telle modélisation fournit toujours la même réponse. L’un des algorithmes de recherches d’itinéraire les plus utilisés est l’algorithme de Dijkstra (Dijkstra, 1959). Les modèles indépendant du temps, bien qu’efficace lors de l’utilisation des distances comme métrique se heurte aux problèmes des temps de parcours dans les réseaux de transports en commun tel que les tramways et autobus. Dans le transport en commun, chaque entreprise dresse chaque année les tableaux de marche prévisionnels. Ces tableaux de marche permettent d’évaluer les temps de parcours entre deux stations selon les temps de passages, les journées et la densité du trafic. Il est impossible de prendre en compte les tableaux de marche dans une modélisation indépendante du temps. (Delling et al., 2009) ont effectué plusieurs travaux de recherche dans le domaine.

Modélisation des réseaux de transports en commun 

Les réseaux ferroviaires restent les réseaux ou l’on a appliqué le plus de recherches, en effet beaucoup de travaux se sont intéressés aux modélisations des réseaux ferroviaires pour l’importance économique que peuvent apporter les transports de marchandises. D’un point de vue transport des voyageurs, deux modèles permettent de modéliser les réseaux des transports en commun et prendre en compte la notion du temps. Ces deux modèles sont connus sous «les modèles dépendants du temps» et «les modèles expanded-time» (Pajor, 2009). Bien que leur appellation puisse porter confusion, ils gèrent tous les deux la notion de temps. Ces deux modèles existent en deux versions, une version simple et une version réaliste.

A. Modèle Expanded- time
Les modèles expanded-time (Schulz et al., 1999) ont pour but de prendre en compte la notion de temps et la variabilité des pondérations des liens entre les différents nœuds selon les différents horaires du voyage. Les graphes de tels modèles sont des graphes statiques où toutes les informations relatives aux stations et temps de déplacements sont exploités. Selon (Schulz, 2005), les problèmes des expanded time ont été largement étudiés dans (Ford et Fulkerson, 1958 ; Ford et Fulkerson, 1962). D’autres études plus récentes des variantes des problèmes expanded-time ont été considérés dans (Fleischer et Tardos, 1998 ; Fleischer et Skutella, 2002 ; Fleischer et Skutella, 2003 ; Kaohler et al., 2002)  .

Dans les modèles expanded-time, nous distinguons deux types de nœuds dans le graphe : des nœuds physiques et des nœuds événementiels. Les nœuds physiques représentent les données réelles concernant une station ou un arrêt, ces informations traitent la latitude et longitudes des stations et d’autres informations relatives à la compagnie. Les nœuds événementiels représentent les horaires des départs et d’arrivées d’une station, chaque départ ou arrivé dans une station données est représenté par un nœud.

Les liens entre les stations sont de plusieurs types :
– Des liens entre deux nœuds événementiels de deux stations différentes : ces liens sont tirés des tuples des tableaux de marches. Le poids de ces liens est la durée du voyage de la station de départ à la station d’arrivé.
– Des liens entre deux nœuds événementiels appartenant à une même station : ces liens représentent soit des départ ou des arrivés propres à une station, ils sont tirés dans un ordre croissant selon le temps.