MODÉLISATION DU TRAFIC

L E S C O L L E C T I O N S D E L ’ I N R E T S

MODÉLISATION DU TRAFIC

Actes du groupe de travail 2006

Coordination scientifiqueJean-Patrick LEBACQUEMaurice ARONVincent AGUILÉRA

AC

TE

S N ° 1 1 8

Huit présentations du séminaire 2006INRETS/ENPC « Modèles de Trafic »

ont été rédigées pour ces actes.- F. Barbier Saint Hilaire présente une version dynamique d’un logiciel d’affecta-tion, avec deux catégories d’usagers, calculant les congestions.- A. Awashti et al. présentent un modèletemps réel de plus court chemin, fondé surune classification préalable des conditionsdu trafic.- F. Leurent, V. Aguiléra et H-D Mai pré-sentent le modèle d’affectation dynamiqueLADTA où un critère supplémentaire aucritère d’optimisation convexe permet detraiter les gros réseaux.- M.S. El Hmam H. Abouaïssa et D. Jollyprésentent un modèle d’écoulement du trafic hybride, avec des « agents » véhicules,macroscopiques et microscopiques.- F. Leurent présente une hiérarchie d’indicateurs de confort pour le transport collectif qui inclut, notamment, un modèlede places assises.- F. Leurent présente une analyse de l’offreplurimodale en « hyperchemin », tenantcompte des fréquences, des places assises.- F. Leurent présente la théorie du réseaude services qui est un cadre pour formaliseret traiter un cheminement optimal souscontrainte.- V. Henn et T. Durlin présentent unmodèle d’intersection associé à un modèled’écoulement adapté à l’affectation dyna-mique du trafic.

Actes n°118Décembre 2008

Prix : 15,24 €Coordination scientifiqueJean-Patrick LEBACQUEMaurice ARONVincent AGUILÉRA

ISSN 0769-0266ISBN 978-2-85782-665-1

MO

DÉ

LIS

AT

ION

DU

TR

AF

IC

Act

es I

NR

ET

S n

°118

Conformément à la note du 04/07/2014 de la direction générale de l'Ifsttar précisant la politique dediffusion des ouvrages parus dans les collections éditées par l'Institut, la reproduction de cet ouvrage estautorisée selon les termes de la licence CC BY-NC-ND. Cette licence autorise la redistribution noncommerciale de copies identiques à l’original. Dans ce cadre, cet ouvrage peut être copié, distribué etcommuniqué par tous moyens et sous tous formats.

(CC BY-NC-ND 4.0)

Attribution — Vous devez créditer l'Oeuvre et intégrer un lien vers la licence. Vous devez indiquer cesinformations par tous les moyens possibles mais vous ne pouvez pas suggérer que l'Ifsttar voussoutient ou soutient la façon dont vous avez utilisé son Oeuvre.

Pas d’Utilisation Commerciale — Vous n'êtes pas autoriser à faire un usage commercial de cetteOeuvre, tout ou partie du matériel la composant.

Pas de modifications — Dans le cas où vous effectuez une adaptation, que vous transformez, oucréez à partir du matériel composant l'Oeuvre originale (par exemple, une traduction, etc.), vousn'êtes pas autorisé à distribuer ou mettre à disposition l'Oeuvre modifiée.

Le patrimoine scientifique de l'Ifsttar

Le libre accès à l'information scientifique est aujourd'hui devenu essentiel pour favoriser la circulation dusavoir et pour contribuer à l'innovation et au développement socio-économique. Pour que les résultats desrecherches soient plus largement diffusés, lus et utilisés pour de nouveaux travaux, l’Ifsttar a entrepris lanumérisation et la mise en ligne de son fonds documentaire. Ainsi, en complément des ouvragesdisponibles à la vente, certaines références des collections de l'INRETS et du LCPC sont dès à présentmises à disposition en téléchargement gratuit selon les termes de la licence Creative Commons CCBY-NC-ND.

Le service Politique éditoriale scientifique et technique de l'Ifsttar diffuse différentes collections qui sontle reflet des recherches menées par l'institut :

• Les collections de l'INRETS, Actes• Les collections de l'INRETS, Outils et Méthodes• Les collections de l'INRETS, Recherches• Les collections de l'INRETS, Synthèses• Les collections du LCPC, Actes• Les collections du LCPC, Etudes et recherches des laboratoires des ponts et chaussées• Les collections du LCPC, Rapport de recherche des laboratoires des ponts et chaussées• Les collections du LCPC, Techniques et méthodes des laboratoires des ponts et chaussées, Guide

technique• Les collections du LCPC, Techniques et méthodes des laboratoires des ponts et chaussées, Méthode

d'essai

www.ifsttar.fr

Institut Français des Sciences et Techniques des Réseaux,de l'Aménagement et des Transports14-20 Boulevard Newton, Cité Descartes, Champs sur MarneF-77447 Marne la Vallée Cedex 2

Contact : [email protected]

http://creativecommons.org/licenses/by-nc-nd/4.0/deed.fr



Coordination scientifique

Jean-Patrick LebacqueMaurice AronVincent Aguiléra

Modélisation du trafic

Actes du groupe de travail 2006

Actes INRETS No 118 Décembre 2008

La coordination scientifique :

Jean-Patrick Lebacque, ingénieur général des Ponts et Chaussées à l’INRETS–GRETIA. [email protected] Maurice Aron, chargé de recherche à l’INRETS–GRETIA. [email protected] Vincent Aguiléra, chargé de recherche au LVMT–ENPC. [email protected]

Les unités de recherche :

Laboratoire génie des réseaux de transport et informatique avancée (GRETIA), INRETS, université Paris-Est 2, rue de la Butte Verte, F-94114 Noisy-le-Grand cedex, France. Tél. : +33 1 45 92 56 06 – Fax : +33 1 45 92 55 01

Laboratoire ville, mobilité, transports (LVMT) INRETS–ENPC–université de Marne-la-Vallée, université Paris-Est 19, rue Alfred-Nobel, cité Descartes, Champs-sur-Marne F-77455 Marne-la-Vallée cedex 02, France.Tél. : +33 1 64 15 21 10 – Fax : +33 1 64 15 21 40

Les auteurs de communication :Hassane Abouaïssa (université d’Artois)Vincent Aguiléra (LVMT–INRETS–ENPC–UMLV)Anjali Awasthi (université de British Columbia, Canada)François Barbier Saint-Hilaire (CIR–INRETS)Thomas Durlin (Laboratoire LICIT, ENTPE–INRETS) Mohamed Said El Hmam (université d’Artois) Vincent Henn (Laboratoire LICIT, ENTPE–INRETS)Daniel Jolly (université d’Artois)Fabien Leurent (LVMT–INRETS–ENPC–UMLV), UPEHai-Dang Mai (LVMT–INRETS–ENPC–UMLV), UPEHichem Omrani (Heudiasyc–CNRS) Michel Parent (INRIA–Imara)Jean-Marie Proth (INRIA, SAGEP)

Institut National de Recherche sur les Transports et leur Sécurité

Direction scientifique / politique éditoriale - Aude Lauby 25, avenue François Miterrand Case 24, F-69675 Bron CEDEX, France. Tél. : +33 (0)4 72 14 23 00 – Fax : +33 (0)4 72 37 68 37 - www.inrets.fr

© Les collections de l’INRETS N ° ISBN 978-2-85782-665-1 N° ISSN 0769-0266

En application du code de la propriété intellectuelle, l’INRETS interdit toute reproduction intégrale ou partielle du présent ouvrage par quelque procédé que ce soit, sous réserve des exceptions légales

Actes INRETS n° 118 3

Fiche bibliographiqueUR (1er auteur)

GRETIA

Projet N° Actes INRETS N° 118

Titre

Modèles de trafic

Sous-titre

Actes du groupe de travail, 2006

Langue

Français

Auteur(s)

Jean-Patrick Lebacque, Maurice Aron, Vincent Aguiléra

Rattachement ext.

UPE/INRETS–GRETIA UPE/ENPC–LVMT

Nom adresse financeur, co-éditeur N° contrat, conv.

Date de publication

Décembre 2008

Remarques

Résumé

• F. Barbier Saint-Hilaire présente une version dynamique du modèle d’affectation par équilibre local, où les choix de deux catégories d’usagers sont modélisés par un Logit. Il étudie les pointes, leur évolution, situe la congestion du réseau en position et en importance.• A. Awashti calcule, pour nombre de conditions de trafic, les plus courts chemins dans un

réseau et classe les couples {plus courts chemins, conditions de trafic}. En temps réel, la condi-tion de trafic (connue) conduit à la plus proche classe, donc au plus court chemin.• F. Leurent, V. Aguiléra et H.-D. Mai affectent dynamiquement le trafic sur de grands réseaux,

grâce à un algorithme hybride « LADTA ». Les arcs du réseau sont chargés de façon chronolo-gique.• M.S. El Hmam, H. Abouaïssa et D. Jolly développent un modèle de trafic hybride multiagents.

Un tronçon comporte des zones microscopiques et macroscopiques, un véhicule fictif assurant la transition.• F. Leurent définit et hiérarchise des indicateurs de confort et de qualité de service en transport

collectif urbain ; il modélise l’existence de places assises. Il propose un plan d’implémentation.• F. Leurent représente génériquement par des « hyperchemins » les modes de transport dans

un réseau plurimodal en tenant compte de la fréquence de desserte, du taux de disponibilité du mode, de la disponibilité des places assises.• F. Leurent propose une théorie des réseaux de services qui formalise et traite génériquement

le cheminement optimal sous contrainte ; les contraintes y sont représentées par une assertion logique, l’optimalité par une propriété logique, le caractère physico-économique du service par une fonction potentiel.• V. Henn et T. Durlin associent un modèle d’intersection à un modèle d’écoulement adapté à l’affec-

tation dynamique et calculent les ondes de choc, les restrictions locales de capacité, les retards.

Mots clés

Affectation dynamique, intersection, trafic routier, logit, qualité de service, transport collectif, plus court chemin, hybride, agent.

Nb de pages

172

Prix

15,24 €

Bibliographie

oui

4 Actes INRETS n° 118

Publication data formUR (1st author)Transportation Network Engineering and advance Informatics (GRETIA)

Projet N° INRETS proceedings N° 118

TitleTraffic Modelling

SubtitleProceedings of the seminar, 2006

LanguageFrench

Author(s)Jean-Patrick Lebacque, Maurice Aron, Vincent Aguiléra

AffiliationUPE/INRETS/GRETIAUPE/ENPC/LVMT

Number, Sponsor, co-editor Contract, conv. N°

Publication dateDecember 2008

Notes

Summary

• François Barbier Saint-Hilaire makes a dynamic version of the Assignment by Local Equilibrium software. A logit models the choices of two end-user categories. This allows for studying peaks, their evolution, for locating the congestion and assessing its extent.• In a beforehand clustered network, Anjali Awashti computes, for a lot of traffic conditions, the

shortest paths, then classes the couples {shortest path, traffic conditions} ; in the real time the (known) traffic condition leads to the nearest class, then to the shortest path.• Fabien Leurent, Vincent Aguiléra, Hai-Dung Mai dynamically assign the traffic on large

networks thanks to a hybrid algorithm “LADTA”. The links are chronologically loaded according to the traffic.• Mohamed S. El Hmam, Hassane Abouaïssa, Daniel Jolly develop a hybrid traffic multi-agent

model, where sections have a microscopic and a macroscopic agent. A fictitious vehicle makes the transition.• F. Leurent defines comfort and service quality indicators for urban public transport. He models the

existence of available seats, makes a hierarchy of the quality factors, proposes an implementation plan.• Fabien Leurent models the route choice on a pluri-modal network, using the hyperpaths for

generically representing the traffic modes. He takes into account the service frequency at the stops, the mode availability rate, and the seat availability.• Fabien Leurent proposes a service network theory formalising and generically processing the

optimal constrained path. The constraints appear as logical assertions, the optimality as a logical property, the economic and physic features as a “potential” function.• Vincent Henn and Thomas Durlin associate an intersection model to a traffic flow model, well

suited for dynamic traffic assignment ; local capacity restrictions, shockwaves and traffic lights are computed.

Key wordsRoad traffic flow modelling, dynamic assignment, shortest path, logit, public transport, comfort, intersection, hybrid, agent.

Nb of pages172

Price

15,24 €

Bibliography

yes


Table des matières

Un modèle d’affectation dynamique pour expliquer la congestion récurrente dans les grandes métropoles 7

F. Barbier Saint-Hilaire

Un système de routage hiérarchique pour les réseaux urbains 25A. Awasthi, H. Omrani, M. Parent, J.-M. Proth

Convergence criteria and computational efficiency of a dynamic traffic assignment model 71

F. Leurent, V. Aguiléra, H.-D. Mai

Contribution à la modélisation et la simulation du flux de trafic : approche hybride basée sur les systèmes multiagents 93

M. S. El Hmam, H. Abouaïssa, D. Jolly

Confort et qualité de service en transport collectif urbain de voyageurs : analyse, modélisation, évaluation 113

F. Leurent

Modélisation du choix d’itinéraire sur un réseau plurimodal 137F. Leurent

Le réseau de services : théorie et application 143F. Leurent

Un modèle d’intersection pour l’affectation dynamique du trafic intégrant les retards 149

T. Durlin, V. Henn

Actes INRETS n° 105 7Actes INRETS n° 118 7

Un modèle d’affectation dynamique pour expliquer

la congestion récurrente dans les grandes métropoles

François Barbier Saint-HilaireCIR, INRETS, 2, avenue du Général-Malleret-Joinville, F-94114 Arcueil, France

Nature du problèmeLes modèles de prévision de trafic disponibles pour étudier la circulation sur

les grandes aires métropolitaines sont, pour la plupart, inadaptés dès que l’on s’intéresse aux phénomènes de congestion et à leur évolution. On sait faire des modèles dynamiques pour prévoir l’évolution du trafic sur des aires très limitées et avec une demande de trafic parfaitement fixée en volume et en itinéraires. A contrario, les modèles adaptant la demande de déplacement à l’offre, à la fois en volume et en itinéraire, utilisent des méthodes d’affectation statique et sont, de ce fait, inadaptés pour étudier l’évolution des phénomènes de congestion.

Pour s’en convaincre, voici un phénomène de congestion parfaitement symp-tomatique qui avait lieu en région parisienne en 1998. A15, l’une des autoroutes radiales de cette région, était, à l’époque, très mal connectée au reste du réseau principal. Depuis, un boulevard interurbain (BIP Ouest) a été ouvert, qui a atténué les phénomènes de congestion. Une autre caractéristique de cette autoroute est qu’elle n’est pas connectée directement au réseau autoroutier national, et, de ce fait, supporte essentiellement un trafic interne à la région.

Le présent article montre la démarche et les résultats obtenus en utilisant une approche globale sur la région avec un réseau déduit de celui de la DREIF. On montrera comment, pour résoudre ce simple problème local, on peut déduire une répartition horaire de la demande beaucoup plus pertinente et susceptible, pour les projections dans le futur, de tenir compte de l’effet des modifications de l’offre.



Données des comptagesLes données correspondent à un poste de comptage fixe sur l’A15 un peu

avant l’échangeur de Sannois. Elles correspondent aux relevés de 28 jours de semaine d’une station automatique fournissant à la fois des comptages horaires et des vitesses moyennes horaires. Une information sur les taux d’occupation était aussi fournie, mais s’est révélée inexploitable. Les données relatives au lundi matin ont aussi été abandonnées car elles présentaient des caractéristiques très différentes de celles des autres jours de la semaine.

Le diagramme débit–vitesse ci-après représente, pour chaque heure, les mesures élémentaires rattachées aux moyennes de chaque heure. Il a pour objet de montrer l’évolution de la congestion, entre six et dix heures, et la grande dis-persion des relevés pendant ces heures de congestion. Voici les caractéristiques principales :

La congestion démarre à 6 heures, mais l’état de l’autoroute demeure assez •fluide (45 km/h) avec un débit maximum (7500 véh/h) ; le trafic est très sta-ble en volume mais la vitesse est un peu instable.

Entre 7 heures et 9 heures, la congestion devient importante (24 km/h) pour •des débits faibles (5700 à 5500 véh/h) ; le trafic est, en fait, très instable à la fois en volume et en vitesse.

L’horaire suivant marque la fin de la congestion avec une vitesse moyenne •de 69 km/h pour un débit moyen de 6 400 véh/h ; le trafic est stable en volume mais très instable en vitesse.

Les autres heures sont toutes fluides, avec des vitesses moyennes supé-•rieures à 90 km/h. Tout au plus peut-on remarquer une légère instabilité en volume entre 19 et 21 heures ; cela montre que, plus loin en banlieue, la pointe du soir provoque aussi des congestions perceptibles malgré la fluidité de l’autoroute.

On doit retenir de ces relevés une pointe de trafic beaucoup plus matinale (6 heures et demi) que ne peut le laisser supposer les enquêtes déplacement. (Pour l’EGT 2001, la pointe de déplacement matinal a lieu à 8 heures et quart).

On remarque aussi l’inadaptation des relations vitesse–débit traditionnelles pour décrire les situations de congestion.

Nous nous sommes d’abord servi de ces données pour comprendre le fonc-tionnement du goulot d’étranglement provoqué par certaines bretelles de l’échan-geur de Gennevilliers à trois kilomètres en aval du capteur.

Mais même les modèles statiques utilisant des files d’attente (la demande écrêtée de Davis) et les faisant remonter sur les tronçons en amont (option Congestion) ne peuvent décrire cette évolution de la congestion.

F. Barbier Saint-Hilaire Affectation dynamique & congestion dans les grandes métropoles


Figure 1. Diagramme d’état

J’ai donc développé une approche dynamique à partir d’une formulation différentielle du premier ordre présenté dans le séminaire « modèles de trafic » de l’INRETS. On introduit la concentration comme le quotient du débit par la vitesse.

Figure 2. Diagramme débit-concentration

50

8000

7000

6000

5000

4000

3000

2000

1000

100 150 200 250 300 350 400Concentration (uvp/km)



La partie fluide du diagramme d’état reprend la formule utilisée dans Davis •en mode demande écrêtée ;

la partie saturée correspond au débit maximum du tronçon ;•

la partie congestionnée est représentée par une droite dans le diagramme concentration–débit. La pente de cette droite correspond à une vitesse d’infor-mation d’environ 18 km/h

Mais le modèle dynamique ainsi constitué ne peut toujours pas expliquer le phénomène observé. En effet, le débit moyen des trois premières heures (6 h à 9 h) de congestion (6 232 véh/h) étant plus faible que celui de la dernière heure de congestion (6 377 véh/h), la congestion devrait s’étendre entre 9 et 10 heures au lieu de se résorber.

L’explication ne peut se trouver qu’en considérant que les usagers n’ont pas tous le même comportement.

Processus du choix de l’horaire de déplacementEn représentant simultanément le trafic sur A15 vers Paris et le volume des

déplacements (VP) extrait de l’EGT 2001 (la précédente EGT donnait un résultat pratiquement identique), on voit la différence entre le désir des usagers et leur pratique réelle sur les axes congestionnés.

Figure 3. Comparaison entre trafic observé et l’extrait de l’Enquête Générale Transport

8000

7000

6000

5000

4000

3000

2000

1000

5h 6h

Volume du trafic

7h 8h 9h 10h 11h 12h 13h 14h 15h 16h 17h 18h 19h 20h 21h Horaire



La moyenne des comptages par heure est représentée en vert et est interpo-lée par quart d’heure selon la méthode d’AELD. Le volume déduit de l’EGT 2001 est mis à l’échelle pour obtenir le même volume de trafic 5 h–22 h.

Il est bien évident que cette comparaison doit rester qualitative, car on parle d’un côté de trafic tout type de véhicules sur une autoroute et, de l’autre, de déplacement motorisé VL de personnes. On remarque que :

La pointe de demande du matin (8–9 heures) est complètement estompée •en laissant paraître une pointe de trafic très matinale (6–7 heures) et un soubresaut vers 10 heures. Contrairement à ce qui est affirmé dans le dépouillement de l’EGT, il semble que la pointe du matin s’étale autant vers les heures matinales que vers les heures plus tardives.

La pointe de demande du soir est sensiblement estompée avec un fort ren-•forcement du trafic d’après-midi.

Cependant, la faible part du trafic interrégional utilisant cette autoroute peut inciter à considérer l’EGT comme une formulation des désirs de déplacements. J’avais, en collaboration avec Jean Delons, développé un modèle de choix horaire par répartition Logit pour expliquer la différence de charge de trafic que nous constations chaque matin entre le réseau autoroutier et le réseau de des-serte. C’est une variante de ce modèle que j’ai appliquée ici. Elle utilise le pos-tulat que les usagers ayant un déplacement de longue durée sont plus sensibles que ceux de courte durée au gain de temps apporté par un déplacement à une heure plus favorable.

Conséquences de l’instabilité du trafic pendant la congestion

On a vu que le trafic devenait instable en volume et en vitesse pendant la congestion.

Tableau 1. Instabilité du débit et du temps au kilomètre en congestion

Débit Temps au km

Horaires (h) Moyenne Écart-type Écart relatif Moyenne (s) Écart-type (s)

5 2652 ±163 ±0,06 38 ±0,6

6 7505 ±264 ±0,04 81 ±10,4

7 5694 ±775 ±0,14 156 ±28,6

8 5497 ±1130 ±0,21 161 ±42,8

9 6377 ±394 ±0,06 60 ±29,3

10 5799 ±275 ±0,05 40 ±1,5

Le modèle dynamique développé étant un modèle d’équilibre, on peut se poser la question de sa convergence vers une solution unique. On sait, pour les modèles satisfaisant les hypothèses de Wardrop (les temps de parcours des tronçons ne



dépendent que des usagers fréquentant ces tronçons) que ceux-ci convergent vers une solution unique. A contrario, dès qu’il y a congestion, c’est-à-dire que les files d’attente débordent d’un tronçon vers son prédécesseur et viennent ralentir tous les usagers de celui-là, qu’ils poursuivent leur chemin par le tronçon saturant ou non, les hypothèses de Wardrop ne sont plus remplies. On peut effectivement trouver des cas d’école où le modèle Davis avec congestions se met à osciller entre plusieurs solutions. Cela m’avait incité à ne pas promouvoir cette option pourtant seule capable de représenter l’état du trafic. Il en va de même de l’appro-che dynamique, dès que l’on se situe sur la partie congestionnée du diagramme fondamental. C’est peut-être une conséquence de la durée de la période prise pour le calcul qui peut entraîner un bouclage des phénomènes de congestion, alors que, mathématiquement, l’évolution de l’onde d’information de congestion ne peut toucher que des usagers postérieurs à ceux qui l’ont déjà subie. Or, dans la réalité, des phénomènes de thrombose généralisée du trafic ont été constatés et montrent que le bouclage de la congestion peut avoir des conséquences extrêmes.

Cependant, le but de la simulation n’est pas de trouver les solutions d’équi-libre, mais une solution moyenne représentative des phénomènes observés. Si une solution d’équilibre existe, on peut raisonnablement penser qu’elle est repré-sentative de la moyenne des cas observés, car temps et charge ont de bonnes propriétés additives. On peut donc mettre en œuvre des mécanismes d’amortis-sement tels que, même si la solution est oscillante, on trouve une solution voisine de la moyenne des solutions.

Pour la congestion, on parle de file d’attente débordant la fin du tronçon et, dans le cas, on sait que la moyenne de la longueur de débordement d’une file d’attente n’est pas égale à la longueur de la file d’attente moins la longueur pou-vant résider sur le tronçon :

E(max(x-y,0)) > E(x) – E(y)

Le diagramme fondamental affirme explicitement que le débit de sortie ne peut être supérieur à la capacité, et que si le débit d’entrée vient à dépasser cette capacité, il y aura création d’une contrainte d’offre et d’un ralentissement dans toute la zone régie par la contrainte d’offre (la file d’attente). Cela est une représentation déterministe du problème. Supposons maintenant que le débit de demande soit une variable aléatoire. Il y aura création d’un ralentissement significatif bien avant que le débit moyen d’entrée n’atteigne la capacité. Ce phé-nomène sera d’autant plus marqué que la variance du débit d’entrée sera forte. Si la variance des débits était homogène dans le temps et dans l’espace, il suffirait de diminuer légèrement la capacité pour compenser le phénomène en gardant une formulation déterministe beaucoup plus simple d’usage.

Malheureusement, l’écart relatif est considérablement plus fort aux heures où la congestion est établie (de 7 à 9 heures). Il faudrait donc moduler la capacité des tronçons en fonction de la variance prévisible du volume du trafic. D’où la proposition de cette règle simpliste :

tout tronçon a deux niveaux de capacité. Quand le débit d’entrée excède le débit maximum de sortie pendant plus d’une heure, le tronçon bascule en mode



dégradé et passe d’un état d’écoulement laminaire à un état turbulent avec, au terme de cette heure, un débit maximum de sortie plus faible.

En fait, on a conservé la valeur de la capacité comme débit maximum dégradé et appliqué un coefficient d’augmentation pour le débit maximum de sortie fluide.

Formulation de l’écoulement dynamique sous forme de modèle d’équilibre

La plupart des modèles d’affectation statique ont été conçus comme des modèles d’équilibre et, comme tels, ont reçu des solutions itératives déduites de la généralisation de la méthode de Frank-Wolfe. Citons :

chacun utilise son plus court chemin (principe d’équilibre individuel de •Wardrop) ;

chacun se comporte vis-à-vis des péages selon sa valeur du temps (exten-•sion stochastique du principe précédent) ;

chacun choisit son mode ou son heure de déplacement selon un processus •stochastique dont l’aléa suit une loi de Gumbel. (C’est le modèle Logit).

Mais dans ces modèles statiques, les performances de l’offre de transport (temps de parcours…) étaient directement fonction de la charge affectée, et leur calcul en cours du processus itératif ne posait pas de difficulté majeure. L’apparition de modèle plus dynamique, dont la demande écrêtée de Davis est une variante très simplifiée, a nécessité un processus de calcul progressif des files d’attente. C’est une généralisation de cette approche qui est utili-sée dans ce nouveau modèle dynamique. Débit et temps de parcours sont considérés comme des variables continues du temps, mais linéaires pendant la durée d’un intervalle. Cette durée est longue, car seules les moyennes horaires nous intéressent. En fait, la durée choisie est la moitié de l’intervalle de définition de la demande (une demi-heure pour une demande horaire) et la linéarisation des débits se fait sur un pas plus court (un quart d’heure) Cette transformation est visible sur la Figure 3 sur laquelle sont représentés simul-tanément le niveau des comptages sur A15 en vert et l’interpolation linéaire équivalente en noir.

Pour chaque tronçon, on déduit les temps de parcours de la valeur du débit à tout instant en utilisant une solution intégrée des équations différentielles régissant l’évolution dynamique du tronçon. Une fois calculés les temps de parcours, on doit recalculer les débits puisqu’on a modifié le tableau de marche des véhicules et leur horaire de passage sur les tronçons de leur itinéraire. C’est ce processus que nous appelons modèle d’équilibre de l’écoulement dynamique. Hors contrainte d’offre, le processus a une très forte convergence.



Prise en compte des contraintes d’offreEn fait, le résultat d’intégration du modèle différentiel doit être obtenu en

comparant, en tout point et tout instant, la demande cumulée qui résulte de l’arrivée des véhicules à l’entrée du tronçon et l’offre cumulée qui provient du débit maximum admissible en sortie à chaque instant. Cette contrainte d’offre en sortie associe les caractéristiques propres aux tronçons (capacité de sortie) et la congestion provenant des tronçons en aval. Comme pour la demande, la contrainte d’offre en sortie sera évaluée sous une forme continue et linéaire.

Au cas où l’offre sur un tronçon est particulièrement insuffisante, la contrainte d’offre cumulée remonte jusqu’à l’origine du tronçon. C’est la congestion. Et il faut reporter ce déficit d’offre sur les tronçons amont. Le modèle de congestion décrit la mécanique de ce report. En fait, on transforme ce déficit d’offre en un délai supplémentaire d’attente que l’on répartit sur les divers mouvements tournants du carrefour, puis on fait la transformation inverse au niveau des sorties des tronçons débouchant sur ce carrefour pour convertir les délais supplémentaires d’attente en détérioration de l’offre cumulée.

Ce processus de remontée de la congestion est une des composantes les plus sensibles du modèle d’équilibre de l’écoulement dynamique.

Calage du modèle DREIF sur les données des capteurs des heures matinales

Nous avons utilisé un réseau représentant la région parisienne en 1995 et fourni par la DREIF. Nous l’avons adapté à l’année 1998. Nous avons utilisé une matrice heure de pointe du soir 1995 et sa transposée pour représenter la demande matinale 1998. La répartition horaire a été déduite de l’EGT 2001, et le niveau global a été calé afin d’obtenir, pour le trafic matinal (5 heures–midi), un volume voisin de celui observé.

Tableau 2. Répartition de la demande matinale

Horaire Pourcentage matrice

HPS

Pourcentage matrice

transposée

Pourcentage de définition de la

demande à l’arrivée

Répartition de la demande

selon l’EGT 2001

5h 0 % 100 % 0 % 1,4 %

6h 0 % 100 % 20 % 5,6 %

7h 0 % 100 % 80 % 17,0 %

8h 0 % 100 % 80 % 32,1 %

9h 21 % 79 % 80 % 16,7 %

10h 42 % 58 % 70 % 12,7 %

11h 50 % 50 % 30 % 14,5 %



Le pourcentage de définition de la demande à l’arrivée traduit le fait que pour les déplacements domicile–travail, c’est l’heure de prise de poste qui détermine l’horaire souhaité du déplacement. Sauf pour la répartition de l’EGT, on a choisi des valeurs plausibles des autres pourcentages. Il a fallu adapter les paramètres du réseau, car les temps de parcours obtenus lors des premières simulations étaient tout à fait irréalistes :

par une augmentation très sensible des coefficients de la relation vitesse–•débit pour atténuer l’effet de la charge du réseau ;

par une augmentation très sensible des paramètres de généralisation du •temps (effet de la distance et coefficient de fiabilité) du réseau de desserte pour mieux équilibrer la concurrence entre autoroute et desserte ;

une augmentation considérable des capacités.•

Cette dernière phase a été la plus critique, car avant cette augmentation, on obtenait des congestions considérables au voisinage des émissions des zones périphériques et une pointe de trafic désespérément plate entre 6 et 11 heures sur l’autoroute A15. En augmentant uniformément les capacités de 20 %, la pointe de trafic est enfin apparue entre 6 heures et 7 heures confor-mément aux observations. Pour la bretelle d’accès de l’autoroute A15 vers l’autoroute A86, celle qui crée le principal goulot d’étranglement en l’absence du boulevard interurbain de Clichy (BIP Ouest), la capacité a dû être portée de 4 000 à 5 000 véhicules par heure pour obtenir la pointe désirée.

Mais outre le niveau global de la demande qui nous a permis de reconstituer le trafic global de l’autoroute pendant les sept heures de simulations, le principal élément de calage était les paramètres du pseudo-Logit de choix horaire. Le coefficient de latence qui mesure l’étalement du Logit a été pris à un quart d’heure faute d’information, et le tableau des pénalités de changement d’horaire a été recherché par tâtonnement en respectant une progressivité logique des comportements. Voici les valeurs en minutes qui nous ont paru satisfaisantes :

Tableau 3. Pénalités (en minutes) de changement d’horaire

5 h 6 h 7 h 8 h 9 h 10 11 h

5 h 0 40 50 60 70 80 90

6 h 30,7 0 18,2 26,5 34,8 43,1 51,4

7 h 33,6 12,8 0 18,2 26,5 34,8 43,1

8 h 36,5 15,7 12,8 0 18,2 26,5 34,8

9 h 39,4 18,6 15,7 12,8 0 18,2 26,5

10 h 42,3 21,5 18,6 15,7 12,8 0 18,2

11 h 45,2 24,4 21,5 18,6 15,7 12,8 0



Analyse des résultats sur l’autoroute A15 à Sannois

Voici, portés sur un même graphique, les résultats en débits et en vitesse. En fait, nous avons préféré représenter l’inverse de la vitesse, le temps de parcours au kilomètre, qui est une information plus facilement manipulable.

Figure 4. Débits et temps au kilomètre observés et modélisés, le matin

Pour les débits, la différence est représentée en rouge à chaque fois que la simulation donne un débit inférieur aux comptages et en vert dans le cas contraire. Pour le temps de parcours au kilomètre, la différence est représentée en rose à chaque fois que la simulation donne un temps inférieur aux observations et en bleu dans le cas contraire. L’écart-type des observations a été représenté par une barre sombre de part et d’autre de la moyenne. Ainsi, on peut considérer que la simulation est tout à fait satisfaisante, sauf une légère sous-estimation du débit de 9 heures (précédé par une surestimation à 8 heures). Pour les temps de parcours, on a une forte surestimation à 7 heures.

Bilan de la déformation de la pointe matinale

Nous avons représenté sur un même graphique, en pourcentage horaire, la pointe de demande et la pointe de trafic.



Les bilans horaires ont été lissés sous forme de ligne brisée continue, pour la lisibilité du graphique, à partir des mesures horaires (ou par demi-heure pour l’EGT) et des résultats par heure de la simulation :

l’EGT 2001 représente les déplacements désirés introduits dans le modèle ; •sa répartition est représentée en bleu clair ;

les comptages sur A15 sont représentés en bleu foncé.•

Pour les résultats de la simulation, nous avons distingué le trafic sur A15 pour le comparer aux comptages, et des résultats plus globaux comme le volume de déplacement selon leur horaire de départ, d’arrivée ou le kilométrage parcouru :

le trafic sur A15 est représenté en violet. L’évolution suit bien la valeur •des comptages en dehors de la légère ondulation de 8 heures et demi en avance par rapport à celle des comptages ;

le volume des déplacements au départ est représenté en orange. Il montre •un aplatissement très sensible de la pointe vers les heures matinales ;

le volume des déplacements à l’arrivée est représenté en vert. L’aplatissement •semble au contraire assez symétrique par rapport à l’EGT ;

le volume du trafic en véhicules * km est représenté en rouge. Il montre que •le trafic est beaucoup plus aplati que le volume des déplacements, avec une nette tendance à une surcharge matinale.

Figure 5. Pointes de la demande et du trafic



Bilan des attentes sur les principales autoroutes

La simulation n’a été calée que sur les informations disponibles sur A15 (débit et vitesse en un point). Nous allons montrer ici la pertinence des résultats pour l’ensemble du réseau. Nous avons distingué huit itinéraires pénétrant vers Paris et huit itinéraires en rocade.

Tableau 4. Temps de parcours et attente maximum sur les radiales vers Paris (simulation 1998)

ItinéraireLong.(km)

Temps de parcours (minute)Attente

maximum (minute)

5 h 6 h 7 h 8 h 9 h 10 h 11 h

A1 Roissy → Périf. extérieur 18,5 11 14 18 19 20 13 13 7

A3 Roissy → Périf. extérieur 20,3 14 19 20 23 22 18 16 7

A4 Lagny → Porte de Bercy 21,4 12 15 22 24 20 13 13 10

A6a Évry → Périf. intérieur 28,5 16 18 23 24 22 18 17 4

A10+A6b Les Ulis → Périf. ext. 24,8 14 16 18 19 17 17 16 1

N118 Les Ulis → Pont de Sèvres 22,6 13 15 21 24 19 15 15 8

A13 Mantes → Périf. extérieur 48,7 27 33 44 44 40 33 31 14

A15 Cergy → A86 Ouest 25,1 13 23 36 35 30 20 16 22

La simulation sous-estime beaucoup la congestion sur le sud-ouest parisien (A6, A10, no 118). Les attentes maximums, correspondant aux horaires en gras, sont plus précoces sur l’autoroute A15 et plus tardives sur l’autoroute A1.

Tableau 5. Temps de parcours et attente maximum sur les itinéraires en rocade (simulation 1998)

ItinéraireLong.(km)

Temps de parcours (minute)Attente

max. (minute)

5 h 6 h 7 h 8 h 9 h 10 h 11 h

Périphérique intérieur 35,1 25 27 29 33 31 27 27 5

Périphérique extérieur 34,9 26 27 29 33 31 27 28 3

A86 Nord Nanterre → La Courneuve 15,9 9 10 11 13 12 11 11 2

A86 Nord La Courneuve → Nanterre 15,5 9 11 15 18 15 11 10 7

A86 Est Bobigny → Carrefour Pompadour

17,8 9 11 19 22 16 10 10 11

A86 Est C. Pompadour → Bobigny 17,5 10 10 11 14 14 10 10 3

A86 N286 C. Pompadour → St Cyr 33,5 18 20 26 30 27 20 20 9

N286 A86 St Cyr → C. Pompadour 31,8 20 21 26 32 27 22 22 8

La congestion du périphérique semble sous-évaluée. Il faut noter que toutes les rocades intérieures sont plus congestionnées que les extérieures. Le nombre



