De nos jours, les réseaux de transport au sein d’une ville sont de plus en plus complexes. Un voyageur possédant un véhicule particulier se voit alors confronté aux problèmes de congestion, ce qui retarde son trajet et lui apporte un certain inconfort que les géstionnaires souhaitent éviter. De plus, les autorités se sont fixés des objectifs de réduction des émissions de CO2 pour des raisons environnementales. Pour cette finalité, on incite les voyageurs à réduire l’usage du véhicule particulier et à favoriser les transports en commun. Ce qui relève une problématique plus importante qui est l’inter-modalité. En effet, selon l’importance ou la compléxité d’une ville, l’usager peut être amené à utiliser plusieurs modes de transport afin d’éffectuer son trajet. Prenons l’éxemple d’une personne domiciliée en banlieue et dont le lieu de travail se trouve au centre. L’idéal pour cette personne serait de prendre son véhicule jusque dans la périphérie de la ville, garer sa voiture dans un parking relai pour ensuite finir son trajet en transport en commun pour éviter la congestion. Pour mettre au point un modèle d’affectation qui propose à un usager un trajet inter-modal, il faudrait représenter les réseaux de chaque mode, puis les croiser afin de créer des chemins multimodaux ce qui fait exploser le nombre d’arcs. Le problème d’affectation étant un problème NP-difficile, sa résolution avec un algorithme exact est quasi impossible. C’est là alors qu’interviennent les modèles multi-agents. Les systèmes multi-agents permettent de modéliser les interactions entre les différents types d’entités impliqués dans le modèle. Notamment les relations utilisateurs-utilisateurs et utilisateurs-opérateurs qui sont modélisés de façon assez lourde dans un modèle classique alors qu’elles sont modélisés de manière implicite dans un modèle multi-agents. C’est cette réduction de compléxité qui nous a poussé à modéliser notre problème en utilisant un modèle multi-agents. Un autre aspect très important que l’on ne doit pas oublier de prendre en compte est l’évolution constante de la technologie et son implication dans le domaine du transport. Les usagers utilisent de plus en plus des applications web ou mobile pour avoir des informations sur l’état du réseau, ou même pour obtenir le meilleur itinéraire possible. La RATP à paris, par exemple, propose à ses abonnés une application qui leur indique l’itinéraire à prendre pour éffectuer leurs trajets. Les utilisateurs peuvent alors choisir parmi plusieurs options, le plus rapide, le moins de correspondances,… Dans le même ordre d’idées, notre modèle s’adresse aux usagers munis d’un système d’information qui permet donc de les tracer et d’avoir une meilleure perception de l’état du réseau. Cependant, il prend aussi en compte les utilisateurs qui ne possèdent pas de système d’information et dont les déplacements sont basés uniquement sur leurs connaissances à priori du réseau. Cette modélisation nous permettra alors de répondre à la question: « Les systèmes d’information améliorent-il l’état du réseau »?

Les réseaux de transports deviennent de plus en plus complexes de nos jours. En effet, le réseau routier et le réseau de transport en commun ne cessent de s’étendre dans le but de satisfaire la demande qui elle aussi ne cesse d’augmenter. Les utilisateurs sont donc contraints d’utiliser plusieurs modes de transports surtout pour effectuer les trajets banlieue-centre. D’où la nécessité d’avoir des modèles mathématiques simple et performants pour modéliser ce genre de problèmes. Les évolutions technologiques font que les utilisateurs ainsi que les opérateurs de transport utilisent de plus en plus les systèmes d’informations. En effet, les usagers s’aident de ces systèmes d’informations dans le but d’avoir des informations en temps réel sur le réseau, informations qui sont procurées par les opérateurs qui eux l’utilisent comme un nouveau système de contrôle. Ainsi l’acquisition de données plus précises devient plus facile. Nous allons donc nous intéresser à deux types de problèmes: l’affectation prédictive des voyageurs et l’affectation réactive. En recherche opérationnelle, le problème d’affectation consiste à déterminer un couplage maximum dans un graphe biparti valué. En transport, l’affectation consiste à calculer pour chaque utilisateur un itinéraire dont le temps de parcours serait optimal et à analyser l’interaction de l’ensemble des choix des usagers. Ainsi, l’affectation prédictive consiste à calculer un itinéraire optimal à l’origine que l’utilisateur devra respecter jusqu’à ce qu’il arrive à la destination désirée. L’utilisateur connait donc bien le système et possède une bonne information, donc choisit à priori son itinéraire. Tandis que l’affectation réactive consiste non seulement à calculer l’itinéraire optimal à l’origine mais aussi à mettre à jour ce calcul au fur et à mesure que l’utilisateur se déplace sur le réseau. Ainsi, si arrivé à mi chemin, une route devient meilleure que celle choisie au départ, l’opérateur proposera un autre chemin que l’utilisateur est susceptible d’accepter.

