Eine Stadt ohne Staus

Kapitel 2.
( der Link zu Kapitel 1 )

Die Kunst, Straßennetze zu gestalten

Transportprobleme einer Stadt mit den Augen eines Informatikers

Wenn mir ein Artikel mit dem Titel „Die Kunst, Straßennetze zu entwerfen“ empfohlen würde, würde ich sofort fragen, wie viele Straßennetze unter Beteiligung des Autors gebaut wurden. Ich muss zugeben, meine berufliche Tätigkeit war weit vom Straßenbau entfernt und wurde kürzlich mit dem Entwurf von Mikroprozessoren in Verbindung gebracht, bei denen ich unter anderem mit dem Ressourcenverbrauch der Datenvermittlung befasst war. Zu dieser Zeit stand mein Tisch direkt gegenüber dem Panoramafenster, das einen schönen Blick auf den langen Abschnitt des Wolgograd Highway und einen Teil des dritten Transportrings mit seinen endlosen Staus von morgens bis abends von Horizont zu Horizont eröffnete. Eines Tages hatte ich einen plötzlichen Schock der Anerkennung: „Die Komplexität des Datenumschaltprozesses, mit dem ich auf einem Chip zu kämpfen habe, ähnelt möglicherweise den Schwierigkeiten, mit denen die Autos beim Durchfließen des Labyrinths des Straßennetzes konfrontiert sind.“
Wahrscheinlich gab mir diese Sichtweise von außen und die Anwendung von Methoden, die für das betreffende Gebiet nicht traditionell waren, die Möglichkeit, die Ursache von Staus zu verstehen und Empfehlungen zur Überwindung des Problems in der Praxis abzugeben.

Was ist die Neuheit des Ansatzes?

Historisch gesehen wird der Hauptzweck von Straßen als die Möglichkeit angesehen, lange Strecken schnell zurückzulegen (zwischen Rom und den Provinzen). Ein solches Urteil ist gerechtfertigt, wenn es um das Intercity-Autobahnnetz auf Bundesebene geht: Die Städte, die sie verbinden, sehen aus wie kleine seltene Punkte auf dem Atlas, und die meisten Autos, die zwischen diesen Städten fahren, fahren ihren Weg, ohne irgendwo abzubiegen.

Sobald wir jedoch mehrere Seiten umblättern und eine detaillierte Karte einer Großstadt öffnen, ändert sich das Bild sofort: Die Anzahl der Adressen, an denen die Reise beginnen oder enden kann, erreicht ungefähr zehntausend, alle sind ziemlich dicht verteilt und relativ klein. Gleichzeitig können Hunderttausende von Autos gleichzeitig auf den Straßen einer solchen Stadt in Bewegung sein. Darüber hinaus besteht das Ziel eines jeden von ihnen nicht nur darin, bereits leere Straßen zu füllen, sondern eine Person oder Fracht von einer zu bewegen Punkt mit einer bestimmten Adresse X zu einem Punkt mit einer bestimmten Adresse Y. Insgesamt bedeutet dies, dass das städtische Verkehrssystem angepasst werden muss, um das Problem der mehrfachen gleichzeitigen Adressierung effektiv zu lösen. Dadurch werden die Funktionen des städtischen Verkehrssystems dem Telefon- oder Computernetz noch ähnlicher als dem Intercity-Straßennetz.

Das Straßennetz als Schaltkreis für einen Hardwareentwickler oder -ingenieur auf dem Gebiet der Informationstransfertechnologien zu betrachten, ist eine völlig natürliche Art, über ein Problem zu sprechen, aber unter Menschen, die an der Erforschung von Verkehrsproblemen beteiligt sind, ist diese Ansicht meines Wissens nach neu.

Die Theorie der Signalumschaltung ist eine enge Ingenieurwissenschaft und allein reicht natürlich nicht aus, um eine separate Straße oder Straßenkreuzung zu planen oder das Verhalten eines Verkehrsstroms auf einem geraden, isolierten Abschnitt einer Autobahn vorherzusagen. Glücklicherweise sind die oben aufgeführten Probleme heute gut erforscht, und die zu ihrer Lösung entwickelten Methoden sind bereits erfolgreich in die Praxis umgesetzt worden. Die Theorie des Wechsels ermöglicht es dem Architekten wiederum, das Risiko zu mindern, dass die Stadt in einen Zustand des Verkehrszusammenbruchs gerät, obwohl alle Elemente des Straßennetzes perfekt ausgeführt sind. Dieses Risiko besteht, weil die gleichzeitige gleichzeitige Adressierung eine ressourcen- und zeitaufwändige Aufgabe ist, deren Schlüssel zu einer effektiven Lösung nicht in der Breite der Straßen und der Bequemlichkeit von Verkehrsknotenpunkten liegt, sondern in der kompetenten Auswahl der jeweiligen Vermittlung Schema, das das vorgeschlagene Straßennetz umsetzen wird.

Anhand dieser Untersuchungen erfahren Sie beispielsweise, warum die in modernen Städten immer noch häufig genutzten „arteriellen“ Verkehrsnetze „schlecht“ sind und zusammen mit dem Bevölkerungswachstum zwangsläufig zu Staus führen. Ein weiteres interessantes Ergebnis, das gut mit den Beobachtungen übereinstimmt, erklärt, warum der Ausbau der Straßen allein, wenn zuvor alle Staus ausschließlich in der Nähe der Abzweigungen auftraten, die Situation wahrscheinlich nicht irgendwie verbessern wird, selbst wenn die Anzahl der Autos in Die Stadt bleibt gleich.

Als ich diesen Artikel schrieb, war es für mich entscheidend, dass er für den gewöhnlichsten Architekten verständlich war und durch seine Arbeit nützlich sein konnte. Ich habe versucht, den Leser in einer einfachen Sprache in Wechselprobleme einzuführen, Kriterien zu entwickeln, anhand derer beurteilt werden kann, wie gut ein bestimmtes Straßennetz die Aufgabe der gleichzeitigen Adressierung bewältigen kann, und anhand von Modellbeispielen gezeigt, wie dieses Wissen in der Praxis eingesetzt werden kann.

Der Artikel richtet sich an einen breiten Kreis von Lesern, die mit dem universitätsweiten Mathematikkurs und der Theorie der Algorithmen ein wenig vertraut sind und bereit sind, sich 1 bis 5 Tage damit zu befassen.

Trennung und Zusammenlegung von Fahrzeugströmen

Für viele Fahrer ist es eine offensichtliche Beobachtung, dass Verkehrsschwierigkeiten hauptsächlich in den Straßenabschnitten auftreten, in denen Autos aus irgendeinem Grund gezwungen sind, die Spur zu wechseln. Beispiele hierfür sind Straßengabeln, Verengungen, Bereiche neben Autobahnausfahrten und Zufahrtsstraßen, Abschnitte von Autobahnen, auf denen einige Fahrspuren durch einen Unfall oder Straßenarbeiten blockiert sind.
In diesem Abschnitt wird versucht, eine quantitative Beschreibung der in solchen Fällen ablaufenden Prozesse zu geben, und wir werden zunächst verstehen, wie Autos die Fahrspur wechseln.

Zwei Strategien zum Wechseln auf eine benachbarte Fahrspur
Der Verkehr entlang einer Autobahn weist eine natürliche Unebenheit auf: Jemand fährt lieber etwas schneller, jemand etwas langsamer, zwischen einigen Autos verringert sich die Entfernung und wird für das Fahren kaum komfortabler, während sie zwischen den anderen so stark zunimmt, dass Autos passen dort von angrenzenden Fahrspuren. Das Auftreten solcher Lücken im Fluss der benachbarten Fahrspur direkt auf der Seite des zufälligen Fahrers kann häufig oder nicht sehr häufig sein. Wenn in dem Moment, in dem er ein Manöver durchführen muss, keine Lücke besteht, kann der Fahrer auf mindestens zwei Verhaltensstrategien zurückgreifen:

Strategie 1
Mehrere geeignete Lücken können sich einfach in der Nähe des Fahrerstandorts befinden. Wenn die Bewegung dicht genug ist, ist es unwahrscheinlich, dass der Fahrer in der Lage ist, die Geschwindigkeit zu erhöhen und die erforderliche Lücke zu schließen. Wenn er jedoch etwas langsamer wird, lässt der Fahrer den Nachbarstrom das Auto überholen, so dass er mit der Lücke gleich wird war ursprünglich im Rückstand - es wäre kein großes Problem. Die Kosten dieser Strategie liegen auf der Hand: Der Fahrer selbst und die Autos, die auf seiner Fahrspur zurückfahren, verlieren aufgrund der Notwendigkeit, die Geschwindigkeit zu reduzieren, einige Zeit.

Strategie 2
Um zu warten, müssen Sie Geduld haben und die notwendige Zeit dafür haben. Eine Alternative kann ein Versuch sein, das notwendige Manöver "hier" und "jetzt" durchzuführen. Nach dieser Idee gibt der Fahrer den Autos hinter ihm ein Zeichen für die Fahrspur, auf die er fahren wird. Diese wiederum sollten als Reaktion auf sein Signal etwas langsamer werden und „die vor ihnen fahrenden Autos vorwärts fahren lassen“, um so die Lücke der erforderlichen Größe in ihrem Fluss zu schaffen. Die Zeitkosten werden in diesem Fall auf die Autos der Fahrspur verteilt, auf die der Fahrer schließlich umschaltet.

Im wirklichen Leben sind beide Strategien gleichzeitig involviert: Zunächst verlangsamt sich der Fahrer und wartet auf eine relativ große Lücke im Strom der angrenzenden Fahrspur. Erst danach geben sie den darin fahrenden Autos ein Signal über ihre Absicht, ein Schaltmanöver durchzuführen.

Zweifellos sind Zufahrtsstraßen, Autobahnausfahrten und Verengungen nicht der einzige Grund für den Wechsel zwischen den Fahrspuren, der bei der Gestaltung von Straßen berücksichtigt werden sollte. Die Fähigkeit von Autos mit höheren Geschwindigkeiten, den gemächlichen Verkehr zu überholen, ist erforderlich, um zu verhindern, dass sich die Situation auf der Autobahn zu einer großen Warteschlange verschlechtert, die mit der Geschwindigkeit des langsamsten Traktors kriecht. Das Problem der Koexistenz von Fahrzeugen, die sich mit unterschiedlichen Geschwindigkeiten auf einer Straße bewegen, hat jedoch einen etwas anderen Charakter und kann von den fraglichen Themen getrennt werden, da der Überholvorgang und das entsprechende Wechseln zwischen den Fahrspuren für den Fahrer nicht erzwungen werden. Wenn sich der Fahrer gemäß der Wahrscheinlichkeitstheorie nicht beeilt, wird dem Fahrer auf natürliche Weise eine bequeme Gelegenheit zur Durchführung eines Manövers gegeben, und dafür muss er die Bewegung anderer Fahrer nicht stören.

Die Kosten für eine einzelne Umschaltung
Das Verhalten der Fahrer in der Realität kann sehr kompliziert sein, aber es ist für uns in erster Linie entscheidend, dass das unter den Modellbedingungen erzielte Ergebnis plausibel bleibt: Jedes erzwungene Wechseln zwischen den Fahrspuren führt zu einer Zeitstrafe für die Verkehrsteilnehmer.

Lassen Sie uns nun bewerten, wie viel Zeit von der Verkehrsdichte auf der Straße abhängt.

Wir werden die Bewegung entlang jeder Spur als separaten Strom betrachten. Die Fahrer versuchen, einen bequemen Abstand zu Autos auf derselben Fahrspur zu halten, und reservieren dabei eine Straßenstrecke mit einer bestimmten charakteristischen Länge d im Strom. Lassen Sie ρ Autos pro Längeneinheit in einen Strom fallen. Wir stimmen zu, die Strömungsdichte klein zu nennen oder zu sagen, dass ρ klein ist, wenn das Produkt ρ × d viel kleiner als 1 ist.

In dem Moment, in dem der Fahrer erkennt, dass er in die nächste Reihe wechseln muss, ist die Wahrscheinlichkeit, dass eine Straßenstrecke mit der Länge d , die der Fahrer einnehmen wollte, bei kleinem ρ nicht frei ist, ungefähr proportional zu ρ selbst. Wenn das beschriebene Ereignis tatsächlich stattfindet, werden zwei Autos, die um einen Platz kämpfen, aufgrund der Manöver insgesamt eine gewisse Verzögerung des durchschnittlichen konstanten Wertes δ erfahren.

Angenommen, ρ ist klein, können wir die Wahrscheinlichkeit vernachlässigen, dass ihre Aktionen in diesem Moment die Bewegung anderer Autos beeinflussen. Wenn also ρ klein ist, beträgt der Zeitverlust durch ein Schalten α⋅ρ , wobei der Koeffizient α eine empirisch messbare Größe ist, die von Kultur, Wetter, Geschwindigkeitsgrenzen (usw.) abhängt, aber in dieser bestimmten Zeit ungefähr konstant bleibt und für diese Stadt als Ganzes.

Verlustintensitätsrate auf einer Straße vor der Ausfahrt
Die Autos, die zur Ausfahrt fahren, müssen, bevor sie die Rampe erreichen (Abbildung 2), manchmal sogar mehrmals in die angrenzende Reihe rechts wechseln. Jedes dieser Manöver stört den Fluss, und infolgedessen ist die Durchschnittsgeschwindigkeit in dem Abschnitt vor der Ausfahrt merklich niedriger als in den Abschnitten „Transit“ (ohne die Ausfahrten, Eingänge und Gabeln) der Autobahn.


Grafik 2

Einen Teil des Weges mit einer niedrigeren Geschwindigkeit zu passieren - bedeutet für Fahrer (und ihre Passagiere) eine zusätzliche Zeit, die sie auf der Reise verbringen. Mit anderen Worten, der Bereich der Autobahn neben der Ausfahrt ist ein konstanter Generator für Zeitverluste.

Nehmen wir an, dass die durchschnittliche Fahrzeuggeschwindigkeit ν und die Strömungsdichte ρ an der Frontalgrenze dieser Strecke für alle Fahrspuren gleich sind.

Nehmen wir außerdem an, dass die Dichte ρ und die Strömungsrate q, die zum Ausgang führt (die durchschnittliche Anzahl von Autos, die pro Zeiteinheit auf die Rampe fallen), gleichzeitig klein sind und s die Anzahl von Fahrspuren auf der Autobahn ist. Um zum Ausgang zu gelangen, schaltet der Fahrer die Manöver 1 zu s um . Wenn die Strömungsdichte auf der Rampe viel niedriger als ρ ist , ist nur das letzte Manöver für den Fahrer praktisch „kostenlos“, während der Rest in jedem Fall Verluste von α⋅ρ verursacht . Im Durchschnitt müssen Sie (0 + 1 + 2 + ... + s - 1) / s = ( s - 1) / 2 "teure" Manöver ausführen.

Angesichts der Schwierigkeiten, die durch alle Autos verursacht werden, die zum Ausgang fahren, können wir die Formel für die Intensität der Zeitverluste erstellen:

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

Der Wert p = ( sρν ) ist nichts anderes als die Durchflussrate aller Autos, die sich entlang der Autobahn in die betreffende Richtung bewegen (die durchschnittliche Anzahl von Autos, die pro Zeiteinheit an einer Bushaltestelle vorbeifahren). Die letzte Bemerkung gibt uns die Möglichkeit, die Formel für I in eine symmetrischere Form umzuschreiben:

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