de zones de congestion est beaucoup plus fort en rocades que pour les radiales. La simulation a identifié 21 zones de ralentissement sur le périphérique pour 70 km et 29 zones sur les A86 pour 132 km, alors qu’elle n’en a trouvé que 25 pour les 190 km de radiales. Cependant, nombre de ces ralentissements cor-respondent à des attentes extrêmement faibles. Ce sont en fait des résidus du processus de calcul itératif, signalant qu’une congestion est apparue au cours de la recherche de l’équilibre.

Figure 6. Congestion entre huit et neuf heures

Ce plan représente le résau principal francilien. Les sections coloriées en rouge représentent celles qui supportent une attente de plus de 15 s. En ocre les sections qui supportent une attente inférieure à 15 s. En noir le reste du réseau. L’épaisseur des traits est proportionnelle au débit. Le réseau secondaire est visualisé pour aider le repérage.



Différence entre les affectations statiques et dynamique

Figure 7. Distribution des tronçons selon la différence entre leurs affectations dynamiques et statiques de 5 heures à 9 heures

Solution de base DynamiqueSolution de base DynamiqueNombrede tronçons

Nombrede tronçons

70

60

50

40

30

20

10

60

50

40

30

20

10

Dynamique Dynamique

De 5 à 6 heures De 6 à 7 heures

Solution de base par Dynamique Solution de base par DynamiqueNombrede tronçons

Nombrede tronçons

100

75

50

25

70

60

50

40

30

20

10

Dynamique Dynamique


Le résultat de l’affectation dynamique apparaît comme une succession d’affectations d’apparence statique. Chacune d’elles contient la description des chemins utilisés par les usagers dont le déplacement démarre pendant l’horaire. Cependant, les débits calculés par le processus dynamique sont ceux relatifs aux usagers qui empruntent les voies pendant l’horaire. On peut donc comparer ces débits avec la charge que représente l’affectation des usagers



commençant leur déplacement de l’horaire. La comparaison entre les débits dynamiques et la charge statique caractérise les effets spécifiques de l’affec-tation dynamique.

On voit que l’affectation statique de 5 heures surestime systématiquement la charge du réseau (ici limitée au réseau principal). L’horaire suivant, 6 heures, le fait un peu moins tandis que 7 heures inverse la tendance. Pour 8 heures, on a une situation relativement équilibrée. Cependant, lorsque l’on regarde le péri-phérique, par exemple, on s’aperçoit qu’un sens est surchargé quand l’autre est déchargé.

Figure 8. Distribution des tronçons selon la différence entre leurs affectations dynamiques et statiques de 9 heures à 11 heures

Solution de base par DynamiqueSolution de base par DynamiqueNombrede tronçons

Nombrede tronçons

80

70

60

50

40

30

20

10

70

60

50

40

30

20

10

Dynamique Dynamique


Curieusement, on retrouve dans les deux horaires tardifs suivants, une situa-tion rencontrée entre sept et huit heures.

Diagramme d’état tel qu’il résulte du fonctionnement de la simulation

On a vu, au début de cet article, que le diagramme d’état, dans un plan reliant la concentration au débit, servait de support aux équations différentielles



définissant la dynamique des tronçons. Pour établir ce diagramme, nous avons utilisé les informations relevées sur A15. On peut maintenant vouloir comparer le diagramme avec le résultat de l’affectation. Pour avoir une vue suffisamment générale du fonctionnement du modèle, nous ne nous limiterons pas au seul tronçon relevé sur A15, mais nous intégrerons dans cette représentation tous les tronçons du réseau autoroutier de deux à cinq voies d’une longueur suffisante présentant, pendant au moins un horaire de la simulation, une attente significa-tive. Pour rendre les informations comparables, nous avons opéré sur les temps de parcours et les débits de la simulation des transformations ad hoc pour repré-senter un tronçon d’un kilomètre, d’une capacité de 8 000 véhicules et ayant un coefficient de courbe débit–vitesse de 0,95 (pour les voies sélectionnées, le coefficient varie entre 0,9 et 0,98).

Figure 9. Diagramme fondamental simulé

Débit d'entrée (uvp/)

8000

7000

6000

5000

4000

3000

2000

1000

50 100 150 200 250 300 350 400Concentration (uvp/km)

On remarque que les points de la simulation ont un débit qui dépasse la capa-cité et une concentration qui dépasse la droite de congestion. Ce résultat est dû au processus mis en œuvre pour tenir compte des aléas du trafic et qui revient à augmenter la capacité avant le début de la saturation.



Figure 10. Diagramme fondamental simulé après contraction des débits

Débit d'entrée (uvp/)

8000

7000

6000

5000

4000

3000

2000

1000

50 100 150 200 250 300 350 400Concentration (uvp/km)

Quelques points sont situés en dehors de l’épure. Cela signifie que la recher-che de l’équilibre n’est pas suffisamment avancée. En effet le processus itératif d’équilibre calculant la remontée de la congestion est parfois interrompu au bout d’un certain nombre de tentatives pour éviter les boucles.

Conclusions

La version dynamique du logiciel AEL (affectation par équilibre local) ouvre une réelle perspective pour l’étude des pointes et leur évolution dans le futur, quelle que soit l’adaptation de l’offre de transport. Elle permet de situer la conges-tion du réseau en position et en importance.

Les données à fournir au logiciel sont celles nécessaires à un modèle d’affec-tation statique. Il faut aussi des informations sur le choix de l’horaire des usagers. Mais des informations pertinentes sur les congestions les plus significatives per-mettent de caler le modèle.

Quant aux performances…, elles sont exactement équivalentes à celles d’un modèle statique que l’on aurait appliqué aux différents horaires.

Reste tout de même un bémol : le logiciel est très sensible aux erreurs de description du réseau et, en particulier, à la sous-évaluation des capacités des voies.


Un système de routage hiérarchique pour les réseaux urbains

Anjali Awasthi1 (Corresponding author), Hichem Omrani2, Michel Parent3,

Jean-Marie Proth

1. Centre for Operations Excellence, Sauder School of Business,

209 - 2053 Main Mall, University of British Columbia, Canada V6T 1Z2

Tél. +1 604 822 5267 ; fax (001) 604 822 1544

E-mail : [email protected]

2. UMR CNRS UTC 6599 HeuDiaSyC,

Centre de recherches de Royallieu, BP 20529, Compiègne cedex, France

Tél. : +33 3 44 23 49 53 (poste 4953)

Email : [email protected]

3. INRIA Rocquencourt, Project - IMARA, 78153 Le Chesnay cedex, France

Tél. : +33 1 39 63 55 93 ; fax +33 1 39 63 54 91


4. INRIA/SAGEP, bureau 410, UFR scientifique, université de Metz,

Île du Saulcy, 57012 Metz, France

Tél. : +33 3 87 31 54 58 ; fax : +33 3 87 31 54 78


Résumé :

Cet article présente un système de routage hiérarchique pour calculer les chemins les plus rapides sur les réseaux urbains. Le système est modulaire et composé de trois modules dont les fonctions sont :

• décomposition d’un réseau urbain en sous-réseaux de taille raisonnable ;

• définition de la séquence de sous-réseaux à visiter pour arriver à destina-tion ;

• optimisation du temps de trajet dans chacun des sous-réseaux.

L’objectif du premier module est de décomposer le réseau urbain en sous-réseaux de taille raisonnable aussi indépendants les uns des autres que pos-sible, c’est-à-dire ayant un nombre de connexions aussi faible que possible. En d’autres termes, nous voulons minimiser les flux entre les sous-réseaux.



Le deuxième module a pour objectif de trouver la séquence de sous-réseaux à visiter afin d’arriver à une destination donnée à partir d’une origine quelconque. La programmation dynamique est utilisée dans ce module. Le troisième module a pour but de calculer les chemins à l’intérieur des sous-réseaux en utilisant la classification hybride. Deux méthodes, notamment la classification automatique, encore appelée méthode des nuées dynamiques, (k-means clustering) et la clas-sification hiérarchique de Ward (Ward’s hierarchical agglomerative clustering) sont utilisées pour la classificaton hybride. Les données auxquelles est appliquée la classification hybride sont générées à partir d’un logiciel de simulation du trafic que nous avons développé.

L’avantage de notre approche est la possibilité de calculer les chemins les plus rapides sur de grands réseaux en temps réel sous des conditions de trafic dynamique. Finalement, nous montrons l’applicabilité de notre approche sur un exemple réel.

Mots clés : Modélisation, simulation de trafic urbain, décomposition des gra-phes, techniques d’analyse des données

Abstract :

This article presents a route guidance system for computing fastest paths on large networks. The approach proposed is modular in natures and consists of :

• decomposition of large network into reasonably sized small sub-networks ;

• finding the sequence of sub-networks to be visited ;

• optimisation of travel time inside each of the sub-networks.

The objective of the first module is to decompose the large network into small subnetworks of reasonable size which are as independent from one other as possible i.e. have least number of interconnections. In other terms, we want to minimize the flow between the subnetworks. The second module has the objective of finding the sequence of subnetworks to reach the destination from any given origin. Dynamic programming is used in this module. The objective of third module is to find the paths inside subnetworks using hybrid clustering. Two methods namely, the k-means clustering and the Ward’s hierarchical agglomera-tive clustering are used for hybrid clustering. The data used for hybrid clustering is generated using a traffic simulation software developed in-house.

The advantage of our approach is that it allows computing fastest paths on very large networks in real time under dynamic traffic conditions. Finally, we show the applicability of our approach using a real example.

Keywords : Modelling, traffic simulation, graph partitioning, data analysis

A. Awashti Routage dynamique pour les réseaux urbains


1. Introduction

Les problèmes de transport deviennent de plus en plus complexes. Cette complexité est due à l’accroissement du nombre de véhicules, ce qui exige une gestion d’une sophistication croissante, donc non seulement des modèles de plus en plus diversifiés, mais aussi l’arrivée de nouveaux types de systèmes de transport comme, par exemple, l’introduction récente des systèmes de transport en libre service ou des véhicules filoguidés.

Les réseaux urbains sont de grande taille. La décomposition d’un réseau en sous-réseaux de taille réduite n’est pas un nouveau problème. Cette méthode a été largement utilisée pour transformer la résolution de problèmes combinatoires de grande taille en ensembles de problèmes de taille réduite, les solutions ainsi obtenues étant ensuite combinées de manière généralement heuristique pour obtenir une « bonne » solution globale. La partition d’un réseau est un problème NP-Complet. Ce problème n’est donc pas soluble en un temps raisonnable. C’est pourquoi, compte tenu de l’importance du problème, de nombreuses approches heuristiques ont été développées. Ces heuristiques peuvent être classées en plu-sieurs catégories : les heuristiques géométriques, les heuristiques combinatoires, les heuristiques spectrales et les heuristiques multiniveaux [16–22].

La recherche du chemin le plus rapide entre deux points ne serait que la recherche du chemin le plus court si le système n’évoluait pas dans le temps. Il suffirait en effet de remplacer les longueurs des arcs par les temps nécessaires pour les parcourir et utiliser un algorithme classique de recherche du plus court chemin. Malheureusement, ces temps de transport varient avec l’état du sys-tème, lequel varie avec le temps. Nous ne pouvons donc pas nous contenter de calculer le meilleur chemin au moment où le véhicule démarre et conserver ce chemin jusqu’à l’arrivée au point souhaité. Cela explique pourquoi nous n’utili-sons pas les algorithmes classiques de recherche du plus court chemin.

Il est cependant intéressant de citer les derniers développements importants dans le domaine. Nous en retenons deux. Il y a d’abord les travaux de Zhan [53] qui se sont traduits par trois algorithmes, notamment le graph growth algorithm implemented with two queues, le Dijkstra algorithm implemented with approxi-mate buckets, et le Dijkstra algorithm implemented with double buckets. Puis, les travaux de Smith et al. [51] proposant une approche hiérarchique pour les réseaux de transport de taille importante.

Les travaux les plus marquants dans l’utilisation de l’analyse des données [43,44,49] dans les problèmes de transport sont les suivants :

l’approche proposée par Kohonen [40,48,50] basée sur les réseaux neuro-•naux avancés pour la prédiction du comportement de la circulation ;

les travaux de Park et Rillett [55] pour la prédiction du comportement d’un •système de transport à la convergence de voies à grande circulation ;

le travail bibliographique de Dougherty [45] s’intéressant à l’utilisation des •réseaux neuronaux dans les problèmes de transport ;



Ces trois derniers travaux utilisent l’approche SOFM (self organizing feature maps) pour transformer un ensemble de signaux en une carte à une ou à deux dimensions.

Kisgyorgy et Rillett [47] utilisent SOFM pour classer les vecteurs d’entrée •en faisant en sorte que ceux d’une même classe aient des composantes similaires.

L’idée que nous développons dans cet article est de décomposer les réseaux en sous-réseaux, puis de procéder en deux étapes :

imposer la séquence de sous-réseaux par lesquels passera le chemin ; —

optimiser les chemins à l’intérieur de chaque sous-réseau au moment où —le véhicule y pénètre.

Comme nous allons le voir dans l’article, la méthode que nous utilisons a pour objectif d’adapter le chemin conseillé au véhicule à l’évolution de l’état de réseau de transport. Cette approche fait intervenir des techniques d’analyse des données qui permettront, périodiquement, de générer le chemin en fonction d’un nombre limité d’éléments du système.

La méthode que nous appliquons pour l’analyse de données est nommée « classification hybride ». La méthode de classification hybride consiste à utiliser d’abord l’analyse des correspondances multiples qui met en évidence les fac-teurs principaux contenant le plus d’informations. La seconde phase consiste à réduire l’espace des variables, ce qui conduit à représenter chaque simulation et ses résultats par un nombre réduit de variables significatives, ou si nous préfé-rons, par des points situés dans un espace de dimension réduite. Ces points sont alors classés par une méthode de type « nuées dynamiques » afin de réduire leur nombre. Une méthode de type classification hiérarchique permet ensuite de réduire encore le nombre d’éléments. Enfin, une étape d’analyse canonique recherche, dans chaque classe, les éléments réellement corrélés : c’est l’étape permettant de relier des variables d’entrée aux caractéristiques des chemins. Le but de l’analyse est alors atteint.

Les données utilisées pour la classification hybride sont générées à partir d’un logiciel de simulation du trafic. Selon le niveau de détails, on trouve en théorie quatre catégories de modèles de simulation de trafic : les modèles submicrosco-piques [24,25], les modèles microscopiques [26,27], les modèles mésoscopiques [28–30] et les modèles macroscopiques [31–38]. Notre modèle est basé sur l’approche macroscopique.

1.1. Rappel de la méthode

Notre méthode de guidage est de type hiérarchique. Le réseau de transport urbain nous intéressant est d’abord partitionné en sous-réseaux de taille raison-nable et qui sont aussi indépendants les uns des autres. Le trajet d’un point du réseau global à un autre point de ce même réseau passera habituellement par une séquence de sous-réseaux. L’efficacité de ce chemin global suppose que les caractéristiques de l’état du système restent invariantes tout au long du trajet, ce



qui n’est évidemment pas le cas. Il convient donc de mettre à jour la trajectoire tout au long du trajet. Cela se fera de deux manières chaque fois que le véhicule pénètre dans un nouveau sous-réseau : d’une part, en recalculant, comme indiqué ci-dessous, la suite des sous-réseaux qui restent à visiter pour atteindre la fin du trajet (chemin global) et, d’autre part, en calculant dans le détail, en tenant compte de l’état réel du système, le chemin le plus rapide pour rejoindre le point de sortie du sous-réseau dans lequel le véhicule vient de pénétrer (ou la fin du trajet), que nous appelons chemin local. La Figure 1 schématise cette approche.

Dans l’exemple de la Figure 1, le réseau a été décomposé en six sous-réseaux notés R1 à R6. Le véhicule considéré part du point I et souhaite rejoindre le point O. À l’entrée du véhicule dans R1 (point I), le chemin global conduisant de I à O est calculé. C’est le chemin IABO. La sortie A du sous-réseau R1 étant connue, nous calculons le chemin local C1 en utilisant la mémoire construite comme indiqué plus loin : c’est le chemin qu’empruntera le véhicule. Lorsque le véhicule arrive en A, nous calculons le nouveau chemin global conduisant en O : c’est le chemin ABO. Nous calculons ensuite le chemin local C2. Enfin, le chemin local C3 entre B et O sera calculé. La méthode utilisée est donc de type plan glissant.

Figure 1. Guidage dynamique



1.2. Le Système d’aide à la circulation urbaine

Le système dont il est question est hiérarchisé. Dans un premier temps, un chemin s’exprimant comme une séquence de sous-réseaux à visiter est calculé à partir de données statistiques sur des tranches horaires et des jours similaires au jour et à la tranche horaire considérés. Ce premier calcul implique :

la mise en place d’un algorithme efficace de décomposition d’un réseau •urbain en sous-réseaux de taille raisonnable et aussi peu connectés que possible les uns aux autres. Ce module est désigné par « DECOM-RESEAU » ;

une étude statistique donnant, en fonction de la journée et de la tranche •horaire, le temps moyen nécessaire pour se déplacer de chaque entrée à chaque sortie de chaque sous-réseau. Nous désignons ce module par « ETUDE-1 » ;

la recherche du chemin le plus court faisant intervenir les entrées et les •sorties de sous-réseaux. Ce module est noté « C-CHEM ».

Le second niveau hiérarchique consiste à trouver, « en temps réel », le che-min le plus rapide joignant une entrée d’un sous-réseau à une sortie de même sous-réseau. Cet aspect nécessite le développement des modules suivants :

la mise en place d’un système de simulation qui permettra de générer les •données nécessaires à l’analyse du système physique. Bien entendu, il est possible d’utiliser un des nombreux logiciels existants, mais l’étude que nous avons menée exigeait la maîtrise du système de simulation. Nous avons donc développé notre propre logiciel dans le module « SIM » ;

une étude statistique sur les flux d’entrée dans le réseau et les encombre-•ments des voies. Cette étude a pour objectif d’évaluer les probabilités cor-respondant aux différentes situations. Les simulations seront effectuées à partir de situations initiales générées en accord avec ces probabilités. Nous désignons ce module par « ETUDE-2 » ;

enfin, l’analyse des données est utilisée pour constituer une mémoire dans •laquelle le système puisera pour obtenir le chemin le plus rapide entre une entrée et une sortie d’un sous-réseau. Ce module, noté « ANA-DO », constitue une nouveauté dans le domaine de l’aide à la circulation urbaine. Il représente le point fort de ce travail.

La Figure 2 schématise les modules du système d’aide à la circulation urbaine.



Figure 2. Système de routage hiérarchique

Dans cet article, nous nous concentrons sur les modules « DECOM-RESEAU », « SIM » et « ANA-DO ».

2. Prédiction de chemins les plus rapides

Cette section présente en détail plusieurs composantes de notre système de routage. La première section est dédiée à la décomposition de réseaux routiers (« DECOM-RESEAU »). La deuxième section présente le logiciel de simulation utilisé pour générer les données du trafic (« SIM »). Finalement, dans la troi-sième section, nous présentons les techniques d’analyse des données afin de calculer les chemins les plus rapides sous les conditions de trafic dynamique (« ANA-DO »).

2.1. Décomposition d’un réseau urbain

L’algorithme de partitionnement que nous présentons dans le paragraphe suivant pourrait être classé dans les heuristiques combinatoires [17–20]. Une première heuristique par regroupements progressifs (HRP-1) est présentée dans la section suivante.

2.1.1. Généralités

Nous disposons d’un réseau de très grande taille que nous voulons partition-ner en sous-réseaux :

aussi peu connectés que possible les uns aux autres. En d’autres termes, •nous souhaitons aboutir à un nombre aussi limité que possible de nœuds



limites ou nœuds frontières. Ces nœuds sont ceux par lesquels un véhicule entre (ou sort) d’un sous-réseau ;

de taille limitée, c’est-à-dire comportant un nombre raisonnable de nœuds.•

Nous voulons limiter le nombre de nœuds frontières, car l’étude préparatoire que nous menons par la suite exige que, pour chaque sous-réseau, nous fas-sions une étude détaillée de tous les couples constitués d’un nœud d’entrée dans le sous-réseau et d’un nœud de sortie du même sous-réseau.

2.1.2. L’algorithme HRP-1

L’idée de base de cet algorithme est d’explorer, à chaque itération, toutes les paires de sous-réseaux connectés et de remplacer une de ces paires par la réunion des deux sous-réseaux. La paire de sous-réseaux qui seront réunis sera celle qui conduit au sous-réseau de plus faible densité de connexion. Nous examinons les paires de sous-réseaux :

qui sont composées de sous-réseaux connectés, c’est-à-dire tels qu’au •moins un arc a son origine dans un des sous-réseaux et son extrémité dans l’autre ;

dont la somme des nombres de nœuds ne dépasse pas une valeur donnée •par l’utilisateur ;

dont les densités des sous-réseaux sont supérieures à une valeur donnée •par l’utilisateur. La densité d’un sous-réseau est le rapport du nombre de nœuds qui connectent ce sous-réseau à un autre par le nombre de nœuds du sous-réseau. Si cette densité est petite, ce sous-réseau est relativement isolé, et nous ne cherchons pas à l’unir à un autre sous-réseau.

Remarquons cependant que si nous choisissions une densité limite trop importante, alors nous forçons les sous-réseaux à avoir un nombre important de connections. Cette densité devra donc être choisie avec soin.

Évidemment, cette densité ne peut être supérieure à 1 : cela signifierait que nous sommes intéressés par des sous-réseaux qui ont plus de nœuds frontières que de nœuds internes, ce qui est bien entendu impossible.

Algorithme HRP-1

A. Introduction des données

On introduit :

N : Nombre de nœuds du réseau.

E : Ensemble des arcs du réseau.

H : {n1, n2, n3, ..nN} ensemble des nœuds du réseau.

Q : Densité minimale des connexions d’un sous-réseau à considérer pour un regroupement. Par définition, la densité des connexions d’un sous réseau rk s’écrit q(rk) = C(rk)/ card(rk) où C(rk) est l’ensemble des nœuds



n’appartenant pas à rk qui sont origines (respectivement extrémités) d’un arc dont l’extrémité (respectivement l’origine) appartient à rk.

W : Nombre maximal de nœuds dans un sous-réseau.

B. Initialisation

Faire K = N.•

K• est la variable qui contiendra à chaque instant le nombre de sous-réseaux.

Pour • k 1, 2, …, K, faire rk = {k}.

Initialement chaque sous-réseau est composé d’un nœud.•

Pour • k = 1, 2, ..., K, faire

C. Calculs

1. Faire n = 0.

2. Pour i = 1 à K – 1.

Pour j = i + 1 à K.

Si (ri et rj sont connectés) et (card(ri) + card(rj) ≤ W) et (q(ri) > Q) et (q(rj) > Q)

Faire n = n + 1.s•

Faire • .

Calculer •

Si (n = 1) faire•

.

.

.

.

Si (n > 1) et • , faire

Set .

.

.

.



3. Si n = 0, arrêt. Imprimer pour k = 1,2, …, K. Fin de l’algorithme.

4. Faire .

5. Faire .

6. Si faire :

Pour i = à K − 1 faire et .

7. K = K − 1.

8. Aller en 1.

Les étapes 4 à 8 ont pour objectif de remplacer les deux sous-réseaux qui ont été réunis par le sous-réseau résultant.

2.1.3. Complexité de l’algorithme

La complexité de l’algorithme HRP-1 est calculée dans le plus mauvais cas (worst case). La complexité de l’algorithme est calculée de la manière suivante :

calcul de la complexité de chaque étape de l’algorithme ;•

calcul de la complexité totale de l’algorithme.•

Considérons l’algorithme HRP-1. Supposons que l’étape A de HRP-1 nom-mée ‘Introduction des données’ prend t1 unités de temps. L’étape B de HRP-1

nommée « Initialisation » prend où t2 et sont les temps pour

l’initialisation de rk et q(rk) respectivement. Dans l’étape C nommée « Calculs », admettons que les étapes numéro 1, 4, 5, 7, 8 prennent chacune 1 unité de temps (total = 5 unités de temps). Comme les calculs des étapes 2 sont effectués

fois, donc le temps de calcul pour l’étape 2 est

où nous supposons que chaque boucle de l’étape 2 prend t3 unité de temps. Les temps de calculs pour l’étape 3 et l’étape 6 sont Nt4 et (N-1) t5 où t4 représente le temps requis pour imprimer les sous-réseaux obtenus à la fin de l’étape 2 et t5 représente le temps de calcul des poids et densités des sous-réseaux eux-mêmes influencés par l’intégration des sous-réseaux à chaque itération.

Comme la boucle contenant l’étape C peut être exécutée N fois au maximum, la complexité totale de l’algorithme HRP-1 est donnée par :

Donc, dans le plus mauvais cas, la complexité de l’algorithme HRP-1 est O(N3), où N est le nombre total de nœuds du réseau.



2.1.4. Expérimentation numérique

L’algorithme HRP-1 a été appliqué sur une partie de réseau routier de Paris (Figure 3). Il contient 690 nœuds et 1 116 arcs. Le Tableau 1 présente les résul-tats de quatre catégories d’expérimentation faits sur le réseau parisien. Dans la première catégorie, la taille de sous-réseau W a été mise à son maximum i.e. W = 690. Dans la deuxième catégorie, la densité Q et la taille W ont été mises à leur maximum i.e. W = 690 et Q = 1. Dans la troisième catégorie, le critère de densité a été éliminé i.e. Q = 0 et le critère de taille a été mis à sa valeur maxi-male i.e. W = 690. Finalement, dans la quatrième catégorie d’expérience, nous avons mis Q = 0,5 et W = 50.

Tableau 1. Expérimentations sur le réseau parisien

N = 690 ; E = 1116

Q = 0,8W = 690

Q = 1 W = 690

Q = 0 W = 690

Q = 0,5W = 50

B = 0,055073T = 3 535P = 110

EC = 409

B = 0,04638T = 3 540P = 128

EC = 452

B = 0,997T = 3 906

P = 2EC = 0

B = 0,942T = 4 118

P = 67EC = 309

T = Temps d’exécution (en secondes) P = Nombre de partitions W = Taille maximale de sous-réseau B = Balance Q = Densité maximale de sous-réseau N = Nombre de nœuds E = Nombre des arcs EC = Edge-cuts

Figure 3. Réseau parisien



Il est clair, en considérant le Tableau 1, que le nombre de sous-réseaux est maximum quand Q = 1 et W = 690 et minimum quand Q = 0, W = 690. Ces deux cas sont les extrêmes, car, dans le premier cas, nous prenons la valeur maximale pour le critère de densité i.e. Q = 1 tandis que, dans l’autre cas, nous avons presque éliminé le critère de densité en mettant Q = 0. On peut voir aussi que le temps de calcul diminue avec l’augmentation de la densité. Les meilleures partitions sont obtenues quand les deux critères i.e. densité et taille des sous-réseaux sont relaxés, i.e. Q = 0, W = 690.

2.2. Simulation du trafic

Cette section présente l’approche de simulation du trafic pour générer les don-nées qui seront ensuite utilisées pour calculer les chemins les plus rapides dans les sous-réseaux obtenus par HRP-1 en utilisant l’analyse des données.

2.2.1. Définitions

Nous représentons le réseau de transport par un graphe orienté G = (N, A), où N représente l’ensemble de nœuds et A l’ensemble des voies orientées. Désignons l’ensemble des points d’entrée par E et l’ensemble des points de sortie par D. Nous représentons le point d’entrée par l’index e et le point de des-tination par l’index d. Le flux d’entrée arrivant par le nœud au temps t est donné par .

Figure 4. Système à voie unique

Considérons le système à voie unique représenté dans la Figure 4. Une voie unique est notée (i, j) où i représente l’entrée et j représente la sortie. Notons l’ensemble des nœuds prédécesseurs d’un nœud i par Pr(i) et l’ensemble des nœuds successeurs de i par Sc(i). Chaque arc (i, j) a trois attributs : sa longueur

, sa capacité à absorber le trafic et le nombre de véhicules présents sur la



voie à l’instant t noté . La capacité représente le nombre maximum de

véhicules pouvant être accumulé dans l’arc au temps t. Le flux d’entrée arrivant au point d’entrée de l’arc (i, j) est noté par . Dans le cas d’un arc à une

voie, . Le flux qui réussira à entrer dans l’arc est noté par .

La capacité d’entrée de l’arc est notée . La proportion du flux arrivant au

nœud i et qui va être dirigée vers le nœud j est représentée par . Le flux

sortant de l’extrémité j de l’arc au temps t est noté . La capacité de sortie

de l’arc est notée . Le nombre de véhicules attendant à l’entrée du nœud

est représenté par . La durée du trajet (i.e. le temps nécessaire pour

parcourir l’arc (i, j)) est notée . L’instant où l’état de l’arc (i, j) change est noté

. En régime permanent (steady state), le flux parcourt l’arc (i, j) à une vitesse constante , mais cette vitesse dépend des paramètres qui définissent l’état du

système entre deux changements consécutifs de cet état.

Le but est d’analyser le comportement du réseau à flux d’entrée constants par morceaux en tenant compte de l’état initial du système. L’analyse du système est ensuite appliquée au réseau entier afin de prévoir la durée de trajet sur plusieurs chemins du réseau.

2.2.2. Analyse d’un système à voie unique

2.2.2.1. Hypothèses

Avant d’analyser le système avec flux d’entrée restant constant à des interval-les de temps successifs, nous faisons les hypothèses suivantes :

les véhicules ne se dépassent pas. Cela implique que les véhicules doivent •suivre la règle first in first out (FIFO) durant le déplacement sur l’arc ;

si un véhicule n’est pas retardé, il se déplace à une vitesse constante.•

Désignons l’instant initial par : c’est l’instant auquel l’étude commence. À

l’instant , nous connaissons le nombre de véhicules présents sur chaque arc

du système , la longueur de l’arc , sa capacité , la vitesse des véhi-

cules , la proportion du flux arrivant au nœud i et qui est dirigée vers le

nœud j (en tenant compte de la capacité de l’arc (i, j)), le nombre de véhicules

en attente au niveau du nœud du réseau, le flux d’entrée

arrivant au nœud du réseau (nous supposons que est connue pour

et reste constant sur ) et la capacité de sortie qui représente

le flux maximal qui peut quitter l’arc. Nous connaissons l’évolution de la capacité

de sortie pour et supposons que la capacité reste constante sur et

que la capacité d’entrée , qui est une fonction de l’état de l’arc (i, j) et



de la capacité de sortie de l’arc. est le flux maximal qui peut entrer

dans l’arc (i, j). Le temps est l’instant jusqu’auquel le flux d’entrée et la

capacité de sortie restent constants et .

2.2.2.2. Analyse d’une voie unique

Considérons la voie unique représentée dans la Figure 4. Quand le flux d’en-trée ne dépasse pas la capacité de l’arc, le système ne sera pas congestionné. C’est la situation idéale : les flux d’entrée vont arriver à leur destination en un temps minimal. Cependant, quand le flux observé dans le système dépasse la capacité de sortie de l’arc, le nombre de véhicules dans l’arc augmente. Supposons que le flux reste constant sur . Dans ce cas, le nombre de véhi-

cules présent dans l’arc au temps t est :

(1)

Analysons maintenant un système à voie unique, avec un flux d’entrée constant par morceaux et une capacité de sortie de l’arc. Nous utilisons plusieurs cas pour étudier le système d’une voie unique. L’étude du système est divisée en deux cas. Dans le premier cas, l’arc n’est pas saturé à l’instant initial et dans le deuxième cas, en revanch,e l’arc est saturé. Ces deux cas peuvent être encore divisés en plusieurs sous-cas selon l’interaction entre le flux d’entrée, la capacité de sortie et l’état de la voie unique. La description de plusieurs cas et de sous-cas est présentée dans les paragraphes suivants :

Cas 1 : c’est le cas quand l’arc n’est pas saturé, i.e. (voir

Figure 5). Dans ce cas, la capacité d’entrée de l’arc est .

Figure 5. Cas où la voie n’est pas saturée (cas 1)



Cas 1.1. : c’est le cas où . Dans ce cas, le flux qui arrive au point

d’entrée de l’arc est supérieur ou égal à la capacité d’entrée . Sous cette condi-

tion, le nombre de véhicules pouvant entrer dans la voie à chaque unité de temps

est limité à la capacité d’entrée de l’arc.

(2)

Le nombre de véhicules en attente au point d’entrée augmente de

à chaque unité de temps. Ces véhicules en attente bloquent le

flux arrivant à l’entrée de l’arc. Par conséquent, les véhicules arrivant au nœud d’entrée s’ajoutent aux véhicules déjà en attente. Quand un flux d’entrée vérifiant

arrivera à l’entrée de l’arc, alors la file commencera à disparaître. Le

flux de sortie de l’arc est :

(3)

Le temps de trajet pour les véhicules qui occupent l’arc est :

Il est clair que le temps du trajet dépend de l’état initial du système et du flux

de sortie de l’arc. Si le flux vérifie , alors le temps de trajet sur

l’arc est minimal et est égal à . Si , alors le temps de trajet

des véhicules dépend de la capacité de sortie de l’arc et est supérieur à

. La vitesse du véhicule sortant de l’arc est :

.

Le nombre de véhicules dans le système à l’instant est obtenu en

utilisant les équations (2-3) dans (1) :



Si le flux se poursuit, alors l’arc sera plein à l’instant :

L’état du système changera à l’instant .

Cas 1.2. : c’est le cas où . Il représente le cas 1.2. de la Figure 5.

Dans ce cas, le flux qui arrive au point d’entrée de l’arc est inférieur à la capacité

d’entrée . Sous cette condition, tous les véhicules arrivant au point d’entrée de

l’arc durant chaque unité de temps sont donnés par :

(4)

Le flux de sortie de l’arc est .

Cas 1.2.1. : c’est le cas où . Il représente le cas 1.2.1. de

la Figure 5. Dans ce cas, le flux qui sort de l’arc ne dépasse pas la capacité de

sortie de l’arc. Sous cette condition, le flux de sortie est donné par :

(5)

Le temps de trajet pour les véhicules situés dans l’arc est

Dans ce cas, le temps de trajet des véhicules sur l’arc est minimal, car le flux d’entrée et le flux de sortie ne dépassent pas les contraintes de capacité de l’arc.

La vitesse des véhicules sortant de l’arc est . Le nombre de véhicules

dans le système au temps est obtenu par les équations (4-5) et l’équa-

tion (1) : . Le système va atteindre

l’équilibre avec un flux de sortie égal au flux d’entrée au temps . L’état

du système changera au temps .



Cas 1.2.2. : c’est le cas 1.2.2. de la Figure 5, où . Dans ce

cas, le flux qui sort de l’arc dépasse la capacité de sortie de l’arc. Sous

cette condition, le flux de sortie est . Le temps de trajet

pour les véhicules figurant dans l’arc est donné par :

(6)

Comme le flux dépasse la contrainte de capacité de sortie de l’arc,

seulement véhicules peuvent sortir de l’arc durant chaque unité de temps.

Par conséquent, le temps de trajet des véhicules sur l’arc augmente

et est supérieur au temps de trajet minimal . La vitesse des véhicules

est donnée par . Le nombre de véhicules dans le système

à l’instant peut être obtenu en substituant les équations (4) et (6)

à l’équation (1) et est donné par .

Comme , alors est le nombre de véhicules

qui s’accumuleront dans l’arc durant chaque unité de temps. Le fait que l’arc soit

saturé ou non à l’instant dépendra du lien entre les paramètres et .

Considérons les trois cas liés à ces deux paramètres.

Cas 1.2.2.1 : c’est le cas où (cas 1.2.2.1. de la Figure 5).

Le flux qui arrive au point d’entrée de l’arc ne dépasse pas la capacité de sortie

de l’arc. Sous cette condition, le nombre de véhicules dans l’arc diminue

et l’arc atteindra l’état d’équilibre avec le flux de sortie à l’instant :

L’état du système change à l’instant .



Cas 1.2.2.2. : c’est le cas où (voir cas 1.2.2.2. de la Figure 5).

Dans ce cas, le flux qui arrive au point d’entrée de l’arc est égal à la capacité

de sortie de l’arc. Sous cette condition, l’état du système reste constant

jusqu’à l’instant . Le flux de sortie reste constant et est donné par

.

Cas 1.2.2.3. : c’est le cas où (voir cas 1.2.2.3. de la Figure 5).

Dans ce cas, le flux qui arrive au point d’entrée de l’arc dépasse la capacité de

sortie de l’arc. Sous cette condition, le nombre de véhicules dans l’arc

continue à augmenter et l’arc sera saturé à l’instant .

L’état du système change à l’instant .

Figure 6. L’arc est saturé (cas 2)

Cas 2. : nous sommes dans le cas où l’arc est saturé, i.e.

(voir Figure 6). Dans ce cas, le flux maximal qui entre dans l’arc

est le minimum entre la capacité de l’arc et la capacité de sortie de l’arc.

Il est donné par . Le flux de sortie de l’arc est



. La durée du trajet pour les véhicules situés dans

l’arc est . Comme l’arc est saturé, la durée du trajet pour

