Une ville sans embouteillages

Chapitre 2.
( le lien vers le chapitre 1 )

L'art de concevoir des réseaux routiers

Problèmes de transport d'une ville aux yeux d'un informaticien

Si on me recommandait un article intitulé «L'art de concevoir des réseaux routiers», je demanderais immédiatement combien de réseaux routiers ont été construits avec la participation de son auteur. Je dois avouer que mon activité professionnelle était loin de la construction de routes et était récemment associée à la conception de microprocesseurs où j'étais, entre autres responsabilités, engagée dans la consommation de ressources de la commutation de données. À cette époque, ma table se tenait juste en face de la fenêtre panoramique qui ouvrait une belle vue sur le long tronçon de la route de Volgograd et une partie du troisième anneau de transport avec leurs embouteillages sans fin du matin au soir, d'horizon en horizon. Un jour, j'ai eu un choc soudain de reconnaissance: «La complexité du processus de commutation des données avec laquelle je lutte sur une puce peut être similaire aux difficultés auxquelles les voitures sont confrontées lorsqu'elles traversent le labyrinthe du réseau routier».
Probablement, cette vision de l'extérieur et l'application de méthodes qui n'étaient pas traditionnelles pour la zone en question m'ont donné l'occasion de comprendre la cause des embouteillages et de faire des recommandations sur la façon de surmonter le problème dans la pratique.

Alors, quelle est la nouveauté de l'approche?

Historiquement, l'objectif principal des routes est considéré comme l'opportunité qu'elles offrent de parcourir rapidement de longues distances (entre Rome et les provinces). Un tel jugement est justifié en ce qui concerne le réseau routier interurbain de niveau fédéral: les villes qu'elles relient ressemblent à de petits points rares sur l'atlas, et la plupart des voitures voyageant entre ces villes passent leur chemin sans tourner nulle part.

Cependant, dès que nous tournons plusieurs pages et ouvrons une carte détaillée d'une grande ville, l'image change immédiatement: le nombre d'adresses où le voyage peut être commencé ou terminé atteint environ dix mille, toutes sont assez densément réparties et de taille relativement petite. Dans le même temps, des centaines de milliers de voitures peuvent être en mouvement dans les rues d'une telle ville à la fois, de plus, le but de chacune n'est pas seulement de remplir des routes déjà vides, mais de déplacer une personne ou une cargaison d'un point avec une adresse spécifique X à un point avec une adresse spécifique Y. Dans l'ensemble, cela signifie que le système de transport urbain doit être adapté pour résoudre efficacement le problème de l'adressage simultané multiple. Ainsi, les fonctions du système de transport urbain deviennent encore plus similaires au réseau téléphonique ou informatique qu'au réseau routier interurbain.

Considérer le réseau routier comme un circuit de commutation pour un développeur ou un ingénieur matériel dans le domaine des technologies de transfert d'informations est une manière tout à fait naturelle de parler d'un problème, mais parmi les personnes impliquées dans la recherche sur les problèmes de transport, ce point de vue est, à ma connaissance, nouveau.

La théorie de la commutation des signaux est une science technique étroite et, à elle seule, bien sûr, ne suffit pas pour planifier une rue séparée, un carrefour ou prédire le comportement d'un flux de circulation sur une section droite et isolée d'une autoroute. Heureusement, les problèmes énumérés ci-dessus sont bien étudiés aujourd'hui et les méthodes développées pour les résoudre ont déjà été mises en pratique avec succès. La théorie de la commutation, à son tour, permet à l'architecte d'atténuer le risque, dans lequel la ville entre dans un état d'effondrement des transports malgré le fait que tous les éléments du réseau routier sont parfaitement exécutés. Ce risque existe parce que l'exécution de plusieurs adressages simultanés est une tâche consommatrice de ressources et de temps, dont la clé pour une solution efficace ne réside pas dans la largeur des rues et la commodité des échangeurs de transport, mais dans le choix compétent de la commutation particulière que le réseau routier proposé mettra en œuvre.

A partir de cette recherche, par exemple, vous découvrirez pourquoi les réseaux de transport de type «artériel», qui sont encore souvent utilisés dans les villes modernes, sont «mauvais» et, avec la croissance de la population, entraîneront nécessairement des embouteillages. Un autre résultat intéressant, qui est en bon accord avec les observations, explique pourquoi l'expansion des routes à elle seule, si avant tous les embouteillages se sont produits exclusivement à proximité des échangeurs, est peu susceptible d'améliorer en quelque sorte la situation même si le nombre de voitures en la ville reste la même.

Quand j'ai écrit cet article, il était crucial pour moi qu'il soit compréhensible pour l'architecte le plus ordinaire, puisse être utile à travers son travail. J'ai essayé d'initier le lecteur aux problèmes de commutation dans un langage simple, de développer des critères pour évaluer dans quelle mesure un réseau routier particulier fera face à la tâche d'adressage simultané, et en utilisant des exemples de modèles, j'ai montré comment utiliser ces connaissances dans la pratique.

L'article est destiné à un large cercle de lecteurs qui connaissent un peu le cours universitaire de mathématiques et la théorie des algorithmes et sont prêts à y consacrer 1 à 5 jours.

Séparation et fusion des flux automobiles

Il est évident pour de nombreux conducteurs que les difficultés de circulation surviennent principalement dans les parties de la route où les voitures, pour une raison quelconque, sont obligées de changer de voie. Les exemples incluent les fourches routières, les rétrécissements, les zones adjacentes aux sorties d'autoroute et aux routes d'accès, les sections d'autoroutes où certaines voies sont bloquées par un accident ou des travaux routiers.
Dans cette section, on tentera de donner une description quantitative des processus qui se produisent dans de tels cas, et nous commencerons par comprendre comment les voitures changent de voie.

Deux stratégies pour passer à une voie de circulation adjacente
La circulation le long d'une autoroute présente une irrégularité naturelle: quelqu'un préfère conduire un peu plus vite, quelqu'un un peu plus lentement, entre certaines voitures la distance diminue et devient difficilement confortable pour conduire, tandis qu'entre les autres elle augmente tellement qu'elle permet aux voitures de s'adapter là des voies adjacentes. L'apparition de tels écarts dans l'écoulement de la voie adjacente directement du côté du conducteur aléatoire peut être fréquente ou peu. Si, au moment où il a besoin de faire une manœuvre, il n'y a pas d'écart, le conducteur peut recourir à au moins deux stratégies comportementales:

Stratégie 1
Plusieurs espaces appropriés peuvent simplement être situés à proximité de l'emplacement du conducteur. Si le mouvement est suffisamment dense, il est peu probable que le conducteur soit en mesure d'augmenter la vitesse et de rattraper l'écart nécessaire, mais en ralentissant un peu, le conducteur laisserait les voisins ruisseler dépasser la voiture afin de devenir égal à l'écart qui était à l'origine derrière - ce ne serait pas un gros problème. Les coûts de cette stratégie sont évidents: le conducteur lui-même et les voitures conduisant derrière dans sa voie perdent du temps en raison de la nécessité de réduire la vitesse.

Stratégie 2
Pour attendre, vous devez être patient et disposer du temps nécessaire pour cela. Une alternative peut être une tentative d'effectuer la manœuvre nécessaire "ici" et "maintenant". Selon cette idée, le conducteur indique aux voitures derrière lui la voie vers laquelle il va se diriger. Ceux-ci, à leur tour, en réponse à son signal devraient ralentir un peu et "laisser les voitures se déplacer devant eux avancer", créant ainsi l'écart de la taille nécessaire dans leur flux. Les coûts de temps dans ce cas sont répartis entre les voitures de la voie, sur lesquelles le conducteur finit par basculer.

Dans la vraie vie, les deux stratégies sont impliquées en même temps: dans un premier temps, le conducteur ralentit, attendant un écart relativement important dans le flux de la voie adjacente, et seulement après cela, il donne un signal aux voitures qui s'y déplacent de leur intention de faire une manœuvre de changement.

Sans aucun doute, les routes d'accès, les sorties d'autoroute et les rétrécissements ne sont pas la seule raison du changement de voie, ce qui mérite d'être rappelé lors de la conception des routes. La capacité des voitures à des vitesses plus élevées de dépasser la circulation sans hâte est nécessaire afin d'éviter la situation sur l'autoroute lorsqu'elle se dégrade en une grande file d'attente rampant à la vitesse du tracteur le plus lent. Néanmoins, le problème de la coexistence de véhicules circulant sur une route à des vitesses différentes a une nature légèrement différente et peut être séparé des problèmes en question, car le processus de dépassement et la commutation respective entre les voies ne sont pas forcés pour le conducteur. Si le conducteur ne se hâte pas, selon la théorie des probabilités, une opportunité pratique d'effectuer une manoeuvre lui sera naturellement donnée et pour cela il n'a pas besoin de perturber le mouvement des autres conducteurs.

Le coût d'une seule commutation
Le comportement des conducteurs peut en réalité être très compliqué, mais il est primordial pour nous que le résultat obtenu dans les conditions du modèle reste plausible: chaque passage forcé entre les voies impose une pénalité de temps aux participants au trafic.

Évaluons maintenant comment la quantité de temps perdu dépend de la densité du trafic sur la route.

Nous considérerons le mouvement le long de chaque voie comme un ruisseau distinct. En essayant de rester à une distance confortable des voitures sur la même voie, les conducteurs réservent ainsi un tronçon de route d'une certaine longueur caractéristique d dans le ruisseau. Laissez ρ les voitures tomber dans un flux par unité de longueur. Nous convenons d'appeler la densité d'écoulement petite, ou de dire que ρ est petit si le produit ρ × d est bien inférieur à 1.

Au moment où le conducteur se rend compte de la nécessité de passer à la ligne suivante, la probabilité qu'un tronçon de route de longueur d , que le conducteur allait occuper, ne soit pas libre, à petit ρ , sera approximativement proportionnel à ρ lui-même. Si l'événement décrit a réellement lieu, alors deux voitures en compétition pour une place connaîtront au total, à la suite des manoeuvres, un certain retard dans la valeur constante moyenne δ .

En supposant que ρ est petit, nous pouvons négliger la probabilité que leurs actions à ce moment affectent le mouvement des autres voitures. Ainsi, lorsque ρ est petit, la perte de temps d'une commutation sera α⋅ρ , où le coefficient α est une quantité empiriquement mesurable en fonction de la culture, du temps, des limites de vitesse (et ainsi de suite), mais restant approximativement constante dans ce temps particulier et pour cette ville dans son ensemble.

Taux d'intensité de perte sur un tronçon de route avant la sortie
Les voitures qui se dirigent vers la sortie, avant d'arriver à la rampe (graphique 2), doivent, parfois même plusieurs fois, passer à la rangée adjacente à droite. Chacune de ces manœuvres perturbe l'écoulement et, par conséquent, la vitesse moyenne dans le tronçon avant la sortie est sensiblement plus faible que dans les tronçons «transit» (privés des sorties, entrées et fourches) de l'autoroute.


Graphique 2

Passer une partie du chemin à une vitesse inférieure - représente pour les conducteurs (et leurs passagers) un temps supplémentaire consacré au voyage. En d'autres termes, la zone de l'autoroute adjacente à la sortie est un générateur constant de pertes de temps.

Supposons que la vitesse moyenne de la voiture ν et la densité d'écoulement ρ à la limite frontale de ce tronçon soient les mêmes pour toutes les voies.

De plus, supposons que la densité ρ et le débit q en direction de la sortie (le nombre moyen de voitures tombant sur la rampe par unité de temps) soient simultanément petits, et s est le nombre de voies sur l'autoroute. Pour arriver à la sortie, le conducteur effectuera 1 à s manœuvres de commutation. Si la densité de flux sur la rampe est bien inférieure à ρ , alors seule la dernière manœuvre sera pour le conducteur pratiquement "gratuite", tandis que le reste entraînera en tout cas des pertes de α⋅ρ . En moyenne, vous devrez effectuer (0 + 1 + 2 + ... + s - 1) / s = ( s - 1) / 2 manœuvres «coûteuses».

Compte tenu des difficultés causées par toutes les voitures se dirigeant vers la sortie, nous pouvons créer la formule de l'intensité des pertes de temps:

I _out = q ⋅ α ρ ⋅ ( s - 1) / 2 = ( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 - 1 / s )

La valeur p = ( sρν ) n'est rien de plus que le débit de toutes les voitures se déplaçant le long de l'autoroute dans la direction en question (le nombre moyen de voitures passant par un arrêt de bus par unité de temps). La dernière remarque nous donne l'occasion de réécrire la formule pour I une forme plus symétrique:

I _out = ( α / 2 ν ) ⋅ pq ⋅ (1 - 1 / s )

Taux d'intensité de perte dans la section adjacente de la route d'accès
La situation qui se produit sur l'autoroute derrière le tronçon où la route d'accès se connecte avec elle répète largement la situation sur le tronçon avant la sortie, bien qu'il y ait quelques différences. Soit un petit flux de wagons de puissance q à travers la rampe latérale se déverse dans le trafic principal de l'autoroute (graphique 3).


Graphique 3