La modélisation du graphe multimodal est l’une des premières difficultés auxquelles nous nous retrouvons confrontés. La taille du réseau, ie: le nombre de nœuds et d’arcs dans un graphe intervient fortement dans la rapidité d’exécution des algorithmes d’affectation dynamique. Dans la littérature, on trouve différents types de modélisation.

Un graphe multimodal G = (N,E), tel que N et E représentent respectivement les ensembles des nœuds et liens physiques, constitue la représentation d’un réseau de transport multimodal. Ainsi un nœud peut soit représenter une station de bus, de métro un carrefour, . . . . De la même façon un arc peut représenter un tronçon routier, une voie de bus, une voie de métro ou un chemin piéton. Ce type de graphe est construit par la superposition des graphes modaux Gm = (Nm, Em), avec m ∈ M L’ensemble de tous les modes de transport. On note Nm L’ensemble des nœuds du mode m ∈ M et Em l’ensemble des arcs du mode m ∈ M. Cette représentation est la plus naturelle et la plus simple et a été utilisée dans beaucoup de travaux, on cite notamment [38]. Cependant elle reste très complexe étant donné le nombre de nœuds et d’arcs. C’est pour cela que d’autres moyens de modélisation ont été introduits .

Ce type de graphe a été créé dans le but de représenter les réseaux de transports en commun. En effet, la particularité des transports en commun est que la modélisation des transferts entre différents services ainsi que l’affectation des flots de passagers vers de multiples services à partir du même tronçon de route sont requis. Ce type de représentation a été utilisé dans plusieurs travaux ( [4], [44], [25]). On cite par exemple les travaux de [11] qui considère que le processus de transfert est décrit de la manière suivante
1. Parking du véhicule
2. Préparation à quitter le véhicule
3. Quitter le véhicule
4. Marcher jusqu’au point de transfert
5. Attente du prochain véhicule
6. Acquisition du véhicule
7. Embarquement dans le véhicule
8. Installation dans le véhicule .

Dans ce document, nous donnons une définition simplifiée qui est décrite comme suit:
1. Parking du véhicule
2. Quitter le véhicule
3. Marcher vers le point de transfert.
4. Attendre le prochain véhicule.
5. Monter dans le véhicule .

Un graphe espace-temps est un graphe qui représente les temps de départ ou d’arrivée à chaque nœud. Ici, un nœud possède deux étiquettes: La première est un noeud dans le réseau de routage et la seconde représente une séquence de temps. Ainsi, un noeud se trouvera représenté (p + 1) fois, p représentant le nombre de pas de temps. De manière similaire, un arc est étendu à (p + 1 − cij ), ou cij représente le temps de parcours sur l’arc (i,j) Ce type de représentation a été utilisé par [26], [21] et [22]. La figure suivante représente un graphe espace-temps.

Cette représentation est utilisée car elle présente des avantages que le graphe multimodal simple n’offre pas. Par exemple, [26] s’est intéressé à la recherche d’un plan de transport multi-pas en prenant en considération les différents moyens de transports en commun, à savoir: le bus, le train mais aussi la marche à pied ainsi que l’appel d’un taxi. Pour ce faire, le problème a été formulé comme un problème d’optimisation qui consiste à construire un ensemble I d’intervalles de temps dans le but de minimiser le coût total de transport soumis à une contrainte de temps. Un voyage est donc représenté comme étant une séquence d’intervalle de temps dont la taille est à déterminer. Le graphe le plus adapté dans ce cas est le graphe espace-temps car la représentation par un graphe multimodale classique ne permet pas d’intégrer la notion de temps tel que formulé dans ce modèle.