les véhicules qui entrent dans l’arc (i, j) est le minimum entre la capacité et

la capacité de sortie . Si , les véhicules traverseront l’arc sans

ralentir, avec un minimum de temps égal à . Si , le temps de trajet

pour les véhicules sera maximum et est égal à . La vitesse moyenne

des véhicules sortant de l’arc est donnée par .

Cas 2.1. : c’est le cas où . Il représente le cas 2.1. de la

Figure 6. Dans ce cas, le flux qui arrive au point d’entrée est supérieur ou égal à la

capacité d’entrée de l’arc. Alors, le flux entrant de l’arc est .

Le nombre de véhicules s’accumulant au point d’entrée de l’arc est donné

par à chaque unité de temps. Sous cette condition, l’arc reste

toujours plein. Le nombre de véhicules en attente à l’entrée de l’arc continuera à

monter, tandis que le nombre de véhicules en attente à l’intérieur de l’arc restera

constant. L’état de l’arc reste constant et change seulement quand le flux d’en-

trée devient inférieur à ou quand la capacité de sortie devient

supérieure à . L’état du système changera au temps .

Cas 2.2. : c’est le cas où . Il représente le cas 2.2 de la

Figure 6. Dans ce cas, le flux qui arrive au point d’entrée de l’arc n’est pas supé-

rieur à la capacité d’entrée . Sous cette condition, la capacité d’entrée de

l’arc est . Le flux entrant de l’arc est . Le nombre de

véhicules dans le système diminue avec le temps et l’arc (i,j) atteindra l’équilibre

avec le flux de sortie égal au flux d’entrée au temps où :

(7)



L’état du système change au temps où .

Note : si un véhicule est dans l’arc au temps , et si sa position est don-

née par sa distance x du point d’entrée de l’arc, alors il arrivera à la fin de l’arc

au temps où et est la vitesse. Considérons que l’état du

système change au temps où . Alors, la position z du véhicule

dans l’arc au temps est donnée par où . Si ,

le véhicule n’est plus dans l’arc.

2.2.2.3. Transfert du flux dans le réseau

Considérons la Figure 7. Le but est de définir comment les flux arrivant au nœud k sont transférés dans les arcs successeurs (k,u) où .

L’étude du transfert du flux à travers des nœuds est exercée afin de tracer le mouvement des flux et d’identifier les nœuds critiques par lesquels la propagation du flux dans le réseau aura lieu. Dans la Figure 7, les flux du trafic arrivant d’arcs (s, k) qui précèdent le nœud k, i.e. les arcs (s, k) où convergent vers

le nœud k. Un flux de sortie égal seulement à la capacité de sortie du nœud k

est transféré aux arcs successifs (k,u) ou . Si le flux d’entrée du nœud

k excède sa capacité de sortie, alors le flux en surplus qui est la différence entre

le flux entrant du trafic et la capacité de sortie sera accumulé dans les arcs prédécesseurs. La proportion de véhicules s’accumulant dans chacun des arcs d’entrée dépend de la proportion de leur contribution au flux du trafic total vers le nœud k. Ces véhicules continueront à s’accumuler dans (ou à atteindre) les arcs prédécesseurs (s, k), jusqu’à ce que le flux d’entrée ou la capacité de sortie du nœud k change. Notons que la capacité de sortie du nœud k dépend de la capacité d’entrée des arcs successifs (k, u). L’analyse de voie unique présentée dans la section 3 explique comment la capacité d’entrée et la capacité de sortie des arcs sont mises à jour avec les changements dans les flux d’entrée ou la capacité de sortie ou bien les deux en même temps.

Figure 7.Transfert du flux du nœud k



Nous admettons que la capacité maximale des arcs (k, u) au temps

t, où est connue. En général, , mais on peut avoir

où l’arc (k, u) est plein au temps t et la capacité des arcs successifs

(k, u) est inférieure à .

Pour , nous définissons :

ou (8)

L’équation (8) donne la capacité de sortie de l’arc (s, k), en d’autres termes les flux délivrés (delivered by) par (s, k) et qui seront transférés aux arcs (k,

u) où . Cette équation implique que la capacité de sortie de

l’arc prédécesseur (s, k) dépend de la valeur de q et du flux de sortie . Si

pour aucune , alors la capacité de sortie de cet arc sera de

0. Le flux total de sortie de l’arc prédécesseur (s, k) contribue au flux d’entrée du nœud k. Si le flux d’entrée au nœud k est supérieur à la capacité de sortie

, alors, un flux de sortie égal seulement à la capacité

de sortie pourra quitter le nœud k, et les véhicules en excès seront accumulés comme véhicules en attente dans les arcs prédécesseurs. Le nombre de véhicu-

les en attente dans chaque arc dépendra du flux , la contribution de cet arc

au flux d’entrée pour le nœud k. Finalement, le flux qui entrera (k, u) est :

(9)

Note : Si , le flux arrivant au nœud k est un flux d’entrée noté par .

C’est comme si nous avons un prédécesseur a k, noté s, et que . Sous

cette hypothèse, les formules précédentes (équation 8 et 9) sont applicables et

deviennent :

et



2.2.2.4. Modélisation dynamique du réseau

Le modèle dynamique du réseau décrit le comportement du système et l’évo-lution du flux à l’intérieur du réseau sous le flux d’entrée et les états initiaux des arcs du réseau. L’évolution du réseau après le temps dépend de :

l’état du réseau au temps • ;

les flux d’entrée • , au temps .

Nous notons que les flux d’entrée restent constants pour des intervalles de

temps discrets. Cela implique que restera constant sur des intervalles du

temps etc.

2.2.2.5. Dynamique du réseau

Les dynamiques du réseau sont obtenues en calculant les dynamiques de chaque arc du réseau. Mais, un tel calcul nécessite la capacité de sortie de cha-que arc qui est influencée par les capacités des arcs des successeurs. Alors, le calcul du prochain état de réseau a deux objectifs :

le calcul de la capacité de sortie de chaque arc ;•

la recherche du temps quand les arcs changeront d’états. Notons ces temps •

par , où . Alors est le temps quand le nouvel

état du réseau est calculé.

2.2.2.6. Calcul de la capacité de sortie des arcs

Ce calcul est fait dans le sens inverse. Soit , si , alors

où la capacité de sortie de l’arc (s, k) est égale à la capacité de l’arc.

Admettons maintenant que . Comme le calcul est fait dans le sens inverse, nous connaissons la capacité de sortie de tous les arcs (k, u) où . Nous connaissons aussi l’état de l’arc au temps , qui est le même quand le dernier

état du réseau est connu. Le flux de sortie de l’arc (s, k) est obtenu en appliquant

l’équation (8) avec les capacités d’entrée des arcs (k, u) qui sont données

par l’équation (10).

si (k, u) n’est pas pleine

si (k, u) est pleine.

(10)



2.2.2.7. Algorithme

Les étapes du modèle dynamique du réseau sont :

(1) entrer l’état du réseau au temps . Introduire le temps de calcul pour l’algorithme ;

(2) calculer la capacité de sortie pour chaque arc du réseau (backward) en utilisant les équations (8-9) ;

(3) • calculer pour chaque arc . Ces calculs sont basés sur l’ana-

lyse d’une voie unique (voir section 3) ;

(4) • calculer ;

(5) • calculer l’état de chaque arc au temps ;

(6) • faire ;

(7) • si , arrêt. Fin de l’algorithme ;

(8) • aller à l’étape 2.

2.2.2.8. Simulation par ordinateur

En utilisant le modèle dynamique du réseau, nous avons généré les données du trafic pour faire l’analyse et le calcul du temps des trajets dans le réseau. Les entrées du modèle sont les flux d’entrée, les états initiaux des arcs, les origi-nes–destinations et les véhicules de test (voitures rouges) pour tracer plusieurs chemins dans le réseau. Les résultats générés par le logiciel sont le chemin le plus rapide entre chaque pair « origine–destination » du réseau. Le logiciel a été développé en C++.

Pour calculer le temps du trajet, le logiciel de la simulation utilise une voiture d’expérimentation (appelée voiture rouge ou voiture de test). Une voiture rouge

est introduite au point d’entrée du réseau au temps . Nous considérons que

cette voiture rouge se divise en autant de voitures que les arcs successifs de

nœuds, jusqu’à ce que les destinations soient atteintes. Le mouvement de cette voiture rouge dans le réseau est simulé sous flux dynamique et contrainte de capacité avec le modèle de réseau dynamique. Le temps au bout duquel les véhicules test apparaîtront aux nœuds de destination est noté.

Pour générer les chemins les plus rapides entre toutes les origines et desti-nations du réseau, les voitures de test sont introduites à chaque point d’entrée du réseau, et le premier temps est mesuré quand ces véhicules test arriveront à chaque nœud de sortie. S’il y a m origines et n destinations, alors le logiciel de simulation génère les m*n chemins les plus rapides pour le réseau.



2.3. Utilisation des techniques d’analyse des données pour trouver le chemin le plus rapide (ANA-DO)

Cette section présente les techniques d’analyse des données pour calculer les chemins les plus rapides sur les sous-réseaux en temps réel. Les détails de cette analyse sont présentés dans les paragraphes suivants.

2.3.1. Calcul du chemin local : méthodologie

Cette sous-section est consacrée à la recherche du « meilleur » chemin local. Lorsque le véhicule pénètre dans un sous-réseau, nous nous intéressons au che-min qui conduira du point d’entrée dans le sous-réseau au point à partir duquel il quitte ce sous-réseau (ou à la fin du trajet si celle-ci appartient au sous-réseau), et nous cherchons à optimiser cette partie du chemin en tenant compte de l’état réel du système, et non plus d’un état « moyen » comme pour la définition du chemin complet.

Lorsque le conducteur pénètre dans un sous-réseau, nous connaissons :

les flux d’entrée dans le sous-réseau ;•

le nombre de véhicules dans chacun des arcs de sous-réseau.•

Les flux d’entrée étant constants par morceaux, nous pouvons supposer qu’ils vont se prolonger durant une période de quelques minutes, suffisante pour per-mettre au véhicule de traverser ce sous-réseau. De plus, l’effet de ces flux, joint à l’état initial du système, va modifier l’état du système durant les quelques minutes à venir et donc influencer les décisions du conducteur qui souhaite arriver « au plus vite » à la sortie de ce sous-réseau.

C’est à ce niveau que nous faisons intervenir la simulation. Nous procédons de la manière suivante (tous ces traitements se font en temps différé) :

nous générons au hasard, dans une fourchette admissible, un grand nom-•bre de couples (flux d’entrée, état du système). Cette génération aléatoire d’états et de flux se fait en fonction des probabilités issues de l’observation. Deux types d’activités préparatoires seront donc menées avant d’aborder la simulation :

recherche du domaine dans lequel chacune des variables représente un —pourcentage important (95 % par exemple) des valeurs observées ;

recherche des corrélations entre les variables d’état et de flux. Il est, par —exemple, peu probable qu’une voie « a » soit saturée, alors que la seule voie qui lui succède, notée « b », est vide. Il y aura donc certainement une corrélation forte entre les variables « nombre de voitures dans “a” et “nombre de voitures dans “b” », corrélation dont on tiendra compte lors de la génération aléatoire des états.

L’étude préliminaire n’a pas été menée dans ce travail. Nous avons simple-ment supposé que les variables d’état et de flux sont non corrélées et qu’elles prennent leurs valeurs entre 0 et le maximum donné suivant une loi de probabilité uniforme.



Pour chacun de ces couples, nous recherchons la durée des trajets entre •tous les points d’entrée de sous-système et tous les points de sortie en pre-nant compte de tous les chemins possibles. Pour chacun des couples, ce calcul se fait en une seule simulation. Le résultat de cette simulation permet donc de connaître, en particulier, le chemin le plus rapide pour tout couple (entrées–sorties) de sous-réseau.

Nous nous servons ensuite des résultats de nombreuses simulations pour structurer « une mémoire » qui permettra de proposer le meilleur choix à un conducteur pour la traversée d’un sous-réseau dès qu’il y pénètre. Cela exige que la connaissance du couple (état du système, flux d’entrée) permette de pré-lever, dans la mémoire, le chemin le plus rapide correspondant.

Nous proposons d’abord une règle de simplification des données. Nous rap-pelons ensuite ce qu’est la méthode de classification hybride que nous utilisons pour trouver le plus court chemin, lorsque nous connaissons le couple (flux d’en-trée, état du système).

Remarque : nous avons affiché comme objectif pour la décomposition d’un réseau de transport en sous-réseaux de transport de faire en sorte qu’ils soient aussi indépendants que possible les uns des autres. Cette exigence peut se traduire en disant que nous cherchons à minimiser le nombre total d’entrées et de sorties de chaque sous-réseau. Cet objectif tend indirectement à minimiser le nombre de couples (entrée, sortie) de sous-réseaux, donc à minimiser le volume des données résultant de la simulation appliquée à chaque sous-réseau.

2.3.2. Classification des données de trafic

Nous cherchons à transformer les données et les résultats des simulations en classes.

Les entrées des simulations, c’est-à-dire les flux et le nombre de voitures dans chaque chaussée de circulation sont divisés en trois classes.

Comme l’effet d’un flux ou du nombre de voitures dans une chaussée est d’autant plus important que ces valeurs sont proches de leur maximum, les clas-ses sont inégales. Plus précisément, chaque valeur de variable qui appartient au couple (état du système, flux d’entrée) est affectée à l’une des trois classes suivantes :

elle est affectée à la classe 1, si elle est comprise entre 0 et 60 % de son •maximum ;

elle est affectée à la classe 2, si elle est comprise entre 60 et 90 % de son •maximum ;

elle est affectée à la classe 3, si elle est supérieure à 90 % de son maxi-•mum.

Les chemins résultant d’une simulation sont eux-mêmes rangés en trois classes :

le chemin le plus rapide est affecté à la classe 1 ;•



le second chemin le plus rapide est affecté à la classe 2.•

tous les autres chemins sont affectés à la classe 3.•

Chaque expérience est donc transcrite sous forme d’une suite de 1,2 ou 3 qui comporte autant d’éléments que de variables d’état et de flux, suivie du chemin le plus rapide et du second chemin le plus rapide, les autres chemins appartenant par définition à la classe 3.

Si donc n1 est le nombre d’entrées, p est le nombre total de chemins entre les entrées et les sorties et m est le nombre des arcs de sous-réseau, nous retien-drons n1 + p + m valeurs pour déterminer les entrées de la simulation, et cette chaîne de n1 + p + m valeurs pourra prendre théoriquement 3n1 + p + m valeurs. Tous les paramètres d’entrée et de sortie n’ont pas la même importance, et le but de la méthode que nous présentons dans le paragraphe suivant est justement d’extraire les paramètres les plus significatifs du point de vue décisionnel. Nous voyons cependant l’importance qu’il y a à limiter la taille de sous-réseaux, c’est-à-dire à réduire m.

Nous conservons trois classes pour chacun des chemins qui joignent les entrées et les sorties des sous-réseaux. Nous désignons par n2 le nombre de sorties. Le Tableau 2 présente les résultats de simulation.

Tableau 2. Représentation des simulations

Entrée 1 Entrée 2 - Arc(i,j) Arc(k,l) -Chemin

C1Chemin

C2-

RangsS.No.

1 2 3 1 2 3 - 1 2 3 1 2 3 - 1 2 3 1 2 3 -

1 X X - X X - X X -

2 X X - X X - X X -

3 X X - X X - X -

4 X X - X X X - X X -

5 X X - X X - X X -

- - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - -

10,0 X X X X X X

Il n’y aura évidemment qu’une seule croix « X » dans chaque triplet de colon-nes attachées à une variable. Par conséquent, le nombre de croix pour une simu-lation sera n1 + m+ (nombre total de chemins joignant les entrées et les sorties).

2.3.3. Traitement des résultats des simulations

Le logiciel utilisé est SPAD ([17]). La Figure 8 schématise la structure de la partie de ce logiciel nous intéressant.



Figure 8. La structure du logiciel d’analyse

2.3.3.1. Analyse des correspondances multiples

La première phase du traitement consiste à appliquer le module CORMU qui est un module d’analyse des correspondances multiples.

Avant de lancer ce module, les données sont filtrées de la manière suivante. Dans le Tableau 2 par exemple, nous comptons le nombre de croix dans chaque colonne et divisons ce nombre par le nombre total de simulations effectuées, c’est-à-dire le nombre de lignes du Tableau : c’est la proportion de simulations au cours desquelles cette valeur de variable est apparue. Si cette proportion est inférieure à un seuil donné par l’utilisateur (0,02 dans le cas de l’exemple traité ultérieurement), nous supprimons la colonne correspondante, considérant que cette valeur n’est pas significative dans le contexte du problème.

L’analyse des correspondances multiples est alors lancée. Elle conduit à des graphes donnant les projections des points (chaque point est donné par une simulation) sur les plans définis par les facteurs contenant un maximum d’in-formations pris deux à deux. Ces graphes représentent des projections, ce qui signifie que deux points proches sur un tel graphe ne sont pas forcément proches dans l’espace complet (par exemple, nous verrons ensuite que la dimension



de l’espace complet associé au petit exemple traité est 59). Il faut donc faire intervenir les angles que forment les segments obtenus en joignant l’origine des coordonnées à ces points avec les plans définis par les axes factoriels.

Traitement 1 : l’analyse des correspondances multiples permet de détecter les variables d’entrée et leurs valeurs qui influencent la classification des che-mins de sortie. Elle permet surtout de mettre en évidence les facteurs principaux contenant le plus d’information (i.e. qui contribuent le plus à l’inertie totale.)

2.3.3.2. Réduction de l’espace des variables

Soit n le nombre de variables initiales, cela signifie que chaque simulation peut être représentée par un point dans un espace de dimension n. Dans l’exem-ple traité plus loin, n = 59. Nous sélectionnons alors les facteurs contenant le plus d’informations. Soit f le nombre de ces facteurs. Bien entendu, f < n. Dans l’exemple traité plus loin, f = 10.

Le second module utilisé, DEFAC, permet de projeter l’ensemble des points (les simulations) situés initialement dans l’espace de dimension n dans l’espace de dimension f.

Traitement 2 : le module DEFAC nous conduit à une représentation des points initiaux (les simulations) dans un espace réduit défini par les facteurs principaux qui contiennent le plus d’informations (i.e. qui contribuent le plus à l’inertie totale).

Nous passons alors au traitement suivant réalisé par le module SEMIS.

2.3.3.3. Classification des points dans le nouvel espace

Nous appliquons aux points situés désormais dans l’espace de dimension f une méthode dite « des nuées dynamiques » (k-means clustering dans la littéra-ture anglo-saxonne).

Traitement 3 : la méthode des nuées dynamiques, appliquée à plusieurs reprises aux points considérés, conduit à des classes stables. Nous pouvons considérer que les points (i.e. les simulations) contenus dans une de ces classes sont très proches et peuvent donc être remplacés par un point unique qui est le dernier point de base des classes.

2.3.3.4. Regroupement des classes les plus proches

Cette dernière phase de calculs fait appel au module PARTI/DECLA qui appli-que la méthode de Ward. C’est une méthode de classification hiérarchique. Les classes (voir Figure 9) se rejoignent d’autant plus tôt dans la hiérarchie que les points de base représentatifs sont plus proches. L’utilisateur définit alors un seuil. Les classes qui se rejoignent en dessous de ce seuil sont réunies.

Dans la Figure 9, la méthode de Ward a réduit les dix classes initiales en sept classes, à savoir :

(C1), (C2, C3), (C4, C5), (C6, C7), (C8), (C9, C10), (C11). Bien entendu, plus le seuil est élevé, plus le nombre de classes décroît, mais moins le résultat est



précis, i.e. moins il est possible de considérer que les éléments d’une même classe peuvent être confondus.

Traitement 4 : les points regroupés à l’occasion de ce quatrième traitement sont caractérisés par un sous-ensemble des variables de départ, c’est-à-dire par un ensemble de flux d’entrée, avec l’intensité des flux, un ensemble de chaus-sées avec le nombre de voitures qui y figurent initialement et un ensemble de chemins avec leur classement.

Figure 9. La méthode de Ward

Classification mixte

Seuil

On comprend que si une classe donnée contient un chemin classé comme le plus rapide entre une entrée et une sortie et, par exemple, quelques arcs avec le nombre initial de voitures qu’ils portent et quelques flux avec leur intensité (1, 2 ou 3), alors, ces variables expliquent probablement pourquoi le chemin est le plus rapide. C’est la manière d’exploiter ce résultat. Encore faut-il affiner le contenu des classes.

2.3.3.5. Application de l’analyse canonique

L’objectif de cette dernière phase d’analyse est de définir les éléments d’une même classe réellement corrélés, étant en accord sur le fait que nous recher-chons les liaisons entre paramètres d’entrée (associés à leur valeur) et chemins (associés à leur rang).



Associée à un seuil (généralement bas) l’analyse canonique nous permet de relier un résultat de simulation, c’est-à-dire un chemin avec son rang, aux para-mètres d’entrée (c’est-à-dire un ou plusieurs flux d’entrée avec leur rang et une ou plusieurs chaussées avec leur rang).

Traitement 5 : l’analyse canonique permet d’extraire des classes mises en évidence précédemment, les éléments que nous pouvons éventuellement consi-dérer comme étant corrélés. Dans notre cas, cela revient à dire que nous som-mes en mesure de mettre en évidence l’explication (en termes de flux d’entrée initiaux avec leur intensité et de véhicules présents initialement dans certaines voies) du rang de certains chemins.

2.3.3.6. Exploitation des résultats

Les résultats que nous venons d’obtenir sont stockés en mémoire sous forme de règles simples qui permettent au conducteur de décider en temps réel du che-min à prendre pour arriver le plus rapidement possible à la sortie du sous-réseau déterminée par l’étude globale traitée en début de section.

Les règles que nous retenons sont toutes de type suivant :

SI • {(r(i1, j1) = 1) ET (r(i2, j2) = 2) ET (r(e1) = 3) ET (r(e2) = 1)}, alors, le chemin le plus court est (a1, a2, ..as).

Dans une telle règle :

r(i1, j1) désigne la voie qui relie le nœud i1 au nœud j1. Dire que r(i1, j1) = 1 signifie que le nombre de véhicules dans la voie (i1, j1) est compris entre 0 et 60 % de sa capacité maximale, comme nous l’avons expliqué précédemment.

Une condition pourrait également s’écrire : r(i1, j1) = 1. Cette condition signifie que la charge de l’arc (i1, j1) n’est pas comprise entre 0 et 60 % de sa charge maximale, et donc qu’elle appartient tantôt à la classe 2 (60 à 90 % de la charge maximale), tantôt à la classe 3 (90 à 100 % de la charge maximale), mais jamais à la classe 1.

(r[e] = 1) est une condition qui indique que le flux qui apparaît à l’entrée e est de classe 1. Comme précédemment, nous pouvons également avoir une condi-tion du type (r[e] = 2).

Nous aboutissons donc à un ensemble relativement réduit de règles. Il est possible que nous soyons dans l’un des cas suivants :

il n’y a pas de règles pour certains couples (entrée dans le sous-réseau, •sortie du sous-réseau). Cela signifie que nous n’avons pas réussi à identifier des conditions qui conduisent au chemin le plus rapide pour le couple en question. Dans ce cas, aucune consigne ne sera fournie et l’on prendra le chemin le plus court ;

il y a plusieurs règles pour certains de ces couples : cela est, en fait, le cas •le plus général.



Le cas 1 peut être la conséquence du fait que les états initiaux et les flux ini-tiaux intéressants n’ont pas été simulés : ils ont ou bien été oubliés dans la liste des états à simuler (conséquence d’une étude préalable mal menée) ou bien été écartés du fait du nombre insuffisant de simulations effectuées à partir de ces données initiales.

2.3.3.7. Remarques importantes

la fiabilité des résultats dépend des états initiaux choisis pour les simulations •et de la fréquence avec laquelle ils sont choisis. Si ces choix et cette fré-quence ne correspondent pas à la réalité, alors les règles obtenues ne sont pas efficaces et peuvent même être contre-productives ;

il faut que le système de guidage soit informé en temps réel des flux d’entrée •et des charges des chaussées ; cependant, les informations nécessaires se limitent à celles qui apparaissent dans les règles, lesquelles sont, dans la plupart des cas, en nombre largement inférieur aux informations sur l’en-semble des flux d’entrée et des chaussées ;

enfin, lorsqu’un véhicule pénètre dans un sous-réseau, il connaît son point •d’entrée et son point de sortie. Il n’aura donc besoin que d’un nombre réduit de règles, celles qui correspondent au couple (entrée dans le sous-réseau, sortie de sous-réseau) qui l’intéresse.

3. Un exemple d’application

3.1. Données

Considérons le sous-réseau représenté dans la Figure 10.

Figure 10. Un sous-réseau de plusieurs entrées et sorties

Destination 1

Destination 2

Origine 1

Origine 2



Les simulations effectuées ont été menées à partir de flux d’entrée et d’états des arcs générés au hasard entre 0 et le maximum correspondant. Nous avons effectué 10 000 simulations. Les flux et les états des arcs sont classés comme indiqué dans les Tableaux 3 et 4.

Tableau 3. Flux d’entrée vs rang

Tableau 4. Etat initial d’un arc vs rang



Les temps de transport sur les chemins joignant une entrée à une sortie

sont classés comme l’indique le Tableau 5.

Tableau 5. Temps de transport vs rang du chemin

Tableau 6. Les flux d’entrée

Tableau 7. Paramètres caractéristiques du sous-réseau

Les temps de transport sur les chemins joignant une entrée à une sortie sont classés comme l’indique le Tableau 5.









Le Tableau 6 s’intéresse aux flux d’entrée dans le sous-réseau. La première colonne donne les deux nœuds d’entrée dans le sous-réseau. La seconde colonne donne le flux maximum. Enfin, la dernière colonne donne l’identification du flux suivant la classe à laquelle il appartient. Par exemple, pour le nœud d’en-trée 1 :

le flux sera désigné par I1, si son intensité lui donne le rang 1 ;•



le flux sera désigné par I2, si son intensité lui donne le rang 2 ;•

le flux sera désigné par I3, si son intensité lui donne le rang 3.•

Les identifications I4, I5 et I6 ont une signification analogue pour le flux d’en-trée du nœud 2.









Ajoutons que chaque simulation se déroule sur 200 unités de temps. Le Tableau 7 présente les données qui caractérisent le sous-réseau. La première colonne donne l’identification des arcs : (i, j), indique que i est l’origine et que j est l’extrémité de l’arc. La colonne pij donne la proportion du flux arrivant au nœud i qui sera dirigée vers le nœud j, lorsque plusieurs choix sont possibles. La colonne pij donne la vitesse sur (i, j) en cas de non-blocage. cij est la capacité de l’arc (i, j), c’est-à-dire le nombre maximum de véhicules qui peuvent se trouver sur la voie représentée par l’arc (i, j). La colonne lij donne la longueur de la voie représentée par l’arc (i, j). La colonne nij(t0) donne le nombre de véhicules dans les voies à l’instant initial t0.

Enfin, la dernière colonne donne l’identification de l’arc, suivant le nombre de voitures que porte la chaussée qu’il représente. Par exemple :

S1 représente l’arc (1,3), s’il porte entre 0 et 60 % de sa capacité maximale •25, c’est-à-dire entre 0 et 15 voitures ;

S2 représente l’arc (1,3) s’il porte entre 60 et 90 % de sa capacité maximale •25, c’est-à-dire entre 15 et 22,5 voitures ;

S3 représente l’arc (1,3) s’il porte entre 90 et 100 % de sa capacité maxi-•male 25, c’est-à-dire entre 22,5 et 25 voitures.

Les Tableaux 7 et 8 s’intéressent à la caractérisation des chemins. La colonne 1 donne les couples (entrée–sortie), notés E/S.




Tableau 8. Caractéristiques des chemins

Tableau 9. Classes finales

Pour chacun de ces couples :

la colonne 2 liste les chemins qui joignent l’entrée à la sortie ;•

la colonne 3 rappelle les longueurs de ces chemins ;•

la colonne 4 identifie ces chemins. Par exemple, le chemin 1-3-7-10 sera •désigné par P1, si ce chemin est le plus rapide, par P2, si ce chemin est le second chemin le plus rapide et par P3, si ce chemin est le troisième chemin le plus rapide.






3.2. Application de la méthode