Verlustintensitätsrate am angrenzenden Abschnitt der Zufahrtsstraße
Die Situation auf der Autobahn hinter dem Abschnitt, an dem die Zufahrtsstraße mit ihr verbunden ist, wiederholt weitgehend die Situation auf dem Abschnitt vor der Ausfahrt, obwohl es einige Unterschiede gibt. Lassen Sie einen kleinen Strom von Kraftfahrzeugen q durch die seitliche Rampe in den Hauptverkehr der Autobahn strömen (Grafik 3).


Grafik 3

Die Rampe hat nur eine begrenzte Länge, daher sollten alle neu ankommenden Autos auf die rechte Fahrspur der Autobahn umgeschaltet werden. Infolgedessen ist die Verkehrsdichte in der rechten Spur 1 lokal höher als der Durchschnitt auf der Straße. Deshalb entscheiden sich einige Fahrer dafür, auf eine weniger belebte benachbarte Spur links zu wechseln, was wiederum zu einer lokalen führt Erhöhung der Dichte bereits auf der zweiten Spur. Dieser Wechsel zwischen den Fahrspuren wird fortgesetzt, bis die Strömungsdichte über die gesamte Breite der Autobahn ausgeglichen ist. Unter der Annahme, dass die Durchschnittsgeschwindigkeit ν für alle n Spuren gleich ist, können wir erwarten, dass nach Abschluss der Schaltvorgänge die Strömungsleistung in jeder von ihnen um genau (1 / s ) ⋅ q zunimmt.

Um zu sehen, wie viel eine solche Umschaltung für die Fahrer kostet, berechnen wir zunächst die Leistung aller Umschaltströme. Die Strömung von der Rampe zur ersten Spur der Autobahn kennen wir bereits: Sie ist gleich q . Um die Erhöhung der Leistung der ersten Spur mit (1 / s ) ⋅ q gleichzusetzen, sollte der Fluss von der ersten Spur in die zweite Spur (1 - 1 / s ) ⋅ q sein , von der zweiten in die dritte = ( 1 - 2 / s ) ⋅ q , vom k- ten bis zum ( k + 1) th = (1 - k / s ) ⋅ q . Gemäß der letzten Formel beträgt die Kapazität des Schaltflusses zur Spur am linken Rand (1 - ( s - 1) / s ) ⋅ q = (1 / s ) ⋅ q , wie vom gesunden Menschenverstand vorgegeben.

Da wir die Zeitstrafe einer einzelnen Umschaltung und die Leistung aller Umschaltflüsse kennen, können wir jetzt die Gesamtintensität der von ihnen erzeugten Verluste berechnen:

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 ).

Wenn wir uns noch einmal daran erinnern, dass sρν die Kraft p des Flusses aller Autos entlang der Autobahn ist, erhalten wir die Kostenformel in ihrer endgültigen Form:

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

Verlustintensitätsrate an der symmetrischen Gabel
In den vorhergehenden Absätzen haben wir Verluste durch die Wechselwirkung von Strömungen festgestellt, von denen einer notwendigerweise groß und der andere notwendigerweise klein war. Um einen Ansatz zur Lösung von Problemen zu demonstrieren, bei dem die Kapazitäten beider Flüsse in ihrer Leistung vergleichbar sind, betrachten wir ein weiteres Extrem: eine Gabel, bei der beide Abzweigungsrichtungen bei Fahrern gleichermaßen beliebt sind (Abbildung 4).


Grafik 4

Der Einfachheit halber werden Autos, die auf der Gabelung nach rechts fahren, als "blau" und Autos, die nach links fahren, als "rot" bezeichnet. Anfänglich bewegen sich Autos beider "Farben" gemischt und verteilt auf alle zwei Fahrspuren der Autobahn. Wenn sie sich der Gabelung nähern, driften die roten Autos langsam in Richtung der linken n Fahrspuren und die blauen in Richtung der rechten: Es gibt Schaltströme in zwei Richtungen zwischen benachbarten Fahrspuren. Im Gegensatz zum Beispiel der Zufahrtsstraße sind diese Ströme nicht mehr „relativ klein“. Übrigens gibt es nur zwischen den beiden zentralen Fahrspuren einen erzwungenen Verkehrsaustausch, dessen Intensität in einer der Richtungen (von links nach rechts oder von rechts nach links) einem Viertel der Gesamtleistung entspricht Strom bewegt sich entlang der Autobahn. Glücklicherweise gibt es in dieser Situation eine gute Möglichkeit, die generierten Kosten abzuschätzen.
Zunächst können wir feststellen, dass der Prozess der Aufteilung von Autos in „rot“ und „blau“ höchstwahrscheinlich lange vor der Gabelung beginnt und langsam verläuft. Daher sollte er einerseits nur geringe Auswirkungen auf die Verkehrsdichte in einer separaten Reihe haben und andererseits Schaltströme über große Entfernungen erstrecken, wodurch die Möglichkeit gegeben wird, jeden von ihnen als eine Kombination einer großen Anzahl von Strömen mit geringer Leistung darzustellen (Abbildung 5).



Grafik 5

Da es sich jetzt um kleine Ströme handelt, wenn auch in größerer Anzahl, hindert uns nichts daran, das fragliche Problem auf bereits gelöste zu reduzieren. Wir können die Autobahn in der Mitte mental in zwei gleiche Teile teilen und sie dann mit einer größeren Anzahl einspuriger Überbrückungsstraßen verbinden, sodass rote Autos nach links und blaue nach rechts fahren können (Abbildung 6). Aufgrund der offensichtlichen Symmetrie können wir uns bei der Berechnung der erzeugten Verluste auf Autos jeder Farbe konzentrieren, z. B. Blau, und am Ende nur das Ergebnis verdoppeln.


Grafik 6

Lassen Sie Geschwindigkeit ν und Dichte ρ für alle Fahrspuren gleich sein und bleiben Sie über die gesamte Strecke konstant, auf der Autos durch Farben getrennt sind. In diesem Fall beträgt die Durchflussleistung aller auf der Autobahn fahrenden Autos:

p = 2 sρv .

Q ₁ , q ₂ , ... q _m bezeichnen die Ströme blauer Autos, die sich entlang imaginärer Überbrückungsstraßen zur rechten Hälfte der Autobahn bewegen. Angenommen, kurz vor dem Trennungsabschnitt in jeder Fahrspur der Autobahn werden beide Farben mit gleichen Anteilen von 50% dargestellt, was dies insgesamt impliziert
q ₁ + q ₂ + ... + q _m entspricht sρv / 2 oder mit anderen Worten p / 4.

Verluste, die durch den Fluss q _i aufgrund seiner Kleinheit erzeugt werden, können wir nach folgender Formel berechnen:

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

Wenn wir die letzte Formel über alles i zusammenfassen , finden wir die Verluste, die nur durch die blauen Autos verursacht werden:

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

Die Gesamtverluste werden, wie bereits erwähnt, doppelt so hoch sein und betragen:

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

Analyse der erhaltenen Formeln
Wenn wir die Intensität I , dh die Zeit, die die Teilnehmer pro Sekunde vollständig verloren haben, durch den seitlichen Fluss q teilen, der per Definition der Anzahl der Autos entspricht, die die Autobahn in einer Sekunde verbinden oder verlassen, erhalten wir die durchschnittliche Verluste durch ein solches Auto:

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

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

Das vielleicht wichtigste in diesen Formeln ist die direkte Proportionalität zwischen dem Leistungsfluss von Autos auf der Autobahn p und den Stückkosten i . Alles sieht so aus, als ob ein Auto, das sich anschließen möchte, oder umgekehrt - den Hauptstrom verlassen möchte, wodurch jeder Fahrer in der Nähe ständig gestört wird.

Die zweite interessante und sehr unerwartete Beobachtung betrifft den äußerst schwachen Effekt auf die Intensität der erzeugten Verluste bei der Anzahl der Fahrspuren in der Nähe der Autobahn direkt neben der Kreuzung. Wie Sie sehen können, ist die Ausfahrt bei Betrachtung der Formel für I _out im Allgemeinen die zeiteffizienteste für eine einspurige Straße ( s = 1, i _out = 0) und die Schwierigkeiten, die durch die angrenzende Zufahrtsstraße für a verursacht werden Die dreispurige und die sechsspurige Autobahn unterscheiden sich nur um

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

Wenn wir bedenken, dass jedes Auto, das jemals in den Verkehr auf der Autobahn eingetreten ist, es irgendwann verlassen muss, dann scheint es durchaus legitim _, bei der Berechnung der Austauschverluste einen einheitlichen Wert anstelle von i _in und i _{out zu verwenden}

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

Trotz der Tatsache, dass die Formel für i _av nicht explizit von der Anzahl der Fahrspuren abhängt, muss beachtet werden, dass ihre Erstellung (siehe die Annahmen für I _in und I _out ) stark von der Annahme einer geringen Dichte von Autos auf der Straße abhängt Daher ist es unwahrscheinlich, dass zufriedenstellende Ergebnisse erzielt werden, wenn auf eine zu schmale Autobahn mit zu viel Verkehr angewendet wird.

Vorläufige Ergebnisse
In Gebieten in der Nähe von Kreuzungen treten unweigerlich Verkehrshindernisse auf, die den Fahrern Zeit nehmen, die Durchschnittsgeschwindigkeit verringern. Letzteres führt zu einer Erhöhung der Fahrzeugdichte und folglich zu einem möglichen Auftreten von Staus. Die mit der Trennung und Zusammenlegung von Fahrzeugströmen verbundenen Zeitverluste werden als Schaltverluste bezeichnet.

Verluste eines ähnlichen Typs treten auf die eine oder andere Weise in jedem Vermittlungsschema auf: sei es ein Telefon- oder Computernetzwerk, ein Mehrkern-Mikroprozessor oder ein Postzustelldienst.

Wenn der Fahrer den Verkehr auf der Autobahn betritt oder umgekehrt verlässt, sind die Umschaltkosten, die durch seine Handlungen entstehen, proportional zur Leistung des zu diesem Zeitpunkt auf der Autobahn beobachteten Fahrzeugflusses.

Um die Schaltverluste in der ganzen Stadt zu verringern, muss das in der Entwurfsphase implementierte Straßennetz sorgfältig abgewogen werden. Etwas später werden wir diese Aufgabe im Detail analysieren, aber einige offensichtliche Empfehlungen können jetzt aufgelistet werden:

1. Schaltverluste sind proportional zur Durchflussleistung auf der Autobahn - es ist nicht erforderlich, die Straßen ohne Notwendigkeit zu vergrößern, zwei kleine Autobahnen sind doppelt so gut wie eine große;
2. Schaltverluste sind proportional zur Leistung der Seitenströme - es lohnt sich, das Netzwerk so zu gestalten, dass der Fahrer während seiner Fahrt so oft wie möglich abbiegen muss;
3. Die gegenseitige Störung durch die Fahrer der Haupt- und Nebenströme sollte im gesamten Stadtgebiet geringer sein, wenn wir versuchen, die Verschmelzung von Strecken zu verhindern, die sich nur in einem kurzen Abschnitt der Straße überschneiden.

Wirtschaftliche Voraussetzungen für die Existenz von Städten.
Ein Stadtmodell mit 'Direktzugriff' ²

(Anmerkung 2: Der Begriff stammt aus dem RAM-Konzept und bedeutet zufällig nach Wahrscheinlichkeit und sogar nach Zeitverbrauch.)
Vielleicht besteht die erste Phase eines Projekts zur Gestaltung (oder Neugestaltung) des Stadtverkehrssystems darin, herauszufinden, welche Art von Umstellung die Stadt jetzt wirklich braucht und wie sich ihre Bedürfnisse in Zukunft ändern werden.

Eine solche Analyse kann durchgeführt werden, wenn wir die Stadt zuerst in nicht zu große, aber nicht zu kleine Gebiete unterteilen und dann für jedes Paar solcher Zonen angeben, welche ungefähre Anzahl von Fahrten auf die eine oder andere Seite von ihren Einwohnern bei benötigt wird die eine oder andere Tageszeit. Wenn Sie die gemachten Vorhersagen in eine Matrix einfügen, erhalten Sie eine Migrationsbedarfsmatrix der Stadtbewohner.

Genau für diese Matrix sollten wir ein Netzwerk durchsuchen, das es Fahrern und Passagieren ermöglicht, so wenig Zeit wie möglich auf einer separaten Reise zu verbringen, und von den Stadtbehörden so wenig Ressourcen wie möglich für die Netzwerkrealisierung benötigt.

Wenn es um bestehende Städte geht, ist es hier wichtig, keinen Fehler zu machen und die Anzahl der Reisen, die die Menschen wirklich benötigen, nicht durch die Anzahl der Reisen zu ersetzen, die historisch unter dem Einfluss einiger Hindernisse oder Schwierigkeiten zum Zeitpunkt von durchgeführt wurden die Designarbeit. Wahrscheinlich kann das Berliner Verkehrsnetz „vor“ und „nach“ dem Fall der Trennmauer das auffälligste Beispiel für das Gesagte sein.

Dieser Abschnitt befasst sich hauptsächlich mit humanitären Fragen, auf die ich kein Spezialist bin, aber ich denke, dass es korrekter ist, sie als Amateur zu diskutieren, als das Problem einfach zu vermeiden.

Um die Migrationsbedürfnisse der Bevölkerung besser darzustellen, lohnt es sich, mit der grundlegenden Frage zu beginnen: „Wofür sind Städte und was ist ihre nützliche Funktion?“

Versuchen wir, dies nicht als gewöhnliche Bewohner von Städten (und Dörfern) zu beantworten, sondern aus der Perspektive der Person, die für den Urbanisierungsprozess in einem großen und entwickelten Staat verantwortlich ist. Unter diesem Gesichtspunkt ist es nicht mehr wichtig, welche historischen Motive einst so viele Menschen auf ein winziges Stück Land drängten oder warum sie es jetzt weiterhin tun, es ist entscheidend - welche wirtschaftlichen Auswirkungen die Städte haben von der einen oder anderen Größe und durch welche Mechanismen dieser Effekt erreicht wird.

Meiner Meinung nach ist der Hauptgrund für die Existenz von Großstädten einerseits die Möglichkeit für Technologieunternehmen, Mitarbeiter seltener Berufe zu finden, und andererseits die Möglichkeit für Menschen, die seltene Berufe beherrschen, ihre zu verkaufen Dienstleistungen für Unternehmen, die an ihnen interessiert sind, zu wettbewerbsfähigen Bedingungen. In einer kleinen (nicht spezialisierten) Stadt ist die Produktion vieler Waren und Dienstleistungen entweder einfach unmöglich oder versetzt die Technologieunternehmen und ihre Mitarbeiter in die Position gegenseitiger Geiseln, ohne dem einen oder anderen Alternativen zu geben.

Nehmen Sie zum Beispiel den nicht so seltenen Beruf eines Schulliteraturlehrers. Laut Statistik beträgt der Bedarf für sie ungefähr 1 Lehrer pro 1000 Personen. In einer regulären Schule unterrichten 3-4 Tutoren Literatur. Die Wahl eines Arbeitsplatzes für einen Literaturlehrer kann als wettbewerbsfähig bezeichnet werden, wenn es in der Stadt mindestens 4-5 weiterführende Schulen gibt, was in Bezug auf die Bevölkerung etwa 15.000 Menschen entspricht.