La rampe n'a qu'une longueur finie, donc toutes les voitures nouvellement arrivées doivent être commutées sur la voie de droite de l'autoroute. En conséquence, la densité de la circulation dans la voie de droite1 est localement supérieure à la moyenne sur la route, c'est pourquoi certains conducteurs décident de passer à une voie adjacente moins fréquentée sur la gauche, ce qui, à son tour, conduit à une voie locale augmentation de la densité déjà sur la deuxième voie. Ce processus de changement de voie se poursuivra jusqu'à ce que la densité de débit soit nivelée sur toute la largeur de la route. En supposant que la vitesse moyenne ν soit la même pour toutes les n voies, nous pouvons nous attendre à ce que, à la fin des processus de commutation, la puissance d'écoulement dans chacune d'entre elles augmente exactement (1 / s ) ⋅ q .

Pour voir combien coûtera une telle commutation aux conducteurs, nous calculons d'abord la puissance de tous les flux de commutation. Le débit de la rampe à la première voie de l'autoroute que nous connaissons déjà: il est égal à q . Afin d'assimiler l'augmentation de la puissance de la première voie à (1 / s ) ⋅ q , le débit de la première voie à la seconde doit être (1 - 1 / s ) ⋅ q , de la seconde à la troisième = ( 1 - 2 / s ) ⋅ q , du k -ième au ( k + 1) th = (1 - k / s ) ⋅ q . Selon la dernière formule, la capacité du flux de commutation vers la voie de bord gauche sera (1 - ( s - 1) / s ) ⋅ q = (1 / s ) ⋅ q , comme le veut le bon sens.

Étant donné que nous connaissons la pénalité de temps d'une seule commutation et la puissance de tous les flux de commutation, nous pouvons maintenant calculer l'intensité totale des pertes générées par ceux-ci:

I _in = α ρ ⋅ q + α ρ ⋅ (1 - 1 / s ) ⋅ q + α ρ ⋅ (1 - 2 / s ) ⋅ q + ... + α ρ ⋅ (1 / s ) ⋅ q =

α ρ q (1 + 2 + ... + s ) / s =

α ρ q ( s + 1) / 2 =

( α / 2 ν ) ⋅ q ⋅ ( sρν ) ⋅ (1 + 1 / s ).

En rappelant à nouveau que sρν est la puissance p du flux de toutes les voitures le long de l'autoroute, nous obtenons la formule de coût sous sa forme finale:

I _in = ( α / 2 ν ) ⋅ pq ⋅ (1 + 1 / s ).

Taux d'intensité de perte à la fourche symétrique
Dans les paragraphes précédents, nous avons constaté des pertes dues à l'interaction des flux, dont l'un était nécessairement important et l'autre était nécessairement faible. Afin de démontrer une approche pour résoudre des problèmes lorsque les capacités des deux flux sont comparables en puissance, considérons un autre extrême: une fourche dans laquelle les deux directions de branche sont également populaires pour les conducteurs (graphique 4).


Graphique 4

Pour plus de commodité, les voitures allant à droite sur la fourche seront appelées «bleues», et les voitures partant à gauche - «rouges». Au départ, les voitures des deux «couleurs» se déplacent de façon mixte, dispersées entre les 2 voies de l'autoroute. À l'approche de la fourche, les voitures rouges commencent à dériver lentement vers les n voies de gauche, et les bleues vers la droite de s : il y a des flux de commutation dans les deux directions entre les voies adjacentes. Contrairement à l'exemple de la route d'accès, ces flux ne sont plus «relativement faibles». Soit dit en passant, seulement entre les deux voies centrales, il y a un échange forcé de trafic, dont l'intensité dans toutes les directions (de gauche à droite ou de droite à gauche) est égale à un quart de la puissance de l'ensemble ruisseau se déplaçant le long de l'autoroute. Heureusement, dans cette situation, il existe un moyen suffisant pour estimer les coûts générés.
Au début, nous pouvons noter que le processus de division des voitures en «rouge» et «bleu» commence très probablement bien avant la fourche et se déroule lentement, par conséquent, d'une part, il devrait avoir peu d'effet sur la densité du trafic dans une ligne distincte. , et d'autre part, rendre les flux de commutation étirés sur de longues distances, donnant ainsi la possibilité de représenter chacun d'eux comme une combinaison d'un grand nombre de flux de faible puissance (graphique 5).



Graphique 5

Puisque nous parlons maintenant de petits flux, quoique en plus grand nombre, rien ne nous empêche de réduire le problème en question à des problèmes déjà résolus. Nous pouvons diviser mentalement l'autoroute au centre en deux parties égales, puis les connecter ensemble avec un plus grand nombre de routes de saut à une seule voie, permettant aux voitures rouges d'aller à gauche et aux voitures bleues à droite (graphique 6). En raison d'une symétrie évidente, lors du calcul des pertes générées, nous pouvons nous concentrer sur une voiture de n'importe quelle couleur, par exemple, le bleu, et à la fin simplement doubler le résultat.


Graphique 6

Soit la vitesse ν et la densité ρ identiques pour toutes les voies et restent constantes sur toute l'étendue où les voitures sont séparées par des couleurs. Dans ce cas, la puissance d'écoulement de toutes les voitures circulant sur l'autoroute sera:

p = 2 sρv .

Soit q ₁ , q ₂ , ... q _m désignent les flux de voitures bleues se déplaçant le long de routes jumelées imaginaires vers la moitié droite de l'autoroute. Supposons que peu de temps avant la section de séparation dans chaque voie de l'autoroute, les deux couleurs soient représentées avec des proportions égales de 50%, ce qui implique qu'au total
q ₁ + q ₂ + ... + q _m est égal à sρv / 2, ou en d'autres termes, p / 4.

Les pertes générées par le flux q _{i en} raison de sa petitesse, on peut calculer par la formule:

I _i = I _out + I _in = ( α / 2 ν ) ⋅ ( p / 2) ⋅ q _i (1 - 1 / s ) + ( α / 2 ν ) ⋅ ( p / 2) ⋅ q _i (1 + 1 / s ) = ( α / 2 ν ) p q _i

En résumant la dernière formule sur tout i , nous trouvons les pertes générées uniquement par les voitures bleues:

I _bleu = ( α / 2 ν ) ⋅ p ⋅ ( q ₁ + q ₂ + ... + q _m ) = ( α / 2 ν ) p 2/4.

Les pertes totales, comme déjà mentionné, seront deux fois plus élevées et s'élèveront à:

I _div = ( α / 2 ν ) p 2/2 .

Analyse des formules obtenues
Si nous divisons l'intensité I , c'est-à-dire le temps totalement perdu par les participants par seconde, par le flux latéral q , qui par définition est égal au nombre de voitures qui se connectent ou quittent l'autoroute en une seconde, nous obtiendrons le pertes moyennes causées par une de ces voitures:

i _in = I _in / q = ( α / 2 ν ) ⋅ p ⋅ (1 + 1 / s )

i _out = I _out / q = ( α / 2 ν ) ⋅ p ⋅ (1 - 1 / s )

La chose la plus importante dans ces formules est peut-être la proportionnalité directe entre le flux de puissance des voitures sur l'autoroute p et les coûts unitaires i . Tout ressemble à une voiture cherchant à rejoindre, ou vice versa - à quitter le flux principal, causant ainsi une perturbation constante à chaque conducteur à proximité.

La deuxième observation, intéressante et très inattendue, concerne l'effet extrêmement faible sur l'intensité des pertes générées dans le nombre de voies à proximité de l'autoroute juste à côté de la jonction. Comme vous pouvez le voir, en regardant la formule pour I _out , la sortie est généralement la plus rapide pour une route à voie unique ( s = 1, i _out = 0), et les difficultés causées par la route d'accès adjacente pour une autoroute à trois voies et à six voies ne diffèrent que par

100% ⋅ [(1 + 1/3) - (1 + 1/6)] / (1 + 1/3) = 12,5%.

Si nous considérons que chaque voiture qui a déjà rejoint le trafic sur l'autoroute devra éventuellement la quitter, il semble tout à fait légitime d'utiliser une valeur unifiée au lieu de i _in et i _out lors du calcul des pertes d'interchange

i _av = ( i _in + i _in ) / 2 = ( α / 2 ν ) ⋅ p .

Malgré le fait que la formule pour i _av ne dépend pas explicitement du nombre de voies, il faut se rappeler que sa création (voir les hypothèses pour I _in et I _out ) repose fortement sur l'hypothèse d'une faible densité de voitures sur la route , il est donc peu probable qu'il donne des résultats satisfaisants lorsqu'il est appliqué à une autoroute trop étroite avec trop de trafic.

Constatations préliminaires
Dans les zones proches des carrefours, des entraves à la circulation se produisent inévitablement, prenant du temps aux conducteurs, réduisant la vitesse moyenne, cette dernière entraînant une augmentation de la densité des voitures et, par conséquent, la survenue possible d'embouteillages. Les pertes de temps associées à la séparation et à la fusion des flux de voitures seront appelées pertes de commutation.

Les pertes d'un type similaire sont présentes d'une manière ou d'une autre dans n'importe quel schéma de commutation: qu'il s'agisse d'un réseau téléphonique ou informatique, d'un microprocesseur multicœur ou d'un service de distribution de courrier.

Lorsque le conducteur rejoint, ou inversement, quitte la circulation sur l'autoroute, les frais de commutation occasionnés par ses actions sont proportionnels à la puissance du flux de voitures observé à ce moment sur l'autoroute.

Pour réduire les pertes de commutation dans toute la ville, il est nécessaire de considérer attentivement le réseau routier qui y est mis en œuvre au stade de la conception. Un peu plus tard, nous analyserons cette tâche en détail, mais certaines recommandations évidentes peuvent être répertoriées maintenant:

1. les pertes de commutation sont proportionnelles à la puissance d'écoulement sur l'autoroute - il n'est pas nécessaire d'agrandir les routes sans le besoin, deux petites autoroutes sont deux fois plus bonnes qu'une grande;
2. les pertes de commutation sont proportionnelles à la puissance des flux latéraux - il convient de concevoir le réseau de sorte que le conducteur doive tourner le moins de fois possible pendant son trajet;
3. la perturbation mutuelle causée par les moteurs des flux principaux et secondaires devrait être moindre à l'échelle de la ville si nous essayons d'empêcher la fusion d'itinéraires qui ne se chevauchent que sur une courte section de la route.

Conditions économiques préalables à l'existence des villes.
Un modèle de ville à «accès aléatoire» ²

(Remarque 2: le terme est tiré du concept de RAM et signifie aléatoire par probabilité et même par consommation de temps.)
La première étape de tout projet de conception (ou de refonte) du système de transport urbain est peut-être d'essayer de déterminer le type de changement dont la ville a vraiment besoin maintenant et comment ses besoins évolueront à l'avenir.

Une telle analyse peut être effectuée si nous divisons d'abord la ville en zones pas trop grandes, mais pas trop petites, puis pour chaque paire de telles zones, indiquez le nombre approximatif de déplacements d'un côté ou de l'autre dont leurs habitants ont besoin à à un moment ou à un autre de la journée. En plaçant les prédictions faites dans une matrice, vous recevrez ainsi une matrice des besoins de migration des habitants de la ville.

Exactement pour cette matrice, nous devons rechercher un réseau qui permet aux conducteurs et aux passagers de passer le moins de temps possible sur un voyage séparé, nécessitant des autorités de la ville le moins de ressources possible pour la réalisation du réseau.

En ce qui concerne les villes existantes, il est important ici de ne pas se tromper et de ne pas remplacer le nombre de voyages dont les gens ont vraiment besoin par le nombre de voyages qui ont été historiquement établis sous l'influence de certains obstacles ou difficultés au moment de le travail de conception. Probablement, le réseau de transport de Berlin «avant» et «après» la chute du mur de séparation peut servir d'illustration la plus frappante de ce qui a été dit.

Cette section traitera principalement des questions humanitaires dans lesquelles je ne suis pas un spécialiste, mais je pense que les discuter en tant qu'amateur est néanmoins plus correct que de simplement éviter le problème.

Afin de mieux représenter les besoins migratoires de la population, il convient de commencer par la question fondamentale: «À quoi servent les villes et quelle est leur fonction utile?»

Essayons d'y répondre non pas en tant que résidents ordinaires des villes (et villages), mais du point de vue de la personne responsable du processus d'urbanisation dans un grand État développé. De ce point de vue, il n'est plus important de savoir quelles motivations historiques faisaient autrefois tant de gens entassés dans un petit morceau de terre, ou les raisons pour lesquelles elles continuent de le faire maintenant, il est crucial - quel est l'effet économique des villes d'une taille ou d'une autre et par quels mécanismes cet effet est obtenu.

À mon avis, la principale raison de l'existence des grandes villes est, d'une part, l'opportunité pour les entreprises technologiques de trouver des employés de professions rares, et d'autre part, l'opportunité pour les personnes ayant maîtrisé des professions rares de vendre leur services aux entreprises intéressées à des conditions compétitives. Dans une petite ville (non spécialisée), la production de nombreux biens et services est soit tout simplement impossible, soit met les entreprises technologiques et leurs employés en otages mutuels, sans donner à l'une ou à l'autre aucune alternative.

