Modèles de réseau

Objectifs
Modèles de réseau Trouvez des chemins connectés à travers le réseau(x)

SIE 510 Estimer les coûts de déplacement dans le réseau

Printemps 2005

Gérer/analyser des parties du réseau ou des actifs

De Miller, H. et S. Shaw. 2001. Informations géographiques associé au réseau
Systèmes de transport. Oxford : Oxford University Press.

Nécessite la représentation de la topologie et de la géométrie de

1er février 2005 le réseau

Sujets du Modèle Réseau Modèles de réseaux et théorie des graphes

La théorie des graphes fournit le cadre mathématique pour les réseaux
La théorie des graphes comme modèle mathématique sous-jacent
Un graphe est un ensemble de sommets et de relations entre les sommets.

Représentation du réseau appliquée au transport

Composants de graphique
systèmes
Sommets – identifiés de manière unique, représentent des membres d'un ensemble
Systèmes de référencement linéaire
Edges – represent relationships among members of the set
les arêtes sont des paires ordonnées de sommets
Segmentation dynamique
arête dirigée – la relation s'applique dans un sens
arête non orientée - la relation s'applique dans les deux sens
Modèles de réseau et théorie des graphes Modèles de réseau
Graphe planaire Graphe non planaire
Ligne droite topologique dirigée
connexion entre deux nœuds ordonnés

Enveloppé dans un plan euclidien, Pas de sommets requis

nécessite un sommet aux intersections des arêtes NodeID #1 NodeID #2
aux passages frontaliers

Réseaux – graphique pour représenter explicitement l'interaction - Chaîne dirigée – un lien dirigé avec une forme intermédiaire
ensemble connecté de nœuds et de liens points entre deux nœuds ordonnés
Nœuds – sommets représentant l'origine, les terminus ou les relais,
uniquement identifié
NodeID #1 NodeID #2
Liens – arêtes représentant des conduits pour l'écoulement entre les nœuds,
identifié par des paires de nœuds étiquetés, pour un graphe dirigé, le nœud
l'ordre est significatif

Représentation en réseau de Représentation du réseau routier

systèmes de transport
Les systèmes de transport sont généralement représentés comme orientés
réseaux
Le système de transport est souvent partitionné en modes
specific sub-networks
Route, métro, air, chemin de fer, bus

Les liens correspondent à des rues ou des routes

Souvent stocké comme des réseaux séparés avec des liens de transfert vers
représenter des connexions Les nœuds correspondent aux intersections de rue

La fonction de coût généralisée représente le coût unitaire pour traverser un

lien
 Représentation du réseau de transit Modèle nœud-lien 32
31
8
7
23
Liens de transport longue distance Link ID Depuis Node À Node Longueur
Arrêt de transfert 6
6 20 23 22
20
7 23 31 86
arrêts
8 31 32 69

Node ID X Y Relational model

20 235,00 420.00 pour le lien de nœud
23 250,11 436,00 se compose de lien et
31 324,05 460,35 relations de nœuds
32 410,65 472,80

Faiblesses du réseau planaire Table de lien

2 Link-ID Nœud d'origine À-Node
La plupart des SIG nécessitent un ancrage plan du modèle nœud-lien 1 10 30
10 1 30
2 30 40
L'embedding planaire force les nœuds à toutes les intersections 4 40 5 50
3 3 30 20
Ne tient pas compte des viaducs, des passages souterrains ou des rampes 4 30 40
20 5 40 50
Suppose que les liens sont homogènes – un attribut est constant sur
un lien Table tournante Table des nœuds

Support limité pour les relations un à plusieurs et plusieurs à plusieurs Node-ID Lien d'origine À-Lien Impedance Node-ID attributes
30 1 3 5 10
Relations de nombreux transports physiques et logiques 30 1 4 10 20
les entités sont complexes 30 1 2 -1 30
Route 202
30 1 1 -1
Route 202 Route 9 40
40 4 2 -1
50
40 4 5 5
50 5 5 5 Ajout d'une table tournante
relation adresse plan
limitation d'intégration
Représentation en table Systèmes de Référence Spatiale

21 Situation de passage supérieur - passage inférieur Un système de référence spatiale définit les paramètres
et des règles pour situer une mesure dans l'espace.
20 23
Les paramètres essentiels pour toute référence spatiale
Identifiant du nœud De l'Arc À Arc Impedance system are an origin and units.
31
2 20 21 -1
2 20 23 0 Voici les paramètres requis pour une linéaire
2 20 31 -1 système de référence spatiale.

Systèmes de Référence Spatiale Systèmes de référence linéaire

155 miles 210, 398 Composants

Données – ensemble d'objets avec des emplacements mesurés directement

Axe Z
Axe Y Réseau - représentation spatiale numérique des nœuds et des liens
pieds
Axe Y
35,107 Méthode de référencement linéaire – méthode pour déterminer un
0,0,0
0 0,0 Axe X position au sein du réseau en utilisant un chemin défini et un
Axe des X
distance de décalage le long du chemin
pieds
Linéaire 2-D 3-D
 Systèmes de référencement linéaire
Méthodes de référence linéaire
Soutenez l'association des "événements" avec des positions au sein d'un
Road name - Mile point réseau de transport
Événements ponctuels
Route 2
Événement linéaire
Événement d'accident codé comme :
5,0 10.0
Référencé comme Route 2 MP 5,5
Route 22, Point de repère 147,5
Événements ponctuels
Control Sections