Anscheinend fühlen sich Menschen mit einer technischen Spezialisierung auf dem Arbeitsmarkt in Städten mit mindestens 100.000 Einwohnern wohl. Natürlich gibt es auch solche Berufe, deren Nachfrage nur in Städten mit mehr als einer Million Einwohnern auftritt, aber die Existenz von mehreren Millionen Städten macht für mich keinen wirtschaftlichen Sinn.

Nach all dem oben Erwähnten sehen zwei Hypothesen durchaus vernünftig aus (deren Gültigkeit jedoch die Wahrheit des Hauptinhalts des Artikels nicht beeinflusst):

1. Der durchschnittliche Erwachsene muss am häufigsten über Entfernungen reisen, die 4-5 der vielversprechendsten Jobs für ihn erfassen.
2. Für einen bedeutenden Teil der Bevölkerung, der die seltenen und wirtschaftlich wertvollsten Berufe darstellt, kann die Entfernung der häufigsten Reisen durchaus mit dem Radius ihrer Stadt vergleichbar sein.

Als verstärkte Reflexion der Hypothesen 1 und 2 werde ich in meinen Beispielen häufig das Modell der Stadt mit „wahlfreiem Zugang“ verwenden, vorausgesetzt, die Leistung der erforderlichen Reiseströme ist zwischen zwei Vierteln davon gleich, oder Mit anderen Worten, in allen Zellen der Migrationsbedarfsmatrix gibt es die gleiche positive Zahl. Wenn Sie sich die Aufzeichnungen der Reisen ansehen, die tagsüber in einer solchen Stadt unternommen wurden, haben alle Quartale für die nächste markierte Reise die gleiche Wahrscheinlichkeit, ob sie beginnen oder enden, und keine Beziehung zwischen der Position der "Anfang" und "Ende" sollten eingehalten werden.

Straßennetze mit der einfachsten Topologie

Versuchen wir, die in den vorhergehenden Absätzen beschriebenen Ideen auf einige Arten von Stadtplänen anzuwenden, die aus dem Leben stammen.

Lineare Stadt

Die ersten großen Siedlungen entstanden vorwiegend entlang der Küste, in Gebieten eines dünnen Landstreifens zwischen Meer und Klippen oder entlang der Wege stark befahrener Straßen, sodass sie im Zuge des Wachstums enge, längliche Grenzen erlangten. Viele dieser Siedlungen haben bis heute überlebt, ihre längliche Form beibehalten und sich in moderne Städte verwandelt (siehe Abbildung unten).


(Ein ausgeschlossenes Gebiet von Rio de Janeiro, der Autor ist unbekannt)

Oft gibt es in einer solchen Stadt nur eine breite Straße, um die sie gebaut wird. Angenommen, jedes Viertel (Zone der territorialen Teilung) erzeugt einen Strom von Reisen mit Potenz 1, die Anzahl aller dieser Viertel entspricht n , und die Stadt selbst folgt dem Migrationsmodell des Direktzugriffs.


Grafik 7

Versuchen wir für die oben aufgeführten Parameter herauszufinden, wie sich die durchschnittliche Reisezeit und die erforderliche Straßenfläche mit zunehmendem n ändern.

Lassen Sie also alle Viertel die gleiche Form und Größe haben und ihre Anzahl multipliziert mit λ (Lambda) mal. Es ist offensichtlich, dass

• Die Länge der Hauptstraße erhöht sich um den Faktor λ .

Aufgrund des akzeptierten Modells des „wahlfreien Zugangs“ enden 50% der Fahrten, die in der rechten Hälfte der Stadt begonnen haben, in der linken Hälfte (das Gegenteil ist auch richtig), sodass die Anzahl der Quartale zunimmt Mit einem Faktor von λ multipliziert sich auch die Kraft des Flusses, der durch die Mitte der Stadt fließt, mit dem λ- fachen. Ähnliche Diskussionen mit derselben Schlussfolgerung werden zutreffen, wenn wir anstelle der Mitte einen Punkt nehmen, der die Stadt in einem bestimmten Verhältnis (1: 3, 2: 5) teilt, was dies impliziert

• die Kraft der Strömung entlang der Hauptstraße erhöht sich um einen Faktor von λ ;
• Die Anzahl der in jedem Abschnitt erforderlichen Fahrspuren der Hauptstraße multipliziert sich mit dem λ- fachen.

Mehr oder weniger offensichtlich, dass die durchschnittliche Länge der Reise und damit

• Die zur Fahrt über die Strecke aufgewendete Nettoreisezeit erhöht sich um den Faktor λ .

Es bleibt nur noch zu berechnen, wie oft sich der Zeitverlust aufgrund von Umstellungskosten auf einer Fahrt erhöht. Ein seitlicher Fluss mit der Leistung 1 tritt in jedes Viertel ein und aus diesem heraus, was zusammen Zeitverluste mit Intensität erzeugt:

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

Dabei ist p die Kraft des Flusses auf der Hauptstraße. Wir wissen bereits, dass die Anzahl der Viertel und die Strömungsleistung auf der Hauptstraße um den Faktor λ zunehmen, daher multiplizieren sich die vom Netzwerk erzeugten Gesamtzeitverluste mit dem λ ^2- fachen. Andererseits erhöht sich die Anzahl der vom Netzwerk erzeugten Fahrten, zwischen denen alle diese Verluste aufgeteilt werden, um den Faktor λ , weshalb

• Die durch die Schaltkosten verlorene Nettofahrzeit erhöht sich um den Faktor λ .

Lassen Sie uns alle Ergebnisse in einer Tabelle zusammenfassen:

Lineare Topologie
Die Anzahl der Adresspunkte (Viertel) mit Potenz 1 ........................ n
Gesamtstraßenfläche ............................................... ....................................... O ( n ² )
Nettoreisezeit,
ausgegeben, um die Strecke zurückzulegen ............................................. ...................... O ( n )
Nettoreisezeit,
verloren aufgrund von Umstellungskosten ............................................. ........................ O ( n )
Anzahl der Vermittlungsknoten .............................................. ..................... O ( n )
Anzahl der Schaltknoten bei gegebener Leistung der Seitenflüsse ............. O ( n )

Die verwendete Notation ' y = O ( x )' bedeutet, dass die Parameter x und y funktional abhängig sind, und wenn x unbegrenzt wächst, tendiert das Verhältnis x / y zu einer endlichen, von Null verschiedenen Zahl.

Zelluläre Stadt

Die zweite, ziemlich übliche Planungsmethode besteht darin, die Viertel in Form einer rechteckigen Matrix anzuordnen, ähnlich wie portionierte Stücke in einem Schokoriegel platziert werden.

Wir sind damit einverstanden, solche Städte "zellular" zu nennen. "


(Los Angeles, Foto: Slava Stepanov)

Grafik 8 zeigt ein Muster einer zellularen Stadt, die aus n (unter Berücksichtigung der "Hälften") Vierteln besteht, die zusammen ein regelmäßiges Quadrat bilden. Die Viertel sind durch insgesamt √ n Straßen voneinander getrennt, die sich bedingt von West nach Ost erstrecken, und √ n Straßen, die sich von Süd nach Nord erstrecken. Insgesamt bilden diese Straßen √ n × √ n Kreuzungen, von denen jede entweder als Ampelkreuzung oder durch Straßenbrücken / Überführungen implementiert werden kann.


Grafik 8

Unabhängig davon, ob es Einbahn- oder Gegenverkehr gibt, kann jede Fahrt von Punkt A nach Punkt B in einer Mobilfunkstadt entlang einer Route durchgeführt werden, die nicht mehr als zwei Straßen und nicht mehr als eine Kurve an einer Kreuzung umfasst.

Unter der Annahme, dass wie im vorherigen Beispiel jedes Quartal einen Strom von Reisen mit Strom 1 erzeugt und die Migrationsbedürfnisse der Bevölkerung dem Modell des "Direktzugriffs" folgen, können wir nun für eine Mobilfunkstadt die Gesetze berechnen, nach denen die average travel time and the resource intensity of road network construction will change with increasing quantity of quarters.

Wenn die Anzahl der Viertel um einen Faktor von λ zunimmt , dann:

• Die Fläche der Stadt multipliziert sich mit dem λ- fachen und ihren linearen Dimensionen unter Beibehaltung der Proportionen - mit √ λ ,
• Die durchschnittliche Verfahrstrecke und die Nettodauer, um sie zurückzulegen, sind proportional zu den linearen Abmessungen und werden mit √ λ mal multipliziert .
• Die Anzahl der Straßen und die Anzahl der an eine bestimmte Straße angrenzenden Viertel multiplizieren sich mit dem √ λ- fachen.
• Die Leistung des Verkehrsflusses, proportional zur Anzahl der Viertel, mit denen der Fluss in Kontakt steht (eine Erklärung dieses Begriffs wird später gegeben), multipliziert sich mit dem √ λ- fachen.
• the required area of ​​all roads grows as (number of streets) × (length of one street) × (power of street flow) = √ λ ⋅ √ λ ⋅ √ λ = λ √ λ

Die seitlichen Flüsse sind unterteilt in solche, die von oder in Richtung der Viertel verlaufen, und solche, die sich an Kreuzungen von einer Straße zur anderen drehen. Die Kraft der ersten Ströme bleibt je nach den Bedingungen immer gleich der Einheit. Bei den zweiten bewegt sich fast der gesamte Verkehr, kommt oder verlässt die Autobahn, wenn wir berücksichtigen, dass es in der Stadt viel mehr Viertel als Viertel auf einer bestimmten Straße gibt. Infolgedessen kann die Änderung der Leistung der zweiten Flüsse durch die Formel (Änderung der Leistung des Flusses) / (Erhöhung der Anzahl der Kreuzungen auf einer bestimmten Straße) = √ λ / √ λ geschätzt werden= 1. Die Gleichheit des letzten Verhältnisses zur Konstanten legt nahe, dass sich diese Ströme mit zunehmender Anzahl von Quartalen nicht wesentlich ändern. Daher wird der Anstieg der vom gesamten Netzwerk verursachten Vermittlungskosten wie folgt sein: (Zunahme der Gesamtzahl Anzahl der Viertel + Kreuzungen) × (Änderung des Durchflusswerts auf einer einzelnen Straße) = λ √ λ . Da die Leistung des von allen Vierteln erzeugten Migrationsflusses um einen Faktor von λ zunahm , dann

• Die durch die Schaltkosten verlorene Nettoreisezeit erhöht sich um den Faktor √ λ

Lassen Sie uns alle Ergebnisse in einer Tabelle zusammenfassen:

Zelltopologie

Die Anzahl der Adresspunkte (Viertel) mit Potenz 1 ..................... n
Gesamtstraßenfläche ............................................... .................................... O ( n √ n )
Nettoreisezeit,
ausgegeben, um die Strecke zurückzulegen ............................................. ................... O (√ n )
Nettoreisezeit,
verloren aufgrund von Umstellungskosten ............................................. .................... O (√ n )
Anzahl der Vermittlungsknoten .............................................. .................. O ( n )
Anzahl der Schaltknoten bei gegebener Leistung der Seitenflüsse .......... O ( n )

Beim Vergleich der linearen und zellularen Netze ist es schwierig, nicht zu bemerken, dass die Zunahme der für den Bau erforderlichen Ressourcenintensität und der Zeit, die für eine Reise mit dem Wachstum der Stadt aufgewendet wird, für das erste Netz viel schneller ist als für der zweite. Zum Beispiel benötigt eine Mobilfunkstadt, die aus 100 Vierteln besteht, 10-mal weniger Asphalt, und das Durchfahren benötigt im Durchschnitt 10-mal weniger Zeit als eine lineare Stadt derselben Größe. Daher ist es sinnvoll, Straßennetze mit linearer Topologie nur in sehr kleinen Städten zu verwenden.

Wenn wir für eine Weile die Existenz von Vermittlungskosten vergessen, kann die Mobilfachtopologie als idealer Weg zum Entwerfen von Straßennetzen angesehen werden, da sie eine asymptotisch optimale O-Schätzung sowohl für die durchschnittliche Fahrtlänge als auch für die erforderliche Straßenfläche liefert. In der Tat wird für jede mehr oder weniger „kompakte“ Lage der Stadt (mit wahlfreiem Zugang) die Länge der Reise nicht langsamer als die Quadratwurzel des Stadtgebiets, die wiederum normalerweise direkt proportional zur Bevölkerung ist . Als Ergebnis erhalten wir alle das gleiche O (√ n ).

Die Tatsache, dass eine typische Route in einer Mobilfunkstadt eher an einer „Ecke“ als an einer geraden Linie verläuft, impliziert im Prinzip die Möglichkeit, nach den besten Möglichkeiten für die Planung von Städten zu suchen, aber die Einsparungen in Höhe von 20% (das ist die Maximum, das wir gewinnen können, wenn Autos lernen, durch Wände zu fahren.) Es ist unwahrscheinlich, dass Architekten eines Tages gezwungen werden, die rechteckige Anordnung von Straßen und Wegen aufzugeben.

Die niedrigstmögliche Grenze für die Kosten für den Aufbau (und die Wartung) des Netzwerks kann erreicht werden, indem berücksichtigt wird, dass jedes Auto einen Teil der Fahrspur für seine Bewegung reserviert. Infolgedessen ist die Gesamtfläche der Straßen proportional zum Produkt aus der durchschnittlichen Reisezeit (durchschnittliche Reisedauer) und der Anzahl der Autos in der Stadt: O (√ n ) × O ( n ) = O ( n √) n ) (vergleiche mit der Tabelle für eine Mobilfunkstadt).

Wenn wir über die Zeit sprechen, die aufgrund von Umstellungskosten auf Reisen verloren geht, hängt das Verhältnis zur Zeit für die Entfernung der Entfernung überraschenderweise nicht asymptotisch von der Anzahl der Viertel in der zellularen oder linearen Stadt ab (O (√) n ) / O (√ n ) = O (1), O ( n ) / O ( n ) = O (1)). Mit anderen Worten, der Prozentsatz des Zeitverlusts beim Reisen aufgrund des Wechsels in großen und kleinen Städten ist gleich. Daraus können wir schließen, dass wenn es in einer kleinen Stadt keine ernsthaften Probleme mit den Umstellungskosten gab (wir können vorschlagen, dass sie auf 10 bis 20% gewonnen haben), sie in einer großen Stadt immer noch nicht beobachtet werden sollten, und wenn dies der Fall wäre, dann würden sie existieren bleiben, egal wie die Stadt wuchs und sich vergrößerte.

Da wir nicht wissen, welche der Alternativen zutrifft (oder besser gesagt, dass es Probleme mit dem Verkehr in Großstädten gibt), lohnt es sich, die Topologie einer Mobilfunkstadt so zu verbessern, dass die Umstellungskosten darin zumindest sinken um einen Faktor von einigen konstanten Zeiten.

Nützliche Beispiele für unrealistische Netzwerke

Lassen Sie uns testen, ob die Zelltopologie den Empfehlungen entspricht, die wir durch Analyse der Umschaltung von Flüssen auf der Autobahn entwickelt haben.