Par exemple, prenez le métier pas si rare d'un professeur de littérature scolaire. Selon les statistiques, leur besoin est d'environ 1 enseignant pour 1000 personnes. Dans une école ordinaire, 3-4 tuteurs enseignent la littérature. Le choix d'un emploi pour un professeur de littérature peut être qualifié de compétitif s'il existe au moins 4 à 5 écoles secondaires dans la ville, ce qui, en termes de population, correspond à environ 15 000 personnes.

Apparemment, les personnes ayant une spécialisation en ingénierie se sentent à l'aise sur le marché du travail dans les villes comptant au moins 100 000 habitants. Bien sûr, il existe également de telles professions, dont la demande n'apparaît que dans les villes de plus d'un million d'habitants, mais l'existence de plusieurs millions de villes n'a aucun sens économique pour moi.

Après tout ce qui précède, deux hypothèses semblent tout à fait raisonnables (dont la validité, cependant, n'affecte pas la vérité du contenu principal de l'article):

1. l'adulte moyen a besoin de voyager le plus souvent sur des distances qui lui confèrent 4 à 5 des emplois les plus prometteurs;
2. pour une partie importante de la population qui représente les professions rares et les plus économiquement précieuses, la distance des déplacements les plus fréquents pourrait bien être comparable au rayon de leur ville.

Pour mieux refléter les hypothèses 1 et 2, dans mes exemples, j'utiliserai souvent le modèle de la ville à `` accès aléatoire '', en supposant que la puissance des flux de déplacement requis est la même entre les deux quarts de celle-ci, ou, en d'autres termes, dans toutes les cellules de la matrice des besoins de migration, il y a le même nombre positif. Si vous regardez au hasard les enregistrements des voyages effectués dans une telle ville pendant la journée, alors pour le prochain voyage marqué, tous les trimestres auront la même probabilité de savoir si le début ou la fin d'un tel voyage, et aucune relation entre la position du les trimestres «initial» et «final» doivent être respectés.

Réseaux routiers avec la topologie la plus simple

Essayons d'appliquer les idées décrites dans les paragraphes précédents à certains types de plans de ville tirés de la vie.

Ville linéaire

Les premières grandes colonies ont été créées principalement le long de la côte, dans des zones d'une mince bande de terre entre la mer et les falaises, ou le long des chemins de routes très fréquentées, de sorte qu'au cours de leur croissance, elles ont acquis des frontières étroites et allongées. Beaucoup de ces colonies ont survécu jusqu'à nos jours, conservant leur forme allongée et se transformant en villes modernes (veuillez voir l'illustration ci-dessous).


(une zone exclue de Rio de Janeiro, l'auteur est inconnu)

Souvent, dans une telle ville, il n'y a qu'une seule route large autour de laquelle elle est construite. Supposons que chaque quartier (zone de division territoriale) génère un flux de déplacements avec la puissance 1, le nombre de tous ces quartiers est égal à n , et la ville elle-même suit le modèle de migration `` à accès aléatoire ''.


Graphique 7

Essayons de trouver pour les paramètres énumérés ci-dessus comment le temps de trajet moyen et la surface de route requise changent avec l'augmentation de n .

Donc, que tous les quartiers aient la même forme et la même taille, et leur nombre multiplié par λ (lambda) fois. Il est évident que

• la longueur de la route principale augmente d'un facteur λ .

En raison du modèle accepté d '«accès aléatoire», 50% des voyages qui ont commencé dans la moitié droite de la ville se termineront dans sa moitié gauche (l'inverse sera également correct), donc avec une augmentation du nombre de trimestres d'un facteur λ , la puissance du flux passant par le milieu de la ville se multipliera également par λ fois. Des discussions similaires avec la même inférence seront vraies si, au lieu du milieu, nous prenons un point quelconque divisant la ville dans un rapport donné (1: 3, 2: 5), ce qui implique que

• la puissance de l'écoulement le long de la route principale augmente d'un facteur λ ;
• le nombre de voies de la route principale requises dans chaque section multiplie par λ fois.

Plus ou moins évident que la durée moyenne du voyage, et avec elle

• le temps de trajet net consacré à parcourir la distance augmente d'un facteur λ .

Il ne reste plus qu'à calculer le nombre de fois que le temps perdu en raison des coûts de changement de poste en un seul voyage augmentera. Un flux latéral de puissance 1 entre et sort de chaque quartier, ce qui génère ensemble des pertes de temps avec intensité:

I = I _in + I _out = ( α / 2 ν ) p ⋅ 2,

où p est la puissance de l'écoulement sur la route principale. On sait déjà que le nombre de trimestres et la puissance d'écoulement sur la route principale augmentent d'un facteur λ , donc les pertes de temps totales générées par le réseau se multiplient par λ ² fois. En revanche, le nombre de déplacements générés par le réseau, entre lesquels toutes ces pertes sont réparties, augmente d'un facteur λ , c'est pourquoi

• le temps de trajet net perdu en raison des coûts de commutation augmente d'un facteur λ .

Présentons tous les résultats dans un tableau:

Topologie linéaire
Le nombre de points d'adresse (trimestres) avec la puissance 1 ........................ n
Superficie totale de la route ............................................... ....................................... O ( n ² )
Temps de trajet net,
dépensé pour couvrir la distance ............................................. ...................... O ( n )
Temps de trajet net,
perdu en raison des coûts de changement ............................................. ........................ O ( n )
Nombre de nœuds de commutation .............................................. ..................... O ( n )
Nombre de nœuds de commutation, compte tenu de la puissance des flux latéraux ............. O ( n )

La notation utilisée « y = O ( x )» signifie que les paramètres x et y sont fonctionnellement dépendants, et lorsque x croît sans limite, le rapport x / y tend vers un nombre fini, différent de zéro.

Ville cellulaire

La deuxième méthode de planification, assez courante, consiste à disposer les quartiers sous la forme d'une matrice rectangulaire, semblable à la façon dont les morceaux portionnés sont placés dans une barre de chocolat.

Nous acceptons d'appeler ces villes "cellulaires". ".


(Los Angeles, photo: Slava Stepanov)

Le graphique 8 montre un schéma d'une ville cellulaire qui se compose de n (en tenant compte des «moitiés»), formant ensemble un carré régulier. Les quartiers sont séparés les uns des autres par un total de √ n routes s'étendant conditionnellement d'ouest en est et √ n routes s'étendant du sud au nord. Au total, ces routes forment des croisements √ n × √ n , dont chacun peut être mis en œuvre soit comme une intersection de feux de circulation, soit à travers des ponts / viaducs.


Graphique 8

Peu importe qu'il y ait un trafic à sens unique ou à double sens, tout trajet d'un point A à un point B dans une ville cellulaire peut être réalisé le long d'un itinéraire impliquant pas plus de deux rues et pas plus d'un virage à une intersection.

En supposant que, comme dans l'exemple précédent, chaque trimestre génère un flux de déplacements avec la puissance 1 et que les besoins de migration de la population suivent le modèle de l'accès aléatoire, nous pouvons calculer, maintenant pour une ville cellulaire, les lois par lesquelles le average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.

Si le nombre de trimestres augmente d'un facteur λ , alors:

• l'aire de la ville se multiplie par λ fois, et ses dimensions linéaires tout en conservant les proportions - par √ λ ,
• la distance moyenne de parcours et le temps net pour la parcourir, proportionnels aux dimensions linéaires, multiplient par √ λ fois,
• multiplier par √ λ le nombre de rues et le nombre de quartiers adjacents à une rue donnée ,
• la puissance du flux de trafic, proportionnelle au nombre de trimestres avec lesquels le flux est «en contact» (une explication de ce terme sera donnée plus loin), multiplie par √ λ fois,
• the required area of ​​all roads grows as (number of streets) × (length of one street) × (power of street flow) = √ λ ⋅ √ λ ⋅ √ λ = λ √ λ

Les flux latéraux sont divisés en ceux qui vont de ou vers les quartiers et ceux qui tournent d'une rue à l'autre aux intersections. La puissance des premiers flux, selon les conditions, reste toujours égale à l'unité. Dans les deuxièmes, presque tout le trafic circule, en provenance ou à destination de l'autoroute, si l'on tient compte du fait qu'il y a beaucoup plus de quartiers dans la ville que de quartiers dans une rue donnée. En conséquence, le changement de la puissance des seconds flux peut être estimé par la formule (changement de la puissance du flux) / (augmentation du nombre d'intersections sur une rue particulière) = √ λ / √ λ= 1. L'égalité du dernier rapport à la constante suggère que ces flux ne changent pas de manière significative avec une augmentation du nombre de trimestres, par conséquent, l'augmentation des coûts de commutation générés par le réseau dans son ensemble sera: (augmentation du total nombre de quartiers + intersections) × (variation de la valeur du débit sur une seule rue) = λ √ λ . Puisque la puissance du flux de migration généré par tous les trimestres a augmenté d'un facteur λ , alors

• le temps de trajet net perdu en raison des coûts de commutation augmente d'un facteur √ λ

Présentons tous les résultats dans un tableau:

Topologie cellulaire

Le nombre de points d'adresse (trimestres) avec la puissance 1 ..................... n
Superficie totale de la route ............................................... .................................... O ( n √ n )
Temps de trajet net,
dépensé pour couvrir la distance ............................................. ................... O (√ n )
Temps de trajet net,
perdu en raison des coûts de changement ............................................. .................... O (√ n )
Nombre de nœuds de commutation .............................................. .................. O ( n )
Nombre de nœuds de commutation, compte tenu de la puissance des flux latéraux .......... O ( n )

En comparant les réseaux linéaires et cellulaires entre eux, il est difficile de ne pas remarquer que l'augmentation de l'intensité des ressources nécessaires à la construction et le temps passé sur un trajet, avec la croissance de la ville, est beaucoup plus rapide pour le premier réseau que pour le second. Par exemple, une ville cellulaire composée de 100 quartiers nécessite 10 fois moins d'asphalte, et le parcourir en moyenne nécessite 10 fois moins de temps qu'une ville linéaire de même taille. Par conséquent, il est logique d'utiliser des réseaux routiers à topologie linéaire uniquement dans les très petites villes.

Si, pendant un certain temps, nous oublions l'existence de coûts de commutation, la topologie cellulaire peut être considérée comme un moyen idéal pour concevoir des réseaux routiers, car elle donne une estimation O asymptotiquement optimale à la fois pour la durée moyenne du trajet et la zone de route requise. En effet, pour tout emplacement plus ou moins «compact» de la ville (avec accès aléatoire), la durée du trajet ne croîtra pas plus lentement que la racine carrée de la zone de la ville, qui est à son tour généralement directement proportionnelle à la population . En conséquence, nous obtenons tout de même O (√ n ).

Le fait qu'un itinéraire typique dans une ville cellulaire longe un «coin» plutôt qu'une ligne droite, implique en principe la possibilité de rechercher les meilleures façons de planifier les villes, mais les économies de 20% (c'est le maximum que nous pouvons gagner si les voitures apprennent à traverser les murs) sont peu susceptibles de forcer un jour les architectes à abandonner la disposition rectangulaire des rues et des routes.

La limite la plus basse possible des coûts de construction (et de maintenance) du réseau peut être obtenue en se rappelant que chaque voiture réserve une partie de la voie pour son déplacement. Par conséquent, la superficie totale des routes est proportionnelle au produit du temps de trajet moyen (durée moyenne du trajet) et du nombre de voitures dans la ville: O (√ n ) × O ( n ) = O ( n √ n ) (comparer avec le tableau pour une ville cellulaire).

Si nous parlons de la quantité de temps perdue en voyage en raison des coûts de commutation, alors, de manière surprenante, sa relation avec la quantité de temps pour couvrir la distance ne dépend pas asymptotiquement du nombre de quartiers dans une ville cellulaire ou linéaire (O (√ n ) / O (√ n ) = O (1), O ( n ) / O ( n ) = O (1)). En d'autres termes, le pourcentage de temps perdu à voyager en raison d'un changement de cap, dans les grandes comme dans les petites villes, sera le même. De cela, nous pouvons conclure que, s'il n'y avait pas de graves problèmes de changement de coûts dans une petite ville (nous pouvons suggérer qu'ils ont gagné à 10-20%), alors dans une grande ville, ils ne devraient toujours pas être observés, et s'ils l'étaient, alors ils continueraient d'exister, peu importe la façon dont la ville s'est développée et agrandie.

Puisque nous ne savons pas laquelle des alternatives est vraie (ou plutôt, nous savons que des problèmes de trafic existent dans les grandes villes), il vaut la peine d'essayer d'améliorer la topologie d'une ville cellulaire afin que les coûts de commutation y diminuent au moins par un facteur de quelques temps constants.

Exemples utiles de réseaux irréalistes

Testons si la topologie cellulaire suit les recommandations que nous avons développées en analysant la commutation des flux sur l'autoroute.

1) N'agrandissez pas les routes sans en avoir besoin.
- Oui. Le trafic est réparti sur de nombreuses routes (comparer avec une ville linéaire).

2) Évitez de concevoir le réseau où le conducteur doit tourner un grand nombre de fois en un seul voyage.
- Oui. Tout voyage sera très probablement effectué le long d'un itinéraire ne nécessitant qu'un seul virage dans les rues.

3) Essayez d'empêcher la fusion d'itinéraires qui ne se chevauchent que dans une courte section de la route.
- Ici, peut-être, il y a quelque chose à travailler. Malgré le nombre minimal de virages par trajet, l'itinéraire faisant partie du flux de la route principale passe par un grand nombre de nœuds de commutation (O ( n )), dans chacun desquels un temps précieux est perdu.