Nous avons effectué 10 000 simulations et 200 itérations par simulation. Pour chacune de ces simulations, nous avons généré un état initial et des flux d’entrée comme indiqué précédemment. La classification hybride a ensuite été utilisée en utilisant SPAD, outil statistique bien connu (voir [CIS97]. Les quatre méthodes CORMU, DEFAC, SEMIS et PARTI/DECLA ont été employées comme indiqué précédemment.

La méthode CORMU (analyse des correspondances multiples) a été utilisée après avoir supprimé les variables qui apparaissent dans les résultats des simu-lations avec un ratio inférieur à 2 %. La Figure 11 donne un des résultats de l’ana-lyse, i.e. le résultat de la projection sur les deux axes principaux correspondant aux deux maxima d’inertie.

Dans la Figure 11, nous observons que la plupart des informations corres-pondant aux arcs et aux flux d’entrée se situent près de l’origine des coordon-nées, alors que les informations concernant les chemins sont éloignées de cette origine.



Nous voyons cependant que les informations concernant des arcs sont voisi-nes d’informations concernant des chemins. C’est le cas, par exemple, de P39 qui représente le chemin 2-5-8-10 dont le rang est 3, et de S39 qui représente l’arc (5,9) lorsqu’il est de rang 3.

L’analyse des correspondances multiples a conduit à 59 axes principaux qui expliquent 100 % de l’inertie totale.

La méthode DEFAC nous a permis de ne retenir que les dix axes principaux qui contiennent le plus d’inertie, soit, respectivement 7,55%, 7,35%, 6,33%, 3,59%, 2,59%, 2,01%, 2%, 1,86%, 1,85% et 1,84% de l’inertie totale. La dimen-sion de l’espace de l’étude passe donc de 59 à 10.

Figure 11. Un résultat de l’analyse des correspondances multiples

Facteur 2

-04 0 04 08Facteur 1

05

0

-05

-10

Le troisième traitement, qui est un traitement de type « nuées dynamique » (k-means analysis), s’appelle SEMIS. La méthode a été appliquée 20 fois à partir de dix centres choisis au hasard. Nous avons obtenu dix classes à chaque exécu-tion, puis retenu les points regroupés dans chaque exécution. Cela nous a conduits finalement à vingt-six classes stables. Ces vingt-six classes stables ont été les entrées de la classification hiérarchique (méthode de Ward) qui a réduit le nombre de classes à sept en choisissant un seuil de 0,29 (voir la Figure 9). Ces sept clas-ses sont données dans la Figure 12, et leur contenu est donné dans le Tableau 9.

Nous observons que dans ces classes, nous trouvons les indicateurs des entrées concernant les arcs et des sorties (chemins). Par contre, à deux excep-tions près, les indicateurs de flux d’entrée sont absents. L’explication est que,



du fait de la topologie du sous-réseau et de la relative brièveté de l’horizon de l’étude, les flux d’entrée n’ont pas le temps d’influencer significativement les chemins.

Enfin, chacune des sept classes a été soumise à une analyse de corrélation canonique. L’objectif, ici, est de définir les entrées susceptibles d’expliquer les sorties. La valeur canonique, r pour chaque classe, est supérieure à 0,56. Un seuil fixé à 0,1 a été choisi pour retenir le coefficient de corrélation entre les varia-bles d’entrée et de sortie. Les résultats sont présentés dans le Tableau 10.


Tableau 10. Les chemins les plus rapides versus l’état des arcs

Tableau 11. Situation initiale

Les informations contenues dans le Tableau 10 sont utilisées pour faire des prédictions sur le chemin le plus rapide, sur l’horizon de la simulation en fonction de l’état actuel du système. Par exemple, en utilisant le Tableau 10, nous voyons qu’à l’instant initial, les arcs (1,3), (2,3), (3,8), (4,8) et (5,8) sont de rang 3, c’est-à-dire que les voies qu’ils représentent portent entre 90 et 100 % du nombre maximal de véhicules, alors le chemin le plus rapide entre l’entrée et la sortie 10 est 1-3-7-10. Nous pouvons également observer qu’un chemin peut être le plus rapide pour deux états initiaux différents.



Figure 12. Les sept classes obtenues par la classification

Facteur 2COUPURE "0" DE L'ARBRE EN 7 CLASSES

Facteur 1

0.4

0

-0.4

-0.8

-0.4 0.4 0.8 1.2 1.60






Considérons, par exemple, le chemin 2-3-8-10 qui joint le nœud d’entrée 2 au nœud de sortie 10. Ce chemin est le plus rapide si les arcs (3,8), (4,8) et (5,8) sont de rang 1, et si l’arc (5,9) est de rang 3. Cependant, nous observons les rangs 1 et 3 pour l’arc (4,9). Nous remarquons que la corrélation est positive (+0,11) pour le rang 3 et négative (–0,13) pour le rang 1. Cela signifie que le chemin 2-3-8-10 est le plus rapide, si (4,9) est du rang 3, et doit être évité, si cet arc est de rang 1. Nous n’avons pas inclus tous les états des arcs dans le Tableau 10. Nous avons éliminé les arcs qui ont une corrélation inférieure à 0,1, ce qui indique une influence faible de ces arcs sur la rapidité de circulation sur ces chemins.

3.3. Utilisation des résultats

Comme nous l’avons indiqué dans la section 3.2, les résultats qui figurent dans le Tableau 10 se traduisent par les règles suivantes :

ORIGINE 1 – DESTINATION 10

SI {r (5,8) = 3 ET r (3,8) = 3 ET r (4,8) = 3 ET r (1,3) = 3 ET r (2,3) = 3}, alors le chemin le plus rapide est (1, 3, 7,10).


SI {r (5,8) = 1 ET r (3,8) = 1 ET r (4,8) = 1}, alors le chemin le plus rapide est (1, 3, 8,10).

SI {r (5,8) = 1 ET r (3,8) = 1 ET r (4,8) = 1 ET r (1,3) = 1}, alors le chemin le plus rapide est (1, 3, 8,10).


Le chemin le plus rapide est toujours (1, 3, 8,11).




SI {r (1,4) = 1 ET r (2,4) = 1}, alors le chemin le plus rapide est (2, 4, 8,10).



Si {r (5,9) = 1 ET r (1,5) = 3 ET r (2,5) = 3}, alors le chemin le plus rapide est (2, 3, 8,11).

SI {r (1,4) = 1 ET r (2,4) = 1}, alors le chemin le plus rapide est (2, 4, 8,11).

SI {r (2,4) = 1} ALORS le chemin le plus rapide est (2, 4, 8,11).





3.4. Validation des résultats

Les résultats ont été validés par comparaison avec des simulations.

Le Tableau 11 présente les flux d’entrée et les états initiaux des arcs utilisés pour la simulation.

Le Tableau 12 donne le résultat de la simulation, c’est-à-dire le chemin le plus rapide entre chaque couple (nœud d’entrée–de sortie).


Tableau 12. Résultat des simulations

Tableau 13. Résultats donnés par les règles

L’application des règles précédentes conduit aux résultats donnés dans le Tableau 12 : l’arc (5,8) étant de rang 1 (voir Tableau 13) la dernière règle de « Origine 1, extrémité 10 » montre que 1-3-8-10 doit être choisi comme chemin le plus rapide entre le nœud 1 et le nœud 10, alors que les résultats de simulation proposent ce chemin pour le rang 2 de l’arc (5,8). La seule règle applicable entre « Origine 1, extrémité 11 » montre que 1-3-8-11 doit être choisi. Nous voyons que la quatrième règle est applicable pour « Origine 2, extrémité 10 », ce qui nous conduit à choisir le chemin (2-5-8-10) comme chemin le plus rapide.

Enfin, la troisième règle s’applique pour « Origine 2, extrémité 11 » et conduit à 2-5-8-11 comme chemin le plus rapide.

Finalement, nous voyons que l’application des règles correspond aux résul-tats de simulation dans 75 % des cas.

Le travail que nous venons de présenter permet de choisir le chemin le plus rapide entre l’entrée et la sortie d’un sous-réseau par simple application de règles qui s’appuient sur un nombre limité de paramètres qui définissent l’état initial du système et les flux d’entrée. L’aspect important est le nombre limité de paramè-tres nécessaires pour parvenir à la conclusion.

Il convient cependant de souligner l’importance de l’étude préalable qui va influencer le choix des simulations que nous allons effectuer. Ce choix, à son tour, gouverne partiellement les paramètres que nous retiendrons. En d’autres termes, il est important que l’état initial du système et les flux correspondent à des situations réalistes. En particulier, cela exige une étude détaillée des corrélations entre ces différents paramètres.









4. Conclusion

Cet article présente une approche hiérarchique et modulaire pour prédire les chemins les plus rapides sur des réseaux de grandes tailles sous conditions dynamiques. Le travail est fait en trois modules : le premier module est dédié à



la décomposition des grands réseaux en sous-réseaux de taille raisonnable afin que le nombre des interconnections soit minimal. Le deuxième module présente le logiciel de simulation utilisé pour générer les données afin de constituer la mémoire. Cette mémoire est utilisée pour calculer le chemin le plus rapide en fonction de l’état initial des arcs des réseaux et le flux d’entrée de véhicules. Finalement, le troisième module est le plus innovant et montre comment l’analyse de données a été utilisée pour faire les tris afin d’extraire les chemins les plus rapides en temps réels.

L’avantage principal de notre approche est que le temps de calcul est réduit au temps de recherche d’une réponse d’une requête dans la base de données. Le deuxième avantage est qu’elle permet d’utiliser les réseaux de très grande taille. De plus, l’approche est modulaire en nature qui permet à chaque module de fonctionner indépendamment des autres modules.

Références

[1] D. Wagner, T. Willhalm. Geometric speed-up techniques for finding shortest paths. In : Large sparse graphs, Konstanzer Schriften in Mathematik und Informatik, No 183, ISSN 1430-3558, 2003. http ://www.inf.uni-konstanz.de/Schriften/papers/2003/preprint-183.pdf.

[2] R. H. Mohring, H. Schilling, B. Schutz, D. Wagner, T. Willhalm. Partitioning graphs to speed-up Dijkstra’s algorithm, ACM Journal of Experimental Algorithmics, 11(2–8) : 1–29, 2006.

[3] Y. Lim, H. Kim. A. shortest path algorithm for real road network based on path overlap. Journal of the Eastern Asia Society for Transportation Studies, 6 : 1426–1438, 2005.

[4] G. Ertl. Shortest path calculation in large road networks, OR Spectrum, 20(1), 1998 http ://www.springerlink.com/content/r32rv2j7276257j2/fulltext.pdf.

[5] P. Sanders and D. Schultes. Engineering Fast Route Planning Algorithms, WEA 2007, 23–36, 2007. http ://algo2.iti.uni-karlsruhe.de/schultes/hwy/weaOverview.pdf.

[6] A. Awasthi, Y. Lechevallier, M. Parent and J.-M. Proth. Using hybrid cluster-ing to approximate fastest paths on urban networks, Journal of Data Science 4 : 39–65, 2006.

[7] G.A. Klunder and H.N. Post. The shortest path problem on large-scale real-road networks, Networks, 48(4) : 182–194, 2006.

[8] E.P.F. Chan and N. Zhang. Finding shortest paths in large network systems, geographic information systems,160–166, 2001.

[9] Yu-Li Chou, H. Edwin Romeijn, R.L. Smith. Approximating shortest paths in large-scale networks with an application to intelligent transportation systems. INFORMS Journal on Computing, 10(2) : 163–179, 1998.http ://wwwper-sonal.umich.edu/~rlsmith/Approximating%20Shortest%20Paths.pdf.



[10] M. Gaertler and D. Wagner. Algorithms to find paths and connections from local information, 2004. http ://i11www.iti.uni-karlsruhe.de/cosin/docu-ments/section_D22.pdf.

[11] H. Bast, S. Funke, D. Matijevic, P. Sanders, D. Schultes (eds). In : Transit to constant time shortest-path queries in road networks. http ://algo2.iti.uni-karlsruhe.de/schultes/hwy/transit.pdf, 2007.

[12] F.B. Zhan and C.E. Noon. Shortest path algorithms : an evaluation using real road networks, Transportation science, 32(1) : 65–74, 1998. http ://uweb.txstate.edu/~fz01/Reprints/Zhan_1998_TS.pdf.

[13] K. Madduri, /~bader/papers/ShortestPaths-ALENE D.A. Bader, J.W. Berry, J.R. Crobak. An Experimental study of a parallel shortest path algo-rithm for solving large-scale graph instances, 2007. http ://www-static.cc.gatech.edu2007.pdf.

[14] S. Knopp, P. Sanders, D. Schultes, F. Schulz, D. Wagner. Computing many-to-many shortest paths using highway Hierarchies, 2007. http ://www.siam.org/meetings/proceedings/2007/alenex/papers/004knopps.psf

[15] I.C.M. Flinsenberg. Route planning algorithms for car navigation, Eindhoven : Technische Universiteit Eindhoven, Proefschrift.-ISBN 90-386-0902-7 NUR, 919, 2004. http ://alexandria.tue.nl/extra2/200412420.pdf.

[16] C. Fiduccia and R. Mattheyses. A linear time heuristic for improving net-A linear time heuristic for improving net-work partitions, In : Proc. 19th IEEE Design Automation Conference, 175–181, 1982.

[17] B. Kernighan and S. Lin. An efficient heuristic procedure for partitioning graphs, The Bell System Technical Journal, 49(2) : 291–307, 1970.

[18] G. Karypis and V. Kumar. A fast and high-quality multilevel scheme for parti-tioning irregular graphs, SIAM Journal on Scientific Computing, 20(1) : 359–392, 1998.

[19] G. Karypis and V. Kumar Multilevel k-way partitioning scheme for irregular graphs, Journal of Parallel and Distributed Computing, 48(1) : 96–129, 1998.

[20] K. Schloegel, G. Karypis and V. Kumar. Graph Partitioning for High Performance Scientific Simulations. In : CRPC Parallel Computing Handbook by J. Dongarra, I. Foster, G. Fox, K. Kennedy and A. White (eds), Morgan Kaufmann, 408, 2000. http ://www-users.cs.umn.edu/karypis/publications/partitioning.html.

[21] M.R Hribar, V.E. Taylor, Boyce D.E. Implementing parallel shortest path for parallel transportation applications. Parallel Computing, 27(12) : 1537–1568 (32), 2001, Elsevier publications.

[22] T. Feder, P. Hell, S. Klein, R. Motwani. Complexity of graph partition prob-lems. Symposium on the Theory of Computing, STOC 1999. 464–472, 1999. Available at : www.cs.sfu.ca/~pavol/stoc.ps

[23] M. Bierlaire, “The important role of simulation in Intelligent Transportation Systems”, Bulletin 108, April 2000, SVOR, 2000. http ://www.svor.ch/bulletins/no108/invitati00.html#bierlaire.



[24] J. Taplin. “Simulation models of traffic flow”, Proceedings of the 34th Annual Conference of the Operational Research Society of New Zealand, 10–11 December, 1999.

[25] Lonnie E. Haefner and Li Ming-Shiun (1998), “Traffic flow simulation for an urban freeway corridor”, Crossroads 2000 Proceedings, Iowa State University, Aug 19–20, 2000.

[26] L. Magne, S. Rabut, J.-F. Gabard. “Towards an hybrid macro-micro traffic flow simulation model”, Presented at INFORMS Spring 2000 Meeting, Salt Lake City, Utah, May 7–10, 2000.

[27] H.K Lee, H.W Lee and D. Kim. “Macroscopic traffic models from microscopic car-following models”, Physical Review E, 64 : 056126, 2001.

[28] I. Prigogine. “A Boltzmann-like approach to the statistical theory of traffic flow”. In : R. Hermand (ed), Theory of traffic flow, 1961.

[29] S.L. Paveri-Fontana. “On Boltzmann-Like treatments for traffic flow : a critical review of the basic model and an alternative proposal for dilute traffic analysis”, Transportation Research B., 9 : 225–235, 1975.

[30] S.P Hoogendoorn. “Multi-class continuum modelling of multi-class traffic flow”, PhD. Thesis T99/5,TRAIL Thesis Series, Delft University Press, 1999.

[31] M.H. Lighthill, and G.B. Whitham. “On kinematic waves II : a theory of traffic flow on long, crowded roads”, Royal Society of London Proceedings, Series A, 229 : 317–345, 1955.

[32] P.I. Richards. “Shockwaves on the highway”, Operations Research, 4 : 42-51, 1956.

[33] H.J. Payne. “Models for freeway traffic and control.” In : Bekey, G.A. (ed), Mathematical models of public systems 1 : 51-61, 1971.

[34] I. Prigogine and R. Herman. “Kinetic theory of vehicular traffic”, American Elsevier, New York, 1971.

[35] D. Helbing. “Modelling multi-lane traffic flow with queuing effects”, Physica A(242) : 175–194, 1997b.

[36] C.F. Daganzo “The cell transmission model : a dynamic representation of highway traffic consistent with hydrodynamic theory”, Transportation Research B., 28(4) : 269–287, 1994a.

[37] C.F. Daganzo “The cell transmission model part II : network traffic”, Transportation Research B., 28(2) : 279–293, 1994b.

[38] S.P. Hoogendoorn and P.H.L. Bovy “Gas-kinetic modelling and simulation of pedestrian flows”. Transportation Research Board, TRB-paper 00-1662, 2000

[39] A. Awasthi, M. Parent and J.M. Proth. Case-based modelling and simula-tion of traffic flows on motorway networks, issue 3, DOI : 10.2316/Journal.205.2006.3.205-4388, 2006.

[40] C. Ambroise, F. Badran, S. Thiria, and G. Sze. Hierarchical clustering of self-organizing maps for cloud classification, Neurocomputing, 30(1–4) : 47–52, 2000.



[41] A. Awasthi, M. Parent and J.M. Proth. Partitioning algorithms for large-scale urban networks, under review, 2004.

[42] CISIA (1997). SPAD Reference’s Manual, Centre international de statistique et d’informatique appliquées, France, 1997.

[43] D. Cutting, D. Karger, J. Pedersen and J.W. Tukey. Scatter/Gather : a cluster-based approach to browsing large document collections, In : Proc. 15th Annual Int. ACM SIGIR Conf., Copenhagen, 1992.

[44] E. Diday and J.C. Simon. Clustering analysis. In : K.S. Fu (Eds). Digital Pattern Recognition. Springer-Verlag, Heidelberg, 47–94, 1976.

[45] M.S. Dougherty. A review of neural networks applied to transport. Transportation Research, 3C(4) : 247–260, 1995.

[46] P. Hansen and B. Jaumard. Cluster analysis and mathematical programming. Mathematical Programming, 79 : 191–215, 1997.

[47] L. Kisgyorgy and L.R. Rillett. Travel Time prediction by advanced neural network, Periodica Polytechnica Ser Civil Engineering, 46(1) : 15–32, 2002.

[48] T. Kohonen. Self-organization and associative memory, 2nd edition, Springer-Verlag, Berlin, Germany, 1988.

[49] J.F. Marcotorchino, J.M. Proth, J. Janesen (eds). Data analysis in real life environments, North Holland, Amsterdam, 1985.

[50] F Murtagh. Interpreting the Kohonen self-organizing feature map using contiguity-constrained clustering. Pattern Recognition Letters, 16 : 399–408, 1995.

[51] R. Smith, J. Chou and E. Romeijn. Approximating shortest paths in large-scale networks with application to intelligent transportation systems. INFORMS Journal on Computing, 10(2) : 163–179, 1998.

[52] J.H. Ward. Hierarchical grouping to optimize an objective function. Journal of the American Statistical Association, 58 : 236–244, 1963.

[53] F. Zhan Benjamin. Three fastest shortest path algorithms on real road networks : data structures and procedures. Journal of Geographic Information and Decision Analysis, 1(1) : 70–82, 1997.

[54] A. Faghri and J. Hua. Evaluation of artificial neural network applications in transportation engineering, Transportation Research Record, 1358, 1992.

[55] D. Park and L. Rillett. Forecasting multiple period freeway link travel times using modular neural networks, Transportation Research Record 1617 National Research Council. Washington D.C, 199


Convergence criteria and computational efficiency of

a dynamic traffic assignment model

Fabien Leurent, Vincent Aguiléra, Hai-Dang Mai

Laboratoire Ville, Mobilité, Transport

INRETS-ENPC-UMLV

19, rue Alfred Nobel, Cité Descartes, Champs-sur-Marne

F-77455 MARNE-LA-VALLEE CEDEX 2, France

Abstract

In this paper, a high-level formulation of the dynamic traffic assignment pro-blem is used to analyse its specific complexities, most notably the chronological relativity of the volume loading. This applies in turn to the time-flow relationship at the path level. This induces significant discrepancies to static assignment, in particular as concerns the convergence criterion to be used in an equilibration algorithm. Convex combination algorithms, either arc-based or path-based, are analyzed in order to complement them with rigorous convergence criteria. A novel “hybrid” algorithm is introduced. Lastly, Leurent’s LADTA model is applied to a large size problem, demonstrating its computational efficiency.

Keywords

Dynamic Traffic Assignment, equilibrium formulation, hybrid algorithm

1. Introduction

This paper considers the problem of dynamic traffic assignment under the User Equilibrium principle. This topic has been the subject of a considerable amount of research during the last two decades, both in the transportation and operations research communities. However, it is acknowledged by many researchers that the theory of Dynamic Traffic Assignment (DTA) is still relatively underdeveloped, while practitioners manifest a heightened interest for large-scale applications, with both real time and planning applications in mind. As a conse-quence, dynamic traffic assignment tools have been given few applications, as



compared to static traffic assignment models. The work presented here — based on Leurent’s Lumpded Analytical Dynamic Traffic Assignment model (LADTA) — is an attempt to bridge the gap between, on one side, a sound analytical problem formulation and, on the other side, computational tractability and efficiency. The sequel is structured as follows.

Section 2 introduces some notations and presents the equilibration algorithm in LADTA. Section 3 concentrates on some specific complexities of dynamic assignment ; most notably the chronological relativity of the volume loading func-tion, which affects in turn the time-flow relationship at the path level. This induces important discrepancies to static assignment, in particular as concerns the con-vergence criterion : this issue is discussed in Section 4. The design of a novel equilibration algorithm, called the hybrid algorithm, is the topic of Section 5. In Section 6, results from computational experiments are presented. Lastly, Section 7 concludes and indicates directions for research development.

2. On the formulation of dynamic assignment

Leurent (2003, 2004) provided a high-level formulation of dynamic traffic assignment, which we shall recall hereafter in order to prepare the analysis in the following sections. The formulation is high-level as it makes explicit only the main traffic variables and their mutual dependencies, which are indicated in an abstract way that leaves place for flexible forms. It is generic in that it may describe most dynamic traffic assignment models : Leurent also provided a particular low-level formulation called LADTA for Lumped Analytical Dynamic Traffic Assignment.

We shall first give the notation (section 2.1). Then the high-level formulation is provided (section 2.2) and it is applied to static assignment (section 2.3). Lastly, the equilibration algorithm in LADTA is described (section 2.4).

2.1. Notation

Let us recall the elements of Leurent’s model (Leurent, 2003) in a simplified version in which the following assumptions are made :

on the demand side, there is a single user class with path choice behaviour •that is homogeneous and deterministic. Each user is assumed to select the path with minimum generalized cost ;

on the supply side, loop-free paths are considered, and congestion is mod-•elled at the arc level on the basis of a vertical queue.

List of notation :

, the transport network with N the set of nodes indexed by n and A

the set of arcs indexed by .

, the subsets of the arcs that respectively come out of, or into node n.

h instant in a period H.

F. Leurent, V. Aguiléra, H. D. Mai Convergence criteria in a dynamic assignment model


, the cumulated flow that entered arc a until h.

, the cumulated flow that exited arc a until .

, the actual travel time of arc a having entered it at h.

, the time of exiting a knowing entry at instant h : this is a function for “chronological transfer”.

the inverse function of : it maps an exit instant into the corre-sponding entry instant h.

S the set of destination nodes indexed by s.

the set of origin nodes o connected to destination s.

the set of origin–destination pairs .

the set of loop-free paths r on the O–D pair i.

the O–D volume of pair i cumulated until departure instant h.

the cumulated flow that entered path r until h.

the cumulated flow that exited path r until .

the actual travel time of route r having entered it at h.

the time of exiting r knowing entry at instant h.

the inverse function of : it maps an exit instant into the corre-sponding entry instant h.

for a path r and an arc a, which belongs to r, designates the part of r that lies strictly upstream of a.

for a path r and an arc a, which belongs to r, designates the part of r that lies strictly downstream of a.

The model endogenous variables are the entry and exit volumes of the paths, and , and of the arcs, and : these are called the primal vari-

ables ; and also the travel times, and , which we call dual variables since these times induce the user costs.

2.2. A high-level formulation

Leurent (2003) decomposed dynamic assignment into four parts as follows :

Service Formation (1a)



User Choice (1b)

Volume loading (1c)

Flowing (1d)

where is used in place of = when the mapping is multi-valued.

A state , which satisfies the system of equations (1) is a

dynamic traffic equilibrium. This abstract formulation is generic for many analytical

dynamic traffic assignment models, including those of Akamatsu and Kuwahara (1998), Tong and Wong (2000) ; Friesz et al. (2005), etc.

2.3. Application to static assignment

The generic formulation also applies to static assignment, provided that we omit the temporal variations, and that we replace cumulated flows X by flow rates x : then the service formation problem amounts to building paths on the basis of arcs, the user choice problem amounts to assigning O–D flows on optimal paths only, the volume loading problem amounts to loading path flows on the network arcs yielding arc flows, and the flowing problem amounts to evaluating the arc travel time functions with respect to the arc flows.

2.4. The LADTA equilibration algorithm

The original approach to equilibrium in the LADTA model, proposed inde-

pendently by Leurent (2003) and Gentile et al. (2003), is to cast the equilibrium

conditions into a fixed-point problem with respect to the arc cumulated flows

, which are the basic endogenous variables. The fixed-point problem is

obtained by linking the other endogenous variables to the basic endogenous

variables, :

(2a)

2b)

(2c)

(2d)

The last condition is a fixed-point condition for the following mapping :

(3)

Then the equilibrium is searched for using a method of convex combination, which is very parsimonious, as it only requires storing arc variables.



The convergence criterion is an inter-iteration gap pertaining to the arc volumes :

(4)

We shall establish more rigorous convergence criteria in Section 5.

3. The specific complexities of dynamic assignment

Let us now use the high-level formulation so as to detect and characterize the specific complexities of dynamic assignment : not only does the temporal dimension drive us to consider temporal profiles as model variables, but more importantly it makes the loading of path flows onto the arcs depend on a time field, in other words a chronology. We call this effect “the chronological relativity” of the volume loading (section 3.1). Then the time-flow relationship is relative to the chronology too, (section 3.2) : path times stem from both path flows and the time field, and the circumstance under which the path times correspond to the time field is a special one, which we call the “time-flow consistency” (section 3.3). We also study the dual relationship from time to flow to obtain weaker conditions of “dual consistency” (section 3.4). Lastly, we define a consistency property that pertains to “flow energies” (total cost), for which we provide some sufficient condi-tions (section 3.5).

3.1. The chronological relativity of volume loading

In static assignment, arc flows are derived from path flows in a straightforward way :

In dynamic assignment, the arc volumes are derived from the path flows

through the volume loading function, .

More precisely, Leurent (2003) stated the volume loading equation as follows :

(5)

It means that the volume that enters a, from instant η to instant h, is the sum of the volumes of the paths r, which traverse a : and that the volume of path r

that enters a during corresponds to the departure interval such as

and : hence and .

Thus, the functions are involved in the volume loading problem through the associated time transfer functions, , and their inverse functions, .



We call this effect the “chronological relativity of volume loading”, as the time transfer functions constitute a chronological field.

3.2. The chronological relativity of the time-flow relationship

In static assignment, the time-flow relationship at the arc level has a simple

form : denoting by the travel time function,

At the path level, the relationship of time to flow is still quite simple :

where and

In dynamic assignment the relationship of time to flow may also be considered

as a simple one, by making use of a local flowing model : the arc travel times

stem from the arc flows , which are constrained

by the local flowing conditions (including the minimal travel time and the

capacity flow rate in the LADTA model). Concerning the paths however,

the relationship of time to flow takes on the following form :

(6)

which shows that the relationship is conditional on the chronology

that influences the volume loading.

3.3. On the time-flow consistency

Let us define the “time-flow consistency” as the condition of identity between

and in Eq. (6) :

(7)

This is a fixed-point condition on (which is parameterised by ).

The consistency is a necessary condition for dynamic traffic equilibrium. It is not a sufficient condition, since it indicates nothing about the user choice.

Under time-flow consistency, the convergence of a traffic state to equilibrium

can be evaluated on the basis of the distance from to , which can be

measured using the following criterion of complementary slackness :

(8)



where .

A consistent pair and the related pair satisfy the consist-

ency of energies, namely that :

This is because stems from according to the chronology associ-

ated to , which is derived from : then the sufficient conditions of §. 5 are

satisfied.

To impose the time-flow consistency, the “natural” approach is to assign the path flows onto the network in a step by step instantaneous way as in perform-

ing a time integration and solving for a differential equation ; this yields also

and . Tong and Wong (2000) implemented that treatment, which amounts to

integrate the volume loading and the flowing problems by using a mesoscopic

simulation.

3.4. Dual time-flow consistency

Using the arc times as the basic endogenous variables, the model cycle is stated as :

(9a)

(9b)

(9c)

(9d)

As stems from , and is derived from under the chronology asso-

ciated to , the consistency of energies holds :

(10)

When the are obtained by an assignment to paths with minimal time, (10)

may be used to evaluate the overall minimal cost : by definition of , the O–D

minimal cost satisfies that

, hence



(11)

3.5. The consistency of energies

In static assignment, the “energetic power” of total cost takes on the same value at the arc and route levels, provided that and :

A similar result holds in the dynamic case under the two following condi-

tions : first, that is derived from (through the service formation) and

second, that stems from under the chronology induced by . Then

and

Summing over the network paths, we obtain that

(12)

since .

4. Convergence criteria for path-based models

Out of the numerous papers dealing with dynamic assignment and equilibrium, none has addressed explicitly the design of a convergence criterion that would rigorously indicate whether a traffic state is in equilibrium or not. In most papers, the convergence criterion is either the variation in arc flows from one iteration to the next (in an intuitive approach that may conduct to miss the equilibrium or to underestimate the gap to it), or the complementary slackness, which has more theoretical ground. However, the complementary slackness alone is not a rigor-ous convergence criterion in the context of dynamic assignment, unless the time-flow consistency is achieved.



We shall first state a rigorous overall convergence criterion in an abstract way (section 4.1). Then, we show how it may be reduced to complementary slackness if the solution algorithm yields time-flow consistency, as in the model of Tong and Wong (2001) (section 4.2). In the absence of consistency, an additional term must be included (section 4.3). Lastly, to avoid the enumeration of paths in the evalu-ation of the complementary slackness, we design an auxiliary complementary slackness that may be evaluated economically (section 4.4).

4.1. An overall convergence criterion

As equilibrium state is characterized as the solution to the system expressed in Eq. (1), which is composed of four conditions, the distance to equilibrium of a given traffic state may be evaluated as the sum of four terms that capture the violation of each condition in Eq. (1) :

(13)

where the notation “small d” means some measure of distance, and the index taken in set {S, U, V, F} indicates the equilibrium condition which is addressed.

This makes a rigorous convergence criterion. In an algorithmic scheme, some components would fall down because of definitional linkages between such or

such endogenous variable. For instance, if then .

4.2. Complementary slackness under time-flow consistency

Time-flow consistency implies that

since each of the three terms is null.

Then, the overall criterion is reduced to , which may be evalu-

ated by the complementary slackness criterion.

4.3. In the absence of time-flow consistency

When time-flow consistency does not hold, the terms in the overall criterion are likely to intervene in the following way. Firstly, it seems easy to zero

because the service formation is a relatively simple problem. However, some

caution is in order because, as convergence is measured at a given stage in the

algorithm, the value of may have changed since was evaluated, yielding a discrepancy between and .

Secondly, the term is difficult to zero. In a convex combination

method the auxiliary path flow vector satisfies that but this

does not apply to the current path flow vector unless equilibrium is reached. The



term is costly to evaluate because it involves path variables. It may be stated as the complementary slackness criterion, which yields no significant computational saving unless the consistency of energies is satisfied, in which case the criterion can be evaluated using only arc variables.

Thirdly, the term has to be evaluated if the path flow

vector does not come from the volume loading function . The

volume loading is costly to perform, not the evaluation of between two arc

flow vectors.

Lastly, the term is relatively easy to evaluate since it amounts to compare two arc-based vectors.

4.4. An auxiliary complementary slackness criterion

In an equilibration algorithm that takes the arc flows as the basic endog-

enous variables, an issue arises of the existence of path flows and path

times that generate the arc flows, i.e.

If this condition could not be met, there would be a “time discrepancy” of the arc flows that would preclude not only equilibrium, but also the primal feasibility !

Let us show that, in equilibration algorithms that handle arc flows by convex

combination, there is no risk of time discrepancy. We may assume that there are

flows by arcs and destinations, , underlying , since in the total arc flow

vector the destination/arc flow vectors are summed up. This decomposition is

left unchanged by convex combination. For each destination/arc flow vector, the primal feasibility condition is that, denoting by dX the elemental variation of X during ,

, (14a)

, (14b)

, (14c)

In Eq. (14) an arc time profile is associated to each arc a, by destination

node s : let us call it a chronological gap between the entry and exit times for a

given flow unit.

Then, if and are known, a chronological gap may be obtained

by application of the following procedure :

1. Let .



2. Let .

3. Let .

Let us call this procedure the “method of chronological inference”.

We may use the set of auxiliary time mappings in order to evalu-

ate an auxiliary complementary slackness criterion : rather than measuring

, which requires to storing , we can evaluate

(15)

because if then and .

Let us now consider , and . As

, the term can be evaluated as

which shows that the auxiliary complementary slackness is easy to evaluate. Then an overall criterion is as follows :

(16)

5. Equilibration algorithms

Here, we shall consider primal algorithms that handle flow vectors as basic endogenous variables. More specifically, as in most models of dynamic assign-ment, we shall consider convex combination methods : firstly at the arc level as in the LADTA model (section 5.1), secondly at the path level with separa-tion of volume loading and flowing (section 5.2), thirdly at the path level with integration of volume loading and flowing as in the model by Tong and Wong (section 5.3). Lastly, we shall introduce a novel algorithm called the “hybrid algo-

rithm” that combines the chronological gap vectors to the travel time vector

that results from the time-flow relationship into the current time

vector (section 5.4).

5.1. Arc-based convex combination method

The algorithm is stated shortly as :

(17)

This algorithm is simple to implement and it requires limited memory space, since it does not require storing path information.



To the best of our knowledge, criterion expressed by Eq. (16) is the simplest rigorous convergence criterion for that algorithm. Its implementation requires the

additional computational effort of inferring the chronological gap, computing

and assigning it onto the network, yielding arc flows . This doubles the base

computation cost of the algorithm ; a strategy to limit the increase is to measure

convergence only at one out of N iterations.

5.2. Path-based convex combination under time-flow consistency

This algorithm is stated shortly as :

(18)

In general, the arc flows obtained using this method, denoted as , differ

from those obtained by the arc-based convex combination, , even if the

coefficients are identical. This is in contrast to static assignment.

The overall criterion in Eq. (13) simplifies into

As , the second term can be replaced by a distance

between and , hence also by a distance between and , yield-

ing a simpler overall criterion :

(19)

As shown in Mai (2006), the first term may be evaluated as follows, using

auxiliary flow and next state

:

(20)

5.3. Path-based convex combination relaxing time-flow consistency

Denoting by the function that operates volume loading and

flowing in an integrated way, this algorithm is stated shortly as :

(21)

This method, which was proposed by Tong and Wong (2000), has two attractive features : first, its theoretical convergence towards equilibrium ought



to be robust ; second, the complementary slackness criterion is rigorous on its own right.

But the computational cost is very heavy because of the mesoscopic simula-

tion to perform ; moreover, the accuracy of is no trivial matter, which

could impede convergence.

5.4. A “hybrid” algorithm

Using the same notation k as iteration counter and as coefficient in the

convex combination, our hybrid algorithm is specified as follows :

Initialisation. Let , , , , ,

.

Service formation. Let .

User choice. Let .

Volume loading. Let and .

Convex combination. Let and

.

Complementary slackness. For each destination s in S, let ,

, and . Then, let

.

Convergence test. If then terminate, oth-

erwise replace , for each destination s in S.

Traffic flowing. Let .

Chronological inference. Derive from and for each destina-

tion s in S.

Time update. Set on the basis of , and eventually some previ-

ous values.

Progression. Increment and go to Service formation.

The time update may be a convex combination (not to be confused with that on flows) :



6. A large-size experiment

The main objective of this experiment is to assess if our implementation of the LADTA model can be of practical use for real world networks. To this end, we first selected a large interurban road network on which congestion frequently occurs. More detailed motivations concerning the choice of the network are given in section 6.1. Second, we collected the data (section 6.2) and processed them to provide appropriate inputs to the simulator (section 6.3). Finally, we present some results related to the evolution of the computation time per iteration (section 6.4).

6.3.1. Motivations

The Vallée du Rhône (VDR) area, located between Lyon and Marseille, is of main concern for the French DOT, not only because some wine is produced there, but also because a significant part of the trans-European road traffic Europe concentrates on it. This is particularly noticeable in summer time, when tourists coming from northern Europe, including Belgium, Germany, Netherlands and the UK travel across France to reach southern countries like Greece, Italy and Spain. When concerned with their choice of itinerary, travellers certainly do not only con-centrate on wine tasting opportunities on the way. A quick glance at the structure of the demand (see Figure 1) explains why a large part of the traffic concentrates on the A7 highway, in the VDR area between Lyon and Orange. Also, the VDR road network supports a very high load of traffic during the whole year, due to goods transportation by trucks. Moreover, traffic forecasts do show an increase of demand for the coming 20 years, for both passenger cars and trucks.

Figure 1. Structure of the traffic demand on the VDR area during summer time



Besides high cost measures (i.e. investments in infrastructure), road authori-ties and highway operators are highly interested by fine-grain (i.e. within an hour) and dynamic (i.e. traffic responsive) time varying exploitation measures to better operate the network. A dynamic traffic assignment tool can be of great help in the design and implementation of dynamic traffic control measures, both at the conception stage (i.e. cost–benefit assessment, design of operating rules...) and at the operation stage, as a decision-aid tool. This last use is certainly the more demanding. It implies to be able to compute and keep up to date several sce-narios, within a few minutes, in order to provide the road-operator with accurate traffic forecasts for the coming hours.

6.2. Data acquisition

Two services of the French DOT, SETRA and CETE Méditerranée, provided us with the following data :

a geocoded model of the road network, comprising 732 (undirected) arcs •and 595 nodes, including connectors ;

for each arc • a its capacity qa its length la, together with its measured aver-age free flow speed, va ; among the 732 arcs, 471 have a capacity of 1,800 veh/h, 26 a capacity of 2,600 veh/h, 145 a capacity of 3,600 veh/h (corresponding to 2-lanes highway sections), 81 a capacity of 5,400 veh/h (corresponding to 3-lanes highway sections). Seven connectors (to Belgium, Germany, the UK, Spain, Italy, etc.) have an infinite capacity.

a static O–D matrix, representing the average annual daily demand for •1,137 O–D pairs, in year 2000, for both passenger cars and trucks, including demand from connectors.

6.3. Data generation

For the purpose of our experiment, those data have been used to generate the appropriate inputs to the LADTA implementation, following the three steps below :

Step 1 : generation of directed arcs. For each undirected arc linking the

set of nodes , two directed arcs and have been

created.

Step 2 : generation of arc data. For each undirected arc , the free flow travel time and capacity profiles of the associated directed arcs and have been set up as follows :

.



Step 3 : generation of demand. For each O–D pair , a cumulated volume

profile has been generated. The annual average daily demand has

been distributed on 24 consecutive periods of one hour each, according to the

following equations

, with for and

The sum of the coefficients is set to 1,8 in order to simulate a summer

Saturday day in year 2020. The distribution of the coefficients during the day

has been chosen to simulate a morning peak and an evening peak within the

simulated day. Figure 2 illustrates the shape of the corresponding flow functions.

Note that coefficients do not depend on the O–D pair , i.e. we assume that

the distribution of the demand within the day is the same for each O–D. This is

certainly a very bad approximation of the reality, but does not conflict with our main objective.

Figure 2. values of the wk coefficients used to generate the demand profiles

6.4. Results

The convex combination operation at the core of the hybrid algorithm pre-sented in section 5.4 is a classical Method of Successive Averages. When applied on scalar values, as it is the case for static assignment, there is noth-ing special to mention. But in the case of dynamic assignment, the values we



are dealing with are (piece-wise linear) functions of time. When computing

, the number of pieces in , denoted as , is in

the range . At the end of the main loop,

is assigned the value of . In other words, increases with the number

of iterations, in a way, which is hard to predict and control. This remark has two

bad consequences in practice :

the computation time par iteration increases with the number or iterations ;•

the memory needed to store the variables increases with the number of •iterations.

This contrasts heavily with the static assignment problem, and typically results from the time dimension of the dynamic assignment problem.

To better figure out the computational behaviour of our implementation, we recorded the time per iteration and the memory usage during a simulation of the VDR network. The simulation was run on a laptop computer equipped with a 1.6 GHz Intel Pentium M processor, 512 MB memory, and running under Windows XP. The code, written in C++, was compiled with g++, with all standard optimisations turned on. Results are presented in Figure 3 and Figure 4.

Figure 3 shows the computation time taken from iteration 1 to iteration 4. As expected, the time per iteration increases with the number of iterations, but in a reasonable way, growing slowly from 6 to 8 seconds.

Figure 3. Evolution of the time per iteration during the simulation



In Figure 4 is plotted the memory occupancy during the simulation. It grows significantly, starting from 50 MB up to nearly 350 MB at iteration 40.

Figure 4. Evolution of the memory occupancy during the simulation

0

50

100

150

200

250

300

350

0 10 20 30 40 50

Itération

Mé

mo

ire

(M

o)

7. Conclusion

Using a high-level formulation of dynamic traffic assignment, we analysed its specific complexities, most notably :

the chronological relativity of the volume loading ;•

the chronological relativity of the time-flow relationship ;•

that the time-flow relationship at the path level does not imply a time-flow •consistency ;

that the time-flow consistency i.e. • is a necessary condition for equilibrium.

We established some related properties of consistency.

As concerns the measurement of convergence, we showed that :

the chronological relativity impedes the computation of the complementary •slackness criterion ;

an auxiliary complementary criterion is available, which is much easier •to evaluate when the volume loading and traffic flowing problems are addressed separately ;

there is a sound approach to design a rigorous convergence criterion, which •will be composed of several components except when the volume loading and traffic flowing problems are integrated.



The algorithmic approach of Tong and Wong (2000) deserves emphasis as it integrates those two problems. We analysed it as well as other convex combina-tion algorithms, either arc-based or path-based, in order to complement them with rigorous convergence criteria. We introduced a novel “hybrid” algorithm. Lastly, we reported on numerical application of the LADTA model to a large size problem, demonstrating its computational efficiency. Further developments are reported in our technical report (Leurent et al., 2006), in which path-based as well as arc-based formulations are introduced, with identification of more time variables, and introduction of various algorithmic frameworks that may be used to design novel algorithms for dynamic assignment.

8. References

M.J. Beckmann, C.B. McGuire, C.B. Winsten. Studies in the Economics of Transportation. New Haven : Yale University Press, 1956.

G. Bellei, G. Gentile, N. Papola (2005) A within-day dynamic traffic assignment model for urban road networks. Transportation Research Part B, (39) : 1–29.

M. Ben Akiva, S. Lerman. Discrete Choice Analysis : Theory and application to Travel Demand. MIT Press, Cambridge, Mass, 1985.

A. De Palma, F. Marchal, Y. Nesterov. Metropolis : a modular system for dynamic traffic simulation. Paper presented at the 76th TRB annual conference. TRB, Washington DC, 1996.

S.E. Dreyfus. An appraisal of some shortest-path algorithms. Operations Research, (17) : 395–412, 1969.

M. Florian, M. Mahut, N. Tremblay. A simulation-based dynamic traffic assignment model : DYNAMEQ. CRT, University of Montreal and INRO Montreal, QC, Canada, 2005.

T.L. Friesz, D. Bernstein, T.E. Smith, R.L. Tobin, B.W. Wie. A variational inequal-A variational inequal-ity formulation of the dynamic network equilibrium problem. Operation Research, 41 : 179–191, 1993.

T.L. Friesz, D. Bernstein, Z. Suo, R.L. Tobin. Dynamic network user equilibrium with state-dependent time lags. Network and Spatial Economics, 1 : 319–313, 2001.

T.L. Friesz, R. Mookherjee. Solving the dynamic network user equilibrium prob-lem with state-dependent time shifts. Transportation Research B . 40(3) : 207–229, 2006.

G. Gentile, L. Meschini and N. Papola. Macroscopic Arc Performance Models For Within-Day Dynamic Traffic Assignment. Paper read at the TRB Annual Meeting, 2003.

H. Joksch. The shortest route problem with constraints. Journal of Mathematical Analysis and Applications, 14 : 191–197, 1966.



M. Kuwahara, T. Akamatsu. Decomposition of the reactive dynamic assign-Decomposition of the reactive dynamic assign-ments with queues for a many to many origin–destination pattern. Transportation Research B .31(1) : 1–10, 1997.