1) Vergrößern Sie Straßen nicht ohne Notwendigkeit.
- Ja. Der Verkehr ist auf viele Straßen verteilt (vergleiche mit einer linearen Stadt).

2) Vermeiden Sie es, ein Netzwerk zu entwerfen, in dem der Fahrer auf einer Fahrt mehrmals drehen muss.
- Ja. Jede Fahrt wird höchstwahrscheinlich entlang einer Route durchgeführt, die nur eine Straßenbiegung erfordert.

3) Versuchen Sie, die Zusammenführung von Routen zu verhindern, die sich nur in einem kurzen Abschnitt der Straße überschneiden.
- Hier gibt es vielleicht etwas zu arbeiten. Trotz der minimalen Anzahl von Abbiegungen pro Fahrt führt die Route als Teil des Hauptautobahnflusses durch eine große Anzahl von Vermittlungsknoten (O ( n )), in denen jeweils wertvolle Zeit verschwendet wird.

Die letzte Bemerkung motiviert dazu, die folgende Frage zu untersuchen: „Was ist das Minimum der durchschnittlichen Anzahl von Vermittlungsknoten, durch die eine Fahrt durch ein Straßennetz führen muss, das n Viertel verbindet?“

Die Suche nach einem solchen Netzwerk ist natürlich nur unter der Bedingung sinnvoll, dass die Anzahl der von einem Vermittlungsknoten kombinierten oder geteilten Flüsse von oben vorab um einen bestimmten festen Wert begrenzt ist. Andernfalls können Sie immer ein Straßennetz mit n Adresspunkten und einer einzelnen Mega-Kreuzung präsentieren.


(Der Autor ist unbekannt)

Es ist viel einfacher, das eigentliche Problem zu untersuchen, wenn es zuvor möglich war, zumindest einen Teil der Muster anhand einiger einfacher, wenn auch nicht realistischer Modellbeispiele aufzudecken. Nach dieser Logik werden wir vorübergehend die geometrischen Einschränkungen des Straßenbaus und die Notwendigkeit von Reisenden, Entfernungen zurückzulegen, vergessen und unsere ganze Aufmerksamkeit darauf richten, wie abstrakte Netzwerke das Problem der parallelen Adressierung lösen. In Bezug auf die Vermittlungsknoten nehmen wir vorerst an, dass jeder von ihnen entweder den Fluss in zwei Teile (den Teilungsknoten) teilt oder zwei Flüsse zu einem kombiniert.


Grafik 9

Adressbaum
Es gebe einen Startadresspunkt, an dem ausnahmslos alle Fahrten beginnen, und einen weiteren n Endadressenpunkt, an dem sie mit gleicher Wahrscheinlichkeit enden (Abbildung 9).

Es ist erforderlich, ein Transportnetzwerk aufzubauen, das es dem Fahrer ermöglicht, so wenige Vermittlungsknoten wie möglich zu durchlaufen.

Die naheliegende (für Programmierer) Lösung, die sich hier anbietet, besteht darin, einen ausgeglichenen Binärbaum zu verwenden. Gleichzeitig müssen wir einen einzelnen Startpunkt oben im Baum platzieren und die verbleibenden n Endpunkte jeweils einen in jedem platzieren seiner Blätter (Grafik 10). Das auf die beschriebene Weise aufgebaute Netzwerk wird als direkter Adressbaum bezeichnet.


Grafik 10

Wenn Sie die Richtungen aller Flüsse im direkten Adressbaum in die entgegengesetzte Richtung ändern, erhalten Sie den umgekehrten Adressbaum, dessen Zweck darin besteht, n Startpunkte mit einem einzelnen Endpunkt zu verbinden.

In Fällen, in denen n eine Zweierpotenz ist, verläuft jede Route innerhalb des Adressbaums genau durch log ₂ n Vermittlungsknoten, was zweifellos (asymptotisch) weniger ist als der gleiche Indikator für ein Netzwerk mit Mobilfunk (O (√ n )) oder lineare (O ( n )) Topologie.

Zwei einfachste Arten von logarithmischen Netzwerken

Bei Verwendung von "baumartigen" Netzwerken als Bausteine ​​ist es nicht schwierig, die vorherige Lösung auf den Fall zu verallgemeinern, wenn k Startpunkte vorhanden sind. Es gibt zwei einfache Möglichkeiten, dies zu tun.

Die erste Möglichkeit besteht darin, den umgekehrten Adressbaum zu verwenden, um zuerst die Routen aller Fahrten in einem gemeinsamen Stream zu erfassen und diesen Stream dann mithilfe des direkten Adressbaums in Teilflüsse zu unterteilen, die an sein Ziel adressieren (Abbildung 11, oberes Schema) )


Grafik 11

Wenn k und n Zweierpotenzen sind, verläuft am Ende jede Route genau durch die Schaltknoten log ₂ k + log ₂ n . Wir erklären uns damit einverstanden, uns auf die Netzwerke zu beziehen, die gemäß dem gerade als (Einweg-) logarithmische Netzwerke mit vorläufiger Zusammenführung beschriebenen Algorithmus entworfen wurden.

Der zweite Weg, um dasselbe Problem zu lösen, kann realisiert werden, indem in der ersten Lösung die Reihenfolge der Zusammenführungs- und Teilungsoperationen umgekehrt wird. Die Implementierung kann wie folgt beschrieben werden: Für jeden Startpunkt erstellen wir einen eindeutigen Satz imaginärer Duplikate aller Endpunkte und verbinden ihn anschließend mit diesen Duplikaten (nicht mehr imaginär) mit einem direkten Adressbaum.

Um das Netzwerkdesign zu vervollständigen, muss nur noch jeder Endpunkt mit seinen k imaginären Duplikaten verbunden werden, indem der umgekehrte Adressbaum angewendet wird (Diagramm 11, unteres Schema).

Immer wenn n und k Zweierpotenzen sind, ist die Anzahl der Vermittlungsknoten entlang einer Route innerhalb des neu aufgebauten Netzwerks wieder gleich log ₂ k + log ₂ n . Wir erklären uns damit einverstanden, solche Netzwerke als (Einweg-) logarithmische Netzwerke mit vorläufiger Unterteilung zu bezeichnen .

Umwandlung von Einwegnetzwerken in symmetrische
Im Allgemeinen bezeichnen wir jedes Netzwerk als Einbahnstraße, wenn die durch es verbundenen Adresspunkte streng in Start- und Endpunkte unterteilt sind. Standardmäßig wird für Einwegnetzwerke davon ausgegangen, dass mindestens eine Route für eine mögliche Fahrt von einem Startpunkt zu einem Endpunkt bereitgestellt wird.

Neben einer lebenslangen Reise ist es schwierig, Beispiele zu finden, bei denen einige Adresspunkte nur als Anfang einer Route dienen und andere nur als Ende. Wir werden unsere Argumentation der Realität näher bringen, wenn wir auch Netzwerke einbeziehen, in denen zwei beliebige Adresspunkte durch Routen in beide Richtungen verbunden sind. Wir stimmen zu, solche Netzwerke als symmetrisch zu bezeichnen.

Tatsächlich gibt es keine ideologische Lücke zwischen Einweg- und symmetrischen Netzwerken: Jedes symmetrische Netzwerk kann auch als Einwegnetzwerk verwendet werden, und jedes Einwegnetzwerk, das anfänglich eine gleiche Anzahl von Start- und Endpunkten verbindet, kann es sein in eine symmetrische umgewandelt (Grafik 12).


Grafik 12

Die Diagramme 13a und 13b zeigen die "symmetrischen" Formen des logarithmischen Netzwerks mit vorläufiger Zusammenführung und des logarithmischen Netzwerks mit vorläufiger Teilung. Ihre Beispiele belegen die grundsätzliche Möglichkeit, n Viertel durch einen solchen Netzwerktyp zu verbinden, bei dem die Anzahl der Vermittlungsknoten während einer Fahrt proportional zum Logarithmus der Anzahl der Viertel in der Stadt ist.


Grafik 13 a


Grafik 13 b

Genaue Schätzung der unteren Grenze

Bisher wurde bereits eine Vielzahl von Netzwerken akkumuliert, von denen jedes eine eigene Funktion enthält, die die Abhängigkeit der durchschnittlichen Anzahl von Vermittlungsknoten während der Fahrt von der Anzahl der Adresspunkte in der Stadt beschreibt. Wir wissen jedoch immer noch nicht, wie klein diese Zahl für eine bestimmte Anzahl von Quartalen grundsätzlich sein kann. Die untere Grenzwertschätzung kann unter Verwendung des Informationsansatzes erhalten werden.

Lassen Sie tatsächlich ein Straßennetz n Adresspunkte miteinander verbinden, und die Migrationsbedürfnisse der Bevölkerung sind so, dass jede Reise, egal wo sie begonnen hat, die gleiche Chance hat, irgendwo in der Stadt zu enden.

Um das betreffende Problem zu lösen, generieren wir nach diesem Rezept eine zusätzliche Informationsnachricht: Über einen langen Zeitraum sammeln wir Aufzeichnungen aller Fahrten mit einem festen Startpunkt und notieren zufällig die Adressen, an denen diese Fahrten stattfinden beendet. Die resultierende Nachricht ist eine zufällige Folge, die aus den Namen von n Adresspunkten der Stadt besteht.

Eine Möglichkeit, diese Nachricht an den Mars zu senden, besteht darin, zum einen alle Namen in Binärwörter gleicher Länge zu codieren, wodurch die ursprüngliche Nachricht in eine Folge von Nullen und Einsen umgewandelt wird, und zum anderen die resultierende Folge über einen digitalen Kommunikationskanal zu senden. Da für eine unterscheidbare Codierung des Satzes von n Namen Binärwörter mit einer Länge von log ₂ n erforderlich sind, beträgt die Länge der digitalen Nachricht:

(Anzahl der Datensätze) × log ₂ n Zeichen.

Das Interessanteste ist, dass es laut Informationstheorie unabhängig vom verwendeten Codierungsalgorithmus einfach unmöglich ist, dieselbe Nachricht mit einer geringeren Anzahl von Binärzeichen zu übertragen.

Eine Alternative zur direkten Übertragung der codierten Namen der Endpunkte kann eine Methode sein, bei der für jede Fahrt angegeben wird, in welche mögliche Richtung sich die Route an der nächsten Gabelung biegt. Nach unseren Annahmen können alle Gabeln im Netzwerk nur zwei Zweige haben, daher ist zur Angabe der Richtung jeweils genau 1 Bit erforderlich. Für alle, die eine Karte der Stadt haben und den Startpunkt kennen, reicht die Bitkette aus, um jede Route zu verfolgen und die ursprüngliche Reihenfolge ihrer Ziele wiederherzustellen. Wenn die durchschnittliche Anzahl der während einer Fahrt besuchten Gabeln (Teilungsknoten) x beträgt, beträgt die Länge der Binärnachricht mit der neuen Codierungsmethode: (Anzahl der Datensätze) × x .

Wie bereits erwähnt, kann das neue Codierungsverfahren nicht effizienter sein als das direkte binäre Adressübertragungsverfahren. Daher: (Anzahl der Datensätze) × x ≥ (Anzahl der Datensätze) × log ₂ n , aus diesem Grund:

x ≥ log ₂ n .

Obwohl die letzte Ungleichung ursprünglich für eine Gruppe von Reisen mit einem gemeinsamen festen Startpunkt abgeleitet wurde, stellte sich heraus, dass sie unabhängig von der spezifischen Wahl dieses Punktes war. Deshalb können wir das Ergebnis auf alle Reisen in der Stadt gleichzeitig ausweiten und so den ersten Teil der fraglichen Schätzung erhalten:

P1 ) Vorausgesetzt, dass jede neue Reise die gleiche Wahrscheinlichkeit hat, an einem der n Adresspunkte der Stadt zu enden, darf die durchschnittliche Anzahl der Teilungsknoten pro Route nicht weniger als log ₂ n betragen.

Wenn wir die Uhr geistig zurückdrehen, können wir jeden Endpunkt der Reise in den Startpunkt und jeden Binärknoten der Teilung des Netzwerks - den Binärknoten der Zusammenführung - umwandeln. Dieser kleine Trick ermöglicht es uns, automatisch aus P1 den zweiten, fehlenden Teil der Schätzung zu erhalten:

P2 ) Vorausgesetzt, dass jede abgeschlossene Reise die gleichen Chancen hat, an einem der n Adresspunkte der Stadt zu beginnen, darf die durchschnittliche Anzahl der Zusammenführungsknoten pro Route nicht weniger als log ₂ n betragen.

Wenn wir uns an die Existenz eines logarithmischen Netzwerks mit vorläufiger Zusammenführung und eines logarithmischen Netzwerks mit vorläufiger Teilung erinnern, erhalten wir sofort zwei Beispiele für Netzwerke, die hinsichtlich der Anzahl der Vermittlungsknoten optimal sind, die im Durchschnitt während dieser Zeit besucht werden eine Reise. Mal sehen, ob diese Qualität dazu beiträgt, die Intensität der erzeugten Schaltverluste zu reduzieren.

Switching-Kosten in logarithmischen Netzwerken

Wenn wir die Netzwerke mit vorläufiger Zusammenführung und vorläufiger Teilung vergleichen, sieht das erste aufgrund seiner Einfachheit viel attraktiver aus. Leider hat diese Einfachheit auch eine Kehrseite der Medaille: Die Kombination aller Routen zu einem Stream widerspricht der Empfehlung von i1 und verursacht möglicherweise große Zeitverluste. Das Netzwerk mit vorläufiger Aufteilung scheint die Anforderungen i1 - i3 zu erfüllen. Nach Abbildung 13b erhöht es jedoch tendenziell schnell die Anzahl der verwendeten Straßenglieder und Schaltknoten. Die letztere Qualität kann Netzwerke dieses Typs für den praktischen Gebrauch zu teuer machen.

Wir werden diese Fragen genauer analysieren. Zunächst sind wir uns einig, dass die Stadt dem Migrationsmodell mit "Direktzugriff" folgt und der von einem ihrer Adresspunkte erzeugte Fluss eine Potenz 1 hat.

Verluste in den Netzwerken mit vorläufiger Zusammenführung

In Abbildung 14 sehen Sie ein Diagramm der Flüsse, die sich aus den oben genannten Bedingungen innerhalb des Netzwerks mit vorläufiger Zusammenführung ergeben.


Grafik 14

Es erschien mir zweckmäßig, das Netzwerk selbst in seiner Einbahnstraße darzustellen, was bedeutet, dass jeder Start- und Endpunkt, der mit denselben Nummern in der Tabelle signiert ist, tatsächlich denselben Adresspunkt in der Stadt bedeutet.

Basierend auf dem Diagramm können wir die im Netzwerk erzeugte Schaltkostenintensität berechnen. Beginnen wir in der linken Hälfte, wo durch den umgekehrten Adressbaum alle Routen in einem Fluss gesammelt werden. Jeder Vermittlungsknoten in diesem Teil des Netzwerks stellt den Ort dar, an dem zwei Einbahnstraßen zu einer zusammengeführt werden (Abbildung 15).


Grafik 15