La dernière remarque motive à enquêter sur la question suivante: «Quel est le minimum du nombre moyen de nœuds de commutation par lesquels un trajet doit passer par un réseau routier reliant n quartiers?»

La tâche de recherche d'un tel réseau n'a de sens, bien entendu, qu'à la condition que le nombre de flux combinés ou divisés par un nœud de commutation soit préalablement limité par le haut par une certaine valeur fixe. Sinon, vous pouvez toujours présenter un réseau routier avec n points d'adresse et une seule méga-jonction.


(l'auteur est inconnu)

Il est beaucoup plus facile d'étudier le problème réel s'il était auparavant possible de révéler au moins une partie des modèles à l'aide d'exemples de modèles simples, voire pas du tout réalistes. En suivant cette logique, nous oublierons temporairement les limites géométriques de la construction de routes et la nécessité pour les voyageurs de couvrir des distances, en concentrant toute notre attention sur la façon dont les réseaux abstraits résolvent le problème d'adressage parallèle. En ce qui concerne les nœuds de commutation, nous supposerons pour l'instant que chacun divise le flux en deux parties (le nœud de division) ou combine deux flux en un.


Graphique 9

Arbre d'adresse
Soit un point d'adresse de départ, où tous les déplacements, sans exception, commencent, et un autre n points d'adresse de fin auxquels ils se terminent avec une probabilité égale (graphique 9).

Il est nécessaire de construire un réseau de transport qui permette au conducteur de passer par le moins de nœuds de commutation possible.

La solution évidente (pour les programmeurs), qui se suggère ici, est d'utiliser un arbre binaire équilibré, en même temps, nous devons placer un seul point de départ en haut de l'arborescence et placer les n derniers points d'arrivée un dans chaque de ses feuilles (graphique 10). Le réseau construit de la manière décrite sera appelé comme arbre d'adresse directe.


Graphique 10

En changeant les directions de tous les flux dans l'arborescence d'adresses directe en sens inverse, nous obtenons ainsi l'arborescence d'adresses inverses , dont le but est de connecter n points de départ à un seul point d'arrivée.

Dans les cas où n est une puissance de deux, toute route à l'intérieur de l'arborescence d'adresses passe exactement par les nœuds de commutation log ₂ n , ce qui est sans aucun doute (asymptotiquement) inférieur au même indicateur pour un réseau avec cellulaire (O (√ n )), ou topologie linéaire (O ( n )).

Deux types de réseaux logarithmiques les plus simples

En utilisant des réseaux «arborescents» comme blocs de construction, il n'est pas difficile de généraliser la solution précédente au cas où il y a k points de départ. Il existe deux façons simples de procéder.

La première façon consiste à utiliser l'arborescence d'adresses inverse pour collecter d'abord les itinéraires de tous les trajets dans un flux commun, puis, à l'aide de l'arborescence d'adresses directe, diviser ce flux en sous-flux adressant à sa destination (graphique 11, schéma supérieur )


Graphique 11

Si k et n sont des puissances de deux, alors, finalement, n'importe quelle route passe exactement par les nœuds de commutation log ₂ k + log ₂ n . Nous convenons de faire référence aux réseaux conçus selon l'algorithme qui vient d'être décrit comme des réseaux logarithmiques (unidirectionnels) avec fusion préalable .

La deuxième façon de résoudre le même problème peut être réalisée en inversant dans la première solution l'ordre des opérations de fusion et de division. Son implémentation peut être décrite comme suit: pour chaque point de départ, nous créons un ensemble unique de doublons imaginaires de tous les points d'arrivée, et après cela, nous le connectons à ces doublons (plus imaginaires) avec une arborescence d'adresses directe.

Pour terminer la conception du réseau, il ne reste plus qu'à connecter maintenant chaque point d'arrivée avec ses k doublons imaginaires en appliquant l'arborescence d'adresses inversée (graphique 11, schéma du bas).

Chaque fois que n et k sont des puissances de deux, le nombre de nœuds de commutation le long de n'importe quelle route dans le réseau nouvellement construit sera à nouveau égal à log ₂ k + log ₂ n . Nous convenons de faire référence à ces réseaux comme réseaux logarithmiques (unidirectionnels) avec division préliminaire .

Conversion de réseaux unidirectionnels en réseaux symétriques
Généralement, nous appelons un réseau unidirectionnel si les points d'adresse connectés par lui sont strictement divisés en points de départ et d'arrivée. Par défaut, pour les réseaux unidirectionnels, on supposera qu'il fournit au moins un itinéraire de déplacement possible de n'importe quel point de départ à n'importe quel point d'arrivée.

Outre un voyage de toute une vie, il est difficile de trouver des exemples où certains points d’adresse ne serviraient qu’au début d’un itinéraire et d’autres à sa fin. Nous rapprocherons notre raisonnement de la réalité si nous incluons également des réseaux dans lesquels deux points d'adresse sont connectés par des itinéraires dans les deux sens. Nous convenons de qualifier ces réseaux de symétriques.

En fait, il n'y a pas de fossé idéologique entre les réseaux unidirectionnels et symétriques: chaque réseau symétrique peut également être utilisé comme un réseau unidirectionnel, et chaque réseau unidirectionnel, connectant initialement un nombre égal de points de départ et d'arrivée, peut être transformé en symétrique (graphique 12).


Graphique 12

Les graphiques 13a et 13b montrent les formes «symétriques» du réseau logarithmique avec fusion préliminaire et du réseau logarithmique avec division préliminaire. Leurs exemples prouvent la possibilité fondamentale de connecter n quartiers par un tel type de réseau, au sein duquel le nombre de nœuds de commutation lors d'un déplacement sera proportionnel au logarithme du nombre de quartiers de la ville.


Graphique 13 a


Graphique 13 b

Estimation précise de la limite inférieure

Une grande variété de réseaux a déjà été accumulée jusqu'à présent, chacun comprenant une fonction propre décrivant la dépendance du nombre moyen de nœuds de commutation le long du trajet par rapport au nombre de points d'adresse dans la ville. Néanmoins, nous ne savons toujours pas à quel point ce nombre peut être faible en principe pour un nombre donné de trimestres. L'estimation de la limite inférieure peut être obtenue en utilisant l'approche de l'information.

En fait, laissez un réseau routier relier n points d'adresse les uns aux autres, et les besoins de migration de la population sont tels que tout voyage, peu importe où il a commencé, a une chance égale de se terminer n'importe où dans la ville.

Pour résoudre le problème en question, nous générerons un message d'information auxiliaire, en suivant cette recette: pendant une longue période, nous collecterons les enregistrements de tous les trajets qui ont un point de départ fixe, et noterons au hasard les adresses où ces trajets terminé. Le message résultant sera une séquence aléatoire composée des noms de n points d'adresse de la ville.

Une façon de transmettre ce message à Mars consiste d'une part à coder tous les noms en mots binaires de même longueur, transformant ainsi le message d'origine en une séquence de 0 et de 1, et d'autre part d'envoyer la séquence résultante via un canal de communication numérique. Étant donné que pour un codage distinct de l'ensemble de n noms, des mots binaires de longueur log ₂ n sont nécessaires, la longueur du message numérique sera:

(nombre d'enregistrements) × journal ₂ n caractères.

La chose la plus intéressante est que selon la théorie de l'information, quel que soit l'algorithme de codage utilisé, il est tout simplement impossible de transmettre le même message avec un plus petit nombre de caractères binaires.

Une alternative à la transmission directe des noms codés des points d'arrivée peut être une méthode dans laquelle il est indiqué pour chaque trajet dans quelle direction l'itinéraire a tourné à la prochaine fourche. Selon nos hypothèses, toutes les fourches du réseau ne peuvent avoir que deux branches, par conséquent, pour indiquer la direction dans chaque cas, exactement 1 bit est requis. Pour tous ceux qui ont une carte de la ville et connaissent le point de départ, la chaîne de bits sera suffisante pour tracer chaque itinéraire et restaurer la séquence d'origine de leurs destinations. Si le nombre moyen de fourches (nœuds de division) visités au cours d'un voyage est x , la longueur du message binaire avec la nouvelle méthode de codage sera: (nombre d'enregistrements) × x .

Comme il a été dit précédemment, la nouvelle méthode de codage ne peut pas être plus efficace que la méthode de transfert direct d'adresses binaires, donc: (nombre d'enregistrements) × x ≥ (nombre d'enregistrements) × log ₂ n , c'est pourquoi:

x ≥ log ₂ n .

Bien que la dernière inégalité ait été initialement déduite pour un groupe de déplacements ayant un point de départ fixe commun, elle s'est révélée indépendante du choix spécifique de ce point. C'est pourquoi nous pouvons étendre le résultat à tous les déplacements dans la ville à la fois, obtenant ainsi la première partie du devis en question:

P1 ) À condition que chaque nouveau trajet ait une probabilité égale de se terminer à l'un des n points d'adresse de la ville, le nombre moyen de nœuds de division par itinéraire ne peut pas être inférieur à log ₂ n .

En retournant mentalement l'horloge, nous pouvons convertir chaque point d'arrivée du voyage en point de départ, et chaque nœud binaire de la division du réseau - le nœud binaire de la fusion. Cette petite astuce nous permet d'obtenir automatiquement de P1 la seconde partie manquante de l'estimation:

P2 ) À condition que chaque trajet achevé ait des chances égales de commencer à l'un des n points d'adresse de la ville, le nombre moyen de nœuds de fusion par route ne peut pas être inférieur à log ₂ n .

Si nous rappelons l'existence d'un réseau logarithmique avec fusion préliminaire et d'un réseau logarithmique avec division préliminaire, nous obtenons immédiatement deux exemples de réseaux qui sont optimaux en termes de nombre de nœuds de commutation, qui, en moyenne, sont visités à l'intérieur d'eux pendant un voyage. Voyons si cette qualité permet de réduire l'intensité des pertes de commutation générées.

Coûts de commutation dans les réseaux logarithmiques

Si nous comparons les réseaux avec la fusion préliminaire et la division préliminaire, le premier semble beaucoup plus attrayant en raison de sa simplicité. Malheureusement, cette simplicité a également un revers à la médaille: la combinaison de toutes les routes en un seul flux contredit la recommandation i1 , entraînant ainsi potentiellement de grandes pertes de temps. Le réseau avec division préliminaire semble répondre aux exigences i1 - i3 , cependant, à en juger par le graphique 13b, il tend à augmenter rapidement le nombre de tronçons de route et de nœuds de commutation utilisés. Cette dernière qualité peut rendre les réseaux de ce type trop coûteux pour une utilisation pratique.

Nous analyserons ces questions plus en détail. Pour commencer, nous convenons que la ville suit le modèle de migration avec un «accès aléatoire», et le flux généré par l'un de ses points d'adresse a une puissance 1.

Pertes dans les réseaux avec fusion préliminaire

Dans le graphique 14, vous pouvez voir un diagramme des flux résultant des conditions susmentionnées au sein du réseau avec fusion préliminaire.


Graphique 14

Il m'a semblé commode de décrire le réseau lui-même sous sa forme unidirectionnelle, ce qui implique que chaque point de départ et d'arrivée, signé avec les mêmes numéros dans le graphique, signifie en fait le même point d'adresse dans la ville.

Sur la base du diagramme, nous pouvons calculer l'intensité des coûts de commutation générée dans le réseau. Commençons par la moitié gauche, où à travers l'arborescence d'adresses inversée, toutes les routes sont rassemblées en un seul flux. Chaque nœud de commutation dans cette partie du réseau représente l'endroit où deux autoroutes à sens unique fusionnent en une seule (graphique 15).


Graphique 15

Si au départ chacune des routes est chargée efficacement, puis après leur fusion, il n'est pas nécessaire de réduire le nombre de voies, par conséquent, il ne devrait pas y avoir de frais de commutation respectifs.

Supposons qu'un débit de puissance 1 soit déjà suffisant pour charger efficacement la route sur au moins deux voies. Dans ce cas, nous arriverons à une conclusion plutôt inattendue: la fusion des flux de voitures à l'intérieur du réseau logarithmique avec la fusion préliminaire se produit absolument `` gratuitement '', sans causer de perte de temps.

Le calcul des coûts qui surviennent dans la moitié droite n'est pas beaucoup plus difficile. Cette partie du réseau est un arbre d'adresse directe, dont chaque nœud est une fourche symétrique que nous avons déjà étudiée. Lorsque le flux entrant avec la puissance p , l'intensité des pertes survenant à la fourche est ( α / 2 ν ) ⋅ p 2/2 . La puissance du flux entrant dans la fourche racinaire est: n , par conséquent, l'intensité des pertes dans le nœud racinaire est: ( α / 2 ν ) ⋅ n 2/2 . Dans chaque génération suivante de l'arborescence d'adresses, le nombre de fourches double et la puissance du flux entrant est divisée par deux. En conséquence, la formule des pertes à l'intérieur de l'arbre entier prendra la forme:

I _{t_div1} = ( α / 2 ν ) ⋅ (1/2) ⋅ [ n ² + 2 ( n / 2) ² + 4 ( n / 4) ² + ... + ( n / 2) ⋅ 2 ² ] =

( α / 2 ν ) ⋅ ( n / 2) ² [1 + 1/2 + 1/4 + ... + 2 / n ] ≈ ( α / 2 ν ) ⋅ n ²

Étant donné que la puissance du flux de déplacements généré conjointement par tous les points d'adresse est n , les coûts de temps par déplacement sont en moyenne ( α / 2 ν ) ⋅ n , montrant ainsi une dépendance linéaire de la taille de la ville.

En ce qui concerne les réseaux abstraits, il est difficile de donner une estimation significative de la superficie des routes qu'ils utilisent. Comme mesure alternative de la complexité structurelle, la puissance totale de tous les flux latéraux peut être calculée. Comme prévu, la valeur résultante devrait refléter l'intensité des ressources de la construction de tous les échangeurs requis par le réseau. Je ne peux pas dire que dans la pratique, cette méthode aura toujours une bonne interprétation, mais une idée approximative de la quantité de travail à venir sera probablement obtenue.

À l'intérieur du réseau logarithmique avec fusion préliminaire, les flux latéraux n'existent que dans l'arbre d'adresse directe, et leur puissance totale pour chaque génération de nœuds est la même: n / 2. Au total, il y a log ₂ n de générations de nœuds dans l'arbre, donc une nouvelle méthode pour évaluer la complexité donne une estimation de la complexité: O ( n log ₂ n ).

Réseaux logarithmiques avec fusion préliminaire

Le nombre de points d'adresse avec puissance 1 .......................................... .......... n
Temps de trajet moyen
perdu en raison des coûts de commutation:
asymptotique ................................................. .................................................. ... O ( n )
valeur exacte ................................................ .................................................. ..... ( α / 2 ν ) ⋅ n
Nombre de nœuds de commutation .............................................. ................................ O ( n )
Nombre de nœuds de commutation, compte tenu de la puissance des flux latéraux ........................ O ( n log ₂ n )

Pertes dans les réseaux avec division préliminaire

Nous passons maintenant à l'analyse du réseau logarithmique avec division préliminaire, en supposant à nouveau que le réseau est utilisé pour connecter les points d'adresse de puissance 1 dans la ville à «accès aléatoire».
Le graphique 16 en montre un fragment composé d'un point d'adresse avec les arbres d'adresse directe et inverse adjacents à ce point.


Graphique 16

Tout d'abord, nous pouvons estimer l'intensité des pertes de commutation générées par le fragment.
Les coûts encourus lors de la division des flux peuvent être trouvés par l'équation suivante I _{t_div1} = ( α / 2 ν ) ⋅ n ² , qui a été déduite pour l'arbre d'adresse directe dans l'exemple précédent, 1 au lieu de n . En effet, les arbres d'adresse directe des graphiques 16 et 14 ont la même profondeur et impliquent des flux similaires en puissance (remarque: la similitude signifie la possibilité d'obtenir un ensemble de valeurs en multipliant les valeurs d'un autre ensemble par un certain nombre fixe , pour illustrer la similitude entre les triangles par leurs côtés). En raison de la relation quadratique entre la valeur des coûts de commutation qui se produisent à une seule fourche et la puissance de son flux entrant, une diminution simultanée de tous les flux de n fois réduira les pertes dans l'ensemble de l'arbre de n ² fois, par conséquent, à la place de l'ancien ( α / 2 ν ) ⋅ n ² , on obtient une valeur égale à:

I _{t_div2} = ( α / 2 ν ).

Nous pouvons maintenant calculer la valeur des coûts dans la moitié gauche du fragment.
En raison de la faible valeur des flux combinés de la route à l'intérieur de l'arbre d'adresse inverse, cette fois, il ne serait pas raisonnable de construire une route plus large que deux voies. La fusion dans de telles conditions n'est plus gratuite: contrairement à l'exemple précédent, il y a des zones de rétrécissement sur l'autoroute (graphique 17), où des coûts de changement de cap seront nécessairement nécessaires.


fig. 17

En supposant que le conducteur soit au courant du rétrécissement à venir, nous pouvons supposer que le processus de changement de la voie sans issue est lent, s'étendant sur des centaines de mètres le long de l'autoroute. Dans ce cas, nous avons le droit de recourir à l'astuce que nous avons utilisée plus tôt pour calculer les pertes à la fourche symétrique - pour diviser le flux de migration total q en plusieurs petites parties q _i , puis interpréter chacune d'elles comme un flux latéral à partir de la rampe. Les pertes générées par chacun de ces sous-flux sont calculées par la formule:

I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ), cependant, il y a deux subtilités ici.