D.R. Leonard, P. Gower and Taylor NB (1989) Contram : structure of the model. TRRL Report RR # 178. Crowthorne, UK.

F. Leurent. On network assignment and supply-demand equilibrium : an analysis framework and a simple dynamic model. Paper presented at the 2003 European Transport Conference (CD Rom edition), 2003.

F. Leurent. The multiclass flowing problem in a dynamic traffic assignment model. Paper presented at the 2004 European Transport Conference (CD Rom edition), 2004.

F. Leurent. The network cost of congestion : analysis and computation of marginal social cost disaggregated by O–D pair and departure time. Paper presented at the 2005 European Transport Conference (CD Rom edition), 2005.

F. Leurent. Structures de réseau et modèles de cheminement. Éditions Lavoisier, Collection Tec et Doc. Lavoisier, Cachan, France, 2006.

F. Leurent, H.D. Mai, V. Aguiléra. 1. Sur la caractérisation d’un équilibre dyna-mique du trafic : formulations analytiques, mesurage de convergence, algorithmes d’équilibrage. Technical Report, ENPC, France, 2006.

J. Li, O. Fujiwara, S. Kawakami. Reactive dynamic user equilibrium model in net-Reactive dynamic user equilibrium model in net-work with queues. Transportation Research B .34(8) : 605–624, 2000.

Y. Lin and B. Heydecker. Dynamic departure time and stochastic user equilibrium assignment. Transportation Research B . 39(2) : 97–118, 2005.

G.F. Newell. A simplified theory of kinematic waves in highway traffic, part I : general theory. Part II : queuing at freeway bottlenecks. Part III : multi-destination flows. Transportation Research B ., 27 : 281–313, 1993.

M. Patriksson. The Traffic Assignment Problem, Models and Methods. VSP, Utrecht, Pays-Bas, 1994.

H.J. Payne. FREFLO : a macroscopic simulation model of freeway traffic. TRR, 772 : 68–75, 1979.

S. Peeta and A. Ziliaskopoulos. Foundations of dynamic traffic assignment : The past, the present and the future. Network and Spatial Economics 1, 3(4) : 233–266, 2001.

S. Peeta and C. Zhou. Stochastic quasi-gradient algorithm for the off-line sto-chastic dynamic traffic assignment problem. Transportation Research B . 40(3) : 179–206, 2006.

B. Ran and D. Boyce. Dynamic urban transportation networks models : theory and implications for intelligent vehicle-highway systems. Lecture notes in economics and mathematical systems #417. Springer-Verlag, 1994.

B. Ran and D. Boyce. Modelling Dynamic Transportation Networks. Springer, Berlin, 1996.

B. Ran, M.S. Shin, R.R. He and K. Choi (2000) Introducing platoon dispersion into an analytical dynamic assignment process. TRR, 1733 : 96–104.



C.O. Tong, S.C. Wong. Predictive dynamic traffic assignment model in congested capacity-constrained road networks. Transportation Research B .34(8) : 625–644, 2000.

D. Van Vliet. SATURN : a modern assignment model. Traffic Engineering and Control, 23 : 578–581, 1982.

H.R. Varia and S.L. Dhingra. Dynamic user equilibrium traffic assignment on con-gested multidestination network. Journal of Transportation Engineering, 130(2) : 211–221, 2004.

J.G. Wardrop. Some theoretical aspects of road traffic research. Proc. Inst. Civil Engrs, I : 325–378, 1952.

B.W. Wie, R.L. Tobin and M. Carey. The existence, uniqueness and computa-tion of an arc-based dynamic network user equilibrium formulation. Transportation Research B . 36(10) : 897–918, 2.


Contribution à la modélisation et la simulation du flux de trafic :

approche hybride basée sur les systèmes multi-agents

Mohamed Saïd EL HMAM, Hassane ABOUAÏSSA, Daniel JOLLY

Laboratoire de Génie Informatique et d’Automatique de l’Artois (LGI2A) - EA

3926 Faculté des Sciences Appliquées - Université d’Artois

Technoparc Futura 62400 Béthune

Résumé

Cet article présente une approche de modélisation de flux de trafic dite hybride. Cette démarche récemment adoptée par les chercheurs en transport utilise conjointement les deux représentations de flux de trafic : microscopique et macroscopique. L’intérêt de ce couplage est de bénéficier des atouts des deux modèles tout en évitant leurs inconvénients. En effet, il s’agit d’adapter le modèle au niveau de détails et à la taille des phénomènes à traiter. Dans ce papier, nous proposons un modèle hybride basé sur le paradigme agent en mettant l’accent principalement sur la procédure de couplage des deux modèles. Ce modèle se distingue par son aspect générique qui consiste à utiliser plusieurs modèles macroscopiques et sa capacité à gérer plusieurs zones de transition micro–macro et vice versa.

Introduction

L’augmentation du nombre de véhicules aux abords des grands centres urbains, surtout à certaines heures de la journée, s’est traduite par une forte demande en trafic qui dépasse souvent la capacité du réseau routier.

Afin de mieux maîtriser cet afflux de véhicules et de mieux gérer nos infrastruc-tures routières, il est rapidement apparu la nécessité de nous doter de modèles de flux de trafic. Ainsi, de nombreux modèles de flux de trafic ont été développés pour comprendre les phénomènes observés et proposer des solutions permettant d’en limiter les effets.



La modélisation du flux de trafic est une tâche coûteuse et difficile compte tenu de la variabilité du flux (différents types de véhicules, aléas liés au comportement des conducteurs, conditions météorologiques…) et du grand nombre de données à traiter. En effet, la variabilité rend la résolution analytique très compliquée et peu réaliste, et le nombre important de données à traiter nécessite d’énormes ressources informatiques.

Deux grandes catégories de modèle de flux de trafic ont été proposées, les modèles macroscopiques et les modèles microscopiques. Les modèles macroscopiques décrivent de manière globale et moyenne le flux de trafic. Ils sont utilisés en général pour traiter les problèmes de planification stratégique, voire tactique [5], et commander le flux. Ces modèles traitent le flux à grande échelle, mais ils sont incapables d’expliciter les interactions entre véhicules. Or, les modèles microscopiques traitent le flux au niveau des véhicules. L’état du flux est cependant directement lié aux interactions entre véhicules ainsi que leurs mouvements. Ils sont utilisés principalement pour la simulation [17] et l’étude du comportement individuel des conducteurs [9]. La taille du système à traiter tend alors à en limiter leur utilisation. En effet, pour simuler un flux de trafic, ils néces-sitent des ressources informatiques importantes afin de traiter la grande quantité de données. Le choix du modèle dépend de l’objectif de la modélisation ainsi que de la taille du système étudié.

Une nouvelle approche de modélisation dite hybride a vu le jour à la fin du 20e siècle [14]. Elle consiste à faire cohabiter les deux représentations de flux de trafic citées ci-dessus au sein du même système. Le couplage d’un modèle macroscopique avec un modèle microscopique au sein du même système per-met d’utiliser les avantages des deux modèles en les adaptant aux phénomènes et aux situations traitées en minimisant leurs inconvénients.

Le modèle hybride offre alors l’avantage de réaliser une étude plus fine, au niveau microscopique, de l’évolution du flux de trafic face à l’apparition d’événe-ments aléatoires (panne, accident…) ou de modifications de comportement de certains conducteurs. Elle permet aussi de traiter un flux important de véhicules circulant sur un réseau routier de grande taille grâce à la vitesse de calcul qu’offre le modèle macroscopique sans pour autant nécessiter d’énormes besoins en ressour-ces informatiques. Ce concept de modélisation permet non seulement de simuler, mais de proposer des techniques de régulation du flux de véhicules circulant dans un grand réseau routier. Dans cette perspective, seules les parties qui nécessitent un grand niveau de détail (carrefour, rond-point, rampe d’entrée/sortie…) seront simulées au niveau microscopique, le reste du réseau le sera au niveau macros-copique. Ainsi, il est possible d’évaluer l’impact d’une régulation, conçue à partir du modèle macroscopique, au niveau microscopique. De même, il est possible d’étudier des conséquences d’une commande du flux de trafic réalisée au niveau microscopique sur le reste du réseau routier simulé au niveau macroscopique.

Cet article est structuré de la façon suivante : nous présentons un rapide état de l’art de la modélisation hybride, nous décrivons ensuite le modèle hybride que nous avons développé, notamment l’interfaçage entre les deux modèles macroscopique et microscopique ; enfin, nous terminons par une conclusion et des perspectives de développement de nos travaux.

EL Hmam Approche hybride basée sur les systèmes multi-agents


1. Modélisation hybride

Les travaux dans le domaine de la modélisation hybride du flux de trafic sont prin-cipalement orientés vers la représentation d’un système dynamique composé d’une partie continue et d’une autre discrète. Cette démarche de modélisation est inspirée des études menées sur les gaz. En tant que matière, le comportement du gaz peut être étudié au niveau microscopique en représentant les interactions intermoléculai-res. Dans ce contexte, l’étude porte alors sur les phénomènes locaux qui régissent le comportement du gaz. Il peut être aussi étudié au niveau macroscopique à l’aide de la description de son état global (étude des phénomènes globaux) [4].

Bien que les descriptions se situent à des niveaux différents, les phénomènes qui régissent le comportement du gaz sont étroitement liés. En effet, la représen-tation effectuée au niveau local peut être généralisée pour décrire le gaz au niveau macroscopique. Ceci est possible grâce à la théorie de la cinétique des gaz qui permet d’établir les équations du comportement macroscopique (équations de Navier Stockes [18]) à partir de l’étude des interactions entre les molécules.

Ce principe de modélisation hybride a été appliqué avec succès dans plu-sieurs domaines tels que la croissance de cristaux en solution [22], la propaga-tion d’une fracture dans une pièce de silicone [2] ainsi que dans le domaine de la productique [26] et dans l’écoulement de fluide [13].

Dans le domaine du trafic, ce principe est encore à l’état de développement, et il n’existe pas encore une définition précise de la notion de modèle hybride. Chaque auteur apporte sa définition et sa vision propre de ce type de modèle. Ainsi, nous distinguons globalement quatre types de modèles dits hybrides (Nous trouvons aussi dans la littérature des modèles hybrides mésoscopiques-microscopiques tels que le modèle de Burghout [6] qui a pour objectif de calculer les plans d’itinéraires avec le modèle mésoscopique et simuler le flux avec le modèle microscopique) :

Le premier, proposé par Chang [7] « MacroParticle Simulation Model » per-met de calculer l’écoulement du trafic soit à partir du flux, soit en considérant un paquet de véhicules qui adaptent leurs vitesses à la vitesse d’équilibre en fonc-tion de la densité du segment de route étudié.

Le deuxième type de modèles hybrides a été élaboré par Daganzo [8]. Il per-met d’étudier le mouvement des véhicules lourds (considérés comme des parti-cules) sous forme de trajectoires dans le flux du trafic assimilé à un liquide.

Le troisième concerne le modèle développé par Helbing [15,16] dans lequel les éléments singuliers du réseau routier (rampes d’entrée/sorties, etc.) sont décrits au niveau macroscopique, alors que le reste des éléments est modélisé au niveau microscopique. Cette démarche est justifiée par le fait qu’il est relative-ment facile de décrire ces éléments singuliers à l’aide d’un modèle macroscopi-que, puisque cela ne nécessite que l’ajout d’un terme dans l’équation du modèle, alors que le choix d’un modèle microscopique nécessite la prise en compte du comportement des véhicules individuels, ce qui rend la description plus difficile.

Enfin, le quatrième type de modèles rejoint notre approche de la modélisation hybride du flux de trafic routier. En effet, dans cette catégorie, Magne, Poshinger et Bourrel [20], Poshinger [24] et Bourrel [3] ont proposé des modèles dans le



but de résoudre les problèmes d’échelle inhérents à la description du trafic selon les deux points de vue, microscopique et macroscopique. Dans ce contexte, le principe consiste à modéliser les éléments du réseau qui ne nécessitent pas trop de détails au niveau macroscopique et de se focaliser sur les parties sensibles aux changements brusques et discontinus en les étudiant au niveau microsco-pique. Ainsi, on arrive à réduire le nombre des véhicules traités tout en assurant une description claire et fine des éléments singuliers tels que les intersections, les rampes d’entrée et de sortie d’autoroute, etc.

Nous nous inspirons dans nos travaux des modèles de Magne, Poshinger et Bourrel, car ils coïncident avec le principe de la modélisation hybride développé dans nos travaux de recherche.

D’une manière générale, la difficulté principale rencontrée lors du développement de ce type de modèles hybrides est d’assurer la transmission des informations entre deux représentations différentes du trafic. En effet, le principe consiste à traduire des données microscopiques caractérisées par les variables de type position et vitesse des véhicules, en termes de données macroscopiques déterminées par des paramè-tres tels que la vitesse moyenne, la densité et le débit du flux de trafic routier.

Tous ces modèles se distinguent par le choix des modèles utilisés ainsi que par la procédure de couplage. Il faut noter que celui de Bourrel est considéré comme une généralisation de ceux proposés par Helbing, Magne, Poshinger puisqu’il com-bine les différentes méthodes d’interfaçage tout en apportant des améliorations.

2. Schéma global du modèle hybride

Le modèle hybride décrit dans cet article est basé sur la cohabitation de deux représentations d’écoulement de trafic au sein d’un même système, l’une décrivant globalement le flux et l’autre les particules composant ce flux. Comme le montre la Figure 1, ces deux représentations sont séparées par des zones de transition qui constituent des interfaces de communication entre les deux mon-des : macroscopique et microscopique.

Figure 1. Tronçon hybride



La difficulté majeure de ce modèle est d’assurer le bon passage d’informa-tion entre les deux représentations du flux au niveau des zones de transition. Il s’agit plus particulièrement de garantir la non-déformation des phénomènes et la conservation des données qui traversent les sas de communication vers l’amont et vers l’aval.

La procédure de couplage nécessite la prise en compte des problèmes liés principalement à l’agrégation des informations entre les deux mondes [4]. Ces problèmes sont issus :

de la transmission d’information : les zones de transition doivent donc assu-•rer la transmission des données dans les deux sens simultanément ;

du manque d’information : le débit de sortie de la zone macroscopique ne •nous donne aucune information sur la répartition des véhicules dans la par-tie microscopique ;

du faible nombre de particules : étant donné que les véhicules sont le seul •moyen de communication, l’absence de véhicules implique l’absence de communication et, par conséquent, une perte d’information ;

de la conversion de données : la conversion de données discrètes en des •données continues peut créer des oscillations ; la conversion des données dans le sens macro-micro peut générer des incertitudes, notamment lors du passage des valeurs continues de débit en un nombre de véhicules qui ne peut être qu’un entier ;

de la vitesse de propagation des contraintes : celle-ci est due à la différence •entre la loi de comportement adoptée par le modèle macroscopique et la loi de comportement du modèle microscopique.

Nous venons de lister les principaux problèmes liés au couplage des deux modèles microscopique et macroscopique. D’autres difficultés seront également à surmonter lors de la validation du modèle hybride.

Pour mettre en place le modèle hybride, nous avons proposé un système multi-agents composé des agents de simulation suivants :

agent macroSection qui représente un tronçon macroscopique ;•

agent microSection qui représente un tronçon microscopique ;•

agent véhicule qui représente le couple conducteur–véhicule ;•

agent intersection chargé de contrôler le flux au niveau des carrefours et •des rampes d’entrée–sortie.

Le choix des systèmes multi-agents comme paradigme de modélisation a été justifié dans nos travaux antérieurs [11]. Les agents de simulation cités ci-dessus sont de type JADE (Java Agent Development Frame) [1] dont le cycle de vie est constitué d’un certain nombre de comportements exécutés d’une manière contiguë. L’ensemble des comportements de ces agents est décrit dans la sec-tion suivante. Toutefois, nous ne décrirons pas le comportement des agents de régulation (agent intersection), car cela sort du cadre de cet article.



3. Comportement des agents de simulation

Nous partons des considérations qu'un réseau routier hybride est composé d'un ensemble de tronçons de route interconnectés. Ces tronçons peuvent être représentés au niveau macroscopique (macrosection) ou microscopique (micro-section) selon les besoins de la simulation. Chaque agent microSection est constitué d'un ensemble de voies sur lesquelles circulent des véhicules.

Lorsque plusieurs agents microSections se croisent, ils forment des intersec-tions qui peuvent être à feux ou à priorité. Pour arriver à destination, un véhicule se déplace à une vitesse variable entre les nœuds (intersections) du réseau par-tant d'un point d'origine et suivant son plan de route vers sa destination.

La figure (Figure 2) présente un schéma simplifié du modèle hybride. Les agents de simulation représentant les éléments du réseau hybride sont distribués selon trois niveaux. Le premier niveau contient les agents véhicules qui consti-tuent les éléments microscopiques de la simulation. Le deuxième niveau contient les agents chargés d'assurer la communication entre le monde macroscopique et le monde microscopique. Le troisième niveau concerne la régulation du flux au niveau des carrefours par le biais des agents intersection. Le comportement de ces agents est décrit dans les sections suivantes. Nous explicitons dans un premier temps le comportement des agents macroSection et microSection et décrivons ensuite très brièvement le comportement de l'agent véhicule.

Figure 2. Agents de simulation



Agent macroSection

L’agent macroSection représente un tronçon étudié au niveau macroscopi-que. Son rôle principal est de calculer les valeurs de débit, vitesse et densité en appliquant des modèles de flux de trafic (discrétisés) tirés de la littérature. Dans le cadre de nos travaux, nous avons appliqué les modèles de LWR [19,25], Payne [23] et Zhang [27].

À chaque pas de temps macroscopique, l’agent macroSection calcule les valeurs de flux (débit, vitesse, densité) de chaque cellule et communique les conditions aux limites aux agents microSection (Figure 3).

Figure 3. Agent macroSection

Dans le sens macro-micro, l’agent macroSection doit garantir la propagation des contraintes (informations) vers l’amont, en communiquant à l’agent micro-Section les conditions aux limites exprimées en termes de débit, vitesse et den-sité. Ces paramètres sont calculés à partir de la dernière cellule macroscopique. Ces données vont permettre à l’agent microSection de créer des véhicules à l’entrée du tronçon microscopique.

Étant donné que les véhicules sont les seuls éléments porteurs d’information (densité, débit, vitesse), leur absence implique une interruption de propagation des informations.



Dans la partie microscopique, les véhicules se déplacent en conformité avec les lois de poursuite : chaque véhicule doit donc connaître la position et la vitesse du véhicule qui le précède. La zone de transition a donc pour rôle d’assurer aux véhicules sortant de la partie microscopique un déplacement conforme à la loi de poursuite. C’est la raison pour laquelle Magne [20] a proposé de créer un véhi-cule fictif à la sortie de la cellule hybride. Ce véhicule fictif est créé à partir des véhicules qui quittent la cellule microscopique.

En nous inspirant de cette idée, nous avons également créé des véhicules fictifs à la sortie de la cellule hybride. À l’état initial, les véhicules sont créés dans

chaque voie à une distance où est la densité à l’équilibre de la pre-

mière cellule macroscopique. Les véhicules fictifs sont créés par l’agent micro-Section de telle sorte qu’ils aient des mouvements conformes aux conditions de circulation de la première cellule macroscopique. Grâce à ce mécanisme, les véhicules qui quittent la cellule microscopique sont assurés de poursuivre leur mouvement en tenant compte des conditions de circulation en aval. Leurs vites-ses seront mises à jour et les contraintes seront propagées en continuité avec les cellules en aval.

La conversion des valeurs discrètes en des valeurs continues crée aussi des anomalies lors du passage micro–macro. En effet, la méthode de calcul de débit cumulé que nous avons adoptée nous donne des valeurs discrètes. Il s’en suit que la cellule macroscopique en aval peut adopter un comportement oscilla-toire et génère aussi des valeurs de débit discrètes à la cellule macroscopique suivante.

Pour lisser ces valeurs, nous avons filtré les données à l’entrée de la cellule macroscopique en aval en insérant un simple filtre « moyenneur » (sur les trois dernières valeurs du débit). Ainsi, l’effet de hachage sur le débit est fortement atténué.

Agent microSection

L’agent microSection synchronise l’exécution des agents véhicules. Il assure aussi la propagation des informations en amont et en aval vers un tronçon traité au niveau microscopique.



Figure 4. Agent microSection

Afin d’assurer la propagation des informations vers l’amont (sens micro–macro), l’agent microSection calcule les paramètres macroscopiques : densité, débit et vitesse moyenne au niveau du modèle microscopique en agrégeant les informations sur les véhicules. Ces paramètres sont communiqués ensuite à la dernière cellule macroscopique qui les introduit dans ses équations de calcul de son prochain état.

Pour assurer la propagation des informations vers l’aval (sens macro-micro), l’agent microSection désagrège les paramètres de débit, vitesse et densité au niveau microscopique. La question qui se pose alors est :

comment l’agent microSection impose le débit q — j (débit à la sortie de la dernière cellule macroscopique) à l’entrée de la cellule hybride ?

Afin de répondre à cette question, l’agent microSection adopte la procédure de génération détaillée ci-dessous.

À partir du débit qj, l’agent microSection calcule la période p qui sépare l’ar-rivée de deux véhicules successifs dans la zone de transition. Ensuite, il crée la liste des instants où les véhicules doivent être générés (instants de création théoriques).

Dans le but d’expliquer la procédure de génération des véhicules à partir du débit, nous proposons l’exemple suivant. Supposons que le débit fourni par la dernière cellule macroscopique est qj = 0,35 véh/s. Sachant que le pas de temps



microscopique est h = 1 s et le pas de temps macroscopique est t = 20 s, la liste des instants de création des véhicules est la suivante (Tableau 1) :

Tableau 1. Liste des instants de création théoriques et effectifs

Afin d’éviter certains effets de bord conduisant à des incohérences, l’agent microSection génère les véhicules à différents instants théoriques suivant la loi tk = p(1/2 + k) avec k . Au moment de leur création, les véhicules sont affec-tés d’une vitesse égale à la vitesse d’équilibre de la cellule macroscopique vj. Les instants de création théoriques sont des instants de création prévus (Figure 3). En effet, dans le cas où ces instants (calculés par l’agent microSection) ne coïn-cideraient pas avec les instants de création effectifs (pas de calcul microscopique k⋅h) (voir exemple (Tableau 1)) ; les véhicules sont créés avec un certain retard. Pour prendre en compte ce retard, l’agent microSection introduit une correction spatiale u = vj ⋅ où est le décalage entre le temps de création effectif et théorique (Figure 6).

Figure 5. Génération des véhicules



Figure 6. Correction spatiale apportée à la procédure de génération des véhicules

instant decréationthéorique

instant decréationeffectif

retard

correstion spaciale

temps

Cette procédure risque de provoquer des erreurs importantes sur les valeurs du débit de véhicules dans le cas d’une circulation fluide aux faibles valeurs du débit. Si nous reprenons le même exemple que précédemment, le débit de 0,35/s correspond à 7 véh/20 s. Or, nous n’avons créé que 6 véh/20 sec. La conser-vation des données n’est donc plus assurée. Pour remédier à cet inconvénient, nous avons apporté une correction à la génération des véhicules à l’entrée du tronçon microscopique. Après chaque pas de temps macroscopique, le débit résultant est comparé avec le débit de départ. Ainsi, une correction peut être réalisée sur la génération des véhicules au pas de calcul suivant. Dans le cas de l’exemple, le prochain débit sera augmenté d’une valeur de 0,05 véh/s.

Le même principe est adopté dans le cas d’un flux congestionné. Avec un débit très important et en appliquant la même procédure, nous risquons de ne plus pouvoir générer les véhicules faute d’espace. Par conséquent, la génération des véhicules est retardée aux prochains pas de calcul en apportant un terme de correction aux débits suivants. Le modèle macroscopique ne nous donne aucune information sur la distribution des véhicules dans la partie microscopique.



L’agent microSection a donc également pour rôle d’affecter les véhicules aux voies de circulation. Cette affectation ne peut s’effectuer que sous certaines conditions : un véhicule roule prioritairement à droite et doit respecter une dis-tance de sécurité par rapport au véhicule qui le précède. Dans le cas d’un tronçon à trois voies, l’agent microSection exécute l’algorithme suivant :

Début

Si (la distance dans la voie à droite est suffisante), alors

Insérer véhicule dans la voie à droite

Sinon si (la distance dans la voie du milieu est suffisante), alorsInsérer véhicule dans la voie du milieu

Sinon si (la distance dans la voie de gauche est suffisante), alorsInsérer véhicule dans la voie à gauche

Sinon retarder la création du véhicule au prochain pas de temps

Fin si

Fin si

Fin si

Fin

Agent véhicule

L’agent véhicule est un agent autonome. Il a son propre but et sa propre connaissance de l’environnement. Cette connaissance supposée partielle cor-respond au champ de vision du conducteur. Elle permet ainsi à l’agent d’évoluer dans son environnement immédiat. L’architecture de l’agent véhicule est illustrée à l’aide de la figure (Figure 7).

L’agent véhicule est aussi un agent réactif [12]. Ses décisions sont générées sur la base de sa perception de l’environnement. Ses actions sont ses dépla-cements physiques sur une voie. Afin de satisfaire les contraintes liées à la dynamique du trafic, les réactions de l’agent véhicule doivent être rapides. Nous avons privilégié cette représentation plutôt que celle d’un agent cognitif, car nous ne nous intéressons pas aux problèmes qui nécessiteraient de l’agent véhicule une sauvegarde de l’état de l’environnement liée par exemple, aux problèmes de traitement des conflits [21] ou d’anticipation [9]. Avant de se déplacer, il évalue son environnement (détection des véhicules qui l’entourent et des infrastructu-res routières). Il collecte toutes les informations qui le concernent, en particulier les positions et les vitesses des véhicules proches dans un rayon limité par le champ de vision du conducteur. Ce champ de vision dépend des conditions météorologiques (pluie), de circulation (congestion) ainsi que de la géométrie de l’infrastructure (virage).



Figure 7. Architecture de l’agent véhicule

Durant son déplacement, l’agent véhicule adapte sa vitesse pour atteindre la vitesse désirée. Il tend à accélérer si sa vitesse est inférieure à la valeur dési-rée, et ce, en fonction de l’espace disponible. Dans le cas d’un trafic dense, la première réaction de l’agent est de vérifier la possibilité de dépasser. À ce stade, le dépassement est soumis aux règles dictées par le modèle de changement de voie. Devant l’impossibilité de dépasser, il reste sur sa voie d’origine tout en adaptant sa vitesse suivant le modèle de poursuite.

Ainsi, le comportement de l’agent véhicule est soumis à deux lois complémen-taires, la première concerne l’application d’un modèle de poursuite et la seconde repose sur le modèle de changement de voie. Ces deux lois sont décrites d’une manière détaillée dans nos travaux antérieurs [11]. En résumé, l’agent véhicule effectue une perception de son environnement afin de déterminer les positions des véhicules qui l’entourent. À partir des données et des informations tirées de son plan de déplacement, l’agent véhicule exécute un modèle de comportement [10]. Ce modèle contient un ensemble de règles issues du comportement de l’agent réel face aux différentes situations du flux.



Le modèle de comportement conduit à l’application de la loi de poursuite ou de changement de voie. La fin du cycle de vie de l’agent véhicule est contrainte par l’arrivée à destination.

4. Simulation

Paramètres de simulation

Avant d’entamer la procédure de validation, nous allons fixer les paramètres de simulation de la façon suivante :

le diagramme fondamental utilisé est celui de METANET :•

: 50 véh/voie/km

Capacité : 1800 véh/voie/h

vf : 90 km/h

la longueur du tronçon hybride : 3 km dont 2 km au niveau macroscopique •et 1 km au niveau microscopique

le pas de temps microscopique : 0,1 s•

le pas de temps macroscopique (Tableau 2).•

Les pas de temps sont choisis de telle sorte que la condition Courant-Friedrichs-Lewy [5] soit vérifiée.

Tableau 2. Deux cas de discrétisation appliqués

Validation de la procédure de couplage

Afin de vérifier la qualité de la procédure de couplage adoptée entre les deux modèles macroscopique et microscopique, nous avons simulé deux tronçons simples en régime stationnaire et congestionné. Le premier est simulé à l’aide



d’un des modèles macroscopiques (LWR, Zhang et Payne) (Dans le cadre de cet article, nous ne présentons que les résultats du modèle de Zhang), le second est simulé à l’aide de notre modèle hybride. Nous proposons dans un premier temps de modifier la demande à l’entrée du tronçon (Figure 8), et ensuite de bloquer la sortie pour simuler une congestion qui doit se propager en amont (Figure 9).

Figure 8. Propagation en aval

tronçon macroscopique

tronçon hybride

sens de circulationtemps

qsm

qsh

qe

Figure 9. Propagation en amont

tronçon macroscopique

tronçon hybride

sens de circulationtemps

ps

Au cours des deux premiers scénarios, nous avons comparé les résultats (Figure 10) fournis par le modèle Zhang et notre modèle hybride lorsque la cir-culation est fluide pour deux pas de discrétisation macroscopique (10 s et 4 s). Les résultats qualitatifs montrent que le modèle hybride reproduit le même signal d’entrée sans déformation. Les résultats quantitatifs montrent également que le modèle hybride est équivalent au modèle de Zhang. Cela signifie que le couplage n’introduit aucune déformation dans la propagation des informations.



Le modèle hybride respecte donc les propriétés fondamentales attendues d’un tel modèle de simulation de flux de trafic que sont : la conservation du flux et la propagation des contraintes.

Dans le mode congestionné (Figure 11), nous remarquons aussi que le modèle hybride reproduit le même phénomène que le modèle de Zhang quali-tativement et quantitativement. En revanche, dans le cas du modèle de Zhang, nous remarquons un léger écart entre les courbes. Ceci n’est que la propagation de l’écart décelé lors de l’étude de compatibilité entre les deux modèles dans le mode congestionné. Cependant, nous pouvons conclure que cet écart n’est pas lié à la procédure de couplage mais à la compatibilité des deux modèles en mode congestionné.

Figure 10. Modèle de Zhang : débit et densité en fonction du temps en mode fluide pour un pas de temps de 10 et 4 secondes



Figure 11. Modèle de Zhang : débit et densité en fonction du temps en mode congestionné pour un pas de temps de 10 et 4 secondes

Conclusion

Dans cet article, nous avons proposé une approche de modélisation hybride utilisant les systèmes multi-agents. Le modèle hybride, présenté ainsi, est géné-rique (prend en charge plusieurs modèles macroscopiques) et capable de traiter plusieurs successions de tronçons hybrides grâce au caractère distribué du système multi-agent. Les résultats montrent que la procédure de couplage ne change pas le comportement de flux aussi bien dans le mode fluide que dans le mode congestionné. Nous envisageons dans la suite de nos travaux de valider le modèle en utilisant des données réelles de flux de trafic. Nous envisageons aussi d’intégrer un SIG (système d’information géographique) à notre simulateur afin de bénéficier d’une représentation réelle du réseau routier.



Références

[1] Plate-forme jade : Java agent development framework, 2000. http ://jade.tilab.com/.

[2] F.F. Abraham, J.Q. Broughton, N. Bernstein, and al. Spanning the length scales in dynamic simulation. Computers in Physics, 12(6) : 538–546, 1998.

[3] E. Bourrel and V. Henn. Mixing micro- and macro- representations of traffic flow : a first theoretical step. Proceedings of the 9th Meeting of the Euro Working Group on Transportation, 2002.

[4] E. Bourrel and J.P. Lesort. Mixing micro- and macro- representations of traffic flow : a hybrid model based on the lwr theory. In : Bourrel, editor, 82th Annual Meeting of the Transportation Research Board, Washington D.C., 12–16 January, 2003.

[5] C. Buisson, J.P. Lebacque and J.B. Lesort. Strada, a discretized macro-scopic model of vehicular traffic flow in complex networks based on the Godunov scheme. Pages 976–981, Lille, France 9–12 July 1996. Proceedings CESA’96 IMACS Multiconference.

[6] W. Burghout. Hybrid microscopic-mesoscopic traffic simulation. PhD thesis, Royal Institute of Technology, Stockholm, Sweden, 2004.

[7] G.L. Chang, H.S. Mahmassani and R. Heman. Macroparticle traffic simula-tion model to investigate peak-period commuter decision dynamics. Transportation Research Records, 1005 : 107–121, 1985.

[8] C.F. Daganzo and F. Laval. Multi-lane hybrid traffic flow model : a theory on the impacts of lane-changing maneuvers. 2005 meeting of the Trans, 1, November 15 2004.

[9] S. El hadouaj, A. Drogoul and S. Espié. How to combine reactivity and antici-pation : the case of conflicts resolution in a simulated road traffic. MABS workshop, Springer Verlag LNAI series, 2000.

[10] M.S. El hmam. Contribution à la modélisation et à la simulation hybride du flux de trafic. In : Thèse de doctorat en Génie Informatique et Automatique, Université d’Artois, déc. 2006.

[11] M.S. El hmam, H. Abouaïssa, D. Jolly and A. Benasser. Simulation hybride de flux de trafic basée sur les systèmes multi-agents. In : MOSIM’06 : 6e Conférence Francophone de MOdélisation et SIMulation, Rabat - Maroc, du 3 au 5 avril 2006.

[12] J. Ferber. Les systémes multi-agents, vers une intelligence collective. InterEditions, Paris, 1995.

[13] E.G. Flekkøy, G. Warner and J. Feder. Hybrid model for combined particle and continum dynamics. Europhysics Letters, 52(3) : 271–276, 2000.

[14] D. Helbing. From microscopic to macroscopic traffic models. A persepective Look at Non-linear Media. From Physics Biology and Social Sciences, pages 122–139, 1998.



[15] D. Helbing, A. Hennecke, V. Shvetsov and al. Micro- and macrosimula-tion freeway traffic. Mathematical and Computer Modelling, 35(5-6) : 517–47, 2000.

[16] A. Hennecke, Treiber M. and Helbing D. Macroscopic simulation of open sys-tems and micro-macro link in traffic and granular flow ’99 : Social, Traffic, and Granular Dynamics, D. Helbing, H. J.Herrmann, M. Schreckenberg and D. E. W. eds., Springer, Berlin., pages 383–388, 2000.

[17] S. Krauß. Microscopic modelling of traffic flow : Investigation of collision free vehicle dynamics. ISSN 1434-845, 1998.

[18] P. Le Tallec and F. Mallinger. Coupling Boltzmann and Navier Stockes equa-tions by half fluxes. Journal of Computational Physics, 136 : 51–67, 1997.

[19] M. J. Lighthill and G. B. Whitham. On kinematic waves ii. A theory of traffic flow in long crowded roads. Proceedings of the Royal Society, A 229 : 317–45, 1955.

[20] L. Magne, S. Rabut, and J.F. Gabard. Towards an hybrid macro-micro traf-fic flow simulation model. Proceedings of the INFORMS Salt Lake City String 2000 Conference, 2000.

[21] R. Mandiau and S Piechowiak. Conflict solving in multi-agent distributed planning. In : IEEE SMC System man and Cybernetics, San Diego, CA, USA, october 1998.

[22] H. Mizuski and Y. Kawazoe. Simulation of crystal growth in solution by hybrid modelling, material transaction. JIM, 40(11) : 1337–1341, 1999.

[23] H. J. Payne. Models of freeway traffic and control. Mathematical Models of Public Systems, 1 : 51–61, 1971.

[24] A. Poschinger, R. Kates and H. Keller. Coupling of concurrent macroscopic and microscopic traffic flow models using hybrid stochastic and deter-ministic disaggregation. Transportation and Traffic Theory for the 21st century, 2002.

[25] P. I. Richards. shockwaves on the highway. Operations research, 4 : 42–51, 1956.

[26] E.J. Williams and I. Ahitov. Integrated use of macro- and micro- models within a simulation study. In : Proceedings of the AutoFact conference, pages 169–79, Dearborn, 12–14 novembre 1996. Society of Manufactury Engineers.

[27] H.M. Zhang. Structural properties of solutions arising from a non-equilibrium traffic flow theory. Transportation Research Part B, 34 n°7 : 583–603, 2000a.


Confort et qualité de service en transport collectif urbain de

voyageurs : analyse, modélisation et évaluation

Fabien Leurent


INRETS-ENPC-UMLV


F-77455 MARNE-LA-VALLÉE CEDEX 2

Introduction

Le contexte

Les transports collectifs (TC) de voyageurs constituent un mode de transport performant à bien des égards :

un mode productiviste, en raison de la capacité de transport et des vitesses •permises par la motorisation ;

un mode économe, dont le coût de production par unité de capacité est •relativement faible ;

un mode respectueux de l’environnement : l’emprise spatiale, la consomma-•tion d’énergie, les émissions de bruit et de polluants sont réduites quand on les rapporte au trafic écoulé.

La raison essentielle, commune à ces qualités, est la concentration, la massification des entités transportées, qui permet des économies d’échelle, d’envergure.

Réciproquement, la massification induit des conditions techniques fortes :