Wenn anfänglich jede der Straßen effizient beladen ist, besteht nach ihrer Zusammenführung keine Notwendigkeit, die Anzahl der Fahrspuren zu verringern, so dass keine entsprechenden Umstellungskosten anfallen sollten.

Nehmen wir an, dass ein Fluss mit Leistung 1 bereits ausreicht, um die Straße auf mindestens zwei Fahrspuren effektiv zu belasten. In diesem Fall kommen wir zu einem eher unerwarteten Ergebnis: Die Zusammenführung von Fahrzeugströmen innerhalb des logarithmischen Netzwerks mit vorläufiger Zusammenführung erfolgt absolut „kostenlos“, ohne Zeitverluste zu verursachen.

Die Berechnung der Kosten, die in der rechten Hälfte anfallen, ist nicht viel schwieriger. Dieser Teil des Netzwerks ist ein direkter Adressbaum, von dem jeder Knoten eine symmetrische Abzweigung ist, die wir bereits untersucht haben. Bei der ankommenden Strömung mit der Leistung p beträgt die Intensität der an der Gabel auftretenden Verluste ( α / 2 ν ) ⋅ p 2/2 . Die Kraft der Strömung, die in die Wurzelgabel eintritt, ist: n , daher ist die Intensität der Verluste im Wurzelknoten: ( α / 2 ν ) ⋅ n 2/2 . In jeder nächsten Generation des Adressbaums verdoppelt sich die Anzahl der Gabeln, und die Leistung des eingehenden Flusses wird halbiert. Infolgedessen hat die Formel der Verluste innerhalb des gesamten Baums die Form:

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 ²

Da die Leistung des von allen Adresspunkten gemeinsam erzeugten Fahrflusses n beträgt, betragen die Zeitkosten pro Fahrt im Durchschnitt ( α / 2 ν ) ⋅ n , wodurch eine lineare Abhängigkeit von der Größe der Stadt gezeigt wird.

Wenn es um abstrakte Netze geht, ist es schwierig, eine aussagekräftige Schätzung der Fläche der von ihnen genutzten Straßen abzugeben. Als alternatives Maß für die strukturelle Komplexität kann die Gesamtleistung aller Seitenströme berechnet werden. Wie geplant sollte der resultierende Wert die Ressourcenintensität beim Aufbau aller vom Netzwerk benötigten Austauschvorgänge widerspiegeln. Ich kann nicht sagen, dass diese Methode in der Praxis immer eine gute Interpretation haben wird, aber es wird wahrscheinlich eine ungefähre Vorstellung vom Umfang der bevorstehenden Arbeit erhalten.

Innerhalb des logarithmischen Netzwerks mit vorläufiger Zusammenführung existieren laterale Flüsse nur im direkten Adressbaum, und ihre Gesamtleistung für jede Knotengeneration ist dieselbe: n / 2. Insgesamt gibt es log ₂ n Generationen von Knoten im Baum, sodass eine neue Methode zur Bewertung der Komplexität eine Schätzung der Komplexität liefert: O ( n log ₂ n ).

Logarithmische Netzwerke mit vorläufiger Zusammenführung

Die Anzahl der Adresspunkte mit Potenz 1 .......................................... .......... n
Durchschnittliche Reisezeit
verloren aufgrund von Wechselkosten:
Asymptotik ................................................. .................................................. ... O ( n )
genauer Wert ................................................ .................................................. ..... ( α / 2 ν ) ⋅ n
Anzahl der Vermittlungsknoten .............................................. ................................ O ( n )
Anzahl der Schaltknoten bei gegebener Leistung der Seitenflüsse ........................ O ( n log ₂ n )

Verluste in den Netzen mit vorläufiger Aufteilung

Wir wenden uns nun der Analyse des logarithmischen Netzwerks mit vorläufiger Unterteilung zu, wobei wiederum angenommen wird, dass das Netzwerk verwendet wird, um die Adresspunkte mit der Leistung 1 in der Stadt mit "wahlfreiem Zugriff" zu verbinden.
Grafik 16 zeigt ein Fragment davon, das aus einem Adresspunkt zusammen mit den direkten und umgekehrten Adressbäumen neben diesem Punkt besteht.


Grafik 16

Zunächst können wir die Intensität der durch das Fragment erzeugten Schaltverluste abschätzen.
Die Kosten, die während der Aufteilung der Flüsse anfallen, können durch die folgende Gleichung I _{t_div1} = ( α / 2 ν ) ⋅ n ^{2 ermittelt werden} , die für den direkten Adressbaum im vorherigen Beispiel 1 anstelle von n abgeleitet wurde . In der Tat haben die direkten Adressbäume in den Diagrammen 16 und 14 dieselbe Tiefe und beinhalten Flüsse mit ähnlicher Leistung (Hinweis: Ähnlichkeit bedeutet die Fähigkeit, einen Wertesatz durch Multiplizieren der Werte eines anderen Satzes mit einer festen Zahl zu erhalten zur Veranschaulichung der Ähnlichkeit zwischen Dreiecken an ihren Seiten). Aufgrund der quadratischen Beziehung zwischen dem Wert der Schaltkosten, die an einer einzelnen Gabelung auftreten, und der Leistung ihres ankommenden Flusses verringert eine gleichzeitige Verringerung aller Flüsse um das n- fache stattdessen die Verluste im gesamten Baum um das n- fache vom alten ( α / 2 ν ) ⋅ n ² erhalten wir einen Wert gleich:

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

Wir können jetzt den Wert der Kosten in der linken Hälfte des Fragments berechnen.
Aufgrund des geringen Werts der kombinierten Straßenflüsse innerhalb des umgekehrten Adressbaums wäre es diesmal nicht sinnvoll, eine Straße zu bauen, die breiter als zwei Fahrspuren ist. Das Zusammenführen unter solchen Bedingungen ist nicht mehr kostenlos: Im Gegensatz zum vorherigen Beispiel gibt es auf der Autobahn Verengungsbereiche (Abbildung 17), in denen notwendigerweise Umstellungskosten anfallen.


Abb. 17

Unter der Annahme, dass der Fahrer die bevorstehende Verengung im Voraus kennt, können wir davon ausgehen, dass der Wechsel von der Sackgasse langsam ist und sich über Hunderte von Metern entlang der Autobahn erstreckt. In diesem Fall haben wir das Recht, auf den Trick zurückzugreifen, den wir zuvor zur Berechnung der Verluste an der symmetrischen Gabel verwendet haben - den gesamten Migrationsfluss q in viele kleine Teile q _i zu teilen und dann jeden von ihnen als Nebenstrom von zu interpretieren die Rampe. Die durch jeden solchen Teilstrom erzeugten Verluste werden nach folgender Formel berechnet:

I _i = ( α / 2 ν ) ⋅ p q _i ⋅ (1 + 1 / s ), hier gibt es jedoch zwei Feinheiten.

Das erste ist, dass Autos nicht weiter als bis zur nächsten Reihe migrieren.
Tatsächlich: Die Strömungen in den beiden zentralen Fahrspuren sollten aufgrund der offensichtlichen Symmetrie immer ungefähr die gleiche Dichte haben, sodass die Fahrer nicht viel Grund haben, die Mittellinie zu überqueren. Aus der gemachten Beobachtung kann geschlossen werden, dass in der Formel für Verluste, die durch partielle seitliche Strömung verursacht werden, s gleich 1 ist.

Wenn die Autos die Randspuren verlassen und in zwei zentrale Spuren wechseln, steigt die Durchflussleistung innerhalb der zentralen Spuren allmählich an und ändert sich jeweils von P / 2 auf P. Die zweite Subtilität ist also die signifikante Abhängigkeit von p von der Anzahl der Teilströme i , die uns schreiben lässt:

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

In dem Fall, in dem viele kleine Teile, in die der Migrationsfluss unterteilt war, alle gleich groß waren, wird die Abhängigkeit p ( i ) durch einen linearen Graphen ausgedrückt (Abbildung 18).


Grafik 18

Um die Verlustintensitätsrate zu berechnen, müssen wir entweder auf die Integration zurückgreifen oder (dies ermöglicht es, eine besonders einfache Form einer integrierbaren Funktion zu erstellen) als p ( i ) den Durchschnittswert in der Grafik nehmen, der 3 P / 4 entspricht. Da der gesamte Migrationsfluss von der Seite jeder Randspur P / 2 beträgt, beträgt die Intensität der Verluste in einem separaten Fusionsknoten:

Ich _verschmelze = 2 ⋅ ( α / 2 ν ) ⋅ (3 P / 4) ⋅ ( P / 2) =

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

Um die Zeitverluste zu ermitteln, die in einem Fragment im umgekehrten Adressbaum erzeugt werden, können wir die Formel für I _merge auf jeden seiner Knoten anwenden:

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 ν ).

Die Gesamtkosten, die innerhalb des Fragments aufgrund der Fusion und Aufteilung der Ströme entstehen, betragen:

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

Ein logarithmisches Netzwerk mit vorläufiger Teilung enthält nur n solcher Fragmente, und genau n Flüsse mit der Leistung 1 werden durch seine Adresspunkte erzeugt, sodass der soeben gefundene Wert genau den Schaltverlusten pro durchschnittlicher Auslösung entspricht.

Tatsächlich ist es für uns wichtiger, nicht einmal eine bestimmte Zahl, die den spezifischen Umstellungskosten entspricht, sondern die Tatsache, dass diese Kosten mit zunehmendem n konstant bleiben. Letzteres macht das logarithmische Netzwerk mit vorläufiger Unterteilung asymptotisch zum wirtschaftlichsten in Bezug auf Schaltverluste unter allen zuvor untersuchten Netzwerktypen.

Leider ist die Führung nicht frei. Trotz des verschwindend kleinen Werts der überwältigenden Anzahl von Flüssen enthält jeder im Netzwerk enthaltene Adressbaum ungefähr 2 n zweispurige Straßenglieder und ungefähr n Schaltknoten voller Größe. Es gibt 2 n Bäume im Netzwerk, was O ( n ² ) Gliedmaßen und Knoten bedeutet, was es nicht nur hinsichtlich der Zeiteffizienz am wirtschaftlichsten macht, sondern auch das teuerste Netzwerk, das unter allen betrachteten Beispielen aufgebaut werden kann.

Was die Summe der seitlichen Strömungen betrifft, so wächst ihr Wert, wie leicht berechnet werden kann, mit der Geschwindigkeit O ( n log2 n ) und hat in diesem Fall keine große Bedeutung.

Logarithmische Netze mit vorläufiger Unterteilung

Die Anzahl der Adresspunkte mit Potenz 1 .......................................... ............ n
Durchschnittliche Reisezeit
verloren aufgrund von Wechselkosten:
Asymptotik ................................................. .................................................. ...... O (1)
genauer Wert ................................................ .................................................. ........ 11/8 ( α / 2 ν ).
Anzahl der Vermittlungsknoten .............................................. ................................... O ( n ² )
Anzahl der Schaltknoten bei gegebener Leistung der Seitenflüsse ........................... O ( n log ₂ n )

Ausgeglichenes logarithmisches Netzwerk

Außergewöhnlich kleine Schaltverluste und gleichzeitig ein beträchtlicher Ressourcenverbrauch des Netzwerkaufbaus, der sich aus der Anwendung eines logarithmischen Netzes mit vorläufiger Aufteilung ergibt, veranlassen uns, einen Weg zu finden, sein Design so zu ändern, dass der Ressourcenverbrauch erheblich reduziert wird, während der Wechselkosten würden sich nicht wesentlich erhöhen.

Offensichtlich ist der Hauptschuldige für eine übermäßig große Anzahl von Straßen im Netz die äußerst geringe Effizienz ihrer Nutzung. Letzteres ist in Abbildung 19 deutlich zu sehen, die ein detailliertes Diagramm der Flüsse innerhalb eines direkten Adressbaums neben dem i-ten Adresspunkt zeigt.


Grafik 19

In der Tabelle gibt die Zahl über dem Ast des Baums die Kraft des Flusses an, der entlang des Astes verläuft, und der Bereich darunter gibt den Satz von Adresspunkten an, zwischen denen dieser Fluss schließlich verteilt wird. Wir gehen davon aus, dass alle in der Tabelle dargestellten Gliedmaßen zweispurige Autobahnen sind. Die Anzahl der Gliedmaßen in jeder Generation des Baums ist unten in der Abbildung angegeben.

Bei sorgfältiger Überlegung stellen Sie möglicherweise fest, dass die Regel, nach der der Fluss in einen bestimmten Knoten aufgeteilt wird, ausschließlich durch die Position dieses Knotens im Adressbaum bestimmt wird und nicht von der Nummer des Adresspunkts abhängt, der diese Auslösungen gestartet hat .

Wenn es mehrere Flüsse gibt, die an denselben Satz von Punkten gerichtet sind, und jeder der Flüsse nicht stark genug ist, um den ihm zugewiesenen Pfad zu füllen, warum kombinieren wir sie dann nicht zu einer Autobahn? Tatsächlich ermöglicht diese im Wesentlichen einfache Idee den Aufbau eines guten abstrakten Netzwerks, das relativ geringe Schaltverluste erzeugt und in Bezug auf die Anzahl der verwendeten Straßen wirtschaftlich ist.

Wenn wir zum Adressbaum des i-ten Punkts zurückkehren, sehen wir, dass der in den Wurzelknoten eintretende Fluss in zwei Sohnflüsse mit einer Kapazität von jeweils 1/2 unterteilt ist. Der erste Sohnfluss besteht aus Fahrten, die an Punkte aus dem Bereich gerichtet sind [1; n / 2], die zweite besteht aus Fahrten, die an Punkte aus dem Bereich [( n / 2) + 1 gerichtet sind; n ].

Nach der oben beschriebenen Idee kombinieren wir die Sohnflüsse des gleichen Typs an jedem ungeraden Punkt und den darauf folgenden Adresspunkt in der Reihenfolge mit einer geraden Zahl. Diese Technik ermöglicht es uns, für jedes ausgewählte Punktepaar anstelle von vier Flüssen mit einer Potenz von 1/2 nur zwei Flüsse mit der Potenz 1 zu haben (Abbildung 20). Wir werden das erhaltene Fragment des zukünftigen Netzwerks als BN ₂ [i; i +1].


Grafik 20

Wenn die Sohnflüsse nicht kombiniert wurden, sondern sich noch im Adressbaum befanden, wurde in der nächsten Generation von Knoten jeder von ihnen wieder in zwei Teile unterteilt, die durch die Leistung und die Größe der Sätze der Adresspunkte gleich sind welche die Reisen gehen.

Warum die etablierte Tradition brechen, denn nach dem Kombinationsprozess haben wir immer noch die gleichen Strömungstypen wie zuvor, aber mit nur weniger Vertretern für jeden Typ. Zu jedem der Ausgänge fließt von BN ₂ [i; i +1] können wir genau dieselbe Teilungsregel anwenden, die für einen Fluss seines Typs innerhalb des Adressbaums gelten würde.

Es gibt keinen Grund, die oben beschriebene logische Konstruktion zum kombinierten Aufteilen derselben Flüsse nicht induktiv zu wiederholen. Grafik 21 zeigt ein Schema zum Kombinieren von zwei Fragmenten
BN ₂ in ein Fragment von BN ₄ , andererseits zeigt Diagramm 22 den gleichen Algorithmus im allgemeinen Fall.