La première est que les voitures ne migreront pas plus loin que la rangée suivante.
En fait: les flux dans les deux voies centrales, en raison d'une symétrie évidente, devraient toujours avoir approximativement la même densité, de sorte que les conducteurs n'auront pas beaucoup de raisons de traverser la ligne médiane. De l'observation faite, on peut déduire que dans la formule pour les pertes causées par un écoulement latéral partiel, s est égal à 1.

Au fur et à mesure que les voitures quittent les voies de bord, passant à deux voies centrales, la puissance de flux à l'intérieur des voies centrales augmente progressivement, changeant dans chaque cas de P / 2 à P. Ainsi, la deuxième subtilité est la dépendance significative de p sur le nombre de sous-flux i , ce qui nous fait écrire:

pas
I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ),
mais:
I _i = ( α / 2 ν ) p ( i ) ⋅ q _i ⋅ (1 + 1 / s ).

Dans le cas où de nombreuses petites pièces, dans lesquelles le flux de migration a été divisé, étaient toutes de taille égale, la dépendance p ( i ) est exprimée par un graphique linéaire (graphique 18)


Graphique 18

Pour calculer le taux d'intensité de perte, il faut soit recourir à l'intégration, soit (ce qui permet de faire une forme particulièrement simple d'une fonction intégrable) prendre comme p ( i ) la valeur moyenne sur le graphique égale à 3 P / 4. Étant donné que le flux de migration total du côté de chaque voie de bordure est P / 2, l'intensité des pertes dans un nœud de fusion distinct sera:

Je _fusionne = 2 ⋅ ( α / 2 ν ) ⋅ (3 P / 4) ⋅ ( P / 2) =

= ( α / 2 ν ) 3 P 2/4.

Pour trouver les pertes de temps générées à l'intérieur d'un fragment sur l'arbre d'adresse inverse, nous pouvons appliquer la formule de _fusion à chacun de ses nœuds:

I _{t_merge} = (3/4) ⋅ ( α / 2 ν ) [1 ⋅ (1/2) ² + 2 ⋅ (1/4) ² + 4 ⋅ (1/8) ² + ... + ( n / 2) ⋅ (1 / n ) ² ] ≈

≈ (3/4) ⋅ ( α / 2 ν ) [1/4 + 1/8 + 1/16 + ...] =

= (3/8) ⋅ ( α / 2 ν ) [1/2 + 1/4 + 1/8 + ...] =

= (3/8) ⋅ ( α / 2 ν ).

Les coûts totaux résultant de la fusion et de la répartition des flux au sein du fragment seront:

I _{t_merge} + I _{t_div2} = ( α / 2 ν ) [1 + 3/8] = 11/8 ( α / 2 ν ).

Un réseau logarithmique avec division préliminaire ne contient que n de tels fragments, et exactement n flux de puissance 1 sont générés par ses points d'adresse, de sorte que la valeur que nous venons de trouver est exactement égale aux pertes de commutation par trajet moyen.

En fait, il est plus important pour nous même pas un nombre spécifique, qui est égal aux coûts de commutation spécifiques, mais le fait que ces coûts restent constants avec l'augmentation de n . Ce dernier rend le réseau logarithmique à division préliminaire asymptotiquement le plus économique en ce qui concerne les pertes de commutation parmi tous les types de réseaux que nous avons étudiés précédemment.

Malheureusement, le leadership n'est pas gratuit. Malgré la valeur infiniment petite du nombre écrasant de flux, chaque arbre d'adresses inclus dans le réseau contient environ 2 n tronçons de route à deux voies et environ n nœuds de commutation de taille normale. Il y a 2 n arbres dans le réseau, ce qui signifie O ( n ² ) membres et nœuds, ce qui en fait non seulement le plus économique en termes de gain de temps, mais aussi le réseau le plus cher à construire, parmi tous les exemples considérés.

Quant à la somme des débits latéraux, sa valeur, facilement calculable, croît avec la vitesse O ( n log2 n ) et dans ce cas n'a pas beaucoup de sens.

Réseaux logarithmiques avec division préliminaire

Le nombre de points d'adresse avec puissance 1 .......................................... ............ n
Temps de trajet moyen
perdu en raison des coûts de commutation:
asymptotique ................................................. .................................................. ...... O (1)
valeur exacte ................................................ .................................................. ........ 11/8 ( α / 2 ν ).
Nombre de nœuds de commutation .............................................. ................................... O ( n ² )
Nombre de nœuds de commutation, compte tenu de la puissance des flux latéraux ........................... O ( n log ₂ n )

Réseau logarithmique équilibré

Des pertes de commutation exceptionnellement faibles et en même temps une consommation considérable de ressources de la construction du réseau, résultant de l'application d'un réseau logarithmique avec division préliminaire, nous donnent envie de trouver un moyen de modifier sa conception afin que la consommation de ressources soit considérablement réduite alors que le les coûts de changement n'augmenteraient pas considérablement.

De toute évidence, le principal coupable d'un nombre excessivement élevé de routes du réseau est la très faible efficacité de leur utilisation. Ce dernier est clairement visible dans le graphique 19, qui montre un diagramme détaillé des flux à l'intérieur d'un arbre d'adresse directe adjacent au ième point d'adresse.


Graphique 19

Dans le graphique, le nombre au-dessus du membre de l'arbre indique la puissance du flux passant le long du membre, et la plage ci-dessous est l'ensemble des points d'adresse entre lesquels ce flux sera finalement distribué. Nous supposons que tous les membres présentés dans le tableau sont des autoroutes à deux voies, le nombre de membres dans chaque génération de l'arbre est indiqué au bas de la figure.

Après un examen attentif, vous remarquerez peut-être que la règle selon laquelle le flux est divisé en un nœud particulier est déterminée uniquement par la position de ce nœud dans l'arborescence d'adresses et ne dépend pas du numéro du point d'adresse qui a donné le début de ces déplacements. .

S'il y a plusieurs flux adressés au même ensemble de points, et que chacun des flux n'est pas assez puissant pour remplir le chemin qui lui est attribué, alors pourquoi ne les combinons-nous pas en une seule autoroute. En fait, cette idée essentiellement simple permet de construire un bon réseau abstrait qui génère des pertes de commutation relativement faibles et est économique en termes de nombre de routes utilisées.

En revenant à l'arbre d'adresses du i-ème point, on voit que le flux entrant dans le nœud racine est divisé en deux flux fils d'une capacité de 1/2 chacun. Le premier flux de fils est constitué de déclenchements adressés à des points de la plage [1; n / 2], le second consiste en des déplacements adressés à des points de la plage [( n / 2) + 1; n ].

En suivant l'idée exposée ci-dessus, nous combinons les flux de fils du même type à chaque point impair et le point d'adresse qui le suit dans l'ordre avec un nombre pair. Cette technique nous permet pour chaque paire de points sélectionnée d'avoir, au lieu de quatre flux de puissance 1/2, seulement deux flux de puissance 1 (graphique 20). Nous nommerons le fragment obtenu du futur réseau BN ₂ [i; i +1].


Graphique 20

Si les flux de fils n'étaient pas combinés, mais étaient toujours à l'intérieur de l'arborescence d'adresses, puis dans la prochaine génération de nœuds, chacun d'entre eux serait à nouveau divisé en deux parties, égales en puissance et en taille des ensembles des points d'adresse à vers quoi se dirigent les voyages.

Pourquoi briser la tradition établie, car après le processus de combinaison, nous avons toujours le même ensemble de types de flux qu'auparavant, mais avec seulement moins de représentants de chaque type. À chacun des flux de sortie de BN ₂ [i; i +1], nous pouvons appliquer exactement la même règle de division que celle qui s'appliquerait à un flux de son type à l'intérieur de l'arborescence d'adresses.

Il n'y a aucune raison de ne pas répéter de manière inductive la construction logique décrite ci-dessus pour combiner-fractionner les mêmes flux. Le graphique 21 montre un schéma pour combiner deux fragments
BN ₂ en un fragment de BN ₄ , d'autre part, le graphique 22 montre le même algorithme dans le cas général.


Graphique 21


Graphique 22

Au final, le processus d'agrandissement des fragments sera achevé et nous conduira au seul élément BN _n [1; n ]. Nous l'appellerons le réseau logarithmique équilibré (graphique 23).


Graphique 23

Examinons ce réseau pour la complexité et la valeur des pertes de commutation générées.
En fonction de la nature inductive de la conception d'un réseau équilibré, le nombre de nœuds de commutation inclus dans sa structure peut être décrit par l'équation récurrente:

nœuds (BN _k ) = 2 nœuds (BN _{k / 2} ) + 2 k ,

avec la limitation suivante:

nœuds (BN ₁ ) = 0.

La solution à ce système d'équations est la fonction:

nœuds (BN _n ) = 2 n log ₂ n .

Étant donné que la conception de BN _n nécessite des étapes d'induction de log ₂ n , chaque trajet passera par des nœuds de division log ₂ n et le même nombre de nœuds de fusion, en alternant entre eux sur son chemin (graphique 24).


Graphique 24

Pertes générées au sein de chaque nœud de division:
( α / 2 ν ) ⋅ (1) 2/2 .

Pertes générées au sein de chaque nœud de fusion:
( α / 2 ν ) ⋅ 3 ⋅ (1/2) 2/4 = 3/16 ( α / 2 ν ).

En considérant que le nombre des deux dans le réseau équilibré est n log ₂ n , nous pouvons obtenir la valeur exacte des pertes de commutation totales:
11/16 ( α / 2 ν ) n log ₂ n ,

qui par voyage est:
11/16 ( α / 2 ν ) log ₂ n

Réseau logarithmique équilibré

Le nombre de points d'adresse avec puissance 1 .......................................... .......... n
Temps de trajet moyen
perdu en raison des coûts de commutation:
asymptotique ................................................. .................................................. ... O (log ₂ n )
valeur exacte ................................................ .................................................. .... 11/16 ( α / 2 ν ) log ₂ n
Nombre de nœuds de commutation .............................................. ............................... O ( n log ₂ n )
Nombre de nœuds de commutation, compte tenu de la puissance des flux latéraux ....................... O ( n log ₂ n )

Les chiffres obtenus ci-dessus nous permettent de considérer le Réseau équilibré comme un bon compromis entre la quantité de pertes de temps introduites et la complexité structurelle globale. Son utilisation comme réseau routier d'une ville réelle est en principe possible, mais difficilement économiquement réalisable. Il me semble que le domaine dans lequel l'utilisation du réseau équilibré peut réellement être très avantageux est celui des systèmes d'information à grande échelle avec des exigences strictes concernant la quantité de retard du signal, comme les communications cellulaires, Internet, l'informatique distribuée et les ordinateurs multiprocesseurs. . Pour nous, la plus grande valeur du Réseau équilibré est la méthode par laquelle il a été conçu. Un peu plus tard, en utilisant une modification de cette méthode, nous pourrons améliorer les réseaux de villes linéaires et cellulaires qui sont vraiment cruciaux en termes pratiques.

Pourquoi les villes historiques sont condamnées aux embouteillages

Ma déclaration peut sembler inattendue, mais la réponse à la question de savoir pourquoi les villes en développement naturel, souffrent généralement d’embouteillages, a déjà été trouvée par nous dans les paragraphes précédents. Quelle en est donc l'essence?

Le fait est que de nombreuses villes historiques qui ont survécu après l'ère des forteresses médiévales (par exemple, presque toutes les capitales du «Vieux Monde») ont hérité de cette époque de la structure radiale des rues. Malheureusement (pour leurs habitants modernes), un réseau routier de topologie similaire n'est pas très évolutif: l'agencement dense des routes radiales à proximité du centre devient trop rare en périphérie. En conséquence, dans le processus de croissance démographique, les rues qui étaient initialement situées en marge des quelques routes menant à la forteresse sont devenues plus grandes et les rues qui sont apparues à la périphérie étaient courtes et n'ont pas acquis une importance de transport en commun suffisante pour croître. ampleur. En conséquence, le réseau routier que nous voyons maintenant dans les grandes villes historiques se réfère le plus souvent à des systèmes de transport de type artériel, et dans notre terminologie,aux réseaux logarithmiques avec fusion préliminaire (incomplète).


(Routes de Moscou, photo: Slava Stepanov)

Si nous parlons de la longueur des routes qu'un conducteur doit emprunter, la mise en place de ce type de réseau n'est pas mauvaise: la distance parcourue diffère souvent peu de la distance en ligne droite, et son la valeur moyenne dans la ville, comme elle devrait l'être pour les systèmes de transport «décents», croît à un taux de O (√ n ). Le problème est qu'avec l'élargissement de la ville au réseau logarithmique avec fusion préliminaire, les coûts de commutation générés par celui-ci augmentent trop rapidement: la durée pour laquelle, en moyenne, le voyage est prolongé à cause d'eux, dépend du nombre des personnes vivant dans la ville comme O ( n ). Il est clair qu'à partir de certains n, ce temps l'emportera sur le temps net pour vaincre la distance, en d'autres termes, des embouteillages apparaîtront dans la ville.

Il ne fait aucun doute que la réorganisation du système de transport dans les grandes villes historiques est une tâche qui peut être résolue. Cependant, il est important de comprendre que la construction d'une autre, deux ou cinq grandes artères de transport, bien qu'améliorant légèrement la situation dans la ville, mais n'éliminera pas la cause profonde des embouteillages. Apparemment, la seule façon de surmonter les inconvénients du réseau logarithmique avec une fusion préliminaire est d'utiliser un autre réseau. Un bon candidat ici peut être un réseau à topologie cellulaire, dans lequel le temps nécessaire pour couvrir la distance augmente, au moins, au même rythme que les pertes de commutation augmentent.


(nuit Berlin, photo: Vincent Laforet)

C'est peut-être la raison pour laquelle le Berlin moderne, bien que doté de grandes autoroutes artérielles, se distingue déjà par une structure cellulaire clairement visible.

Il existe de nombreuses solutions intéressantes dans le monde pour rendre les habitants des villes historiques plus mobiles, mais le prix principal de la lutte pour l'accessibilité des transports devrait probablement être attribué aux ingénieurs de Barcelone.


(Réseau routier modernisé de Barcelone, photo: Vincent Laforet)

Zoom sur les réseaux de villes linéaires et cellulaires

After the methods of analysis were found and honed on abstract networks, now it is time to apply them to more realistic cases of cities with Linear and Cellular topology. In this section we will try to analyse in all details the features of their transport networks, establish the numerical value of the switching losses intensity rate, find how its value depends on the size of the quarters, and discuss possible variations and improvements.

Linear city
This time, we will consider an example of a city in which there are two one-way highways: Western highway with a traffic towards the north and Eastern highway with a traffic towards the south (Chart 25).


Chart 25

Let each quarter generate a flow with power 1. In this case, the power of one route heading from one quarter to another one amounts to 1/ n .

To begin with, we will define the power of side flows in the highways. Western highway is the only way to get to the quarter i from the quarter ( n − i ) located southwards, and the only way to get from the quarter i is to the quarter ( i − 1) located northwards. It means that the power of traffic exchange flows between Western highway and the quarter i are:

q _{W_out} = ( n − i )/ n — the power of the side flow leaving Western highway,
q _{W_in} = ( i − 1)/ n — the power of the incoming side flow.

It is clear that the power of side flows in Eastern highway depends on i in a symmetrical way:
q _{E_out} = ( i − 1)/ n — the power of the side flow leaving Eastern highway,
q _{E_in} = ( n − i )/ n — the power of the incoming side flow.

Of course, the sum of the flows leaving the i -th quarter:
q _{E_in} + q _{W_in} = ( n − 1)/ n ,

coincides with the sum of the flows entering it:
q _{E_out} + q _{E_out} = ( n − 1)/ n ,

and both of these values ​​do not depend on i (each quarter has a flow with power 1/ n , this flow consists of trips which begin and finish within the given quarter).

To calculate the power of the main flows, we will draw an imaginary line across the Western highway on the same level with the i -th quarter. In total, this line will cross:
(the number of quarters southwards) × (the number of quarters northwards) = ( n − i )( i − 1) of routes that together create a flow with the power:

P _W ( i ) = ( n − i )( i − 1)/ n .

The same formula:
(number of quarters southwards) × (number of quarters northwards)/ n ,
should express the power of the traffic flow in the Eastern highway P _E , in other words:

P _E ( i ) = P _W ( i ) = P ( i ).

Connaissant la puissance de tous les flux principaux et secondaires, nous pouvons calculer le taux d'intensité des pertes qui se produisent dans le réseau dans la zone proche du i- ème trimestre:

I ( i ) = ( α / 2 ν ) ⋅ P ( i ) ⋅ [( q _{E_in} + q _{W_in} ) ⋅ (1 + 1 / s ) + ( q _{E_out} + q _{E_out} ) ⋅ (1 - 1 / s )] =
= ( α / 2 ν ) ⋅ P ( i ) ⋅ [ (1 − 1/ n ) ⋅ (1 + 1/ s ) + (1 − 1/ n ) ⋅ (1 − 1/ s ) ] =
= ( α /2 ν ) ⋅ 2 P ( i ) ⋅ (1 − 1/ n ) =
= 2( α /2 ν ) ⋅ (1 − 1/ n ) ⋅ ( n − i )( i − 1)/ n =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n - i ) ⋅ ( i - 1) ⋅ (1 / n ).