la disponibilité dans l’espace est limitée à certaines lignes et à certains •lieux le long de ces lignes : les stations d’accès et de correspondance. Les conditions d’accès et de correspondance sont tout aussi importantes pour les voyageurs, que les conditions de roulement en TC ;



la disponibilité dans le temps est limitée à des dessertes ponctuelles : entre •deux dessertes, les voyageurs doivent attendre la prochaine, dans des conditions de confort variables mais généralement ressenties comme plus pénibles que le roulement ;

dans un véhicule de TC, le nombre de places assises, tout comme l’espace •de « stockage » debout sont limités : des congestions peuvent survenir entre les voyageurs ;

la circulation des véhicules peut, elle aussi, être soumise à de la conges-•tion : au sein du trafic routier en trafic mixte, ou même en site propre dans le cas de fréquences très élevées.

L’objectif

La communication porte sur les aspects constitutifs de la qualité de service et du confort en transport collectif urbain de voyageurs. Au-delà de l’analyse qualitative, elle a pour objet d’associer des coûts aux pénibilités et de tracer des ordres de grandeur typiques pour hiérarchiser les pénibilités. De plus, nous indiquons comment modéliser les divers aspects, notamment l’accès aux places assises, et comment les intégrer dans un modèle de simulation afin de servir à l’évaluation socio-économique des projets d’investissement en transport collectif urbain.

Le plan de la communication

La communication est structurée en quatre parties :

1. Une introduction qualitative aux aspects constitutifs de la qualité de ser-vice et du confort en TC de voyageurs. Nous y indiquons l’état actuel de la repré-sentation de ces aspects, d’une part, dans les diagnostics des déplacements, et, d’autre part, dans les modèles de simulation et d’évaluation socio-écono-mique. Après avoir constaté certaines carences, nous indiquons des pistes de progrès.

2. Une modélisation de la congestion des places assises sur une ligne de TC : on met en évidence l’importance de distinguer les positions assises–debout et les conséquences sur le coût généralisé, pour un voyageur, d’un trajet entre deux stations sur une ligne.

3. Une prospection quantitative pour les coûts des divers aspects de la qualité de service : sur des distances typiques de déplacement en milieu urbain, avec des hypothèses standard de rabattement et de correspondance, nous hié-rarchisons les termes qui composent le coût généralisé du voyageur.

4. Enfin, nous suggérons un plan d’implémentation dans les outils d’aide à la décision, afin de prendre en compte effectivement la qualité de service dans les décisions de planification.

F. Leurent Confort et qualité de service dans les transports en commun


1. Qualité de service et confort en transport collectif de voyageurs

Pour commencer, nous allons passer en revue les aspects constitutifs de la qualité de service en transport, non seulement pour les voyageurs, mais aussi pour le fret, en identifiant ce qui est spécifique aux voyageurs (§ 1.1.). Puis, nous examinerons comment les observatoires ou les « baromètres » des déplace-ments intègrent et traitent ces aspects, selon que le « diagnostic » est produit pour une collectivité, une autorité organisatrice ou un opérateur de réseau (§ 1.2.). Ensuite, nous indiquerons comment la qualité de service est actuellement représentée dans les outils d’aide à la décision : modèles de simulation et métho-des d’évaluation socio-économique des projets ou des politiques de transport (§ 1.3.). Enfin, nous indiquerons des pistes de progrès aux plans institutionnel, décisionnel et scientifique (§ 1.4.).

1.1. Aspects constitutifs de la qualité de service et du confort

En transport de fret, un usager-chargeur apprécie un service d’après les cri-tères de qualité suivants :

la disponibilité dans l’espace, i.e. la proximité de la gare ou l’existence de •services de rabattement (tournées de ramasse-dépose) ;

la disponibilité dans le temps : les plages horaires d’ouverture des gares, •des tournées de ramasse-dépose ;

la rapidité ;•

la fiabilité, mesurée par la fréquence des retards et leur durée moyenne, •ainsi que par le taux de pertes.

Joints au tarif, ces aspects se résument dans une fonction de coût généralisé qui dépend de l’usager et du service. Il reste alors à regrouper les usagers en classes de chargeurs, d’après les coefficients qu’ils affectent à chaque terme du coût généralisé.

En transport de voyageurs, un usager-voyageur évalue le service d’après les mêmes critères de base complétés par des critères de confort et de sécurité :

le nombre de correspondances ;•

les durées des attentes ;•

la disposition d’une place assise ;•

le confort d’une place debout compte tenu de l’encombrement ;•

les sensations visuelles, sonores, olfactives, les vibrations ;•

la sécurité de la circulation, la sûreté à bord du véhicule et en station.•

Ces critères complémentaires induisent des termes supplémentaires dans la fonction de coût généralisé. Le temps passé tient un rôle crucial : une règle usuelle est de valoriser le temps en fonction de la position, en particulier de mul-tiplier les temps de marche ou d’attente par un facteur d’environ 2.



1.2. Place dans les observatoires et autres baromètres

1.2.1. Nature des dispositifs de mesure et d’observation

Il existe deux types de dispositifs pour mesurer la qualité de service sur un réseau de transport de manière systématique (i.e. au moins de manière objecti-vée, et de manière pérenne, avec un renouvellement annuel de la mesure sur le long terme) :

D’une part, des observatoires basés sur des mesures d’ingénieur pour, •entre autres, les vitesses commerciales, la charge des véhicules, les distan-ces parcourues, les horaires des courses dans les stations, etc.

D’autre part, des « baromètres » pour mesurer la qualité de service telle •que perçue et déclarée par les usagers. Sur le réseau routier national français, il existe un baromètre de satisfaction des usagers, qui consigne les proportions d’usagers par niveau de satisfaction, pour divers critères tels que « le confort du revêtement pour le roulement » ou « la propreté des aires de service », cela, en distinguant le caractère autoroutier ou non des routes.

À la charnière de ces deux types, se situent des enquêtes pour traduire en termes technico-économiques, les perceptions des usagers : le STIF projette de réaliser une telle enquête, alors que plusieurs ont déjà eu lieu dans divers pays européens (Jong et al., 2004).

Concernant les transports de voyageurs dans les agglomérations françaises, la qualité de service est mesurée, surtout dans le cadre d’observatoires. Il existe des enquêtes commerciales, mais à caractère ponctuel (en liaison avec un cer-tain projet) et sans suivi dans le temps : elles ne constituent pas un baromètre.

L’absence de baromètres-usagers révèle, en creux, que le confort des clients n’est pas encore une préoccupation majeure des collectivités, des autorités orga-nisatrices ou des opérateurs.

1.2.2. Sur les observatoires du transport collectif

Certes, il existe des observatoires au niveau d’un périmètre fonctionnel et avec une continuité dans le temps. Y sont rapportés des indicateurs technico-économiques tels que :

la ponctualité par mode de transport (les bus, les RER, etc.) ;•

la vitesse commerciale des véhicules. C’est un indicateur à double tran-•chant, car si le client souhaite un déplacement rapide, il arrive que des gains marginaux de vitesse soient obtenus au détriment du confort (ex. : un surcroît de vitesse en virage d’un bus, pénalise les voyageurs debout) ;

les véhicules.kilomètres offerts ;•

les places.kilomètres offerts ;•

les voyageurs.kilomètres servis ;•



de tels indicateurs conviennent, surtout pour une relation entre une autorité •organisatrice et un opérateur de réseau, car ils mesurent le niveau d’offre et aussi, partiellement, la productivité.

1.2.3. Vers des indicateurs « orientés clients » ?

Dans un observatoire d’exploitant de TC, on attendrait des indicateurs de confort tels que :

la part des voy.km qui disposent d’une place assise ;•

la part des voy.km effectuée au-delà du seuil de congestion à 4 voyageurs •par mètre carré ;

la carte de ces indicateurs sur les principales sections du réseau, par condi-•tion temporelle type.

Dans un observatoire d’autorité organisatrice, ou de collectivité territoriale, on attendrait des indicateurs de confort tels que :

la carte d’accessibilité moyenne aux activités dans un périmètre-cible, selon •le lieu d’origine ;

le nombre d’habitants, ou la part de la population, situé à moins de tel •seuil de distance de tel sous-réseau (cf. l’objectif d’une desserte à moins de 50 km par le réseau autoroutier sur le territoire national, fixé en 1995) ; les sous-réseaux en question seraient à distinguer moins par le moyen de transport (bus, tramway, métro ou train), que par la fréquence de desserte et la qualité d’accessibilité ;

la carte des qualités d’interface avec le mode automobile : avec un indica-•teur pour la disponibilité d’une place de stationnement à telle heure, pour tel prix maximum et à telle distance de la station de TC ;

la proportion de trajets en TC bénéficiant d’une information dynamique sur •l’horaire du passage de la prochaine course.

Il s’agit là d’une liste rapide, qui vise à l’illustration et n’a pas de prétention à l’exhaustivité.

1.3. Place dans les modèles de simulation et les méthodes d’évaluation socio-économique

Actuellement, la qualité de service est représentée dans les modèles de choix d’itinéraire sur les réseaux de TC, ou de choix modal, ainsi que dans les métho-des d’évaluation socio-économique des projets d’investissement et des politiques de transport-déplacement, de la manière suivante :

Par déplacement, entre une zone d’origine et une zone de destination, •découpées dans un périmètre fonctionnel, on sait décomposer les états passés par moyen de transport (marche, telle mission de TC, automobile) et identifier les transitions entre ces états.

On sait quantifier le temps passé dans chaque état-type : marche, roule-•ment, attente en station et hors véhicule, etc.



A chaque état-type, et à chaque type de transition entre deux états, on sait •associer un coût spécifique, qui est un coût par unité de temps dans le cas d’un état.

On valorise l’ensemble des états et des transitions qui composent le dépla-•cement, ainsi que le tarif et autres prix, dans un coût généralisé, qui synthé-tise les coûts subis par le client du déplacement. C’est la somme des coûts monétaires des temps passés dans les états pondérés par le coût par unité de temps spécifique à l’état et des coûts de transition.

Les coûts unitaires, associés respectivement à divers états, sont censés •refléter leur pénibilité intrinsèque : ainsi, le temps marché ou attendu, est en général valorisé deux fois plus cher que le temps passé en véhicule. Une explication communément avancée est que le temps passé en véhicule peut resservir à d’autres usages – notamment la lecture ou la relaxation : mais cela ne vaut que pour des places assises et pas pour des positions debout.

Cette représentation classique appelle un certain nombre de critiques :

Certaines différences essentielles pour le client, notamment entre une place •assise et une position debout, ne sont pas encore intégrées !

Au niveau du déplacement, le coût généralisé n’intègre que des aspects •à très court terme ; on n’évalue pas, entre autres, le stress général et les conséquences sur les activités et l’état psycho-physiologique des longues durées passées quotidiennement en déplacement par certains individus.

Les coûts spécifiques, associés aux états ou aux transitions, sont évalués •d’après le comportement des clients : en admettant qu’alors les coûts reflè-tent correctement ce comportement, ils constituent des valeurs comporte-mentales. Or, la collectivité pourrait choisir, pour ses évaluations socio-éco-nomiques, des valeurs tutélaires distinctes des valeurs comportementales, afin de faire valoir des objectifs particuliers, et notamment des objectifs de nature sociale.

Les projets d’investissement soumis à l’évaluation concernent surtout des •modifications de lignes (particulièrement des extensions) ou des variations de fréquence. Mais on évalue encore trop rarement des projets d’améliora-tion du confort, tels que des augmentations du nombre de places assises dans les véhicules ou dans les stations (à quai ou en salle d’attente), ou que la fourniture d’information dynamique.

1.4. Des pistes de progrès

À ce stade, nous pouvons déjà constater que :

les acteurs des transports publics (puissance publique et autorités organisa-•trices, opérateurs et clients) sont sensibles à la qualité de service ;

cette sensibilité est encore loin d’être complètement intégrée aux outils •d’aide à la décision : observatoires incomplets ; baromètres-usagers qui



restent à concevoir ; modèles de simulation peu sensibles au confort, ce qui se répercute sur les méthodes d’évaluation socio-économique basées sur ces modèles.

Afin de progresser vers une meilleure prise en compte du confort et de la qualité de service, diverses actions sont envisageables et souhaitables :

de manière générale, partager une perception de la qualité de service, •qui soit orientée client : nous espérons que la description fournie au § 1.1. contribue positivement en ce sens ;

au plan institutionnel, faire une place convenable à des indicateurs « orien-•tés client » pour la qualité de service, dans le diagnostic d’une situation, et en particulier dans un observatoire des déplacements. Le rôle d’un tel observatoire est fondamental pour structurer la perception collective ;

au plan décisionnel : valoriser, dans les méthodes d’évaluation socio-éco-•nomique et de sélection des investissements, les aspects qualitatifs des services ;

au plan scientifique : modéliser explicitement les aspects qualitatifs des •services de transport, ainsi que leurs effets sur les comportements de dépla-cement, notamment dans les choix d’itinéraire et de mode.

Dans la suite de l’article, nous proposons une modélisation pour un aspect important de la qualité de service en TC : la différenciation des places assises et debout et la modélisation de leur disponibilité respective. Un tel modèle peut d’ailleurs servir dans un observatoire, afin de suppléer un dispositif incomplet d’observation, dans la production de certains indicateurs.

2. Un modèle d’occupation des places assises / debout

Le phénomène de congestion : ou comment, dans quelle mesure, le volume de trafic influence la qualité de service ; est un sujet bien connu en ingénierie du trafic routier, avec des modèles statiques ou dynamiques de la congestion rou-tière. Les recherches les plus récentes à ce sujet concernent la perception diffé-renciée par l’usager des temps passés dans les divers régimes de congestion, et particulièrement la différence de perception entre le régime fluide, d’une part, et le régime saturé, d’autre part (file d’attente, stop and go) : cf. Jong et al. (2004).

La congestion en transport public est un sujet beaucoup moins étudié, qui reste largement à explorer et à défricher. Pour ce faire, il existe plusieurs pistes de développement :

la modélisation de « modes de service », selon la possibilité d’accéder à •divers types de places ;

la modélisation de fonctions d’inconfort, notamment pour la position •debout ;

la congestion en montée-descente des véhicules et ses répercutions sur la •ligne de transport ;



Nous nous concentrons ici sur la première piste : la différenciation de places et de classes, grâce à la modélisation de modes de service.

2.1. Motivation

Dans une course qui assure un service de transport public, et donc dans un véhicule, il est fréquent que les places offertes aux voyageurs se rangent en plu-sieurs catégories aux caractères typiques. La distinction entre les places assises et les positions debout est particulièrement importante en transport public urbain de voyageurs :

Une place assise est plus stable : elle amortit les irrégularités du parcours •(sinuosité, pente, freinage et accélération, vibrations) ; elle est moins sou-mise aux frictions avec d’autres voyageurs. Elle permet aussi de mener simultanément une autre activité que le mouvement, souvent la lecture.

Une position debout est soumise aux irrégularités du parcours, aux mouve-•ments du véhicule et des autres voyageurs : en cas d’affluence, le voyageur subit des proximités involontaires pouvant aller jusqu’à une forte compres-sion et une perception d’écrasement.

Par le choix des véhicules composant sa flotte, l’exploitant détermine une répartition des places assises et des positions debout avec, éventuellement, un type intermédiaire de strapontins. Il peut aussi définir des classes de service (souvent une 1ère classe et une 2ème classe en transport ferroviaire), moduler le niveau de service et le tarif de chaque classe, répartir sa capacité de trans-port entre les classes, et, aussi, fixer des priorités d’accès entre des classes de voyageurs.

Ainsi, l’exploitant régule l’accès aux places et aux classes, par des disposi-tions tarifaires qui induisent des règles commerciales de priorité et aussi par des règles de priorité à caractère social. D’autres mécanismes de priorité s’appliquent en pratique, notamment d’ordre physique comme la priorité d’antériorité : les voyageurs debout, qui poursuivent leur trajet au-delà d’une station, sont priori-taires sur les voyageurs qui montent en cette station, pour occuper les places laissées vacantes par les voyageurs en descente.

2.2. Définition des modes de service

À chacune des diverses positions : places ou classes, sont associés un niveau de tarif, et un niveau de confort, qui entraîne un certain coût d’inconfort a priori plus réduit pour une place assise que pour une position debout. Désignons par un indice m une certaine position, et pour une interstation a modélisée par un arc,

notons la position de l’usager sur a.

L’usager, sur un trajet entre une station de montée (entrée) et une station de descente (sortie), accède à certaines possibilités de service et obtient un mode de service : pour un trajet de N interstations ; un mode de service est

une séquence de N positions .



Dans le cas simple où l’on distingue seulement les places assises (A) et les positions debout (D), un mode de service est un mot de N lettres A ou D.

Figure 1. Positions du voyageur sur un service de transport collectif

Stations en montée

Stations en transit / descente

Debout

Assis

Trajet Entrée-Sortie de n interstations : une séquence Debout x k , Assis x (n-k ), est un mode de service

2.3. Coûts des modes de service et coût aléatoire d’un trajet

Nous pouvons supposer qu’un coût spécifique est associé à chaque position, et que les positions m sont rangées dans un ordre de coût qui varie en sens inverse de la qualité de service :

un indice croissant de position marque un coût plus fort et une qualité infé-•rieure ;

a priori, les ordres sont les mêmes pour tous les usagers – sinon, il faudrait •modéliser plusieurs types d’usagers ;

sur une interstation, un usager essaie d’obtenir la meilleure position possible •parmi celles disponibles, éventuellement en gardant sa position de l’intersta-tion précédente, s’il était déjà dans la course et si aucune position meilleure n’est accessible ;

ainsi, seuls des modes de service, dont la séquence de positions • m est croissante, sont choisis par l’usager.

Dans le cas de deux positions A (assis) ou D (debout), un mode de service se réduit ainsi à une séquence de k interstations parcourues en position A, suivies de N-k interstations en position D, si l’usager préfère être assis et peut conserver une place assise quand il l’obtient.



Compte tenu des coûts des positions sur chaque interstation, à chaque mode de service est associé un certain coût.

Sur un trajet entrée-sortie, le mode de service obtenu in fine dépend des flux de voyageurs, en volume et en structure selon les couples entrée-sortie. Le voyageur en montée ne connaît pas à l’avance le mode de service, il perçoit un éventail de modes possibles et une distribution statistique des coûts, avec un aléa qui tient aux possibilités de s’asseoir et à la répartition d’un reliquat de pla-ces assises, parmi un ensemble de candidats, à chaque station.

2.4. Règles de priorités pour l’accès

Spécifions maintenant un modèle pour le remplissage des divers types de pla-ces, en considérant une ligne de TC, avec S stations en montée ou descente, S-1 interstations, deux positions A (assise) et D (debout), la position A étant réputée plus confortable et moins chère pour l’usager que la position D.

Nous posons deux règles de priorité pour l’accès aux places assises :

(1) qu’à l’arrivée dans une station s, les voyageurs debout présents dans le véhicule, avant s et qui continuent leur course, sont prioritaires sur les voyageurs en montée, pour accéder aux places assises laissées vacantes par la sortie des voyageurs en descente.

(2) que les voyageurs en position D ont un accès équiprobable aux places assises vacantes. Cette règle s’applique en deux occasions successives pour chaque station : d’abord, l’accès aux places assises des voyageurs qui conti-nuent et étaient debout avant l’arrivée en station ; puis, s’il reste des places assises, l’accès des voyageurs en montée.

2.5. Modèle du chargement en volume

Notons l’interstation arrivant en s, le nombre de voyageurs debout

avant s et qui continuent au-delà de s, la capacité assise laissée vacante en

s par les voyageurs assis qui descendent. Deux cas de figure se présentent :

soit • , auquel cas tous les voyageurs debout qui souhaitent s’asseoir

le peuvent et laissent une capacité assise résiduelle de ;

soit • , certains voyageurs ne peuvent s’asseoir et il n’y a plus de places assises, .

On traite globalement les deux cas en posant une probabilité d’accès

aux places assises avant l’arrivée, , et en en déduisant

.

En repartant de la station s, des voyageurs en nombre sont montés et sou-

haitent s’asseoir : là encore, deux cas de figure sont possibles, selon que



ou non. On traite globalement les deux cas en posant une

probabilité d’accès aux places assises en montée en s, donc après le départ de

la station.

Après que les voyageurs se soient assis ou soient restés debout sur l’inters-

tation suivante qui mène à la station s+1, le nombre de voyageurs

debout et qui continuent la course au-delà de s+1, , est la partie qui ne des-

cend pas du nombre de voyageurs debout

.

Tandis que le nombre de places assises vacantes est

, avec le nombre des voyageurs assis qui des-

cendent en s+1.

Il suffit donc de connaître la répartition des voyageurs assis, d’une part, et celle des voyageurs debout, d’autre part, en fonction de la station de descente, pour appliquer les règles d’accès et continuer de traiter les autres interstations.

Voici un algorithme formel pour le chargement en volume, en notant

les volumes de déplacement entre les stations d’entrée i et les

stations de sortie k, en supposant un service de capacité k. On note aussi

le nombre des voyageurs assis à destination de k, le nombre de voyageurs

debout à destination de k, et les nombres de voyageurs respectivement

assis et debout sur l’interstation sortant de s.

Début. On pose , , , .

Test de fin. Si , alors terminer, sinon poser et continuer.

Progression, station s :

calculer • , ;

• .

calculer : • et

poser • et ;

poser • . Calculer et

;



calculer • et

.

poser • et .

Cet algorithme pourrait être quelque peu profilé, mais déjà sous cette forme, on voit que le traitement de chaque interstation courante s coûte un nombre d’opérations proportionnel à S-s, et donc que l’algorithme de chargement en volume a une complexité informatique en O(S²), raisonnable pour une ligne de transport public.

2.6. L’évaluation des coûts

Sur un trajet à N interstations , avec des positions successives

, un mode de service a pour coût la somme des coûts des

interstations, soit , en notant le coût de la position m sur

l’interstation .

Dans le cas de deux positions, pour une interstation a, on note le coût

assis, et le coût debout, réputé supérieur. En vertu du comportement optimi-

sant de l’usager, les seuls modes de service utilisés sont les séquences de k D et N-k A, de coût

Cela représente tout de même N+1 modes de service distincts, puisque k varie de 0 à N.

Sur une ligne à S interstations, avec relations

entrée–sortie, le nombre de modes de service à considérer s’élève à :

, soit O( ), avec pour chacun un

coût à calculer par la formule indiquée précédemment.

Pour simplifier l’évaluation, on choisit :

de privilégier le coût moyen des modes de service et leur variance ;•

d’appliquer un schéma de calcul récursif, en remontant vers l’amont depuis •chaque station de sortie.

Nous avons ainsi obtenu un algorithme en O(S²), opérations pour évaluer le coût moyen et la variance du coût, pour toutes les relations entrée–sortie sur une même ligne à S interstations.



2.7. Algorithme d’évaluation des coûts

Par station de sortie k et par station d’entrée j, on définit deux coûts :

le coût de voyager assis de • j à k, ;

le coût moyen • de j à k, conditionnel à l’état debout sur l’interstation (j, j+1) ;

entre une station d’entrée • j et la station d’entrée précédente j-1, ces deux coûts vérifient les équations de récurrence ;

• ;

• .

De plus, le coût moyen de j à k est .

Enfin, la variance du coût d’entrer en j pour sortir en k peut être calculée,

grâce à une équation de récurrence, sur la variance conditionnelle de ce trajet

pour un voyageur qui aurait été debout sur l’interstation (j-1, j), notée :

• variance conditionnelle ;

• variance du coût de monter en j-1.

Ces deux formules s’obtiennent par le théorème de la variance totale : un trajet de j-1 à k est soit un trajet commençant debout, avec une probabilité

, soit un trajet assis, avec une probabilité . La variance interclasse

est , avec la différence des coûts moyens des

deux cas. La variance intraclasse est juste fois la variance du coût de

commencer debout, car il n’y a pas de variance du coût assis si l’on s’assied dès

j-1 : or, la variance du coût de commencer debout en j-1 n’est autre que .

2.8. Un exemple

Soit une ligne de transport public à S = 4 stations, avec les flux entrée-sortie suivants :

en • montent voyageurs dont pour 2, pour

3 et pour 4 ;

en • montent voyageurs dont pour 3 et

pour 4 ;

en • montent voyageurs pour aller jusqu’en 4.



Pour un véhicule de capacité assise , le chargement en volume pro-duit les résultats suivants :

en • s = 1, , , donc , et

, et , et ,

et ;

en • s = 2, , donc tous les voyageurs debout qui conti-

nuent s’assoient, , donc , et ,

et , et ;

en s = 3, • , donc tous les voyageurs debout qui continuent

s’assoient, , donc , et ,

et ;

en • s = 4, tous les voyageurs descendent.

Pour l’évaluation des coûts en moyenne et en variance, nous présentons seu-lement le traitement de la station s = 4 en tant que station de sortie, en supposant

des coûts , , , , , :

en • s = 4, et ;

en • s = 3, et , , et ;

en • s = 2, et , , (tous s’assoient après 3)

et ;

en • s = 1, et , , (tous assis après 2)

et .

Dans ce cas particulier, on constate que la variance du coût reste modérée, et qu’elle se « tasse » en fonction du nombre d’interstations dans le trajet, car les occasions de s’asseoir sont d’autant plus nombreuses.

2.9. Prolongements

Un algorithme pour les proportions des divers modes de service, par trajet entrée–sortie sur la ligne de TC, est donné en annexe au § 6.

Il reste à modéliser des situations plus complexes :

davantage de types de places avec, alors, éventuellement, des comporte-•ments de satisfaction plutôt que d’optimisation ;

d’autres mécanismes de priorité ;•

les effets de règles sociales de priorité, amenant à revenir en position •debout pour laisser s’asseoir une personne prioritaire.



Il reste à mesurer le coût perçu par une classe de demande sur un type de places.

Il conviendrait aussi de préciser les relations avec la notion d’hyperchemin (Spiess et Florian, 1989), qui modélise le cheminement des usagers vers une destination via un réseau de TC : en parcourant un hyperchemin depuis la desti-nation vers l’amont, on traite les flux en montée dans l’ordre inverse des stations le long d’une ligne ; or, les coûts dépendent des choix des autres voyageurs en amont de la sortie. La mise en cohérence des causalités aval–amont de l’hyper-chemin, et amont–aval des lignes, est vraisemblablement assurée par un ajuste-ment mutuel, et idéalement un équilibre, qui reste à préciser et à formuler.

Pour mémoire, des travaux assez récents du CRT (Marcotte et Nguyen, 1998 ; Nguyen et al., 2001) ont considéré la limitation du nombre total de places dans un véhicule de TC et proposé de rediriger les volumes excédentaires vers d’autres missions sur l’hyperchemin. Il manque les notions de types de places et de coût spécifique. La contrainte de capacité est imposée en termes uniquement physiques, et non de manière économique au travers de coûts de congestion.

3. Prospection des effets de la qualité de service sur les coûts

Cette 3e partie a pour objectif de soupeser et de hiérarchiser les facteurs de la qualité de service pour les clients des TC urbains. L’échelle de mesure est le coût généralisé ou, plutôt, le temps généralisé, car en dehors du prix, l’essentiel du coût généralisé tient à des aspects temporels.

Tout d’abord, nous expliciterons les facteurs considérés dans l’analyse et les aspects qualitatifs qu’ils représentent (§ 3.1.). Puis, nous prospecterons leurs importances respectives, en moyenne et en variance dans un déplacement typi-que en TC urbain de voyageurs (§ 3.2.). Nous terminerons en hiérarchisant les facteurs, au moins à titre indicatif (§ 3.3.).

3.1. Les facteurs d’analyse

Nous laissons de côté le prix et les autres frais monétaires, afin de nous concentrer sur les facteurs suivants de la qualité de service :

le trajet terminal à l’origine et à la destination du déplacement : leur coût •mesure la disponibilité spatiale du moyen de transport, d’une part, à l’origine et, d’autre part, à la destination ;

l’attente du service, en accès initial ou en correspondance : le coût d’attente •mesure la disponibilité temporelle du service au lieu de montée ;

toute correspondance, en dehors du temps d’attente, a un coût spécifique •pour passer d’un quai à un autre : souvent, le mouvement piéton n’est pas négligeable. Le coût de correspondance mesure la qualité d’intercon-nexion, de manière statique, puisque les temps d’attente sont comptés par ailleurs ;



le parcours en véhicule consomme du temps, d’autant plus coûteux pour le •client que sa position est moins confortable. Nous retrouvons, ici, l’alterna-tive Assis ou Debout. Le temps généralisé en véhicule représente le confort basique du service de transport au sens strict.

Les irrégularités du service se manifestent dans la plupart des facteurs, de manière directe ou indirecte : directement dans la variabilité des temps d’attente ; indirectement dans le coût de correspondance, car des irrégularités de service induisent des grappes de voyageurs dans les stations ; directement dans le par-cours en véhicule, qu’il s’agisse des irrégularités de la trajectoire ou des aléas dans le trafic des véhicules, ou des fluctuations dans la charge en voyageurs et donc dans la disponibilité des types de places.

3.2. Une prospection quantitative

Procédons maintenant à un exercice de prospection et de quantification, afin de soupeser chaque facteur identifié pour la qualité de service. Il s’agit unique-ment d’un exercice, à valeur indicative et non définitive.

Nous considérons le déplacement en milieu urbain d’un voyageur qui utilise le transport public, en mesurant chaque facteur par cinq indicateurs :

un temps généralisé conditionnel : temps généralisé qui relativise un temps •physique en fonction de l’importance économique que lui accorde l’agent économique ; conditionnel à un voyageur particulier, mais éventuellement en moyenne sur plusieurs occurrences du déplacement pour cet individu (ex. : répétition d’un déplacement pour motif domicile-travail) : la variabilité parmi ces occurrences constitue la variabilité intra-individu ;

un temps généralisé moyen, moyenne des temps généralisés condition-•nels, sur une population d’individus traités génériquement dans un modèle de simulation. Un tel traitement générique, agrégé, est opéré quand on regroupe les déplacements par relation origine-destination ou sur le réseau en fonction d’une portion d’itinéraire ;

la variance intra-individu du temps généralisé, pour un individu qui répète •plusieurs occurrences du déplacement ;

la variance inter-individus du temps généralisé, due à la variabilité parmi les •individus des temps généralisés conditionnels ;

la variance totale, somme de la variance intra-individu et de la variance •inter-individus.

Pour fixer les idées, la variabilité inter-individus peut être attribuée à l’allure de la marche : rapide pour un jeune actif, lente pour une personne âgée. Nous suivons cette distinction en affichant deux temps conditionnels.

Le Tableau 1 expose les éléments quantitatifs de notre prospection, pour un déplacement avec deux trajets en TC, donc deux attentes dont une en accès initial et une en correspondance.



Les valeurs des moyennes et des variances résultent de considérations phy-siques et probabilistes. Il serait oiseux d’en reproduire ici le détail ; indiquons simplement les paramètres physiques :

trajet terminal, dans un rayon de 500 m autour de la station ;•

services de TC, avec une fréquence de 10 ou 12 services par heure, et un •bon cadencement ;

un facteur de pénibilité de 2 pour le temps d’attente ;•

un parcours en véhicule, de 10’ en temps physique dans le 1• er maillon des TC, de 8’ dans le second, avec un surcoût de 50 % pour le temps passé debout.

3.3. Hiérarchisation indicative

De la quantification illustrative, nous tirons qu’en termes de temps généralisé moyen :

le parcours en véhicule fait une moitié du total ;•

les temps d’attente et les temps terminaux ont un rôle sensiblement équiva-•lent en moyenne, chacun pour un quart du total.

Concernant les variabilités et précisément les variances :

les attentes sont la cause majoritaire, avec 60–65 % du total ;•

ensuite, viennent les temps terminaux, avec 20–25 % du total ;•

le parcours en véhicule occasionne une variance non nulle, mais qui pèse •à peine 10 % du total.

La distinction des individus lents ou rapides influence la moyenne, mais inter-vient faiblement dans la variance.

Tableau 1. Prospection des facteurs qualitatifs du service, en minutes de temps généralisé

Temps généralisé moyen Variance du TGFacteur Lent Rapide Inter-indivIntra Inter Totale

Trajet terminal origine 6 4 5 8 1 9Trajet terminal destination 6 4 5 8 1 9Terminal 2 bouts 12 8 10 16 4 20Attente initial 6 6 6 36 0 36Attente correspondance 5 5 5 25 0 25Total Attente 11 11 11 61 0 61Mouvement correspondance 2 1 1,5 0,5 0,25 0,75Parcours véhicule 1 11 11 11 3 0 3Parcours véhicule 2 9 9 9 4 0 4Tous parcours en véhicule 20 20 20 7 0 7

TOTAL 45 40 42,5 84,5 4,25 88,759,19 2,06 9,42



4. Plan d’implémentation pour l’aide à la décision

Nous avons établi, d’une part, la faisabilité de mieux modéliser la qualité de service en TC urbain de voyageurs (même si le modèle du § 2 ne traite qu’une partie du sujet), et, d’autre part, l’influence non négligeable du confort en véhicule sur le coût généralisé, en moyenne et en variance (au § 3).

Dans cette dernière partie, notre objectif est de tracer le chemin à parcourir pour intégrer un modèle de la qualité de service aux outils d’aide à la décision. L’enjeu est bien de rendre opérationnelles les considérations relatives au confort et à la qualité de service.

Pour ce faire, nous allons délimiter des tâches, en esquisser le contenu, et les organiser dans un diagramme de tâches.

Les tâches suivantes peuvent être identifiées en raison de leur nature spécifique :

modélisation formelle ;•

logiciel de simulation ;•

mesure statistique ;•

prévisions de trafic ;•

évaluation socio-économique ;•

valeurs tutélaires.•

Dans la suite de cette partie, nous évoquons successivement la modélisa-tion formelle (§ 4.1.), le logiciel de simulation (§ 4.2.), les mesures statistiques (§ 4.3.), les prévisions de trafic (§ 4.4.) et l’évaluation socio-économique, et la question des valeurs tutélaires (§ 4.5.). Enfin, nous suggérons une architecture de développement (§ 4.6).

4.1. Modélisation formelle

Au § 2, nous avons exposé un modèle d’occupation des places assises, qui traite d’une ligne de transport public sans notion de choix d’itinéraire.

Les développements à donner incluent :

l’intégration dans un modèle de choix d’itinéraire, qui a été évoquée briève-•ment au § 2.9. : c’est une condition nécessaire pour le passage au stade opérationnel. La difficulté principale est d’équilibrer l’offre et l’usage, d’une part, avec la demande, d’autre part, en ajustant le chargement en volume dans les coûts et les choix d’itinéraire. La difficulté peut être surmontée, car un tel ajustement relève du même traitement que celui pour la congestion dans les modèles d’affectation statique du trafic sur un réseau routier ;

la modélisation d’autres aspects de la qualité de service : congestion en •montée–descente, fonctions d’inconfort à l’intérieur d’un état donné de confort, information dynamique…



Il s’agit donc d’une tâche de recherche, combinant analyse économique et comportementale, et recherche opérationnelle.

4.2. Logiciel de simulation

Il existe depuis longtemps des logiciels pour simuler le choix d’itinéraire et le choix modal : des logiciels « commerciaux » produits par des éditeurs spécialisés (1), ou des logiciels « maison » de grands opérateurs ou bureaux d’études de transport (2).

Il conviendrait d’adapter un tel logiciel, en y incorporant le modèle formel de la qualité de service :

la modification des bases de données serait marginale pour ajouter des •informations sur la capacité assise sur une ligne et pour élargir les résultats des simulations ;

les ajouts aux codes de calcul seraient substantiels : les algorithmes de •chargement du volume et d’évaluation des coûts indiqués au § 2 et un algo-rithme d’équilibrage comme dans l’affectation statique du trafic routier ;

des fonctions de visualisation et d’édition de résultats, appropriés aux fac-•teurs de la qualité de service.

Pour un logiciel « maison » d’opérateur TC, l’ajout d’un algorithme d’équilibrage constituerait vraisemblablement une évolution importante, dont l’opportunité est à évaluer en considérant l’éventualité de passer à un logiciel « commercial ».

4.3. Mesure statistique

Sur le terrain, on observe que les voyageurs arbitrent entre divers états de confort :

au passage d’un véhicule en station, en cas de charge importante, les voya-•geurs se pressent pour obtenir l’une des places assises laissées vacantes, de manière fortement concurrentielle !

En Île-de-France, sur les lignes de métro très chargées, à la station en tête •de ligne, une forte proportion de voyageurs préfère laisser partir une rame où il n’y a plus de places assises disponibles, pour attendre la rame suivante avec une bonne chance de s’asseoir ;

toujours en Île-de-France, cet « avantage d’antériorité » est également •manifeste sur la ligne 1 du métro, où l’on voit le matin des voyageurs mon-tés et assis avant la station Nation, rester sur la ligne jusqu’à la station La Défense, plutôt que de prendre la ligne A du RER qui, pourtant, leur ferait gagner du temps : et ce, afin de garder leur place assise ;

1 Par exemple, CUBE, EMME/2, TransCAD, VISUM.2 Par exemple, à la RATP, ou à la SEMALY.