Grafik 21


Grafik 22

Am Ende wird der Prozess der Fragmentvergrößerung abgeschlossen sein und uns zum einzigen Element BN _{n führen} [1; n ]. Wir werden es das ausgeglichene logarithmische Netzwerk nennen (Abbildung 23).


Grafik 23

Untersuchen wir dieses Netzwerk auf die Komplexität und den Wert der erzeugten Schaltverluste.
Basierend auf der induktiven Natur des symmetrischen Netzwerkdesigns kann die Anzahl der in seiner Struktur enthaltenen Vermittlungsknoten durch die wiederkehrende Gleichung beschrieben werden:

Knoten (BN _k ) = 2 Knoten (BN _{k / 2} ) + 2 k ,

mit folgender Einschränkung:

Knoten (BN ₁ ) = 0.

Die Lösung für dieses Gleichungssystem ist die Funktion:

Knoten (BN _n ) = 2 n log ₂ n .

Da das Entwerfen von BN _n log ₂ n Induktionsschritte erfordert, durchläuft jede Fahrt log ₂ n Teilungsknoten und die gleiche Anzahl von Zusammenführungsknoten, die sich auf ihrem Weg abwechseln (Diagramm 24).


Grafik 24

Innerhalb jedes Teilungsknotens erzeugte Verluste:
( α / 2 ν ) ⋅ (1) 2/2 .

Innerhalb jedes zusammengeführten Knotens erzeugte Verluste:
( α / 2 ν ) ⋅ 3 ⋅ (1/2) 2/4 = 3/16 ( α / 2 ν ).

Wenn man bedenkt, dass die Anzahl von beiden im ausgeglichenen Netzwerk n log ₂ n beträgt, können wir den genauen Wert der gesamten Schaltverluste erhalten:
11/16 ( α / 2 ν ) n log ₂ n ,

was pro eine Reise ist:
11/16 ( α / 2 ν ) log ₂ n

Ausgeglichenes logarithmisches Netzwerk

Die Anzahl der Adresspunkte mit Potenz 1 .......................................... .......... n
Durchschnittliche Reisezeit
verloren aufgrund von Wechselkosten:
Asymptotik ................................................. .................................................. ... O (log ₂ n )
genauer Wert ................................................ .................................................. .... 11/16 ( α / 2 ν ) log ₂ n
Anzahl der Vermittlungsknoten .............................................. ............................... O ( n log ₂ n )
Anzahl der Schaltknoten bei gegebener Leistung der Seitenflüsse ....................... O ( n log ₂ n )

Die oben erhaltenen Zahlen ermöglichen es uns, das ausgeglichene Netzwerk als einen guten Kompromiss zwischen der Menge der eingeführten Zeitverluste und der gesamten strukturellen Komplexität zu betrachten. Die Nutzung als Straßennetz einer realen Stadt ist grundsätzlich möglich, aber wirtschaftlich kaum machbar. Es scheint mir, dass der Bereich, in dem die Verwendung des ausgeglichenen Netzwerks tatsächlich von großem Nutzen sein kann, große Informationssysteme mit strengen Anforderungen an die Signalverzögerung sind, wie z. B. Mobilfunk, Internet, verteiltes Rechnen und Multiprozessor-Computer . Für uns ist der größte Wert des Balanced Network die Methode, mit der es entworfen wurde. Wenig später können wir mit einer Modifikation dieser Methode die Netzwerke von linearen und zellularen Städten verbessern, die in der Praxis wirklich entscheidend sind.

Warum historische Städte zum Stau verurteilt sind

Meine Aussage mag unerwartet erscheinen, aber die Antwort auf die Frage, warum sich natürlich entwickelnde Städte, die normalerweise unter Staus leiden, bereits von uns in den vorhergehenden Absätzen gefunden wurden. Was ist das Wesentliche daran?

Tatsache ist, dass viele historische Städte, die nach der Ära der mittelalterlichen Festungen überlebt haben (zum Beispiel fast alle Hauptstädte der „Alten Welt“), aus dieser Zeit die radiale Struktur der Straßen geerbt haben. Leider (für ihre modernen Bewohner) lässt sich ein Straßennetz mit einer ähnlichen Topologie nicht gut skalieren: Die dichte Anordnung radialer Straßen in der Nähe des Zentrums wird an der Peripherie zu selten. Infolgedessen wurden im Zuge des Bevölkerungswachstums die Straßen, die sich ursprünglich am Rande der wenigen Straßen befanden, die zur Festung führten, größer, und die Straßen, die an der Peripherie erschienen, waren kurz und hatten keine ausreichende Transitbedeutung, um darin zu wachsen Breite. Infolgedessen bezieht sich das Straßennetz, das wir heute in großen historischen Städten sehen, am häufigsten auf Verkehrssysteme vom Typ Arterien und in unserer Terminologie aufzu den logarithmischen Netzwerken mit (unvollständiger) vorläufiger Zusammenführung.


(Moskauer Straßen, Foto: Slava Stepanov)

Wenn wir über die Länge der Straßen sprechen, auf denen ein Fahrer fahren sollte, ist die Implementierung dieser Art von Netzwerk nicht schlecht: Die zurückgelegte Entfernung unterscheidet sich oft kaum von der geraden Entfernung und ihrer Der Durchschnittswert in der Stadt wächst, wie es für „anständige“ Verkehrssysteme sein sollte, mit einer Rate von O (√ n ). Das Problem ist, dass mit der Erweiterung der Stadt im logarithmischen Netz mit vorläufiger Zusammenführung die dadurch entstehenden Umstellungskosten zu schnell steigen: Die Zeitdauer, für die die Reise im Durchschnitt aufgrund dieser Netze verlängert wird, hängt von der Anzahl ab von Menschen, die in der Stadt leben wie O ( n ). Es ist klar, dass ab einigen nDiese Zeit wird sich gegen die Nettozeit durchsetzen, um die Entfernung zu überwinden. Mit anderen Worten, es werden Staus in der Stadt auftreten.

Zweifellos ist die Umstrukturierung des Verkehrssystems in historischen Großstädten eine Aufgabe, die gelöst werden kann. Es ist jedoch wichtig zu verstehen, dass der Bau einer weiteren, zwei oder fünf großen Verkehrsadern die Situation in der Stadt zwar geringfügig verbessert, die Grundursache für Staus jedoch nicht beseitigt. Offensichtlich besteht die einzige Möglichkeit, die Nachteile des logarithmischen Netzwerks durch vorläufiges Zusammenführen zu überwinden, darin, ein anderes Netzwerk zu verwenden. Ein guter Kandidat kann hier ein Netzwerk mit zellularer Topologie sein, innerhalb dessen die Zeit zum Zurücklegen der Entfernung zumindest mit der Geschwindigkeit wächst, mit der die Schaltverluste zunehmen.


(Nacht Berlin, Foto: Vincent Laforet)

Vielleicht zeichnet sich das moderne Berlin deshalb, obwohl mit großen Ausfallstraßen, bereits durch eine deutlich sichtbare Zellstruktur aus.

Es gibt weltweit viele interessante Lösungen, wie die Bewohner historischer Städte mobiler werden können, aber der Hauptpreis im Kampf um die Zugänglichkeit des Verkehrs sollte wahrscheinlich den Ingenieuren von Barcelona verliehen werden.


(Barcelonas aktualisiertes Straßennetz, Foto: Vincent Laforet)

Ein genauerer Blick auf die Netzwerke von linearen und zellularen Städten

Nachdem die Analysemethoden in abstrakten Netzwerken gefunden und verfeinert wurden, ist es jetzt an der Zeit, sie auf realistischere Fälle von Städten mit linearer und zellulärer Topologie anzuwenden. In diesem Abschnitt werden wir versuchen, die Merkmale ihrer Transportnetze in allen Einzelheiten zu analysieren, den numerischen Wert der Intensitätsrate der Schaltverluste zu ermitteln, herauszufinden, wie ihr Wert von der Größe der Quartale abhängt, und mögliche Abweichungen und Verbesserungen zu erörtern.

Lineare Stadt
Dieses Mal betrachten wir ein Beispiel für eine Stadt, in der es zwei Einbahnstraßen gibt: Westautobahn mit Verkehr nach Norden und Ostautobahn mit Verkehr nach Süden (Abbildung 25).


Grafik 25

Lassen Sie jedes Quartal einen Fluss mit Leistung 1 erzeugen. In diesem Fall beträgt die Leistung einer Route, die von einem Viertel zum anderen führt, 1 / n .

Zunächst definieren wir die Kraft der Seitenströme auf den Autobahnen. Die Autobahn ist West einziger Weg zum get zum Viertel der i aus dem dem Quartal ( n - i ) lag nach Süden, und der einzige Weg, die das Viertel erhält von der i das Viertel zu dem (ist i - 1) lag nach Norden. _Dies bedeutet, dass die Kraft des Verkehrsaustauschs zwischen der _Westautobahn und dem Viertel i wie _folgt ist:

q _{W_out} = ( n - i ) / n- die Leistung des Seitenflusses, der die westliche Autobahn verlässt,
q _{W_in} = ( i - 1) / n - die Leistung des ankommenden Seitenflusses.

Es ist klar, dass die Kraft der Seitenströme auf der _Oststraße symmetrisch von i abhängt:
q _{E_out} = ( i - 1) / n - die Kraft der Seitenströmung, die die _Oststraße verlässt,
q _{E_in} = ( n - i ) / n - die Leistung des eingehenden Seitenstroms.

Natürlich die Summe der Flüsse, die das i- _te Quartal verlassen:
q _{E_in} + q _{W_in}= ( N - 1) / n ,

fällt mit der Summe aus der er fließt Eingabe:
q _{E_out} + q _{E_out} = ( n - 1) / n ,

und beide dieser Werte hängen nicht von i (jeweils Viertel a hat Durchfluss mit Leistung 1 / n , dieser Durchfluss besteht aus Fahrten, die innerhalb des angegebenen Quartals beginnen und enden.

Um die Leistung der Hauptströme zu berechnen, werden wir eine imaginäre Linie über die Westautobahn auf dem gleichen Niveau wie im i- ten Quartal ziehen. Insgesamt kreuzt sich diese Linie:
(Anzahl der Viertel nach Süden) × (Anzahl der Viertel nach Norden) = (n - i ) ( i - 1) von Routen, die zusammen einen Fluss mit der Leistung erzeugen:

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

Die gleiche Formel:
(Anzahl der Viertel südwärts) × (Anzahl der Viertel Norden) / n ,
sollte die Leistung des Verkehrsflusses in dem östlichen highway auszudrücken P _E : mit anderen Worten

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

Wenn wir die Leistung aller Haupt- und Nebenflüsse kennen, können wir die Verlustintensitätsrate berechnen, die im Netzwerk in der Nähe des i- ten Quartals auftritt :

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 ).

Wenn wir den letzten Ausdruck über i zusammenfassen , erhalten wir die Verlustintensitätsrate, die vom gesamten Netzwerk als Ganzes erzeugt wird.

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

Die Summe ∑ _i ( i / n ) ⋅ (1 - i / n ) ⋅ (1 / n ) für jedes große n kann mit guter Genauigkeit durch das Integral ersetzt werden:

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

Basierend darauf können wir die Intensität der Schaltverluste in einer linearen Stadt mit erhaltenn Viertel mit Strom 1 beträgt:

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

Bis zu diesem Punkt haben wir nur Beispiele betrachtet, in denen Viertel immer Flüsse mit Leistung 1 erzeugten. Betrachten wir, ob sich die Formel für Schaltverluste einer linearen Stadt ändert, wenn für jedes Quartal nicht eine Flussquelle mit Leistung 1 vorhanden ist, sondern - λ (die Viertel werden λ- mal größer).

Nehmen wir eine Stadt mit m Vierteln. Wenn Viertel Ströme mit Strom 1 erzeugt, dann würden die Schaltverluste sein ( α / 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 nQuellen mit einer Leistung von 1. In diesem Fall ist n gleich m ⋅ & lgr; daher:

I (= α / 2 ν ) m ² ⋅ & lgr; ² /3 =
= ( α / 2 ν ) ( m ⋅ & lgr; ) ² / 3 =
= ( α / 2 ν ) N ² /3.

Mit anderen Worten, Wechselverluste in einer linearen Stadt hängen nicht davon ab, wie klein die Fragmentierung ihres Territoriums in Viertel gewählt wird.

Zelluläre Stadt

Stellen Sie sich eine Mobilfunkstadt vor, in der die Autobahnen senkrechter Straßen auf verschiedenen Höhen / Ebenen angeordnet sind. Dies wäre beispielsweise möglich, wenn alle von Norden nach Süden führenden Autobahnen auf Brücken errichtet und auf der Erdoberfläche Autobahnen von West nach Ost gebaut würden. Wenn außerdem alle Autobahnen in beide Richtungen befahren sind, wird das Straßennetz in einer solchen Stadt auf die Standard-Mobilfunktopologie bezogen (Abbildung 26).

Hier geht es natürlich nicht darum, das oben beschriebene Netzwerk ernsthaft in die Praxis umzusetzen: Es würde vor dem Hintergrund der Stadtlandschaft nicht allzu ästhetisch aussehen und darüber hinaus aufgrund der Notwendigkeit eines mehrstufigen Austauschs essen die bessere Hälfte des Straßenraums. Dennoch ist dieses rein hypothetische Netz ein guter Weg, um die notwendigen Schätzungen zu erhalten, die später leicht auf Straßennetze ausgedehnt werden können, die im Hinblick auf ihre Anwendbarkeit in realen Städten wirklich interessant sind.

Wie üblich gehen wir davon aus, dass die Migrationsbedürfnisse der Bewohner durch das Modell des wahlfreien Zugriffs beschrieben werden, und beginnen unsere Betrachtung mit dem Fall, in dem die Leistung aller von einem bestimmten Quartal erzeugten Ströme 1 beträgt.

Im Beispiel der Standardstadt Cellular ist es zweckmäßig, von der etablierten Tradition abzuweichen und als Adresspunkt kein separates Viertel, sondern eine territoriale Zone mit quadratischer Form innerhalb der Kreuzung von Autobahnen und 1/4 aller Viertel zu betrachten daneben. Grafik 27 zeigt die relative Positionierung mehrerer solcher Zonen und ein Verkehrsmuster in einer von ihnen. Diese Grafik zeigt deutlich, dass jeder Fahrer, der das Viertel verlässt, die Möglichkeit hat, auf die Autobahn zu fahren und sich in Richtung einer der vier Seiten der Welt zu bewegen.


Grafik 26

Um den Wert der von der Stadt verursachten Umstellungskosten zu berechnen, berechnen wir die Leistung aller Haupt- und Nebenflüsse in jeder ihrer Gebietszonen. Die Form und die gegenseitige Positionierung der Zonen ermöglichen es uns, auf eine Schachanalogie zurückzugreifen, um das fragliche Problem zu lösen, indem wir die Zonen als Feldzellen und die Bewegung von Autos zwischen ihnen betrachten - als Bewegungen des Turmes (Abbildung 27). Im Allgemeinen kann der Turm in zwei Zügen von einer Zelle in eine andere bewegt werden. Wenn sich beide Zellen auf derselben horizontalen oder vertikalen Linie befinden, dann - in einem Zug.


Schaubild 27

Um viele unbequeme Vorbehalte zu vermeiden, gehen wir davon aus, dass die Bewegung, bei der sich der Turm nirgendwo bewegt, auch nach unseren Regeln zulässig ist. Die Bewegungsroute des Turmes, die aus zwei Bewegungen besteht, von denen eine notwendigerweise vertikal und die andere horizontal ausgeführt wird, wird als die einfachste bezeichnet. Es ist vernünftig, die Bewegung "Stillstand" gleichzeitig als vertikal und horizontal zu betrachten. In diesem Fall stellt sich heraus, dass zwei beliebige Zellen auf der Platine auf genau zwei verschiedenen einfachsten Wegen miteinander verbunden sind.

Für Fahrer ist die einfachste Route der einfachste Weg, mit minimalen Störungen von einer Gebietszone in eine andere zu gelangen. Daher ist davon auszugehen, dass echte Fahrten entlang elementarer Routenlinien stattfinden. Nach dem Modell des "Direktzugriffs" sollte der vom Adresspunkt (Gebietszone) erzeugte Strom mit Leistung 1 gleichmäßig auf alle n = d ² Adresspunkte der Stadt verteilt werden. Daher beträgt die Leistung des Flusses, der entlang einer Routenlinie verläuft, 1 / (2 n ).

Wir können den Fluss mit der Leistung berechnen, die durch die Zelle ( i , j ) in Richtung von Süden nach Norden fließt . Der einfachste Weg kreuzt die Zelle ( i , j) von Süden nach Norden in nur zwei Situationen. Die erste von ihnen (Grafik 28 links):

1a) Die Startzelle der Route befindet sich in einer der letzten ( d - i ) horizontalen Linien (Zeilen).
2a) der Endpunkt der Route ist eine der ersten ( i - 1) Zellen der j- ten vertikalen Linie (Spalte);
3a) Die Route beginnt mit einem horizontalen Abschnitt oder liegt vollständig innerhalb der j- ten Spalte.