Si nous résumons la dernière expression à travers i , nous obtiendrons le taux d'intensité des pertes généré par l'ensemble du réseau dans son ensemble.

I = ∑ _i I ( i )
= ∑ _i 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ ( n- i ) ⋅ ( i - 1) ⋅ (1 / n ) =
= 2 ( α / 2 ν ) ⋅ (1 - 1 / n ) ⋅ n ² ⋅ ∑ _i (1 - i / n ) ⋅ ( i / n - 1 / n ) ⋅ (1 / n ) ≈
≈ 2 ( α / 2 ν ) ⋅ n ² ⋅ ∑ _i (i / n ) ⋅ (1 − i / n ) ⋅ (1/ n ).

The sum ∑ _i ( i / n ) ⋅ (1 − i / n ) ⋅ (1/ n ) for any large n can be replaced with good accuracy by the integral:

∫ t (1 − t ) d t ( t ∈[0; 1] ) = 1/2 − 1/3 = 1/6.

Based on this, we can obtain that the intensity of switching losses in a Linear city with n quarters with power 1 amounts to:

I = ( α /2 ν ) n ² /3.

Up to this point, we considered only examples in which quarters always generated flows with power 1. Let's consider if the formula for switching losses of a Linear city will change if for each quarter there is not one source of flow with power 1, but — λ (the quarters will become λ times larger).

Let us take a city with m quarters. If quarters generated flows with power 1, then the switching losses would be ( α /2 ν ) m ² /3.

An increase in trip production power by every quarter by a factor of λ leads to an increase in both the main and side flows by a factor of λ . As a result, the costs at each junction, and therefore inside the network as a whole, increase by a factor of λ ² times, and the losses formula transforms into:

I = ( α /2 ν ) m ² ⋅ λ ² /3.

To a large extent, it doesn't matter how the switching losses depend on the number of quarters in the city, the main thing for us is how they depend on the flow power of all the trips generated inside it, or in other words, on the number n of sources with power 1. In this case, n is equal to m ⋅ λ , therefore:

I = ( α /2 ν ) m ² ⋅ λ ² /3 =
= ( α /2 ν ) ( m ⋅ λ ) ² /3 =
= ( α /2 ν ) n ² /3.

In other words, switching losses in a Linear city do not depend on how small the fragmentation of its territory into quarters is chosen.

Cellular city

Imaginez une ville cellulaire dans laquelle les autoroutes des rues perpendiculaires sont attribuées à différents niveaux / hauteurs. Cela serait possible, par exemple, si toutes les autoroutes allant du nord au sud étaient surélevées sur des ponts et que des autoroutes s'étendant d'ouest en est étaient construites à la surface de la terre. Si, en outre, toutes les autoroutes ont un trafic à double sens, le réseau routier d'une telle ville sera référé à la topologie cellulaire standard (graphique 26).

The point here, of course, is not to bring the network described above seriously into practice: it would not look too aesthetically pleasing against the background of the city landscape and, moreover, due to the need for multi-level interchanges, it would eat up the better half of the street space. Nevertheless, this purely hypothetical network is a good way to get the necessary estimates, which later can be easily extended to road networks that are really interesting from the point of view of their applicability in real cities.

As usual, we will assume that the migration needs of residents are described by the 'random access' model, and we will start our consideration with the case when the power of all the flows generated by a given quarter is 1.

In the example of the standard Cellular city, it is convenient to step aside from the established tradition and consider as the address point not a separate quarter, but a territorial zone of a square shape within the intersection of highways and 1/4s of all quarters adjacent to it. Chart 27 shows the relative positioning of several such zones and shows a traffic pattern inside one of them. This chart clearly demonstrates that any driver, leaving the quarter, has the opportunity to enter in the highway, moving in the direction of any of the four sides of the world.


Graphique 26

Pour calculer la valeur des coûts de commutation générés par la ville, nous calculerons la puissance de tous les flux principaux et secondaires dans chacune de ses zones territoriales. La forme et le positionnement mutuel des zones nous permettent de recourir à une analogie d'échecs pour résoudre le problème en question, en considérant les zones comme des cellules de terrain et le mouvement des voitures entre elles - comme des mouvements de la tour (graphique 27). Dans un cas général, la tour peut être déplacée d'une cellule à l'autre en deux mouvements; si les deux cellules sont sur la même ligne horizontale ou verticale, alors - d'un seul coup.