l’abandon d’une place assise au profit d’une personne prioritaire semble •devenir un comportement de moins en moins spontané, d’année en année… mais d’autres facteurs socio-économiques peuvent jouer à cet égard.

Ces aspects empiriques justifient, tout comme la modélisation comportemen-tale, d’associer des valeurs distinctes aux coûts spécifiques de divers états de confort.

L’importance du sujet suggère de recourir conjointement aux deux grandes familles de techniques pour mesurer les coûts spécifiques des états de confort :

les enquêtes de préférences déclarées, en faisant arbitrer en temps différé •des voyageurs sur des scénarios virtuels présentant certaines options de choix, différenciées selon plusieurs facteurs de la qualité de service ;

les observations de préférences révélées : les enquêtes sur les déplace-•ments effectuées par les ménages en agglomération décrivent l’usage des moyens modaux, de manière déjà particulièrement précise dans le cas francilien (l’EGT, Enquête Globale de Transport de voyageurs en Île-de-France).

À court terme, il paraît envisageable d’exploiter conjointement une enquête de déplacements (de préférence l’EGT) et un logiciel de simulation traitant expli-citement le confort : le logiciel permettrait de simuler les facteurs qualitatifs de moyens de transport choisis ou alternatifs, ce que l’on confronterait aux choix observés dans l’enquête, afin d’estimer statistiquement les paramètres de choix, et tout particulièrement les coûts spécifiques des états de confort.

À plus long terme, il pourrait être opportun d’enrichir les dispositifs d’enquête en ajoutant des questions portant sur :

l’emploi « secondaire » du temps en véhicule ou en attente : discussion, •téléphonie, écoute (radio, baladeur), lecture, flânerie, relaxation, autre ;

l’accès à une place assise, en renseignant, le cas échéant, le lieu d’obten-•tion.

4.4. Sur les prévisions de trafic

Concernant les prévisions de trafic, trois changements seraient nécessaires pour donner une juste place à la qualité de service :

dans la constitution des hypothèses pour la prévision, renseigner des •informations qui conditionnent la qualité de service, notamment la capacité assise par mission et par période horaire, en liaison avec la fréquence de la mission durant cette période ;

dans l’analyse des résultats, mettre en évidence les niveaux de service •atteints et au minimum l’état de remplissage des places assises ;

effectuer des tests de sensibilité aux facteurs du confort, puisqu’un opéra-•teur dispose d’une certaine latitude dans l’affectation aux missions de sa flotte de véhicules.



Pour cela, il faudrait non seulement que les logiciels de simulation soient adaptés, mais encore assurer une formation spécifique des chargés d’études.

4.5. Évaluation socio-économique et valeurs tutélaires

Pour la prévision de trafic, on donne des valeurs comportementales aux coûts des états de confort, afin de simuler les comportements des voyageurs avec réalisme.

Dans l’évaluation socio-économique des projets d’investissement ou des poli-tiques de transport, il faut, d’une part, considérer les prévisions de trafic, l’état de l’offre et de la demande et, d’autre part, évaluer l’utilité pour la collectivité de cet état offre–demande, en fonction de valeurs tutélaires associées aux divers aspects. Les valeurs tutélaires peuvent différer des valeurs comportementales, en fonction d’objectifs politiques propres à la collectivité (3), ou pour corriger certaines imperfections du marché (notamment la myopie des marchés face aux enjeux du long terme).

Comme pour les logiciels de simulation, il existe depuis longtemps des métho-des d’évaluation socio-économique éprouvées : pour bien y intégrer la qualité de service, il suffirait de modifications marginales, comme l’ajout de certains para-mètres et l’adaptation de certaines formules, sans besoin d’algorithmes sophisti-qués, ni de fonctions particulières de visualisation.

L’expression des valeurs tutélaires constitue un sujet plus délicat et difficile, qui nécessiterait un projet spécifique de recherche afin :

de recueillir l’expression d’acteurs significatifs et représentatifs : puissance •publique, opérateurs, associations d’usagers, panels d’usagers, associa-tions de contribuables… ;

de concilier ces diverses expressions, éventuellement par la concertation •d’un groupe de représentants.

4.6. Une architecture de développement

La Figure 2 donne un diagramme des tâches, en signalant leurs articulations mutuelles.

Chaque tâche nous paraît constituer un travail d’au moins une année, et, sans doute, deux années pour l’expression des valeurs tutélaires, et d’une à trois années pour la mesure statistique (selon l’option retenue). Certaines mises en parallèle sont possibles, notamment entre l’expression des valeurs tutélaires et la chaîne modèle – logiciel – mesure statistique.

Au total, l’implémentation opérationnelle de la qualité de service dans les outils d’aide à la décision constituerait un projet pluriannuel sur environ cinq années : pour son bon accomplissement, une organisation professionnelle de projet paraît indispensable, avec l’implication de divers partenaires représentant,

3 Parfois, une collectivité territoriale particulière, plutôt que l’ensemble.



d’une part, des fonctions de recherche–développement, d’autre part, les acteurs institutionnels : autorité organisatrice, exploitants, voire, des collectivités au sein d’un comité directeur.

Figure 2. Diagramme des tâches pour l’implémentation opérationnelle

Modélisationformelle

Logiciel de simulation

Expression des valeurs tutélaires

Prévisions de trafic

Mesure statistique

Evaluation socio-économique

Aide à la décision

5. Annexe : algorithme de partage entre les modes de service

5.1. Coûts et proportions des modes de service

Sur un trajet entre une station d’entrée i, et une station de sortie s, il y a modes de service possibles sous la forme d’une séquence de m inters-

tations en position debout et interstations en position assise : m varie de 0 à .

Le coût du mode de service m entre i et s, noté est basé sur les coûts

assis et debout et des interstations :

Le mode m reçoit une partie du volume entrée–sortie , en proportion

qui est liée aux probabilités et de s’asseoir à partir de la station k res-

pectivement en y montant ou en y arrivant en véhicule mais debout, probabilités

elles-mêmes issues du chargement en volume. Par définition de chaque mode, la

probabilité du mode est , tandis que la probabilité du mode est la

probabilité d’être debout en montée, de rester debout (ne pas s’asseoir) pendant

m interstations et de s’asseoir en arrivant à la station , donc on combine les probabilités de chaque état local :



5.2. Algorithme de calcul

Pour évaluer efficacement les proportions des modes de service, on peut appliquer le schéma récursif suivant, de l’aval vers l’amont : pour une station s de sortie, revenir vers les stations i d’entrée, en calculant une suite auxiliaire ρ

telle que et

Alors si , ou si .

On peut aussi calculer les coûts dans le schéma récursif, en utilisant les formules

Remerciements. L’auteur remercie Chao-Fu Yeh, dont le stage de DEA Transport de l’ENPC-UMLV en 2005 a permis de mener l’application numérique rapportée au § 2.8.

Références

Leurent F (2006) Structures de réseau et modèles de cheminement. Éditions Lavoisier, collection Tec et Doc. Lavoisier, Cachan, France.

P. Marcotte and S. Nguyen. Hyperpath formulations of traffic assignment prob-Hyperpath formulations of traffic assignment prob-lems. In : Marcotte P and Nguyen S (eds) Equilibrium and Advanced Transportation Modelling, 175–200. Kluwer, Boston, 1998.

S. Nguyen, S. Pallottino and F.A. Malucelli. Modeling Framework for Passenger Assignment on a Transport Network with Timetables. Transportation Science, 35(3) : 238–249, 2001.

TRB. Transit Capacity and Quality of Service Manual. On-line report prepared for the Transit Cooperative Research Program 1999. Available on-line at the following website address :

http ://gulliver.trb.org/publications/tcrp/tcrp_webdoc_6-a.pdf.



G. de Jong, E. Kroes, R. Plasmeijer, P. Sanders. The value of reliability. European Transport Conference, Strasbourg, 2004.

Sétra. Perception par les usagers des critères de qualité, de sécurité du réseau routier et appréciation des types de routes (Baromètre de satisfaction des usagers sur le réseau routier national). Sétra, Bagneux, France 2005.

H. Spiess. Contributions à la théorie et aux outils de planification des réseaux de transport urbain. Publication du Centre de recherche sur les transports, université de Montréal, 1985.

H Spiess and M Florian. Optimal strategies : a new assignment model for transit networks. Transportation Research B, 23(2) : 83–102, 1989.


Modélisation du choix d’itinéraire sur un réseau plurimodal

Fabien Leurent


INRETS-ENPC-UMLV


F-77455 MARNE-LA-VALLÉE CEDEX 2, France

Support écrit pour la conférence prononcée au séminaire modélisation du trafic, septembre 2004

Introduction

Les modes collectifs de transport fournissent des services d’acheminement, à l’intérieur d’un véhicule, entre des stations de montée et des stations de des-cente. En une station, le mode n’est disponible qu’aux moments où un véhicule est présent et proche de partir. L’usager subit des inconforts et des incertitudes à deux niveaux : le niveau des véhicules et le niveau des voyageurs (ou char-gements). Enfin, l’accomplissement d’un déplacement depuis l’origine jusqu’à la destination nécessite d’accéder au mode, et souvent de faire une correspon-dance entre deux moyens de TC.

Tous ces aspects spécifiques aux TC représentent des défis stimulants pour les modélisateurs du trafic sur un réseau. Je commencerai par baliser la progres-sion de la modélisation (section 1) et par situer mes recherches à ce sujet (sec-tion 2). Ensuite, j’évoquerai mes contributions à la modélisation de la disponibilité (section 3), du confort et de la qualité de service (section 4) et des cheminements plurimodaux (section 5).

1. Progression de la modélisation

Les premiers modèles d’affectation du trafic sur un réseau de TC sont appa-rus dans les années 1960, leur spécificité étant un codage spécifique afin de combiner les lignes sur les éventuelles portions communes de leurs itinéraires. Dans les années 1970, la combinaison des fréquences, pour des lignes alterna-tives entre deux nœuds de choix, a été modélisée rigoureusement par Chriqui



et Robillard (1975) ; le cheminement d’origine à destination a été modélisé par LeClerq (1972) comme une chaîne, ensemble de chemins passant par les mêmes nœuds de choix, plutôt que par un itinéraire simple.

Les années 1980 ont apporté des progrès décisifs : Spiess et Florian (1989) ont élargi la combinaison des lignes à toutes les possibilités sur un réseau, pas seulement les tronçons communs, grâce à la notion d’hyperchemin (1) ; de manière très remarquable, les problèmes de recherche et de chargement d’un hyperchemin présentent la même complexité informatique que pour un plus court chemin. De plus, ils ont donné un premier traitement de la congestion en TC, avec des fonctions de temps de parcours sur les arcs.

Depuis environ 1995, le concept d’hyperchemin a été abondamment appliqué pour modéliser des cheminements plurimodaux, qui combinent des modes en série et en parallèle, d’autant plus que le cheminement en hyperchemin s’inter-prète comme le choix local, en un nœud courant, du prochain arc vers la desti-nation, en fonction d’une information dynamique : or, désormais, les exploitants savent de mieux en mieux produire et diffuser l’information dynamique.

2. Problématique choisie

Je me suis intéressé, d’une part, à présenter rigoureusement les concepts de chaîne et d’hyperchemin, en délimitant leur portée et en explorant leur champ d’application ; et, d’autre part, à développer la modélisation de la disponibilité des modes, du confort en TC, des cheminements plurimodaux : en fonction des coûts, des incertitudes et de l’information dynamique.

Ces développements sont évoqués aux prochaines sections. En bref, ils consistent en :

des modélisations qualitatives : position d’hypothèses, sélection de notions-•inputs et de notions-outputs, expression des relations logiques conduisant des inputs aux outputs ;

des algorithmes qui traduisent quantitativement les modèles qualitatifs ;•

mais je n’ai pas encore donné de formulation mathématique en problème type •de recherche opérationnelle, comme ont pu le faire Spiess et Florian, dans leur article de 1989, sur l’affectation du trafic aux hyperchemins en TC.

Les concepts de chaîne et d’hyperchemin font l’objet d’une présentation sys-tématique dans mon ouvrage Structures de réseau et modèles de cheminement (Leurent, 2006a) au chapitre 6, sections 2 à 4 et au chapitre 8, sections 3 et 4. Ces concepts appellent, ici, quelques brefs commentaires :

Concernant le coût moyen associé à une chaîne, il paraît difficile de conci-•lier, d’une part, le calcul rigoureux du coût de correspondance entre deux

1 Sous-graphe connexe acyclique dirigeant vers un nœud de destination, avec en chaque nœud n non terminal une distribution discrète de probabilité sur les arcs sortants éléments du sous-graphe.

F. Leurent Modélisation du choix d'itinéraire sur un réseau plurimodal


maillons partageant certaines lignes, et, d’autre part, la progression arc par arc et sans mémoire dans la recherche de chaîne optimale.

Il y a deux notions de coût pour un hyperchemin : d’une part, le coût simple, •moyenne des coûts des chemins qui composent l’hyperchemin, pondérée par leur probabilité respective qui est elle-même le produit des probabilités locales des arcs qui les composent ; d’autre part, le coût mutualisé, au sens qu’aux nœuds de choix, la disponibilité de plusieurs modes permet de réduire l’attente et donc le coût moyen. De nombreuses confusions ont eu lieu à cet égard parmi les chercheurs, au préjudice de la mutualisation qui, pourtant, est la finalité même du cheminement en hyperchemin.

Les chaînes et les hyperchemins sont transposables aux transports indi-•viduels, en particulier en milieu routier interurbain où les grands itinéraires sont assez homogènes en aménagement et en signalisation, de manière comparable aux lignes de TC : de plus, la signalisation de direction corres-pond naturellement au principe de cheminement vers la destination dans un hyperchemin.

3. Modélisation de la disponibilité

Pour combiner des sections parallèles de lignes, à partir d’une station com-mune d’entrée, le modèle classique est d’associer à chaque ligne un intervalle de coûts jusqu’à la station commune de sortie :

le coût inférieur est le coût moyen en cas de disponibilité quand le voyageur •arrive à la station d’entrée ;

le coût supérieur est le coût moyen en cas d’indisponibilité. Il comprend le •coût inférieur plus un coût d’attente.

On retient le mode de plus faible coût inférieur, ainsi que les autres modes dont l’intervalle rencontre celui du mode « minimal ».

En fait, une telle combinaison repose sur une hypothèse implicite : à savoir qu’à l’arrivée du voyageur, aucun mode n’est disponible, sauf ceux qui le sont continuellement, notamment la marche.

Cela entraîne deux effets pervers :

dans certaines situations, seul un mode continuellement disponible est •choisi dans le modèle, alors que si à son arrivée le voyageur trouvait un service de bus, il se démènerait pour le prendre ;

le coût moyen, ainsi modélisé, est en fait conditionnel à une situation non •exhaustive, il diffère du coût moyen véritable.

Pour résoudre ce problème, il suffit de considérer explicitement les cas de disponibilité des modes à disponibilité partielle : et, ensuite, de mélanger les différents cas, en fonction des taux de disponibilité (Leurent, 2006 chapitre 6, section 2).



4. Modélisation du confort et de la qualité de service

Spiess et Florian, en 1989, ont modélisé le confort de voyageurs en TC urbain par des fonctions de coût d’inconfort croissantes, en fonction de la charge de la ligne, cela, tronçon par tronçon.

D’autres chercheurs ont ensuite relié la fréquence réelle de desserte au niveau de flux.

Cependant, le remplissage des places par type Assis ou Debout n’avait pas été représenté, alors qu’un voyageur assis peut récupérer du temps (lecture) et surtout évite la compression éventuelle des voyageurs debout.

J’ai modélisé (Leurent, 2006b) l’occupation de chaque type de place, ainsi que la priorité d’accès aux places assises dont les voyageurs debout, qui conti-nuent la ligne au-delà de la prochaine station, disposent sur ceux qui monteront ensuite.

Le principe est d’associer un coût par tronçon de ligne au mode assis, et un autre coût plus grand au mode debout. Pour chaque couple entrée–sortie de stations, le voyageur accède à un « mode de service » qu’il subit et choisit par-tiellement. La répartition entre les modes de service est aléatoire.

J’ai indiqué comment calculer, par ligne, le coût moyen par entrée–sortie, et la variance du coût : la complexité informatique est le carré du nombre de stations. Pour calculer les modes de service et leurs proportions respectives, la complexité est le cube du nombre de stations.

Dans une affectation, les coûts conditionnés par la charge de trafic sont calcu-lés par ligne, avant de servir à la recherche du cheminement optimal.

5. Sur les cheminements plurimodaux

La disponibilité de plusieurs modes de transport sur un territoire rend possible la multimodalité (usage d’un mode ou un autre parmi plusieurs disponibles entre deux nœuds de choix) et l’intermodalité (enchaînement consécutif de modes distincts).

Dans (Leurent 2006a chapitre 8, section 4), j’ai proposé une représentation générique pour les modes de transport, comprenant :

aux nœuds desservis, le taux de disponibilité et la fréquence de desserte ;•

par arc desservi, le coût et le temps de traversée, le temps de séjour au •sommet final.

Cette représentation permet d’affecter le trafic à des chaînes plurimodales optimales, ou à des hyperchemins plurimodaux optimaux, sous réserve d’hypo-thèses complémentaires quant aux dépendances entre les services aux mêmes nœuds.

F. Leurent Modélisation du choix d'itinéraire sur un réseau plurimodal


Une autre solution (Leurent 2006a chapitre 8, section 2) est de dissocier la recherche du treillis d’exploitation (i.e. la structure topologique d’un hyperche-min, sans les proportions) et le chargement de ce treillis par la demande. Le treillis d’exploitation exprime des possibilités robustes de cheminement et aussi la signalisation donnée sur le réseau : sa définition explicite paraît du devoir de l’exploitant. Le chargement du treillis peut, quant à lui, intégrer le comportement des usagers en fonction des coûts et des incertitudes.

6. Références

C. Chriqui and P. Robillard. Common bus lines. Transportation Science, 9 : 115–121, 1975.

R. Dial. Transit pathfinder algorithm. Highway Research Record, 205 : 67–85, 1967.

G. Gallo, G. Longo, S. Nguyen and S. Pallotino. Directed hypergraphs and appli-cations. Discrete Applied Mathematics, 4 : 23–35, 1993.

F. Le Clerq. A public transport assignment model. Traffic Engineering and Control, 14 : 14–20, 1972.

F. Leurent. Structures de réseau et modèles de cheminement. Collection Tec et Doc. Lavoisier, Cachan, France, 2006a.

F. Leurent. Confort et qualité de service en transport collectif urbain de voya-geurs : analyse, modélisation et évaluation. Proceeding of the ATEC Congress, CD Rom édition. ATEC, Paris, France, 2006b.


Le réseau de services : théorie et applications

Fabien LeurentLaboratoire Ville, Mobilité, Transport INRETS-ENPC-UMLV 19, rue Alfred Nobel, Cité Descartes, Champs-sur-Marne F-77455 MARNE-LA-VALLÉE CEDEX 2, France

Support écrit pour la conférence prononcée au séminaire modélisation du trafic, juin 2004

Introduction

Une théorie est une construction logique, un corpus d’hypothèses et de déduc-tions : la combinaison des hypothèses peut induire, par déduction, des propriétés renforcées. La distinction entre une théorie et un modèle, tient principalement à ce que l’approche théorique privilégie la déduction ; tandis que l’approche modé-lisatrice privilégie la représentation.

La théorie du réseau de services s’applique à divers modèles de chemine-ment et d’optimisation sur un réseau : elle nécessite et met en œuvre certaines propriétés structurelles d’ordre local, pour déduire des propriétés globales et des procédés généraux de résolution.

Dans cette communication, j’évoque :

d’abord la finalité de la théorie du réseau de services : transporter sur un réseau •les composants d’un problème d’optimisation relatif aux chemins (§ 1) ;

les théories parentes : programmation dynamique, cheminements généra-•lisés (§ 2) ;

le contenu de la théorie : l’axiomatique des concepts et les théorèmes pour •exploiter la récursivité et la généricité (§ 3) ;

les algorithmes atomiques pour résoudre récursivement et génériquement •des problèmes sophistiqués de cheminement sur un réseau (§ 4) ;



la manière de traiter certains problèmes de • plus court chemin (PCC) : sous contrainte de budget, avec un budget et des coûts variables, avec des contraintes de séjour aux nœuds et d’accès aux arcs ; le PCC dynamique ; le PCC bicritère (§ 5).

Je termine par un bilan (§ 6).

1. Finalité de la théorie du réseau de services

La théorie du réseau de services est destinée aux problèmes de plus court chemin sous contraintes : un service associe un chemin sur un réseau-support et une qualification physique ou économique.

La théorie représente les éléments constitutifs d’un problème d’optimisation : un domaine, des contraintes et une propriété caractéristique souvent d’optima-lité. Elle les associe à des chemins sur un réseau. Lorsque les contraintes et la propriété caractéristique sont récursives, alors, on les propage via le réseau, ou mieux, on les transporte ; et, réciproquement, la structure de réseau sert à déter-miner récursivement des solutions.

De plus, la théorie peut représenter conjointement un ensemble de problèmes plutôt qu’un seul, afin de les traiter génériquement, en bénéficiant d’économies d’envergure.

2. Sur les théories parentes

Il existe essentiellement deux théories pour représenter et traiter des problè-mes sophistiqués de cheminement sur un réseau : la programmation dynamique due à Richard Bellman (1957) ; et les cheminements généralisés dus à Michel Minoux (1975).

En programmation dynamique, on représente des états physiques ou écono-miques liés les uns aux autres par des (mécanismes de) transitions, à l’aide d’un réseau d’états : en chaque nœud un potentiel (éventuellement vectoriel) carac-térise un état particulier. Pour déterminer un état optimal, on parcourt le réseau en utilisant deux axiomes, l’un de décomposition en série, l’autre de composition en parallèle : c’est l’algorithme de programmation dynamique (algorithme de Bellman).

La théorie des cheminements généralisés combine la topologie de réseau à un caractère algébrique : à chaque nœud est associé une variable d’état qui appartient à un monoïde commutatif, et à chaque arc est associée une transition, endomorphisme du monoïde. Les transitions relèvent d’un dioïde distributif : il s’agit de résoudre un système linéaire dans ce dioïde, dont la matrice est consti-tuée des transitions entre les nœuds du réseau. Par consolidation dans un che-minement progressif, on obtient une solution du système linéaire. Ce formalisme permet d’exprimer élégamment des problèmes variés de chemin optimal, et de les résoudre par des algorithmes à la Ford-Bellman ou à la Dijkstra.

F. Leurent Le réseau des services


Évidemment, ces deux théories sont apparentées, ainsi qu’à la théorie du réseau de services qui s’en distingue :

par rapport à la programmation dynamique, des états plus structurés dont •la qualification peut aller au-delà d’une fonction de potentiel pour évaluer l’optimalité. De plus, les algorithmes du réseau de services construisent dynamiquement les états, alors que l’algorithme de programmation dynami-que traite des états codés initialement, de manière statique ;

contrairement aux cheminements généralisés, la description n’est pas algé-•brique mais fonctionnelle. On se concentre sur les propriétés structurelles de récursivité, sans faire d’hypothèses quant aux propriétés algébriques des solutions.

3. Contenu de la théorie

La théorie du réseau de services a pour objets :

un ensemble • H d’états, dont les sous-ensembles sont des portées η : pour traiter génériquement des séries de problèmes ;

des services itinéraires–portée • ;

une fonction de potentiel • Ψ sur les services, pour donner une qualification physico-économique ;

une assertion logique V sur les services, afin d’exprimer la compatibilité ou •non vis-à-vis des contraintes ;

une propriété logique W sur les services, pour exprimer un caractère d’op-•timalité.

Les services sont définis récursivement sur le réseau. Si V est récursive, un problème de PCC contraint sur le réseau originel équivaut à un problème libre sur le réseau de services, dont la topologie internalise V.

Quand de plus, Ψ et W sont récursives, on peut représenter un service par un atome [nœud, portée, potentiel, arc d’accès, pointeur sur atome en amont].

Les atomes se composent en un faisceau, moyen efficace de codification récursive.

Quand les problèmes de PCC sont solubles, il existe un faisceau qui organise les solutions optimales.

Si de plus la récursivité de Ψ et W se combine avec un caractère markovien, alors, de telles solutions optimales s’organisent en un faisceau optimal récursif, sans double accès à un même état.

4. Algorithmes atomiques

Sous les hypothèses récursive et markovienne, on peut résoudre générique-ment des problèmes sophistiqués de PCC par des algorithmes de recherche, dits



atomiques, car on élabore progressivement un faisceau d’atomes. Ces algorith-mes reprennent les principes classiques :

d’énumération de chemins–candidats ;•

de sélection du meilleur candidat.•

J’ai donné un algorithme atomique à la Dijkstra, qui utilise une partie du poten-tiel Ψ comme fil conducteur pour le cheminement. Et aussi un algorithme atomi-que à la Ford-Bellman, qui recherche les services efficaces par ordre croissant du nombre d’arcs depuis l’origine.

5. Problèmes traités

J’ai appliqué la théorie du réseau de services aux problèmes suivants de cheminement :

le PCC en temps sous contrainte de coût. Un service se confond avec un •itinéraire. L’assertion V teste que l’itinéraire a le bon nœud d’origine et est élémentaire. Le potentiel Ψ = (coût, temps). La propriété d’optimalité W est que l’itinéraire soit le plus court en temps parmi ceux de coût supérieur ou égal au sien ;

traitement similaire pour le PCC en temps sous contrainte de coût, avec, par •arc, un temps variable avec le coût de traversée (en sens croissant) ;

le PCC en temps à contraintes de plages d’accès aux arcs et de plages de •séjour dans les nœuds. Pour cela, on définit un nœud – serveur du réseau de services, comme un triplet avec l’instant initial et l’instant

final du créneau de présence au nœud n. Ce problème correspond

notamment à la recherche d’un sillon ferroviaire pour un convoi supplémen-

taire (déjà traité par Minoux avec les cheminements généralisés) ;

le PCC dynamique : pour chaque instant d’une plage temporelle, recher-•che d’un PCC en temps ou en coût. J’ai modélisé des portées–intervalles

, un potentiel résumé avec et les instants

de sortie du service qui correspondent aux instants d’entrée et , et

et des coûts auxiliaires de sortie aux instants et . Un coût

auxiliaire se compose du coût de traversée compte tenu de l’instant

initial, et d’un coût d’attendre à l’origine jusqu’à l’instant du départ. La

partie du potentiel Ψ sert de fil conducteur dans l’algorithme atomique

à la Dijkstra ;

la recherche bi-critère prix–temps de PCC : l’algorithme atomique à la Ford-•Bellman correspond à l’algorithme Ford-Bellman-Minoux pour les chemi-nements généralisés. L’algorithme atomique à la Dijkstra est applicable là aussi ; le choix du prix comme critère de fil conducteur simplifie grandement les tests d’efficacité des chemins.

F. Leurent Le réseau des services


De plus, un faisceau d’atomes se prête naturellement bien au problème de chargement des services qu’il décrit : pour l’affectation dynamique, ou pour l’af-fectation bicritère, etc.

6. Bilan et perspectives

La théorie du réseau de services constitue un cadre pour formaliser et traiter un modèle de cheminement optimal sous contrainte. Elle aide à reconnaître les composantes essentielles d’un problème d’optimisation sous contraintes associé à un réseau et à identifier, et utiliser les propriétés essentielles de récursivité, ainsi que de généricité le cas échéant.

Elle ne se substitue pas aux théories parentes, mais plutôt elle en est complé-mentaire. En particulier, l’algorithme à la Dijkstra pour le problème de PCC dyna-mique manifeste bien la distinction par rapport aux cheminements généralisés.

J’ai publié cette théorie dans mon livre Structures de réseau et modèles de cheminement (Leurent 2006a chapitre 7, section 4).

Références

R. Bellman. Dynamic Programming. Princeton University Press. Princeton, NJ, 1957.

R. Bellman. On a routing problem. Quarterly of Applied Mathematics, 16 : 87–90, 1958.

Dijkstra E. A note on two problems in connexion with graphs. Numerische Mathematics, 1 : 269–271, 1959.

L.R. Ford. Network Flow Theory. Report P-923, Rand Corporation. Santa Monica, CA, 1956.

F. Leurent. Structures de réseau et modèles de cheminement. Collection Tec et Doc. Lavoisier, Cachan, France, 2006a.

M. Minoux. Plus court chemin avec contraintes : algorithmes et applications. Annales des Télécommunications, 30(11–12) : 383–394, 1975.

M. Minoux. Structures algébriques généralisées des problèmes de cheminement dans les graphes : théorèmes, algorithmes et applications. RAIRO revue verte, 10(6) : 33–62, 1976.


Un modèle d’intersection pour l’affectation dynamique du trafic

intégrant les retards

Thomas Durlin – Vincent HennENTPE/INRETS – Laboratoire d’Ingénierie Circulation Transports (LICIT) [email protected] – [email protected]

Cet article fait suite à la session du séminaire Modèle de Trafic du 15 décem-bre 2005 présentée par Vincent Henn et Thomas Durlin, intitulée « Construction d’un modèle d’affectation dynamique à l’aide de suivi d’onde ». La dernière partie de l’exposé, relative à la construction d’un modèle de carrefour, est plus particu-lièrement traitée ici. Les deux premières, consacrées à une présentation générale des modèles d’affectation dynamique et à celle du modèle de suivi d’onde, seront moins approfondies que lors de la présentation.

Résumé

En deçà des dynamiques journalières et intrajournalières classiquement considérées en affectation dynamique de trafic, un autre phénomène dynamique dû à l’alternance des phases dans les intersections à feu se distingue à une échelle plus petite. Celui-ci induit des fluctuations du flux de l’ordre de la durée du cycle de feu. Une telle précision dans la description des flux n’est pas pertinente pour une application pour l’affectation dynamique.

Nous proposons ici d’intégrer ces microdynamiques dans un nouveau modèle d’intersection. L’alternance des phases n’est plus représentée explicitement, mais ses effets moyens sur le flux sont conservés (restriction de capacité, retards…). Ce nouveau modèle s’avère satisfaisant en termes de similitude de comportement avec le modèle détaillant, précisément les phases de feu rouge et vert. Ses performances au niveau du temps de calcul répondent également aux exigences d’une application en affectation dynamique.



1. Introduction

Les modèles d’affectation dynamique du trafic (DTA) ont pour objectif la repré-sentation de l’évolution du trafic sur un réseau, lorsque les conditions de trafic évoluent. Ces variations incluent une variation de la demande, par exemple, suite à des changements dans les flux par couple origine–destination (OD), et égale-ment une variation de l’offre. Celle-ci peut se produire lors d’un accident ou d’une modification du plan de feu d’une intersection. Nous considérons ici uniquement la dynamique intrajournalière du trafic sans la dynamique journalière : les condi-tions de trafic sont variables à l’échelle de la journée mais se répètent d’un jour à l’autre. On suppose également que ces variations intrajournalières se produisent à une grande échelle, de l’ordre de l’heure ou de la demi-heure.

Les modèles d’affectation dynamique doivent être adaptés à ces échelles de travail. Ils décrivent l’affectation des flux OD sur les différents itinéraires et leur écoulement sur le réseau correspondant à un état d’équilibre. Nous nous intéres-sons ici à l’équilibre usager. Celui-ci est défini par Wardrop [15] comme l’état dans lequel aucun usager ne peut améliorer son temps de parcours en modifiant son itinéraire. Pour prendre en compte les effets des variations de la demande et de l’offre sur l’affectation, les modèles d’affectation dynamique sont classiquement composés de deux sous-modèles :

un modèle de trafic, ou « Dynamic Network Loading model » (modèle DNL), •qui fournit les temps de parcours sur les différents liens du réseau, pour un scénario donné d’offre et de demande par lien (qui découle directement des demandes par itinéraire) ;

un modèle d’affectation, qui détermine les coefficients d’affectation des flux •OD par itinéraire en fonction des temps de parcours, c’est-à-dire qui modé-lise la répartition des flux entre chaque origine et chaque destination sur les différents itinéraires possibles consécutive aux choix de parcours des usagers.

La détermination de l’équilibre d’affectation constitue un problème de recher-che de point fixe, généralement résolu par une heuristique itérative : à partir d’une affectation initiale, on calcule les temps de parcours correspondant avec le modèle de trafic, qui vont pouvoir alimenter le modèle d’affectation. Celui-ci fournit alors de nouveaux coefficients d’affectation, c’est-à-dire une nouvelle demande par itinéraire. Tant que l’équilibre n’est pas atteint, on poursuit le pro-cessus « calcul des temps de parcours–calcul de l’affectation ».

Cette démarche itérative contraint le modèle DNL à présenter une certaine facilité de calcul, d’autant plus que les échelles de travail spatiales et temporelles des modèles d’affectation dynamique sont généralement grandes. Les modèles DNL pour l’affectation dynamique dérivent donc généralement de ceux utilisés en affectation, tels que les modèles à temps de parcours, [1] ou Contram [8], ou ceux à fonction de sortie [11]. D’autres modèles DNL sont également basés sur des modèles d’écoulement, par exemple Dynasmart [6]. Les modèles employés en affectation sont généralement performants en termes de temps de calcul mais

T. Durlin, V. Henn Un modèle d'intersection


limités quant à la qualité de leur description des phénomènes de trafic. Les modè-les d’écoulement ont généralement des caractéristiques symétriques : une bonne capacité de description du trafic, mais des temps de calcul longs.

Les sorties des modèles d’affectation dynamique sont les temps de parcours et les débits (les débits sur les liens résultant du choix d’itinéraire). Dans un contexte d’exploitation, et notamment d’évaluation de stratégies d’exploitation, ces seuls éléments de description du trafic sont rarement suffisants : une plus grande finesse de description est nécessaire, au moins au voisinage de la zone effectivement étudiée, afin de calculer les différents indicateurs utilisés pour l’évaluation. Par exemple, l’estimation de l’influence des plans de feux sur la hauteur de remontée des files d’attente en amont d’un feu exige la connaissance précise de l’état du trafic sur les liens en amont de ce feu. Ce niveau de descrip-tion dépasse celui des modèles DNL classiques. C’est pourquoi il nous semble nécessaire d’utiliser également un modèle capable de fournir une description précise de l’état du trafic, une fois l’état d’équilibre atteint par le processus ité-ratif, c’est-à-dire un modèle d’écoulement. La Figure 1 reprend le modèle ainsi obtenu.

Figure 1. Principe d’un modèle d’affectation dynamique pour l’exploitation

Temps de parcours

Non Débit par itinéraire

Demande (débit par O/D)

Offre (arcs et intersections)

Modèle DNL

Modèle d’écoulement Description précise du trafic sur le réseau

Equilibre ?

Oui

Modèle d’affectation

Ce second modèle de trafic doit être cohérent avec le modèle DNL afin de s’assurer que l’état d’équilibre calculé avec le modèle DNL conserve encore sa signification avec le modèle d’écoulement. Dans le cas contraire, si les deux modèles sont trop différents, rien ne garantit que l’équilibre obtenu avec le pre-mier modèle correspond toujours à un état d’équilibre avec le second modèle. C’est pourquoi nous avons choisi de ne travailler qu’avec un seul modèle pour les deux étapes : le modèle d’écoulement. Nous l’adaptons en simplifiant sa résolu-tion numérique pour satisfaire aux contraintes de calculabilité propres au modèle DNL. Ceci nous assure donc de la cohérence entre les deux modèles.

Dans ce contexte, nous considérons que les variations d’offre consécutives à l’alternance des phases de feu vert et de feu rouge sont de moindre importance



que celles résultant des autres variations de l’offre et de la demande. Cette alter-nance de phases crée de petites fluctuations des temps de parcours dues à des variations du flux. Leurs échelles de variation sont supposées être inférieures à la sensibilité des usagers et ne sont donc pas directement prises en compte dans leur choix d’itinéraire. Nous faisons donc l’hypothèse que les usagers ne connaissent pas, au moment de leur choix d’itinéraire, l’état précis de l’intersec-tion lorsqu’ils y parviendront (feu rouge, vert avec une file d’attente ou vert sans file d’attente), mais qu’ils restent sensibles au retard moyen qu’ils peuvent ren-contrer. Deux solutions sont possibles pour supprimer ces petites fluctuations de débits et de temps de parcours :

lisser a posteriori les résultats d’un modèle d’écoulement qui considère •explicitement les alternances de feu rouge et feu vert ;

ne pas représenter ces alternances mais intégrer a priori leurs effets dans •le modèle d’intersection utilisé par le modèle écoulement.

La première approche implique que l’écoulement et l’affectation se font selon deux niveaux de description distincts, ce qui nous apparaît peut satisfaisant. De plus, elle n’améliore pas les performances calculatoires du modèle. C’est pour-quoi nous proposons ici un modèle d’intersection correspondant à la seconde approche.