Diagramm 28

Die Bedingungen, die die zweite Situation beschreiben, sehen symmetrisch aus (Diagramm 28 rechts):

1a) Der Startpunkt der Route ist eine der letzten ( d - i ) Zellen der j- ten vertikalen Linie.
2a) die Zielzelle der Route befindet sich in einer der ersten ( i - 1) horizontalen Linien;
3a) Die Route beginnt mit einem vertikalen Schnitt oder liegt vollständig innerhalb der j- ten Spalte.

Auf dem Schachbrett gibt es nur 2 × [ d ⋅ ( i - 1) + 1⋅ ( i - 1)] × ( d - i) einfachste für die Anforderungen geeignete Routen, die zusammen einen Strom mit der Leistung erzeugen:

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

Wenn wir j fixieren , erhalten wir die Funktion

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

Beschreibung der Abhängigkeit der Kraft der Strömung, die sich entlang der j- ten vertikalen Autobahn nach Norden bewegt, von der Entfernung zur oberen Grenze der Stadt, gemessen in Zellen.
Es gibt einige mehr oder weniger offensichtliche Beobachtungen bezüglich der Funktionen ( P _SN ) _j ( i ), lassen Sie uns diese diskutieren.

Beginnen wir mit einem Umstand, der schwer zu übersehen wäre: P _SN ( i , j ) praktisch unabhängig vom zweiten Argument. Infolgedessen sind die Funktionen ( P _SN ) _j ( i ) = P _SN (i ) für alle Werte von j die gleiche Form haben , mit anderen Worten, die spezifische Position der Autobahn innerhalb der Zellularstadt beeinflusst ihre Last nicht. Formal ist die letzte Aussage nur für die Autobahn in Richtung Norden bewiesen, aber aufgrund der Symmetrien der Stadt gilt sie automatisch auch für die Autobahn in andere Richtungen.

Betrachten wir nun die Formel für P _SN ( i ) selbst:

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

Wie wir sehen, ist die gesamte Abhängigkeit von P _SN voni auf i liegt im Ausdruck ( i - 1) ⋅ ( d - i ). Dieser Ausdruck kann als Produkt der Längen der rechten und linken Strecke interpretiert werden, in die sich der ganzzahlige Abschnitt der Länge d aufteilt, nachdem das i-te Element davon ausgeschlossen wurde (Abbildung 29a).


Grafik 29a


Abbildung 29b

Es ist klar, dass das Ergebnis des Produkts gleich bleibt, wenn Sie „rechts“ in „links“ und „links“ in „rechts“ ändern (Abbildung 29b). Basierend auf einer so einfachen Beobachtung können wir zwei Schlussfolgerungen ziehen, die im Wesentlichen für uns sehr nützlich sind:

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).

Diagramm 30

Die Kräfte der Hauptströme entlang horizontaler Autobahnen lassen sich leicht anhand von Rotationssymmetrien ermitteln. Formal kann dieser Prozess durch einfaches Ersetzen von i durch j in P _SN ( i ) und eine kleine Korrektur des unteren Index implementiert werden.

Der nächste Schritt besteht darin, die Kraft der Seitenströme zu ermitteln. Fahrten, die auf einer vertikalen Autobahn innerhalb der Zelle ( i , j ) in den Verkehr einfahren oder diesen verlassen , können bequem in vier Kategorien unterteilt werden:

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);

Schaubild 32: abcd

Nachdem wir die Anzahl der Routenlinien angegeben haben , die zu jeder einzelnen Kategorie gehören, können wir schließen, dass die Potenzen aller vier Flüsse gleich und gleich sind:

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

Mit der Werte der Leistungen der Haupt- und Nebenströme in einer vertikalen Autobahn ist es nicht schwierig, den Wert der jeweiligen Schaltkosten zu berechnen. Innerhalb einer einzelnen Zelle ( i , j ) sind die Schaltkosten gleich:

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 ).

Um die Kosten zu ermitteln, die in allen vertikalen Straßen der ganzen Stadt anfallen, müssen wir 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

Viertel, die Flüsse mit Leistung 1 erzeugen, sind eine eher künstliche Einschränkung der Bedingungen des Problems. Wir können die oben erhaltenen Ergebnisse auf die Fälle erweitern, in denen die Leistung des von einer Zelle erzeugten Flusses gleich λ ist .
Lassen Sie die Stadt aus m solchen Zellen bestehen. Wenn alle Zellen Leistung 1 wären, wäre die Intensität der gesamten Schaltverluste I ₁ = 2/3 ⋅ ( α / 2 ν ) ⋅ m √ m . Eine Erhöhung der Anzahl der Fahrten um den Faktor λ wird mit λ multipliziertmal die Leistung aller Haupt- und Nebenflüsse auf den Autobahnen, was wiederum dazu führt, dass alle in der Stadt erzeugten Schaltkosten um den Faktor λ ² steigen . Die neue Formel für die Verlustintensitätsrate hat also die Form:

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

Wenn wir annehmen, dass die Zelle aus λ Adresspunkten mit Potenz 1 besteht, dann die Summe Die Anzahl solcher Punkte ist: n = λm . Drücken wir I als Funktion von n und λ aus :

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

Die durchschnittlichen Kosten pro Fahrt unter den neuen Bedingungen betragen 2/3 ⋅ √ λ ( α / 2 ν ) ⋅ √ n und sind √ λ höher als ihr Wert in einer Stadt, die aus Stadtteilen mit Leistung 1 besteht.

Die letzte Formel besagt, dass bei gleicher Bevölkerung, Bevölkerungsdichte und Gesamtfläche aller Straßen die Umstellungskosten umso höher sind, je größer die vom Architekten ausgewählten Viertel sind. In dem Fall, dass die Bevölkerung der Stadt ungleichmäßig über ihr Territorium verteilt ist, müssen wir natürlich nicht auf geometrische Dimensionen achten, sondern vor allem auf die durchschnittliche Anzahl der Menschen innerhalb des Viertels und ihre Migrationsaktivität.


(Foto im Stadtzentrum von New York: Vincent Laforet)

Die obige Bemerkung ist besonders wichtig bei der Gestaltung von Bereichen mit Wolkenkratzergebäuden. Aufgrund der Kombination aus hoher Bevölkerungsdichte und hoher Mobilität ist es entscheidend, Quartiere in Hochhäusern zu entwerfen, die um ein Vielfaches kleiner sind als bei Standardgebäuden üblich. In Zivilisationen, in denen der Bau von Wolkenkratzern eine lange Geschichte hat, ist die Praxis, sogar einzelne große Gebäude als Viertel zu isolieren, weit verbreitet.

Eine Mobilfunkstadt mit Ampelvorschriften
In jedem Fall muss der Architekt, wenn sich die Linien zweier stark befahrener Autobahnen auf der Karte kreuzen, eine Wahl treffen: entweder eine dieser Straßen zur Brücke heben, damit die andere frei fließen kann, oder die Kreuzung in der Form einer Kreuzung, und lösen Sie den Flusskonflikt durch Ampelregulierung. Die zweite Option wird häufig in Städten gewählt, da sie attraktiv einfach ist, keine großen technischen Strukturen errichten muss und Fußgängern eine einfache Möglichkeit bietet, die Straße zu überqueren.


(Geschäftsviertel von Los Angeles am Nachmittag, Foto: Boris Shein)

Die Verwendung von Ampeln in Netzwerken mit zellularer Topologie hat ihre eigenen Eigenschaften. In Kapitel 1 wurde gezeigt, dass Autos bei richtiger Synchronisation der Ampeln, während sie sich auf derselben Straße bewegen, nicht einmal an Kreuzungen anhalten müssen: Ein grünes Licht leuchtet immer in ihre Richtung. Diese Art von Phänomen wird üblicherweise als Verkehrsmanagement für grüne Wellen bezeichnet. Um dies zu erreichen, müssen die Verkehrsströme abwechselnd in zwei Teile geteilt werden: mit Autos gefüllt und frei von diesen. Als nächstes wird eine solche Art des Ampelbetriebs ausgewählt, dass in der Zeitspanne, in der der nächste "Teil" die Kreuzung entlang einer der Straßen passiert, der vorherige Teil der Autos, die sich entlang der senkrechten Straße bewegen, diese bereits passiert hat, und der nächste man ist noch nicht angekommen (Grafik 33).


Schaubild 33 Das

Verkehrsmanagement für grüne Wellen trägt seine eigenen Kosten und legt bestimmte Einschränkungen für die Gestaltung der Straßen der Stadt fest.

Bei erneuter Betrachtung von Abbildung 33 ist leicht zu erkennen, dass zu einem bestimmten Zeitpunkt genau die Hälfte der Fläche aller Straßen nicht tatsächlich genutzt wird. Um diese Ausfallzeit zu kompensieren, sollten in der aktiv genutzten Hälfte die lokale Leistung der Fahrzeugströme und die Anzahl der dafür erforderlichen Fahrspuren doppelt so groß sein wie in einer Stadt mit Überführungen.

Der zweitwichtigste Umstand bei der Verwendung von grünen Wellen ist die strikte Regelung der zulässigen Größe von Vierteln: Ihre Länge (für Einbahnstraßen) sollte ein Vielfaches der Länge der gefüllten grünen Welle (eines Abschnitts der Strömung) betragen innerhalb dessen eine ungehinderte Bewegung möglich ist), in Höhe von ca. 500 Metern. Wie im vorherigen Absatz erwähnt, erfordern Gebiete mit einer hohen Bevölkerungsdichte eine erhöhte Häufigkeit der Standortbestimmung von Straßen, sodass die Beschränkung des Abstands zwischen Autobahnen (die zulässige Größe der Viertel) möglicherweise zu Verkehrsproblemen führen kann.

Es ist interessant festzustellen, dass sich im Green Wave-Verkehrsmanagement die Vermittlungsregeln innerhalb des Netzwerks geringfügig ändern. Zum Beispiel kann die Hinzufügung eines weiteren Autos zum Hauptverkehrsfluss in den Intervallen zwischen den gefüllten Zonen durchgeführt werden, ohne dass dadurch ernsthafte Umstellungskosten verursacht werden (Punkt 1 in Abbildung 34a).


Diagramm 34

Natürlich muss dieses Auto selbst einige Zeit verlieren, bis es auf die nächste leere Zone wartet, bevor es auf die Autobahn fährt, und danach an der Ampel stehen, bis die nächste gefüllte Zone darauf trifft (Punkt 2, Diagramm 34a) Der Wert dieser Verluste hängt weder von der Größe der Stadt noch von der Verkehrsbelastung auf der Straße ab, daher können sie in großem Umfang vernachlässigt werden.

Ganz anders sieht es aus, wenn ein Auto versucht, den Straßenverkehr zu verlassen (Grafik 34b). Hier gibt es offenbar keine kniffligen Möglichkeiten mehr, die vom Fahrer verursachten Schaltverluste zu verringern. Darüber hinaus verursacht das Verlassen eines zufällig ausgewählten Autos aufgrund der Verdoppelung der lokalen Kraft des Flusses innerhalb der gefüllten Zonen doppelt so viel Zeit wie in einer Stadt mit Überführungen. Insgesamt gleichen sich der billigere „Einstieg“ und der teurere „Ausgang“ aus, was die Ampelzellstadt in dieser Hinsicht fast nicht besser, aber nicht schlechter als die Standardstadt macht.

Überführung Mobilfunkstadt mit Einbahnstraße

Neben der Verwendung von Ampeln gibt es mindestens eine weitere Möglichkeit, die monströsen Abzweigungen der Standardstadt zu vermeiden. Dies impliziert die räumliche Aufteilung von Autobahnen in zwei Richtungen (Abbildung 35).


Schaubild 35

Infolge solcher Änderungen wird sich die Anzahl der Straßen verdoppeln, sie werden alle zu Einbahnstraßen, aber am wichtigsten ist, dass der Austausch erheblich vereinfacht wird (Schaubild 36).


Schaubild 36

Da die Anzahl der Autobahnen, die zu jeder Seite der Welt führen, und die Anzahl der Fahrten, die auf ihnen verlaufen, gleich blieben, fließen die Kräfte aller Flüsse zusammen mit den Umstellungskosten in der Einweg-Mobilfunkstadt und der Standardstadt mit 2 mal größere (linear) Viertel sollten zusammenfallen. Wenn wir die Standard- und die Einwegstadt mit denselben Viertelgrößen vergleichen, sind die Schaltverluste in der zweiten doppelt so hoch.

Fortgeschrittene Straßennetze

"Lineare" Straße

Wie können Schaltverluste in einem Mobilfunknetz reduziert werden? Die Antwort auf diese Frage kann durch Auswahl einer richtigen Analogie mit Hilfe eines kleinen Sachverständigen gefunden werden.

Betrachten wir eine etwas ungewöhnliche Modifikation des Mobilfunknetzes, die impliziert, dass alle von West nach Ost verlaufenden Autobahnen in beide Richtungen verlaufen, während die zu ihnen senkrechten Autobahnen nur in eine Richtung verlaufen: entweder nach Norden oder nach Süden, und diese Richtungen wechseln sich von der Straße ab zur Straße.

Wie immer nehmen wir an, dass die Stadt dem Direktzugriffsmodell folgt und jedes Viertel einen Strom mit Leistung 1 erzeugt.