Graphique 27

Afin d'éviter de nombreuses réservations gênantes, nous supposons que le déplacement dans lequel la tour ne se déplace nulle part est également autorisé selon nos règles. L'itinéraire de déplacement de la tour, composé de deux mouvements, dont l'un est nécessairement exécuté verticalement, et l'autre - horizontalement, sera appelé le plus simple. Il est raisonnable de considérer le mouvement «à l'arrêt» comme vertical et horizontal à la fois. Dans ce cas, il s'avère vrai que deux cellules de la carte sont connectées l'une à l'autre par exactement deux voies différentes les plus simples.

For drivers, the simplest route is the easiest way to get, with minimal interference, from one territorial zone to another, so it's reasonable to assume that real trips will take place along elementary route lines. According to the 'random access' model, the flow with power 1 generated by the address point (territorial zone) should be equally distributed between all n = d ² address points of the city. Therefore, the power of the flow passing along one route line is 1/(2 n ).

We can calculate the flow with what power passes through the cell ( i , j ) in the direction from the south to the north. The simplest route crosses cell ( i , j ) from the south to the north in only two situations. The first of them (Chart 28 on the left):

1a) the start cell of the route is located in one of the last ( d − i ) horizontal lines (rows);
2a) the finish point of the route is one of the first ( i − 1) cells of the j -th vertical line (column);
3a) the route starts with a horizontal section, or lies entirely inside the j -th column.


Chart 28

The conditions describing the second situation look symmetrical (Chart 28 on the right):

1a) the start point of the route is one of the last ( d − i ) cells of the j -th vertical line;
2a) the finish cell of the route is located in one of the first ( i − 1) horizontal lines;
3a) the route starts with a vertical section, or lies entirely inside the j -th column.

On the chessboard there is only 2× [ d ⋅ ( i − 1) + 1⋅ ( i − 1) ] × ( d − i) les itinéraires les plus simples adaptés aux exigences, qui créent ensemble un flux avec la puissance:

P _SN ( i , j ) = ( d + 1) ⋅ ( i - 1) ⋅ ( d - i ) / n (= P _SN ( i )).

En fixant j , on obtiendra la fonction

( P _SN ) _j ( i ) = P _SN ( i , j = Const),

décrivant la dépendance de la puissance de l'écoulement se déplaçant vers le nord le long de la j- ème autoroute verticale sur la distance jusqu'à la limite supérieure de la ville, mesurée en cellules.
Il y a plusieurs observations plus ou moins évidentes concernant les fonctions ( P _SN ) _j ( i ), discutons-en.

Commençons par une circonstance difficile à ignorer: P _SN ( i , j ) pratiquement indépendant sur le second argument. En conséquence, les fonctions ( P _SN ) _j ( i ) = P _SN (i ) have the same form for all values ​​of j , in other words, the specific position of the highway inside the Cellular city does not affect its load. Formally, the last statement is proved only for the highway heading to the north, but due to the symmetries of the city it automatically applies to the highway of other directions too.

Now let us look at the formula for P _SN ( i ) itself:

( d + 1) ⋅ ( i − 1) ⋅ ( d − i ) /(2 n ).

As we see, the whole dependence of P _SN i sur i réside dans l'expression ( i - 1) ⋅ ( d - i ). Cette expression peut être interprétée comme le produit des longueurs des tronçons droit et gauche dans lesquels la section entière de longueur d se divise après que le i-ème élément en soit exclu (graphique 29a).


Graphique 29a


Graphique 29b

Il est clair que si vous changez «droite» en «gauche» et «gauche» en «droite» (graphique 29b), le résultat du produit restera le même. Sur la base d'une observation aussi simple, nous pouvons tirer deux inférences qui, en substance, nous sont très utiles:

1. the function P _SN ( i ) is symmetric with respect to the midpoint of the street i = (d + 1)/2, in order words, the flow power at a distance Δ from the lower boundary of the city is exactly the same as at a distance from the lower boundary of the city is exactly the same as at a distance Δ from the upper boundary.
2. On the whole, the city itself is symmetrical up and down, therefore, to get the function ( P _NS ) _j ( i ), which describes the power flow on the j -th highway, but in a southward direction, it's enough to simply mirror the function graph ( P _SN ) _j ( i ) in the line i = ( d + 1)/2. Since ( P _SN ) _j ( i ) = P _SN ( i ), and the graph P _SN ( i ) with respect to the line i = ( d + 1)/2 is symmetric, then ( P _NS ) _j ( i ) = P _SN ( i ) = P _vert ( i ),, in other words,
3. direct and oncoming traffic flows have equal power at any point of the city. A closer graph of P _SN ( i )is shown in Chart 30 (it is believed that d >> 1, i >> 1, d − i >> 1).

Graphique 30

Les puissances des principaux flux le long des autoroutes horizontales sont faciles à trouver en utilisant des symétries de rotation; formellement, ce processus peut être mis en œuvre par un simple remplacement de i par j dans P _SN ( i ) et une petite correction de l'indice inférieur.

La prochaine étape à franchir est de trouver la puissance des flux latéraux. Les trajets qui entrent ou sortent de la circulation sur une autoroute verticale à l'intérieur de la cellule ( i , j ) peuvent être commodément divisés en quatre catégories:

1. the flow q _{in_transit} : start point is in any cell of the i -th horizontal, finish point is in any cell of the j -th vertical, except for the ( i , j ) itself (Chart 31a);
2. the flow q _{out_transit} : start point is in any cell of the the j -th vertical, except for the ( i , j ) itself, finish point is in any cell of the i -th horizontal (Chart 31b);
3. the flow q _in : start point is the ( i , j ) itself, finish one is any cell outside the i -th horizontal (Chart 31c);
4. the flow q _out : start point is in any cell outside the i -th horizontal, finish point is the ( i , j ) itself (Chart 31d);

Chart 32: abcd

Having recounted the number of route lines belonging to each separate category, we can conclude that the powers of all four flows are the same and equal:

q ₀ = d ⋅ ( d − 1) /(2 n )

Having the values ​​of the powers of the main and side flows in a vertical highway, it is not difficult to calculate the value of the respective switching costs. Inside a single cell ( i , j ) the switching costs will be equal to:

I _vert ( i , j ) = ( α /2 ν ) ⋅ P _vert ( i ) ⋅ [( q _in + q _{in_transit} ) ⋅ (1 + 1 / s ) + ( q _out + q _{out_transit} ) ⋅ (1 - 1 / s )]
= 4 ( α / 2 ν ) ⋅ ( d + 1) ( i - 1) ( d - i ) ⋅ d ( d - 1) / 2 n ² ≈
≈ 2 ( α / 2ν ) ⋅ d ⁵ ⋅ ( i / d )(1 − i / d ) ⋅ (1/ d ) ⁴ =
= 2 ( α /2 ν ) ⋅ d ² ⋅ ( i / d )(1 − i / d ) ⋅ (1/ d ).

To find the costs incurred in all the vertical streets within the whole city, we need to sum I _vert ( i , j ) for both indices:

I _vert = ∑ _ij I _vert ( i , j ) =
= 2 ( α /2 ν ) ⋅ d ² ⋅ ∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ).

Since the value of the summands does not depend on j in any way, summing over the second index is equivalent to multiplying by d :

∑ _ij ( i / d )(1 − i / d ) ⋅ (1/ d ) = d ⋅ ∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ).

The last amount can be approximated by the integral that we already know:

∑ _i ( i / d )(1 − i / d ) ⋅ (1/ d ) ≈ ∫ t (1 − t ) d t ( t ∈[0; 1] ) = 1/2 − 1/3 = 1/6.

Based on this, we can obtain:

I _vert = ( α /2 ν ) ⋅ d ³ /3 = ( α /2 ν ) ⋅ n √ n /3.

We can answer the question what is the value of costs I _horiz , arising in the horizontal highways, using the symmetry of the city:

I _horiz = I _vert = ( α /2 ν ) ⋅ n √ n /3.

Therefore, the switching losses intensity rate within the entire network of the Standard Cellular city is equal to:

I = I _vert + I _horiz = 2/3 ⋅ ( α /2 ν ) ⋅ n √ n ,

and per trip, on average, the switching costs will be

2/3 ⋅ ( α /2 ν ) ⋅ √ n

The effect of cell size on the value of switching losses

Quarters generating flows with power 1 are a rather artificial limitation of the conditions of the problem. We can extend the results obtained above to the cases when the power of the flow generated by one cell is equal to λ .
Let the city consist of m such cells. If all cells were power 1, then the intensity of the total switching losses would be I ₁ = 2/3 ⋅ ( α /2 ν ) ⋅ m √ m . An increase in the number of trips by a factor of λ will multiply by λ times the powers of all the main and side flows in the highways, which in turn will cause the increase by a factor of λ ² in all the switching costs generated within the city. The new formula for the losses intensity rate will thus take the form:

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m

If we assume that the cell consists of λ address points with power 1, then the total number of such points will be: n = λm . Let's express I as a function of n and λ :

I = 2/3 ⋅ ( α /2 ν ) λ ² ⋅ m √ m =
= 2/3 ⋅ ( α /2 ν ) ⋅ √ λ ⋅ ( λ √ λ ) ⋅ ( m √ m ) =
= 2/3 ⋅ √ λ ( α /2 ν ) ⋅ ( λ m )√( λ m ) =
= 2/3 ⋅ √ λ ( α /2 ν ) ⋅ n √ n .

The average cost per trip under the new conditions will be 2/3 ⋅ √ λ ( α /2 ν ) ⋅ √ n , being √ λ higher than their value in a city made up of quarters with power 1.

The last formula tells us that for the same population, population density and total area of ​​all roads, the larger the size of the quarters chosen by its architect, the higher the switching costs. In the case when the city's population is unevenly distributed over its territory, of course, we need to pay attention not to geometric dimensions, but first of all to the average number of people inside the quarter and their migration activity.


(New York City Center photo: Vincent Laforet)

The remark made above is especially important when designing areas with skyscraper buildings. Due to the combination of high population density and its high mobility, it is crucial to design quarters in high-rise areas several times smaller in size than is usual for standard buildings. In civilizations, where skyscraper construction has a long history, the practice of isolating even separate large buildings as a quarter is widespread.

A cellular city with traffic light regulations
In each case, when the lines of two busy highways intersect on the map, the architect must make a choice: either lift one of these roads to the bridge, allowing the flow of the other to pass freely below, or realise the intersection in the form of an intersection, and resolve the flow conflict by traffic light regulation. The second option is often chosen in cities as it is attractively simple, does not imply the need to build large-scale engineering structures, and in addition it provides pedestrians with an easy way to cross the road.


(business quarters of Los Angeles in the afternoon, photo: Boris Shein)

The use of traffic lights in networks with cellular topology has its own characteristics. In Chapter 1, it was shown that with proper synchronisation of traffic lights, cars, while they are moving along the same street, do not even have to stop at intersections: a green light will always light in their direction. This kind of phenomenon is usually called the green wave traffic management. To create it, traffic flows need to be divided into two alternating: filled with cars and free of them. Next, such a mode of traffic lights operation is selected that in the period of time when the next “portion” passes the intersection along one of the streets, the previous portion of cars moving along the perpendicular street has already passed it, and the next one has not yet arrived (Chart 33).


Chart 33

Green wave traffic management carries its own costs and imposes certain restrictions on the layout of city streets.

Looking again at Chart 33, it is easy to see that at any given time exactly half of the area of all roads is not actually used. To compensate this downtime, in the actively used half, the local power of car flows and the number of lanes necessary for them should be twice as large as in a city with overpasses.

The second most important circumstance associated with the use of green waves is the strict regulation of the permissible size of quarters: their length (for two-way streets) should be a multiple of the length of the filled green wave (a section of the flow within which unhindered movement is possible), amounting to about 500 metres. As noted in the previous paragraph, areas with a high population density require an increased frequency of location of roads, so the restriction on the distance between highways (the permissible size of quarters) can potentially cause traffic difficulties.

It is interesting to note that in the green wave traffic management, the switching rules inside the network slightly change. For example, the addition of one more car to the main traffic flow can be performed in the intervals between the filled zones, without thereby causing any serious switching costs (point 1 in Chart 34a).


Chart 34

Of course, this car itself will have to lose some time waiting for the nearest empty zone before getting into the highway, and after that stand at the traffic light until the next filled zone hits it (point 2, Chart 34a), however the value of these losses does not depend either on the size of the city or on the busyness of traffic in the street, therefore, they can be neglected on a large scale.

The situation is completely different if a car tries to leave the highway traffic (Chart 34b). Here, apparently, there are no longer any tricky ways how to make the switching losses created by the driver less. Moreover, due to the doubling of the local power of the flow inside the filled zones, leaving of a randomly selected car from it causes time costs twice as much as in a city with overpasses. In total, the cheaper “entry” and more expensive “exit” offset each other, making the Traffic Light Cellular city in this respect almost no better, but no worse than Standard one.

Flyover Cellular city with one-way traffic