Dans la suite de l’article, nous décrivons le modèle d’écoulement utilisé en section, avec sa résolution par la méthode de suivi d’onde. Ensuite, nous étu-dions les effets moyens sur le flux de l’alternance de phases, ce qui permet de construire le nouveau modèle d’intersection dans la partie 4. Une application théorique illustre le principe de fonctionnement du modèle et met en perspective des commentaires sur le modèle.

2. Modèle d’écoulement

2.1. Le modèle LWR

Les modèles d’écoulement et d’intersection sont étroitement liés et doivent donc présenter des propriétés similaires. C’est pourquoi le modèle d’écoulement doit être capable de décrire précisément les phénomènes de trafic tels que la congestion, tout en restant facilement calculable pour une utilisation en affecta-tion dynamique.

Nous avons choisi le modèle LWR (Lighthill, Whitham [9] et Richards [12]), car il réalise un bon compromis entre facilité de calcul et capacité de description. Ce modèle macroscopique du premier ordre représente le trafic comme un flux homogène et continu, décrit par trois variables : le débit Q(x,t), la densité K(x,t), et la vitesse du flux V(x,t). Le modèle LWR est basé sur trois équations :

l’équation de conservation : •



l’équation de définition du flux : •

la relation fondamentale : •

Ces équations peuvent se synthétiser en une équation de conservation hyper-bolique non linéaire :

Peu de paramètres sont nécessaires au modèle, puisqu’ils se limitent à ceux utilisés dans la relation fondamentale, par exemple, deux paramètres pour une relation fondamentale parabolique, trois pour une relation triangulaire ou quatre pour une relation biparabolique (cf. Figure 2a).

La relation fondamentale présente deux parties distinctes de part et d’autre de la concentration critique Kc. La première, croissante, correspond à l’état fluide, la seconde, décroissante, à l’état congestionné.

2.2. Résolution numérique

Le modèle LWR est généralement résolu grâce à un schéma de Godunov (Daganzo [2] and Lebacque [7]), basé sur le principe des différences finies cor-respondant à une discrétisation spatiale et temporelle. Lebacque [7] définit les notions d’offre Ω(k)etdedemandeΔ(k) (voir Figure 2b) et montre que le débit Q(k) est le minimum de Ω(k)etdeΔ(k) à chaque point à chaque instant :

Figure 2.a. Exemple de relation fondamentale biparabolique Q = QE(K) 2.b. Demande Δ(K) et offre ∑ (K) correspondantes

Qmax

0 K C K X

Q Qmax

0 K X K C

Demande ( )

Offre ( )

Q

La grande échelle de travail en affectation dynamique, de l’ordre de l’heure, oblige à utiliser une grille de discrétisation également large, incompatible avec une bonne description du comportement des intersections (voir [3] pour plus de détails). Un grand pas de temps de discrétisation est en effet synonyme d’une qualité peu satisfaisante de description des phénomènes de trafic, par exemple, au niveau de l’estimation des retards dans les intersections. Nous avons donc



opté pour une autre méthode de résolution : la méthode de résolution par suivi d’onde, ou méthode « Wave Traking » (WT). Les principes de cette méthode sont brièvement expliqués ici. Henn [4] apporte davantage de précision sur ses fondements théoriques.

La méthode WT est basée sur le calcul exact de la propagation d’ondes et de leur collision dans un diagramme espace–temps. Dans le cas général, avec une relation fondamentale quelconque, le modèle LWR génère différents types d’ondes : des ondes de choc et des ondes de raréfaction. Les premières séparent deux zones de concentrations différentes dont celle en aval est la plus élevée (et symétriquement pour les ondes de raréfaction), leur particularité est d’être linéaires, donc faciles à manipuler. Une résolution exacte du modèle se heurte au problème des ondes de raréfaction, générées en éventail de manière continue et qui sont donc difficiles à manipuler numériquement, au contraire des ondes de choc qui restent discrètes.

L’idée générale du schéma WT est d’approximer la relation fondamentale par une fonction linéaire par morceau. Dans ce cas, les éventails continus d’ondes de raréfaction se réduisent à un ensemble discret et fini d’ondes se comportant comme des ondes de choc. La solution exacte de ce problème approché peut alors être calculée numériquement. La Figure 3 montre un exemple d’application du schéma WT et la comparaison entre la solution qu’il propose et la solution exacte.

Le schéma WT permet d’adapter facilement la qualité de la solution calculée : il donne une solution d’autant plus proche de la solution exacte que le nombre de segments de la fonction linéaire par morceau est élevé. De plus, la comparaison des résultats entre la solution donnée par le schéma WT et la solution exacte montre que même un petit nombre de segments permet d’obtenir des résultats significatifs [5]. Nous utilisons donc ce schéma de résolution à la fois pour le modèle d’écoulement final et pour le modèle DNL.

Figure 3. Illustration de la méthode WT pour un scénario de réduction locale de capacité

0020010

Temps (s)

0

50

100

150

200

250

300

350

)m(

ecaps

E

00200100

50

100

150

200

250

300

350

)m(

ecaps

E

Temps (s)

cifartud

sneS

ednoitcudé

Réticapac

Ondes de raréfaction Ensembles discrets

Solution avec la méthodeSolution continue



Les méthodes d’estimation de matrices de demande par couple origine–destination fournissent généralement des demandes constantes par morceau. Puisque le schéma WT ne produit que des ondes de choc discrètes, les débits en entrée et en sortie de tous les liens sont alors constants par morceau. En utilisant la méthode classique des débits cumulés [10], on peut donc calculer facilement les temps de parcours des liens, qui sont alors linéaires par morceau.

Seules les intersections d’ondes de choc génèrent des calculs avec le schéma WT. Avec une matrice OD constante par morceau, les calculs se limitent alors, en l’absence de congestion, au traitement des transitions entre les états successifs. Par comparaison avec le schéma de Godunov, qui nécessite une réactualisation de l’ensemble du réseau à chaque pas de temps, le schéma WT semble donc plus approprié en tant que modèle DNL pour une application en affectation dyna-mique (voir § 6.3).

3. Comportement moyen du carrefour avec alternance de phase

L’étude des effets de l’alternance des phases sur les flux de trafic fournit les éléments nécessaires à la construction d’un modèle d’intersection présentant directement un comportement moyen. Étant donné notre échelle de travail, les phénomènes dont les ordres de grandeur sont plus petits que la durée d’un cycle de feu ne doivent pas être décrits explicitement mais intégrés de façon moyenne. A contrario, les phénomènes dynamiques se produisant à plus grande échelle sont calculés et décrits explicitement.

Cet article ne traite pas de la totalité du comportement des intersections mais se concentre en fait sur la modélisation d’un feu et de ses conséquences sur le flux. Dans la suite de l’article, on ne considérera donc qu’un type extrêmement simple d’intersection : une entrée, une sortie (c’est-à-dire, par exemple, un feu piéton). La généralisation du modèle à des configurations plus complexes d’inter-section sera proposée brièvement dans la partie 6.

L’alternance des phases de feu vert et rouge produit trois effets sur le trafic, détaillés dans les sous-parties suivantes. Elle génère un retard cyclique dû à la présence de files d’attente cyclique. Les phases de feu rouge induisent égale-ment une restriction moyenne de capacité. La propagation des ondes de choc d’un lien à l’autre est également affectée par la présence du feu.

3.1. Retard cyclique dû aux files d’attente cycliques

Des files d’attente cycliques apparaissent durant la phase de feu rouge et se résorbent complètement durant la phase de feu vert suivante. Leur ordre de gran-deur étant égal à la durée du cycle de feu, ces files ne doivent pas être décrites précisément mais plutôt de manière moyenne.

La littérature en matière de retard moyen dans les carrefours est assez riche (voir par exemple [14]). Nous considérons, ici, une formule de retard largement connue et approuvée, présentée dans le Highway Capacity Manual



[13] et correspondant au premier terme de la formule de Webster. En faisant les hypothèses d’arrivées constantes et d’une relation fondamentale triangulaire, le retard dépend de la durée du cycle c, de la proportion de temps de vert λ, du débit maximal en sortie Qmax et du débit arrivant dans l’intersection Q :

avec taux de saturation

L’utilisation d’autres formules de retard est naturellement possible. Certains modèles prennent également en compte des composantes stochastiques dans l’expression du retard, par exemple, Contram [6]. La formule de Webster inclut également, avec son second terme, les effets d’arrivées distribuées. Nous avons choisi de ne pas prendre en compte de tels effets stochastiques dans cet article. Toutefois, une simple modification de la formule de retard permet d’incorporer ces effets sans difficulté.

3.2. Restriction moyenne de capacité

Le feu étant rouge pendant une fraction λ du temps, la capacité Cp de l’inter-section est réduite à :

avec Qmaxin, le débit maximum de l’entrée et Qmax

out, le débit maximum de la sortie. Lorsque la demande Δ dépasse Cp ou l’offre Σ à l’entrée du lien aval1, une file d’attente divergente apparaît en amont de l’intersection et génère un retard également divergent. Cette file ne peut se résorber que si Δ décroît ou si Σ. et Cp augmentent (par exemple, suite à un changement du plan de feu de l’intersection). Puisque Δ, Σ. et Qmax

inter ont des échelles de variation plus grandes que la durée des cycles de feu, les files d’attente dues à la restriction de capacité doivent être décrites explicitement.

La Figure 4.a montre les deux phénomènes simultanés mais de natures dif-férentes : le retard cyclique et le retard dû à la restriction de capacité. Le retard dynamique présente, même pour une demande constante, de petites fluctuations d’amplitude égale à la durée de la phase de feu rouge et provoquées par les files cycliques. Lorsque la demande Δ dépasse l’offre λ.Qmax, une file d’attente divergente se forme en amont du carrefour, et le retard croît en moyenne, même si le retard dynamique présente toujours des fluctuations autour de cette valeur moyenne. Les deux types de files d’attente, cyclique et divergente, coexistent donc. Lorsque la demande décroît sous le seuil λ.Qmax, la file se dissipe, et le retard moyen décroît jusqu’à atteindre le retard cyclique, lorsque le carrefour n’est plus saturé. Cet exemple illustre la formule suivante de décomposition du retard dans le carrefour :

Retard total = retard cyclique + retard dû à la restriction de capacité

1 Pour des intersections à plusieurs sorties, Σ. peut être une fonction des offres des différentes sorties dépendant du modèle d’intersection choisi (Cf. §6).



Figure 4.a. Retard dynamique et moyenné dans une intersection à feu 4.b. Variation de la demande correspondante en entrée de

l’intersection

spmet 0

τ

t1 t2

Intersection saturée

Résorption de la file

Retard dynamique

Retard moyennéτ rouge

λ .Qmax

0 temps

Δ

t1 t2


3.3. Propagation des ondes de choc

Le dernier impact de l’alternance des phases rouges et vertes sur le flux est moins évident, mais n’en est pas moins important. Il concerne la propagation d’ondes de choc dans l’intersection, vers l’aval (des ondes se propageant depuis le lien entrée vers le lien sortie) ou vers l’amont (ondes remontant le flux).

Les ondes qui se propagent vers l’aval ont un comportement proche de celui des véhicules : elles peuvent traverser directement l’intersection s’il n’y a plus de file d’attente cyclique ou rester bloquées par le feu rouge. Leur retard est donc proche de celui subit par les véhicules. La Figure 5 montre ces deux possibilités. Une onde de choc séparant deux zones de concentration K1 et K2 (avec K1 < K2)

Figure 5. Exemples de propagation d’onde de choc vers l’aval dans une intersection avec une alternance de phase —

concentration K(x,t) dans un diagramme espace/temps

a. Onde directement propagée b. Onde retardée

temps

x

temps

x K Kx

0



arrive de l’amont. Dans le premier cas, l’onde de choc étant directement propa-gée, les deux états sont également distinctement propagés à travers l’intersec-tion. Dans le second cas, on distingue une période de transition entre les deux régimes (visible, par exemple, par la longueur intermédiaire de la file d’attente intersectée par l’onde de choc). La durée exacte de cette transition est difficile-ment calculable mais reste inférieure à la durée d’un cycle. C’est pourquoi, nous ne chercherons pas à décrire cette transition de manière précise.

Les ondes de choc se propageant vers l’amont se comportent différemment. Si elles atteignent l’intersection lorsqu’une file cyclique est encore présente, leur vitesse de propagation augmente dans la file, car la concentration y est plus grande. Ceci leur confère une certaine avance (et non un retard) lors de leur passage dans l’intersection. Si les ondes de choc arrivent lorsque le feu est vert, elles se propagent directement. En moyenne, la présence d’un feu n’occasionne donc pas de retard mais donne, au contraire, une certaine avance à ces ondes.

4. Modèle d’intersection intégrant les retards

Nous proposons un nouveau modèle d’intersection. Les phénomènes de trafic dont les ordres de grandeur sont inférieurs à la durée d’un cycle ne sont plus décrits explicitement mais restent intégrés dans le modèle d’intersection. L’alternance des phases de feux rouge et vert n’est plus représentée, mais ses effets moyens sur le flux sont modélisés a priori : la restriction de capacité, le retard cyclique et la propagation des ondes de choc.

4.1. Restriction de capacité

La restriction de capacité est modélisée par une simple loi de restriction du débit, en introduisant λ dans la formule donnant le débit en fonction de l’offre et de la demande :

Les files d’attente divergentes peuvent donc apparaître en amont de l’inter-section dans les mêmes conditions qu’avec le modèle à alternance de phases, lorsquelademandedépassel’offre(lorsqueΔ>λ.Σ). Ces files génèrent un retard divergent. Cette loi de restriction de capacité peut être facilement intégrée dans le schéma WT en utilisant une condition aux limites adaptée.

4.2. Retard cyclique

Le modèle LWR a pour variables de base le débit, la concentration et la vitesse, mais non le temps de parcours (calculé a posteriori). C’est pourquoi, créer un retard donné est plus difficile qu’introduire une restriction de capacité. L’idée que nous proposons est d’introduire un lien artificiel supplémentaire situé entre la sortie du lien amont et l’entrée du lien aval (cf. Figure 6.a.). Ceci permet d’augmenter la longueur parcourue et donc le temps de parcours. En jouant sur la longueur de ce lien fictif, on peut adapter le retard ainsi créé à une formule de retard, par exemple, la formule du HCM (cf. § 3.1.).



Figure 6.a. Principe du lien fictif 6.b. Relation fondamentale triangulaire

Lien amont

Intersection

Lien fictif

Lien aval max maxfictifQ =Q

fictifc cK K= fictif

c2.K K

Q

Afin d’introduire le moins d’éléments artificiels possibles, le lien fictif fonc-tionne de la même manière que les autres liens. Son comportement est donc également régi par le modèle LWR, et le lien possède sa propre relation fonda-mentale. Nous avons choisi une relation triangulaire, basée sur les paramètres de celle du lien amont (cf. Figure 6.b.). Cette relation fondamentale n’a pas de réelle signification physique, le lien fictif ne cherchant qu’à reproduire le retard moyen et non le comportement physique de la file d’attente moyenne. D’autres choix de relation fondamentale sont donc possibles, mais la forme triangulaire a l’avantage de conférer au flux et aux ondes de choc une vitesse identique en régime fluide, sans dispersion de peloton. Le lien fictif crée alors un retard pur. La longueur du lien fictif est donc une fonction affine du retard :

avec

Les débits à l’entrée et à la sortie du lien fictif sont limités par :

, et

, et ,

avec Qin et Qout débits en entrée et en sortie du lien fictif, Σfictif et Σ offres à l’entrée du lien fictif et à l’entrée du lien aval, Δ et Δ fictif demandes à la sortie du lien amont et à la sortie du lien fictif (cf. Figure 7).

La propagation spécifique des ondes de choc de l’aval vers l’amont est réali-sée en introduisant une restriction du débit supplémentaire entre le débit entrant dans le lien fictif et l’offre en entrée du lien amont :

Nous ne pouvons pas donner d’avance aux ondes de choc se propageant vers l’amont, mais cette contrainte garantit la propagation instantanée de ces ondes du lien aval au lien amont sans parcourir le lien fictif.

On obtient les expressions suivantes pour Qin et Qout :



La Figure 7 reprend ces deux formules ainsi que les différentes notations.

Figure 7. Notations et gestion des débits à travers l’intersection et le lien fictif

fictif

fictif

Qout = min ( fictif , .Qmaxout, )

Qin = min ( , .Qmaxin, fictif , )

Lien fictif

Intersection

Lien aval

Lien amont

L’écoulement (relation fondamentale et gestion des débits) se comporte donc de la même façon que pour un lien normal, à l’exception de la restriction du débit à l’entrée du lien fictif par l’offre en sortie qui permet la propagation immédiate des ondes de choc vers l’amont.

4.3. Variation du retard cyclique et adaptation de la longueur du lien fictif

Lorsque le débit à travers l’intersection est constant, le retard, et, par consé-quent, la longueur du lien fictif, est également constant. Le flux se trouve donc uniquement retardé.

Lorsque le débit varie de Q1 à Q2, le retard dans l’intersection doit varier de (Q1) à (Q2). La longueur du lien fictif passe donc de L1 = L( (Q1)) à L2 = L( (Q2)). La frontière aval du lien fictif se déplace alors pour permettre cette variation de longueur. Le choix d’une frontière aval mobile, et non de la frontière amont mobile, permet de conserver le caractère FIFO2 du lien fictif amont.

Puisque le lien fictif n’a pas de signification physique réelle, il est similaire à une file d’attente verticale : l’abscisse de sortie du lien amont et l’abscisse d’en-trée du lien aval ne varient donc pas.

Lorsque la frontière aval du lien fictif bouge, le débit, à travers elle, est conservé. Cela fournit la relation suivante entre le nouveau débit Q2 quittant le lien fictif et le débit en entrée du lien aval Q2’ :

,

2 FIFO = First In First Out : si le véhicule a entre sur le lien fictif suivi par le véhicule b, a sortira avant b.



avec Vfrontière, la vitesse des véhicules sur le lien fictif. Lorsque la longueur désirée L2 est atteinte, la frontière redevient fixe. Les débits d’entrée et de sortie valent alors tous deux Q2, et le retard est bien égal à (Q2).

Le débit en sortie Q2’ correspond à un état transitoire : l’intersection passe de l’état 1 à l’état 2 définis respectivement par les débits Q1 et Q2. Nous ne recherchons pas la description précise de cet état transitoire, aussi, nous faisons l’hypothèse simplificatrice que le retard varie linéairement de (Q1) à (Q2). La longueur du lien fictif varie donc également linéairement, et sa vitesse de varia-tion Vfrontière est constante.

La Figure 6.a. reprend le comportement de l’intersection lorsque le débit décroît de Q1 à Q2. Les abscisses de l’entrée et de la sortie du lien fictif sont notées, respectivement 0– et 0+, afin de signifier le caractère non physique du lien. Deux trajectoires sont représentées en pointillés : les véhicules pénètrent bien sur le lien fictif à l’abscisse x = 0– le parcourent sur sa longueur jusqu’à l’abscisse x = 0– + L et ressortent ensuite à la sortie à l’abscisse x = 0+.

Comme une description précise de la phase de transition n’est pas essen-tielle, nous faisons également l’hypothèse :

Ceci confère au lien fictif un comportement très simple, comme le montre la Figure 6.b., et permet de calculer Vfrontière :

Figure 8. Principe de la frontière mobile pour une diminution de la demande

a. Avec une phase de transition distincteb. Avec l’hypothèse simplificatrice

Q2’ = Q1

Frontière mobile

Lien amont

Lien aval

Lien fictif Q1

Q1

Q2

Q2’ Q2

x

temps

Vfrontière L1

L2

x = 0+

x = 0 -

Q1 Q2

Q1

Q1

Q2

Q2

x

temps

Vfrontière L1

L2

trajectoire

x = 0+

x = 0 -

Q2 Q1



La Figure 9.a. montre la propagation des ondes de choc vers l’amont. Le scénario est en réalité double : une onde de choc remonte d’abord de l’aval et traverse l’intersection, puis la demande diminue, ce qui permet la résorption de la congestion.

L’intersection est initialement dans l’état 1, correspondant à un débit Q1. Le retard vaut alors 1. Une onde de choc remonte ensuite depuis l’aval et atteint l’intersection. Elle correspond à l’état saturé 2, avec un débit Q2 < Q1. Le débit entrant sur le lien fictif est alors restreint par l’offre limitante : Qin = Q2, et l’onde de choc peut donc se propager en amont de l’intersection. La longueur du lien fictif augmente jusqu’à la longueur Lmax, correspondant au retard maximum. Le retard total (cf. Figure 9.b.) se décompose alors en deux termes non nuls : le retard cyclique et le retard dû à la file d’attente divergente.

Ensuite, lorsque la demande prend la nouvelle valeur Q3, avec Q3 < Q2, la file d’attente se résorbe. Quand la congestion est effectivement résorbée sur le lien amont, et que le nouveau débit Q3 atteint l’extrémité du lien fictif, la longueur de celui-ci diminue alors jusqu’à la longueur L3.

Figure 9.a. Principe de la frontière mobile pour une remontée d’onde de choc suivie d’une diminution

de la demande

Figure 9.b. Retards correspondants : retard

total = retard cyclique + retard dû à la congestion

L1 t

x

x = 0 -

x = 0+


L2 = L max L3

Q1

Q1

Q2

Q2

Q3

Q3

Retards

2 = max 1

t

Retard cyclique

Retard dû à la congestion

3

Retard total

Avec le schéma WT, les concentrations et les débits aux entrées et aux sorties des liens sont constants par morceaux. Ce modèle d’intersection ne modifie donc pas cette propriété : une variation en entrée du carrefour produit une seule varia-tion en sortie, et les phases transitoires sont gérées sans modification du débit de sortie. Les temps de parcours, calculés selon la méthode des débits cumulés [10], sont donc toujours linéaires par morceau.

5. Illustration

Nous proposons une application théorique simple pour illustrer le modèle d’intersection. Le réseau est constitué de trois liens reliés par trois intersections dont la durée du cycle est c = 100 s et les temps de vert respectivement 60 s et



50 s (λ1 = 0,6 et λ2 = 0,5). Les trois liens ont une même relation fondamentale parabolique, avec Qmax = 1 véh/s et Kx = 0,3 véh/m. Les débits maximums dans les intersections sont alors Σmax

1 = 0,6 véh/s et Σmax2 = 0,5 véh/s. Les variations

de demande en entrée du réseau sont représentées dans la Figure 10.a. Le pas de temps de ces variations est d’une minute. Le scénario dure quatre heures (voir Figure 10).

Pour t < t1, la demande est constante. Aucun calcul n’est donc effectué : les longueurs des liens fictifs ne changent pas, les retards ne variant pas, aucune onde de choc ne se propage (cf. Figure 10.b.).

Lorsque la demande augmente, les longueurs des deux liens fictifs augmen-tent également pour correspondre aux retards donnés par la formule de retard, mais avec une vitesse différente, puisque λ1 et λ2 sont différents. Le retard total croît donc aussi. Lorsque la demande dépasse Σmax

2, l’intersection 2 sature : une file d’attente se forme alors, et la congestion se propage vers l’amont. Lorsqu’elle atteint l’intersection 1, le débit de sortie de celle-ci chute, et la congestion peut continuer en amont. Le retard total augmente alors rapidement du fait du temps passé dans la congestion.

Lorsque la demande diminue sous la valeur Σmax2 jusqu’à sa valeur initiale, la

congestion se résorbe progressivement. Une fois que l’intersection 1 n’est plus congestionnée, elle retourne à son état initial, et l’onde de choc est propagée en aval. La congestion disparaît ensuite lorsqu’elle atteint l’intersection 2, et le retard total reprend également sa valeur initiale.

Le scénario dure quatre heures, mais le temps de calcul reste acceptable pour un usage en affectation dynamique3, car seules les variations de demande et les propagations des ondes de choc génèrent des calculs. Le pas de temps de variation de la demande (1 minute) est trop petit, ici, pour correspondre à une vraie application en affectation dynamique. Avec un pas de temps plus grand, le nombre d’événements et, donc, de calculs, serait encore plus petit. Avec un modèle d’intersection à alternance de phase, un éventail est généré à chaque redémarrage au feu vert. De nombreuses ondes peuvent ainsi être générées à chaque cycle, qui occasionneront d’autant plus d’événements à traiter en aval. Le nombre d’opérations augmente donc rapidement avec la diminution du pas de temps de la demande, avec le modèle à alternance de phase.

Les différentes contraintes imposées sur notre modèle semblent respectées : un temps de parcours intégrant directement un comportement moyen pour une application en affectation dynamique, une description de l’état du trafic assez fine pour permettre de suivre les ondes de choc et un temps de calcul compatible avec un usage dans un processus itératif. La prochaine partie propose des com-mentaires sur le modèle d’intersection à partir de cette illustration.

3 Environ 5 s avec un Pentium 4 — 3.6 GHz sans recherche d’optimisation des calculs.



Figure 10.a. Demande Δ(t) en véh/s, t en min

10.b. Temps de parcours expérimenté (t) en s, t en min

10.c. Concentration correspondante dans un diagramme espace temps (x en m, t en h et K en véh/m)

6. Commentaires

6.1. Coordination entre les feux

Les Figures 11.a. et 11.b. présentent la comparaison des temps de parcours entre notre modèle d’intersection et le modèle avec l’alternance de phase (appelés, respectivement, temps de parcours intégré et temps de parcours dynamique) obtenu avec l’illustration du chapitre précédent. La Figure 11.a. montre que le temps de par-cours intégré suit bien les variations du temps de parcours, à la fois pour les états stationnaires et pour les états de formation et de dissipation de la congestion.



Figure 11.a. Temps de parcours avec le modèle intégrateur et valeurs extrémales du temps de parcours avec le modèle à alternance de phase

(avec un zoom sur le retard dynamique)

Figure 11.b. Temps de parcours avec le modèle intégrateur et avec le modèle à alternance de phase pour différentes coordinations entre

les feux des deux intersections

Temps de parcours (s)

Temps (min)

0 20 40

700

600

500

400

300

200

100

060 80 100 120 140 160 180 200 220

La Figure 11.b. illustre un des problèmes majeurs de notre modèle, à savoir la prise en compte des phénomènes de coordination entre les feux. Notre approche des temps de parcours suppose que le temps de parcours cyclique créé par une intersection peut s’exprimer de manière exogène comme une fonction du débit et des caractéristiques de l’intersection. Ceci est vrai dans le cas où les intersections sont suffisamment distantes les unes des autres pour se comporter comme des intersections isolées. Cependant, la coordination entre des feux successifs a des effets notables sur le retard cyclique et devrait donc être prise en compte. Pour des axes bien coordonnés, les véhicules ne subissent que de petits retards (voire des retards nuls), dès lors qu’ils sont effectivement entrés sur l’axe. Au contraire, un axe mal coordonné peut conduire à un arrêt systématique à chaque intersection.



Le modèle accepte n’importe quelle expression de retard ; donc, la formule de retard du HCM peut être modifiée sans problème à chaque intersection et pour chaque entrée. Le problème reste qu’il est (très) difficile d’exprimer littéralement le retard dans une intersection en fonction du débit en prenant en compte les possibles interactions avec les autres intersections. Toutefois, dans un contexte d’affectation dynamique, une incertitude sur la connaissance précise du réseau peut être acceptée. Dans la mesure où même les exploitants ne parviennent que rarement à connaître l’état exact du réseau à chaque instant, les usagers ne sont pas forcément sensibles systématiquement aux effets des coordinations. C’est pourquoi, nous proposons, dans une première approximation, de prendre en compte la coordination des feux uniquement sur les axes clairement identifiés comme coordonnés par l’exploitant et les usagers. Le premier retard pour l’usa-ger qui pénètre sur l’axe est le retard classique, puis les suivants, aux intersec-tions suivantes, seront réduits.

6.2. Imprécision spatiale

Ne pas représenter directement les phénomènes inférieurs à la durée d’un cycle, notamment l’alternance des phases, peut occasionner également certains problèmes. Cette approximation temporelle induit une approximation spatiale. Des ondes de choc peuvent se propager ou apparaître plus ou moins tôt, ce qui génère une certaine incertitude sur leur position exacte dans le diagramme espace–temps. Cette incertitude demeure toutefois en dessous de notre échelle de travail et reste donc cohérente avec nos hypothèses.

L’extension spatiale des files d’attente est également négligée. Les véhicules ne s’arrêtent plus sur le lien en amont de l’intersection, mais se déplacent sur le lien fictif. Ils sont donc temporairement présents sur le lien fictif en dehors des liens physiques, ce qui augmente artificiellement la capacité de stockage des liens. Puisque la longueur du lien fictif est bornée, le nombre de véhicules pré-sents dessus est toutefois toujours inférieur à :

,

avec max retard cyclique maximum. Dans notre exemple, on peut stocker ainsi Nmax = 24,5 véhicules supplémentaires (respectivement, 12 et 12,5 véhicu-les dans chacune des intersections). La capacité totale de stockage du réseau (540 véhicules) est donc augmentée de moins de 5 %, ce qui reste acceptable.

6.3. Aspects calculatoires

Le temps de calcul est une contrainte majeure pour les modèles d’affectation dynamique. Notre modèle d’intersection possède un comportement bien adapté au schéma WT dans lequel le nombre de calculs ne dépend que du nombre d’événements (création ou collision d’ondes). En effet, l’intersection ne crée pas de dynamique supplémentaire : si la demande et l’offre sont constantes, aucun événement n’est généré, et si une onde de choc atteint l’intersection, une seule onde de choc et quatre événements sont créés (cf. Figure 12.a.). Une seule onde de choc atteindra donc l’intersection suivante.



Avec le modèle à alternance de phases, au moins trois événements4 sont créés à chaque cycle (cf. Figure 12.b.). De plus, trois ondes de choc5 sont pro-pagées vers l’intersection suivante, ce qui crée un phénomène combinatoire qui augmente encore plus le nombre d’événements à considérer en aval.

En considérant un pas de temps de dix minutes pour la demande et une durée de cycle de 100 s, 24 événements au maximum sont créés par heure par notre modèle (si la demande varie effectivement à chaque pas de temps) quelle que soit la relation fondamentale utilisée, et six ondes sont générées en sortie. Avec le modèle à alternance de phase, au minimum 108 événements sont créés, pour le cas le plus simple d’une relation fondamentale triangulaire, et ce, sans tenir compte de l’impact des changements de la demande ni de l’effet combinatoire sur les intersections en aval, puisqu’au minimum 108 ondes sont propagées vers l’aval (soit près de vingt fois plus). Le modèle diminue donc considérablement le nombre de calculs.

Figure 12.a. Création d’événements avec le modèle intégrateur

12.b. Création d’événements avec le modèle à alternance de phases

Q1

Q1

Q1

Q2

Q2

Q2

Lien 1

Lien 2

Lien fictif

A

C B

D

Lien 1

Lien 2

Intersection A

C

B

F

ED

Q1 Q1

Q1 Q=0 Q=0

Q=0 Q=0 Qma

Le schéma WT est particulièrement bien adapté à une telle discrétisation événementielle. En effet, même si le schéma de Godunov est plus classiquement utilisé, celui-ci n’est pas pertinent avec notre modèle d’intersection. En effet, la capacité de description des temps de parcours sur le lien fictif dépend de la finesse de résolution du schéma, si bien que les temps de parcours recréés sont multiples du pas de discrétisation temporel, puisque la longueur du lien fictif est, par construction, un multiple du pas de discrétisation spatial (voir [3] pour une application des principes de modélisation présentés dans cet article à un schéma de Godunov et les problèmes rencontrés).

4 Trois événements pour une relation fondamentale triangulaire, mais ce nombre augmente si la relation fondamentale est plus raffinée.5 Idem.



6.4. Cas des intersections plus complexes

Notre dernière remarque concerne l’extension de notre modèle à des inter-sections plus complexes et plus réalistes que le cas simpliste à une entrée et une sortie. Comme nous l’avons vu, le modèle développé ici n’est pas un vrai modèle d’intersection mais plutôt un modèle de feu. Il peut être rajouté dans tout type de configuration d’intersection (à n entrées et p sorties), et à n’importe quel type de modèle d’intersection qui gère les flux entre les demandes en amont de l’intersection et les offres en aval. n liens fictifs sont alors créés entre la sortie des entrées et l’intersection. Les débits dans le carrefour, c’est-à-dire entre la sortie de ces liens fictifs et les entrées des sorties, sont gérés directement par le modèle d’intersection en utilisant les demandes en sortie des liens fictifs et les offres aval. L’utilisation d’un lien fictif crée une intersection supplémentaire entre le lien en entrée et son lien fictif. Le modèle d’intersection doit alors être légèrement modi-fié en incorporant une contrainte supplémentaire sur le débit (cf. 4.2.).

Dans les intersections avec des mouvements tournants, certains flux peuvent être gênés par d’autres (par exemple, les véhicules tournant à gauche sont gênés par les véhicules venant d’en face) ou l’existence de différentes phases sur une même entrée peut conduire à des temps d’attente différents. On peut alors utiliser des voies directionnelles pour utiliser des formules de retard cyclique adaptées à chaque type de mouvement tournant.

Conclusions

Nous avons proposé un nouveau type de modèle d’intersection associé à un modèle d’écoulement adapté à l’affectation dynamique. Notre approche consiste à simplifier un modèle d’écoulement précis en supprimant les phénomènes dyna-miques dont l’échelle est inférieure à la durée d’un cycle, notamment l’alternance de phase de feux rouge et vert. Cette simplification n’est pas une perte de pré-cision, mais plutôt une adaptation de notre niveau de résolution au contexte de l’affectation dynamique.

Notre modèle d’intersection prend en compte les retards créés dans l’inter-section, les restrictions locales de capacité et la propagation des ondes de choc. Elle utilise une relation offre–demande adaptée et un lien fictif dont la longueur variable recrée un retard dépendant du débit d’entrée. Ce modèle permet une bonne description des phénomènes de trafic, tout en restant rapidement calcula-ble, puisque seules les transitions entre des états constants génèrent des calculs. Ce modèle d’intersection devrait être maintenant incorporé dans un modèle d’af-fectation dynamique complet pour évaluer son intérêt dans une mise en œuvre au sein d’un réseau.



Références

[1] V. Astarita. A continuous time link model for dynamic network loading based on travel time function. In : J.B. Lesort, editor, Proceedings of the 13th International Symposium on Transportation and Traffic Theory, Lyon, France, pages 79–102. Pergamon, Oxford, 1996.

[2] C.F. Daganzo. A finite difference approximation of the kinematic wave model of traffic flow. Transportation Research – Part B, 29(4) : 261–276, 1995.

[3] T. Durlin. Modélisation du trafic routier – Affectation pour l’exploitation, Rapport de DEA, ENTPE, Vaulx-en-Velin, France, Septembre, 2004.

[4] V. Henn. A wave-based resolution scheme for the hydrodynamic LWR traf-fic flow model. Proceedings of the 5th meeting on Traffic and granular Flow, Delft, The Netherlands, October, 2003.

[5] V. Henn. Tracking waves through boundaries : boundary conditions in the wave tracking resolution of the LWR. Proceeding of the 4th IMA Conference on Mathematics in Transport studies, London, United Kingdom, September, 2005.

[6] R. Jayakrishnan, H.S. Mahmassani, T.Y. Hu. An evaluation tool for advanced traffic information and management systems in urban networks. Transportation Research –C, 2(3) : 129–147, 1994.

[7] J.P. Lebacque. The Godunov scheme and what it means for first order traf-fic models. In J.B. Lesort, editor, Proceedings of the 13th International Symposium on the Transportation and Traffic Theory. Lyon, France, pages 647–678. Pergamon, Oxford, 1996.

[8] D.R. Leonard, J.B. Tough, P.C. Baguley. Contram : a traffic assignment model for predicting flows and queues during peak periods. TRRL Laboratory Report 841, Transport and Road Research Laboratory, Crowthorne, UK, 1978.

[9] M.L. Lighthill, G.B. Whitham. On kinematic waves II – A theory of traffic flow in long crowded roads. Proceedings of the Royal Society, A(229) : 317–345, 1955.

[10] G.F. Newell. A simplified theory of kinematic waves in highway traffic, Part 1 : General theory. Transportation Research – Part B, 27(4) : 281-287, 1993.

[11] B. Ran, D.E. Boyce. A link-based variational inequality formulation of ideal dynamic user-optimal route choice problem. Transportation Research – Part C, 4(1) : 1–12, 1996.

[12] P.I. Richards. Shockwaves on the highway. Operation Research, 4 : 42–51, 1956.

[13] Transportation Research Board. Highway Capacity Manual. Washington, USA, CD-ROM. chapter 16, 2000.

[14] F. Viti, H.J. Van Zuylen. Modelling queues at signalized intersections. Transportation Research Record 1883, pages 68–77, National Research Council, Washington D.C., December, 2004.

[15] J.G. Wardrop. Some theoretical aspects of road traffic research. Proceedings of the Institute of Civil Engineering, Part 2, 1 : 325–378, 1952.

Imprimé en France – JOUVE, 11 bd de Sébastopol – 75001 Paris472880m- Dépôt légal : Février 2009

Documents

MODÉLISATION DU TRAFIC