In diesem Fall erscheint es durchaus plausibel, dass der Fluss innerhalb des Viertels entstanden ist ( i , j) wird wie folgt auf die nächstgelegenen Straßen verteilt: 1/4 davon führt zur horizontalen Straße nach Norden, 1/4 - zur horizontalen Straße nach Süden, 1/4 i / d - zur vertikalen Autobahn nach Norden und 1 / 4 ⋅ (1 - i / d ) - zur zweiten vertikalen Autobahn nach Süden (Grafik 37).

Schaubild 37

Tatsächlich wird nach den zuvor diskutierten Routenalgorithmen laut Statistik die Hälfte der Fahrten von einem horizontalen Abschnitt ausgehen, und für Fahrer, die diese Hälfte bevorzugen würden, sollte es weitgehend egal sein, ob ihr Weg nach Norden oder nach Norden liegt südlich des Viertels ( i , j ). Die verbleibende Hälfte der Fahrten beginnt in einem vertikalen Verkehrsabschnitt und wird zwischen Autobahnen in Richtung Süden und Norden als Verhältnis der Anzahl der nach Süden liegenden Viertel vom Viertel ( i , j ) zur Anzahl der liegenden Viertel aufgeteilt nach Norden davon.

In Bezug auf den Fluss der Fahrten nach innen im Quartal ( i , j) ist die Regel der Aufteilung in Bezug auf die das Viertel umgebenden Autobahnen symmetrisch (Abbildung 38).


Grafik 38

Unter den vier an das Viertel angrenzenden Kreuzungen ( i , j ) können wir die seitlichen Strömungen an der Kreuzung der unteren horizontalen Autobahn und der vertikalen Straße mit Verkehr nach Norden getrennt betrachten (Grafik 38). Der Fluss der Autos, die in die Kreuzung einfahren und von der horizontalen zur vertikalen Straße fahren, beträgt:
1/2 (Anzahl der Viertel in der Horizontalen) × (Anzahl der Viertel in der Vertikalen nicht niedriger als ( i , j )) ⋅ 1 / d ² =
= 1/2 ⋅ d ⋅ i / d ² =
= 1/2 ⋅ i/ d .

Die Kraft der seitlichen Strömung in die entgegengesetzte Richtung beträgt:
1/2 (die Anzahl der Viertel in der Vertikalen ist streng niedriger als ( i , j )) × (die Anzahl der Viertel in der Vertikalen) ⋅ 1 / d ² =
= 1/2 ⋅ ( d - i ) ⋅ d / d ² =
= 1/2 ⋅ (1 - i / d ).

Wenden wir uns nun der gesamten Stadt Cellular zu einer ihrer vertikalen Straßen zu. Nennen wir sie My_street. Aufgrund von Symmetrien werden wir unsere Argumentation in keiner Weise einschränken, wenn wir davon ausgehen, dass die Bewegung entlang der My_street von Süden nach Norden gerichtet ist (Abbildung 39).


Abbildung 39

Abbildung 40 zeigt die Leistung der Haupt- und Nebenflüsse auf der Autobahn entlang der My_street, die, wie der Leser vielleicht bemerkt, ähnlichen Grafiken für die Einbahnstraße einer linearen Stadt unglaublich ähnlich sind (Abbildung 26).



Diagramm 40

In diesen Beispielen stimmen die Flussdiagramme vollständig überein, wenn innerhalb von My_street die seitlichen Flüsse, die sich auf jedes Paar gegenüberliegender Viertel und die horizontale Autobahn darunter beziehen, formal einer imaginären Territorialzelle zugeordnet sind. Wie aus den früheren Tabellen hervorgeht, erzeugt das Straßennetz einer linearen Stadt einige der größten Schaltverluste unter den bereits untersuchten Netzen. Unter diesem Gesichtspunkt sieht das Verkehrsmuster innerhalb der Grenzen einer einzelnen Straße einer Mobilfunkstadt äußerst ineffizient aus und ist ein Element, das in erster Linie verbessert werden sollte.

Erweitertes lineares Städtenetzwerk

Wir stehen also vor der Aufgabe, ein lineares Netzwerk so zu verbessern, dass es nicht zu einem "quadratischen" wird. Der Umstand, der die größte Ineffizienz beim Betrieb des linearen Netzwerks darstellt, ist die Zusammenführung aller Routen zu nur zwei sehr großen Verkehrsströmen. In dieser Situation wäre ein vernünftiger Schritt, die Ströme entlang der beiden Straßenautobahnen in Q gleiche Teile aufzuteilen . Da die Zeitkosten, die durch das Ein- und Aussteigen jedes Autos verursacht werden, proportional zur Verkehrsintensität sind , sollten die Schaltverluste innerhalb einer linearen Stadt aufgrund der Aufteilung der Straßenlinien in Q- isolierte Teile (Abbildung 41a) das Q- fache verringert haben .


Grafik 41

Auch nach dem Bau von zehn Straßen in der Nähe können wir nicht hoffen, dass die Fahrer selbst gleichmäßig auf sie verteilt werden - leider scheint es keine Erfolgschance zu geben. Eine viel nachdenklichere Entscheidung wäre, das Netz so zu gestalten, dass jede Straße nicht zu allen Stadtteilen führt, sondern nur zu einem kleinen „Segment“ der Stadt, in dem es schwierig wäre, ohne die angegebene Straße zu gelangen (Abbildung 41b) )

Sie können eine ähnliche Idee im Bewegungsschema von Aufzügen in mehrstöckigen Gebäuden sehen, in denen Sie mit jedem Aufzug nicht auf allen Etagen, sondern nur in einem bestimmten Höhenbereich ein- und aussteigen können. Wenn wir dieses Konzept akzeptieren, schauen wir uns die Straße r _k genauer an , die den Zugang zum Segment Δ ermöglicht_k = ( x _k , x _{k +1} ] für Fahrten, die (nicht streng) von xk nach Süden begannen (es wird angenommen, dass die Nummerierung der Viertel von unten nach oben erfolgt).

Von jedem Viertel ist diese Zahl geringer (nicht streng) ) als x _k tritt ein q _im Strom mit einer Leistung von & Dgr; _k | / n (1 / n zu jedem Viertel innerhalb von & _Dgr ; _k ) in die Straße r _{k ein} , gleichzeitig wird angenommen, dass es keine Möglichkeit zum Abbiegen gibt von 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).


Schaubild 42

Tatsächlich besteht der Beitrag „interner“ Fahrten zur Leistung von Nebenströmen, der Wert dieses Beitrags übersteigt jedoch niemals | Δ _k | / n daher in dem Fall, in dem x _k >> | Δ _k | kann einfach vernachlässigt werden. Die Leistung p _k des Hauptstroms entlang r _k mit vorgenommenen Vereinfachungen wird durch einen Graphen von zwei geraden Abschnitten mit einem Maximum P _k gleich x _k ⋅ | dargestellt Delta _{der 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 |,

wobei die erste Summe über ein Segment x ∈ [1, x _k ] und die zweite über x ∈ Δ _{k genommen wird} . Die Ausdrücke:

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

( ∑ _x p _k ( x )) / | Delta _{der k} |, x ∈ Delta _{die k}

sind nichts anderes als die Zeit , durchschnittliche Leistung der Strömung entlang r _{die 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 ²

Versuchen wir nun, die Folge x _k der Zahlen jener Viertel zu berechnen, nach denen eine lineare Stadt in Segmente unterteilt werden soll. Als Kriterium für die Auswahl von Segmenten können wir die Anforderung annehmen, dass die maximale Leistung der Verkehrsströme P _k auf den sich nähernden Straßen unabhängig von k den gleichen Wert haben sollte , mit anderen Worten:

x _k ⋅ | Δ _k | = Konst.

Daran erinnern | Δ _k | = x _{k + 1} - x _k können wir die Differenzgleichung ableiten:

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

Unter der Annahme, dass x und k stetige Variablen sind und

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

durch d x / d k ⋅ 1 ersetzt, können

wir die Differenzgleichung durch die Differentialgleichung approximieren:

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

woraus wir eine Lösung für x _k in der allgemeinen Form ableiten können :

x _k = C ₁ √ ( k + C ₂ ).

Es bleibt uns überlassen, den Wert der Konstanten C ₁ und C ₂ anhand ihrer Randbedingungen zu bestimmen , es gibt jedoch eine wichtige Feinheit in dieser Angelegenheit. Anders als in anderen Segmenten begannen alle Autos, die von der Westautobahn mit der Nummer 1 in die Viertel des Segments kamen, ihre Fahrten innerhalb desselben Segments. Infolgedessen hat der Graph der Strömungsleistung auf der ersten Autobahn nach Norden die Form einer regelmäßigen umgekehrten Parabel.

Gleichzeitig wurde bei den a priori-Bedingungen, unter denen die Formel für x _{k erhalten} wurde, im Wesentlichen davon ausgegangen, dass die Flussleistungsgraphen auf allen Autobahnen nahe an einer Dreiecksansicht liegen sollten und die Fahrten selbst hauptsächlich außerhalb des Segments beginnen sollten, in das sie gerichtet sind zu. Diese Anforderungen können mit angemessener Genauigkeit erfüllt werden, wenn wir das erste Segment formal in zwei gleiche Teile teilen, ohne die Anzahl der Straßen zu erhöhen. Die meisten Fahrten entlang der ersten Autobahn beginnen in der südlichen Hälfte und enden in der nördlichen Hälfte. Wenn wir nur sie betrachten, machen wir damit keinen großen Fehler bei der Berechnung der Schaltverluste, aber jetzt hat das Leistungsdiagramm des Hauptstroms nur noch eine dreieckige Form (Abbildung 43).


Grafik 43

Es ist die Mitte des ersten Segments, die als Punkt x ₁ in der Formel für x _{k betrachtet werden sollte} . Dies ermöglicht es uns, die erste Randbedingung zu erhalten:

x ₂ = 2 x ₁ oder

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

C ₂ = - 2/3.

Die zweite Randbedingung ergibt sich aus der Anforderung, dass die Straßen und Segmente von allem genau Q sind , was bedeutet, dass x _{Q + 1} nach dem Viertel mit der größten Anzahl in der Stadt liegen sollte:

C.₁ √ ( Q + 1 - 2/3) = n + 1, von wo aus

C ₁ ≈ ( n + 1) / √ Q .

Daher gilt:

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 ) ² .

Da alle 2 Q- Autobahnen Verluste gleicher Intensität erzeugen, beträgt der Wert der Vermittlungskosten innerhalb des gesamten Netzes:

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

Wie Sie sehen, wurde das gewünschte Ergebnis erzielt: Nach Aufteilung der Hauptautobahnen in Q.Teile nahmen die Verluste tatsächlich um den Faktor Q ab (mit Ausnahme des von 1/3 auf 1/2 erhöhten konstanten Koeffizienten im Vergleich zur Formel für die übliche lineare Stadt). Nun, wir sind auf halbem Weg, es bleibt nur, dieses Ergebnis anzuwenden, um die Stadt mit zellularer Architektur zu verbessern.

'Wolkenkratzeraufzug' in einer Mobilfunkstadt Der

Einfachheit halber betrachten wir ein Beispiel für eine Stadt, in der alle Straßen in eine Richtung verlaufen. Unter Verwendung der Analogie zwischen einer linearen Stadt und den einzelnen Straßen einer zellularen Stadt können wir die Autobahn entlang dieser in Q unterteilenTeile. Standardmäßig wird angenommen, dass der Fahrer beim Verlassen des Viertels jede Autobahn wählen kann, die in der Nähe verläuft. Gleichzeitig gibt es unter allen Autobahnen, die entlang einer Straße verlegt sind, eine Kurve in Richtung eines bestimmten Viertels von genau einer von ihnen. Bei der Festlegung von Regeln sind deren Einheitlichkeit und Einfachheit äußerst wichtig. Werfen wir einen Blick auf Abbildung 44:


In Abbildung 44 haben

alle Straßen die gleiche Ansicht und die gleichen Regeln, welche der Straßen den Zugang zu welchem ​​Viertel ermöglicht. Diagramm 45 zeigt ein Diagramm der zulässigen Abbiegungen zwischen Autobahnen. Wenn man dieses Bild betrachtet, ist es schwer, nicht verwirrt zu werden. Das gleiche wird oft über das U-Bahn-System in einer Großstadt gesagt. In beiden Fällen wird jedoch alles klar und einfach, wenn Sie die Logik der Idee kennen. Die logische Regel für zulässige Abbiegungen klingt recht einfach: Wenn Sie auf einer Autobahn fahren, überqueren Sie Straßen senkrecht zu Ihrer Bewegung und können in ein Viertel direkt dahinter abbiegen. Sie können in jede dieser Straßen abbiegen.


Tabelle 45

Die Topologie „Wolkenkratzeraufzug“ ist sowohl mit Ampelkreuzungen als auch mit Überführungen kompatibel. Es ist schwierig, aber möglich, es auf Netzwerke zu verallgemeinern, die nicht unbedingt eine zelluläre oder lineare Struktur haben. Letzteres ist wirklich wichtig für historische Städte, in denen es unwahrscheinlich ist, dass es eine richtige Entscheidung wäre, die Hälfte der historischen Denkmäler abzureißen, um viele kleine gerade Straßen zu entwerfen, in denen es jedoch bereits ziemlich große Straßen gibt, die mehrere zwei aufnehmen können - oder dreispurige Autobahnen.

Über die Transportprobleme und die Arbeit eines Mathematikers

Es ist angenehm, die 6 Monate mühsame Arbeit abzuschließen. Die Arbeit, die ich geschrieben habe, löst natürlich nicht alle Probleme und Schwierigkeiten der Straßenplanung - dieses Problem erfordert eine große Anzahl sehr vielseitiger und vielseitiger Mitarbeiter. Dennoch bieten die Ergebnisse die Möglichkeit, wichtige Fehler in bereits gebauten Städten zu erkennen und Methoden zur Vermeidung solcher Fehler in der Zukunft bereitzustellen. Dieser Artikel war nicht als Nachschlagewerk gedacht, das alle möglichen Fälle abdeckt, denen ein Ingenieur in der Praxis begegnen kann. Ich war der Ansicht, dass mein Hauptziel darin besteht, einen neuen Standpunkt zu vertreten, einen neuen Weg zu finden, um über das Problem zu argumentieren und darüber zu sprechen der Leser mit dem notwendigen Minimum an einfachen Modellbeispielen, die vom Leser weiter ausgebaut werden könnten.

Es wird traurig, wenn man merkt, wie viel Zeit die Stadtbewohner im Stau verloren haben, nur weil es zur richtigen Zeit keinen Mathematiker gab, der den Abend mit einem vollständig lösbaren Problem verbringen konnte. Wie viele solcher Probleme umgeben noch unser Leben oder verstecken sich in Ihrem Beruf? Sitzt eine Person bei der Arbeit in Ihrer Nähe, deren Werkzeuge ein Bleistift und ein Blatt Papier sind?

Ich hoffe, dass sich alles zum Besseren ändert.

Ich möchte Janine Lacroix (Pseudonym) meinen aufrichtigen Dank für ihre Arbeit bei der Übersetzung dieses Textes vom Russischen ins Englische aussprechen.
Vielen Dank für Ihre Aufmerksamkeit und viel Glück!
Sergei Kovalenko

2019
magnolia@bk.ru


(Foto: Vincent Laforet)