In addition to the use of traffic lights, there is at least one more opportunity to avoid the monstrous interchanges of the Standard city. It implies dividing spatially two-way highways (Chart 35).


Chart 35

As a result of such changes, the number of streets will double, they will all become one-way streets, but most importantly, the interchanges will be greatly simplified (Chart 36).


Chart 36

Since the number of highways heading to each of the sides of the world and the number of journeys passing along them remained the same, the powers of all flows together with the switching costs in the One-way Cellular city and the Standard city with 2 times larger (linearly) quarters, should coincide. If we compare the Standard and the One-way cities with the same quarter sizes, then the switching losses in the second one will be twice as high.

Advanced Road Networks

«Linear» street

How could switching losses be reduced in a Cellular network? The answer to this question can be find by selecting a correct analogy, with the help of a little savvy.

Let us consider a somewhat unusual modification of the Cellular network, which implies that all highways stretching from west to east are two-way, while the perpendicular to them highways are only one-way: either north or south, and these directions alternate from street to street.

As always, we will assume that the city follows the random access model, and each quarter of it generates a flow with power 1.

In this case, it seems quite plausible that the flow originated inside the quarter ( i , j ) is distributed between the nearest streets as follows: 1/4 of it will go to the horizontal road northwards, 1/4 — to the horizontal road southwards, 1/4⋅ i / d — to the vertical highway to the north and 1/4 ⋅ (1 — i / d ) — to the second vertical highway to the south (Chart 37).

Chart 37

Indeed, according to the previously discussed route algorithms, according to statistics, half of the journeys will start from a horizontal section, and for drivers who would prefer this half, it should to a large extent not matter whether their path lies northwards or southwards of the quarter ( i , j ). The remaining half of the journeys will start from a vertical section of traffic and will be divided between highways heading to the south and north as a ratio of the number of quarters lying southwards from the quarter ( i , j ) to the number of quarters lying northwards from it.

As to the flow of trips heading inward the quarter ( i , j ), the rule of its division with respect to the highways surrounding the quarter will be symmetrical (Chart 38).


Chart 38

Among the four intersections adjacent to the quarter ( i , j ), we can consider separately the lateral flows at the intersection of the lower horizontal highway and the vertical street with traffic to the north (Chart 38). The flow of cars entering into the intersection and heading from the horizontal street to the vertical one is:
1/2⋅ (number of quarters on the horizontal)×( number of quarters on the vertical not lower than ( i , j )) ⋅ 1/ d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i / d .

The power of lateral flow in the opposite direction is:
1/2⋅ (the number of quarters on the vertical is strictly lower than ( i , j ))×(the number of quarters on the vertical) ⋅ 1/ d ² =
= 1/2 ⋅ ( d − i ) ⋅ d / d ² =
= 1/2 ⋅ (1 − i / d ).

Let's now turn our attention from the Cellular city as a whole to any one of its vertical streets, let's call it My_street. By virtue of symmetries, we will not limit our reasoning in any way, if we assume that the movement along My_street is directed from south to north (Chart 39).


Chart 39

Chart 40 depicts the power of the main and side flows on the highway along My_street, which, as the reader may notice, are incredibly similar to similar graphs for the one-way highway of a Linear city (Chart 26).



Chart 40

In these examples, the flow diagrams coincide completely if inside My_street the lateral flows relating to each pair of opposing quarters and the horizontal highway below them are formally assigned to one imaginary territorial cell. As can be seen from the earlier tables, the road network of a Linear city generates some of the largest switching losses among the networks we have already studied. From this point of view, the traffic pattern within the boundaries of a single street of a Cellular city looks extremely inefficient and is an element that should be improved in the first place.

Advanced Linear City Network

So, we are facing the task of improving a Linear network so that it does not turn into a «square» one. The circumstance that represents the greatest inefficiency in the operation of the Linear Network is the merging of all routes into only two very large traffic flows. In this situation, a reasonable step would be to divide the flows along both of its street highways into Q equal parts. Since the time costs caused by each car joining or leaving traffic are proportional to the traffic intensity on it, as a result of dividing the street lines into Q isolated parts (Chart 41a), the switching losses inside a Linear city should have decreased Q times.


Chart 41

Even after the construction of ten roads nearby we can't hope that the drivers themselves will be equally distributed between them — unfortunately, it does not seem to have a chance of success. A much more thoughtful decision would be to design the network so that each road does not lead to all quarters, but only to a small “segment” of the city, where it would be difficult to get to without using the given road (Chart 41b).

You can see a similar idea in the scheme of movement of elevators inside multi-storey buildings where each elevator allows you to enter and exit it not on all floors, but only within a certain range of heights. Accepting this concept, let us take a closer look at the road r _k , which gives access to the segment Δ _k = ( x _k , x _{k +1} ] for trips that started (not strictly) southwards from xk (it is believed that the numbering of the quarters is performed from the bottom up).

From each quarter which number is fewer (not strictly) than x _k , a q _in stream with a power of Δ _k |/ n ( 1/ n to each quarter inside Δ _k ) enters the road r _k , at the same time it is assumed that there is no possibility to turn from r _k towards any of the mentioned quarters either due to established traffic rules, or due to a special design of the road network.

The cars accumulated on the segment [1, x _k ] will eventually be evenly distributed between the quarters inside Δ _k , therefore, if there were no trips whose start and finish points lie inside Δ _k , then the side flows q _out in the direction of each of the quarters in this section would have the power x _k / n (Chart 42).


Chart 42

In fact, the contribution of “internal” trips to the power of side flows does exist, however, the value of this contribution never exceeds | Δ _k |/ n , therefore, in the case when x _k >> | Δ _k |, it can be simply neglected. The power p _k of the main stream along r _k with simplifications made will be represented by a graph of two straight sections with a maximum P _k equal to x _k ⋅ | Δ _k |/ n . The approximate value of switching losses in the road r _k can be found by the formula:

I _k = ( α /2 ν ) ⋅ ∑ _x [ q _in ( x ) ⋅ p _k ( x ) ⋅ (1 + 1/ s ) ] + ( α /2 ν ) ⋅ ∑ _x [ q _out ( x ) ⋅ p _k ( x ) ⋅ (1 − 1/ s ) ] =

= ( α /2 ν ) ⋅ (1 + 1/ s ) ∑ _x [ | Δ _k |/ n ⋅ p _k ( x ) ] + ( α /2 ν ) ⋅ (1 − 1/ s ) ∑ _x [ x _k / n ⋅ p _k ( x ) ] =

= ( α /2 ν ) ⋅ (1 + 1/ s ) ⋅ ( x _k ⋅ | Δ _k |/ n ) ⋅ ( ∑ _x p _k ( x ) )/ x _k + ( α /2 ν ) ⋅ (1 − 1/ s ) ⋅ ( x _k ⋅ | Δ _k |/ n ) ⋅ ( ∑ _x p _k ( x ) )/| Δ _k |,

where the first sum is taken over a segment x ∈ [1, x _k ], and the second over x ∈ Δ _k . The expressions:

( ∑ _x p _k ( x ) )/ x _k , x ∈ [1, x _k ] and

( ∑ _x p _k ( x ) )/| Δ _k |, x ∈ Δ _k

are nothing other than the average power of the flow along r _k inside the indicated intervals. Since the power graph within these intervals has the form of a straight line, the average power in both cases is P _k /2. Replacing

x _k ⋅ | Δ _k |/ n by
P _k ,

we finally present the formula for losses intensity rate in its simplest form:

I _k = 2 ( α /2 ν ) ⋅ P _k ⋅ P _k /2 = ( α /2 ν ) ⋅ P _k ²

Let us now try to calculate the sequence x _k of numbers of those quarters by which a linear city should be divided into segments. As a criterion for the selection of segments, we can take the requirement that the maximum power of the traffic flows P _k in the roads approaching them should have the same value, independent of k , in other words:

x _k ⋅ | Δ _k | = Const.

Remembering that | Δ _k | = x _{k + 1} − x _k , we can infer the difference equation:

x _{k + 1} − x _k = Const/ x _k .

Assuming x and k are continuous variables, and replacing

x _{k + 1} − x _k = x ( k + 1) − x ( k )

by d x /d k ⋅ 1,

we can approximate the difference equation by the differential one:

d x /d k = Const/ x <=> x d x = Const ⋅ d k .

from which we can infer a solution for x _k in the general form:

x _k = ₁ √( k + ₂ ).

It remains for us to determine the value of the constants ₁ and ₂ based on their boundary conditions, however, there is an important subtlety in this matter. Unlike the situation in other segments, all the cars arriving from the western highway to the quarters of the segment with number 1, began their trips inside the same segment. As a result, the graph of the flow power in the first highway to the north will have the form of a regular inverted parabola.

At the same time, the a priori conditions from which the formula for x _k was obtained essentially assumed that the flow power graphs on all highways should be close to a triangular view, and the trips themselves should begin mainly outside the segment where they are directed to. These requirements can be fulfilled with reasonable accuracy if we formally divide the first segment into two equal parts, without increasing the number of roads. Most of the trips that take place along the first highway begin in its southern half, and end in the northern half. Considering only them, we thereby do not make a big mistake in calculating the switching losses, but now the power diagram of the main flow will have just a triangular shape (Chart 43).


Chart 43

It is the middle of the first segment that should be considered the point x ₁ in the formula for x _k . This allows us to get the first boundary condition:

x ₂ = 2 x ₁ or

√( 2 + ₂ ) = 2 ⋅ √( 1 + ₂ ) =>

₂ = − 2/3.

The second boundary condition can be obtained from the requirement that the roads and segments of everything are exactly Q , which means x _{Q + 1} should be subsequent to the quarter with the largest number in the city:

₁ √( Q + 1 − 2/3) = n + 1, whence

₁ ≈ ( n + 1)/√ Q .

Therefore:

x _k ≈ ( n + 1) ⋅ √( k − 2/3)/√ Q ,

| Δ _k | ≈ d x /d k = ( n + 1)/ 2√( k − 2/3) ⋅ √ Q

P _k = x _k ⋅ | Δ _k |/ n =

= ( n + 1) ² / 2 n ⋅ Q ≈ n / 2 Q

I _k = ( α /2 ν ) ⋅ P _k ² =

= ( α /2 ν ) ⋅ ( n / 2 Q ) ² .

Since all 2 Q highways generate losses of the same intensity, the value of switching costs within the entire network will be:

I = 2 Q ⋅ ( α /2 ν ) ⋅ ( n / 2 Q ) ² = ( α /2 ν ) ⋅ n ² / 2 Q .

As you can see, the desired result has been achieved: after dividing the main highways into Q parts, the losses indeed decreased by a factor of Q (except for the increased from 1/3 to 1/2 constant coefficient, compared to the formula for the usual Linear city). Well, we are halfway there, it remains only to apply this result to improve the city with Cellular architecture.

'Skyscraper Elevator' in a Cellular city

For simplicity, we will consider an example of a city in which all the streets are one-way. Using the analogy between a Linear city and the individual streets of a Cellular city, we can divide the highway along the latter into Q parts. By default, it is believed that leaving the quarter, the driver can choose any highway passing near it. At the same time, among all the highways laid along one street, there is a turn towards a specific quarter from exactly one of them. In the process of establishing rules, their uniformity and simplicity are extremely important. Let's take a look at Chart 44:


Chart 44

all the streets have the same view and the same rules as to which of the roads opens access onto which quarter. Chart 45 shows a diagram of permitted turns between highways. Looking at this picture, it is hard not to get confused. The same is often said about the underground scheme in some large city. However, in both cases, everything becomes clear and simple if you know the logic of the idea. The logical rule of permitted turns sounds quite simple: if driving along a highway, you cross roads perpendicular to your movement and you can turn into a quarter located directly behind them, you can turn into any of these roads.


Chart 45

The 'Skyscraper elevator' topology is compatible with both traffic light intersections and overpasses. It is difficult, but possible to generalise it to networks not necessarily of a cellular or linear structure. The latter is really important for historical cities, where it is unlikely that it would be a right decision to demolish half of the historical monuments in order to design many small straight streets, but in which there are already quite large streets that can accommodate several two- or three-lane highways.

About the transport problems and the work of a mathematician

It is pleasant to complete the 6 months laborious work. The work I wrote, of course, does not solve all the problems and difficulties of road design — this issue requires a large number of very versatile and multi-skilled people. Nevertheless, its results provide an opportunity to see important errors in already built cities and provide methods of how to avoid such errors in the future. This article was not intended as a reference book covering all possible cases that an engineer can face in practice — I considered my main aim is to give a new point of view, to develop a new way to reason and talk about the problem, to provide the reader with the necessary minimum of simple model examples which could be expanded by the reader further.

It becomes sad when you realise how much time was lost by city residents in traffic jams just because at the right time there was no mathematician who could spend the evening on a completely solvable problem. How many such problems still surround our life or hide in your profession? Is a person sitting near you at work whose tools are a pencil and a sheet of paper?

I hope everything will change for the better.

I would like to express my sincere gratitude to Janine Lacroix (pseudonym) for her work on translating this text from its original Russian to English.
Thank you for your attention and good luck!
Sergei Kovalenko

2019
magnolia@bk.ru


( Photo: Vincent Laforet)