Événements linéaires
Section de contrôle 1 Section de contrôle 2 Section de contrôle 3
Événement linéaire
Zone de dépassement codée comme
Route 22, Panneau kilométrique 126.125
Lien et Nœud au repère kilométrique 134,25
Lien 43

Nœud 30 Référencé le long du lien 43 Nœud 40

à partir du nœud 30

Systèmes de référence linéaire Maintenir des relations

Utilisé largement par les départements des transports depuis les distances Chaussée physiqueÆ Réseau
le long des routes étaient plus faciles à collecter que les positions 2D et la plupart
Marqueur physique
les actifs sont supposés être sur la route. (point d'ancrage)

Souvent collecté sur route par un instrument de mesure de distance

1 Mesure physique
(DMI)
Marqueur physique
Facile de rendre compte des attributs routiers (par exemple, accident ½ Représentations spatiales multiples
Une route physique
un mile au sud du point kilométrique 153 sur l'I-95 (liens réseau)

Point d'ancrage Section d'ancre

Peut être facilement compris par les utilisateurs (par exemple, conducteur d'ambulance) Identifiant Identifiant
Description de l'emplacement Depuis le point d'ancrage

Au point d'ancrage
Évolution avec l'utilisation croissante du GPS
Donnée Linéaire Distance mesurée
Segmentation dynamique Objet spatial pour chaque attribut
Lien d'événements référencés de manière linéaire (discrets ou d'intervalle) Route 9
à un ensemble d'objets spatiaux de réseau à l'exécution. Route 101

Permet d'associer plusieurs ensembles d'attributs RM102 RM105 RM108,5

avec une partie de toute caractéristique linéaire RM108
RM1 RM9 RM11 RM17
Élimine la nécessité d'un ensemble d'objets spatiaux pour Plusieurs ensembles d'événements référencés linéairement
chaque attribut.
Sans segmentation dynamique, chaque événement nécessite un nœud
Crée des objets basés sur des attributs au besoin.
sur le segment pour indiquer le début et la fin d'un
valeur d'attribut

Exemple de segmentation dynamique

Suppose un ensemble d'événements concernant l'état du pavage référencé
utilisant le nom de route LRM - point de mile

Route 101
RM 0 RM 22 RM 57 RM 177

Pav cond Route ID Start Fin Revêtement

event# Marqueur Marqueur cond
10 101 RM0 RM22 Juste
11 101 RM22 RM57 Pauvre
12 101 RM57 RM177 Bon

Comment plaçons-nous ces événements sur le réseau ?

Attribut mesuré –
État du revêtement
Maintaining relations
RM 0 RM 22 RM 57 RM 177
Données au Réseau
101
Itinéraire
5
Sections 5 5
2 3
10 2 3
Liens-nœuds
6 7 8 Un à un
Données Nœud 23 Lien 13 Nœud 24
Maintient avec précision Section d'ancre
Points d'ancrage
distances mesurées
Point d'ancrage 10 Section d'ancrage 2 Point d'ancrage 11
Un à plusieurs
Monde réel Nœud 23 Link 13 Nœud 24
section de route

Section d'ancrage 2 Section d'ancrage 3 Section d'ancrage 4

Maintenir des relations Liens, Itinéraires et

8
Réseau vers les composants LRM
Sections 7
3
Nombre à nombre 2 Itinéraire n° 5

6 Itinéraire # Route ID
Noeud 23 Lien 13 Nœud 24
1 5 101

Route A Secte Lien De À De À Pos Itinéraire

ID ID Mesurer Mesurer Pos #
Route B
1 6 0 22 0 100 5

2 7 22 108 0 100 5
Sections
3 8 108 177 0 50 5
Segmentation dynamique pour les multimodaux
Modèles de données ITS
Routage
Conception de base de données de réseau virtuel basée sur des systèmes de routage Améliorer l'utilisation de la capacité existante des systèmes
qui capturent des dépendances fonctionnelles dans un mode multidimensionnel

réseaux Suite de dispositifs de capteurs routiers contribuent à la dynamique

modèle du système de réseau et sa charge
Réseau topologique stocké indépendamment
Pour les autoroutes comme
L'objectif est de fournir des informations en temps réel aux voyageurs, pour
direction de voyage
dispositifs de contrôle de la circulation, panneaux à messages variables
Nœud 23 Lien 13 Nœud 24

Arrêt de bus Itinéraire de bus

Attributs maintenus en tant que systèmes de routes et événements

Besoin de modèles de données 3D Pour un overpass complexe,

Ajout de voies et de virages complexes
underpass, multi-ramp
configurations au modèle de données systèmes

Besoin d'un modèle pour représenter

de multiples voies, changement de voie
contraintes, divisions de voie et
fusions, voie temporaire
modifications, voie-voie
virages aux intersections

Segmentation dynamique
l'approche attribue un itinéraire à
chaque voie
Problèmes de mise à jour du réseau Géocodage d'adresse
22 North Main
Un B C
90 Noeud 65
10
0 100
11 Chaîne 159 89
Nœud 63
Chaîne De À De To De To
ID Nœud Noeud LADD LADD RADD RADD

159 63 65 10 90 11 89

AB/AC
100 * 0,15 = 15
12/80 = 0,15