Frank-Wolfe und der Verkehr verständlich erklärt

Jede Fahrerin wählt den schnellsten Weg, doch ein Weg wird langsamer, je mehr ihn wählen. Diese Seite erklärt, wie man berechnet, wohin der Verkehr dann fährt, und warum die letzte Genauigkeit so lange dauert.

Zuletzt aktualisiert: 11. November 2026

Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.

Eine Stadt am Montagmorgen

Stellen Sie sich eine Stadt am Montagmorgen vor. Viele Menschen fahren aus ihren Stadtteilen zur Arbeit. Jede Fahrerin kennt mehrere Wege und nimmt den, der gerade am schnellsten ist.

Doch wie schnell ein Weg ist, hängt davon ab, wie viele ihn wählen. Ein leerer Weg ist schnell. Nehmen ihn alle, staut er sich und ist nicht mehr der schnellste. Dann weichen einige auf einen anderen aus, der dadurch langsamer wird.

Irgendwann kommt das zur Ruhe. Dann ist kein benutzter Weg länger als ein anderer, und niemand spart Zeit durch einen Wechsel. Dieser Zustand heißt Nutzergleichgewicht. Die Frage dieser Seite: Wie berechnet man ihn für eine Stadt mit vielen Straßen?

Ein Rechenbild der Stadt

Zu dieser Seite gehört ein Programm zum Ausprobieren im Browser, kurz Demo. Der erste Knopf unten öffnet es, der zweite führt zum zweiten Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

Die Demo rechnet mit einem vereinfachten Rechenbild (Fachwort: Modell). Es ist eine erfundene Stadt mit 8 mal 8 Kreuzungen und mehreren Stadtteilen. Zwischen je zwei Stadtteilen fahren Menschen. Jede Straße wird langsamer, je voller sie ist. Es sind so viele kleine Fahrer, dass man sie wie Wasser beliebig teilen darf: Ein Weg kann auch nur einen kleinen Teil von ihnen tragen. Jede Fahrerin kennt die Fahrzeit aller Wege. Die Aussagen in diesem Teil beschreiben dieses Rechenbild, nicht eine echte Stadt.

So rechnet das Verfahren

Das Verfahren heißt Frank-Wolfe. Es arbeitet in Runden:

• Start: Alle fahren den Weg, der bei leeren Straßen am kürzesten ist.
• Messen: Wie lange braucht jede Straße bei diesem Verkehr? Die beliebten Straßen sind jetzt voll und langsam.
• Gedankenspiel: Was geschähe, wenn alle zugleich auf den Weg wechselten, der jetzt am schnellsten ist? Das Verfahren rechnet es nur durch, ohne es zu tun.
• Ein Stück weit: Wirklich wechselt nur ein Teil der Fahrer, der Rest bleibt. Danach beginnt die nächste Runde.

Warum wechseln nicht alle? Denken Sie an eine Radioansage: Die Umgehungsstraße ist frei. Fahren alle dorthin, ist sie sofort verstopft. Das Gedankenspiel zeigt deshalb nur die Richtung, nicht das Ziel.

Wie groß ist das Stück?

Hier unterscheiden sich vier Regeln, die die Demo nebeneinander zeigt:

• Gesucht: Das Programm probiert aus, welcher Teil die Lage am meisten verbessert.
• Nach Plan: Der Teil wird von Runde zu Runde kleiner, nach einer festen Vorschrift ohne Ausprobieren.
• Mit Gedächtnis: Das Verfahren merkt sich, in welche Richtung es in der vorigen Runde geschoben hat, und wählt die neue Richtung so, dass sie diese Arbeit nicht teilweise wieder aufhebt. Der Teil wird dabei gesucht.
• Immer gleich: Jede Runde wechselt derselbe Anteil. Als Gegenprobe: Der Verkehr springt immer wieder hin und her und kommt nicht zur Ruhe.

Der lange Endspurt

Wie weit ist die Rechnung vom Ruhezustand entfernt? Dafür gibt es die Restlücke. Stellen Sie sich vor, alle wechselten gleichzeitig auf die jetzt schnellsten Wege. Die Restlücke ist die Fahrzeit, die alle zusammen dadurch noch sparen würden, gerechnet mit den jetzigen Fahrzeiten. Sie wird als Anteil der gesamten Fahrzeit angegeben. Im Ruhezustand ist sie null.

Drei Stufen der Genauigkeit: Das Ergebnis heißt grob, wenn die Restlücke unter einem Hundertstel der gesamten Fahrzeit liegt, fein unter einem Tausendstel und sehr fein unter einem Zehntausendstel. Die Hauptansicht der Demo rechnet höchstens 200 Runden.

In der Beispielstadt mit der Regel „Gesucht“ ist das Ergebnis nach 4 Runden grob, nach 21 Runden fein und nach 102 Runden sehr fein. Die nächste Stufe, unter einem Hunderttausendstel, erreicht die Rechnung in 200 Runden nicht. Jede weitere Stufe dauert ein Mehrfaches der vorigen.

Warum zieht sich das Ende? Gegen Schluss fahren zwischen zwei Stadtteilen viele Fahrer auf zwei Wegen, die fast gleich schnell sind. Das Gedankenspiel kennt aber nur „alle auf den einen Weg“. Mal ist der eine Weg um ein winziges Stück schneller, mal der andere, und jedes Mal wäre der Vorschlag viel zu groß. Das Verfahren darf nur ein kleines Stück davon übernehmen. Das ist die bekannte Erklärung; die Demo misst nur die Dauer.

Bei dichtem Verkehr zieht sich der Endspurt noch mehr. Wir rechnen fünf erfundene Städte mit halb so viel, mit gleich viel und mit doppelt so viel Verkehr wie in der Beispielstadt. Im Mittel brauchen sie bis zum feinen Ergebnis bei halb so viel Verkehr 2 Runden und bei doppelt so viel Verkehr mehr als 249, denn in einer Stadt reichen sogar 300 Runden nicht (dieser Vergleich rechnet bis zu 300 Runden statt 200). Bei gleich viel Verkehr liegt der Wert dazwischen.

Wie genau muss man rechnen?

Beim groben Ergebnis liegt die Gesamtfahrzeit aller Fahrer weniger als 2 Prozent daneben. Wenn nur sie interessiert, genügt in der Beispielstadt also schon das grobe Ergebnis. Wie viel Verkehr auf einer einzelnen Straße fährt, stimmt später. Der Fehler der Gesamtfahrzeit schrumpft von Stufe zu Stufe schneller als der Fehler der am stärksten abweichenden Straße (dieser gemessen an der gesamten Nachfrage). Wer wissen will, wie voll eine bestimmte Straße wird, etwa für eine Maut, muss deshalb weiterrechnen.

Ruhezustand und bestes Ergebnis für alle

Der Ruhezustand ist nicht das Beste für alle zusammen. Jede Fahrerin sieht nur ihre eigene Fahrzeit, nicht die Verzögerung, die sie anderen verursacht. Könnte eine Zentrale die Wege zuteilen, wäre die Gesamtfahrzeit in der Beispielstadt kürzer: Im Ruhezustand ist sie um etwa 4 Prozent länger.

Häufige Missverständnisse

• „Zeigen zwei Rechnungen verschiedene Wege für die Fahrer, ist eine falsch.“ Nicht unbedingt. Im Ruhezustand ist eindeutig, wie viel Verkehr auf jeder Straße fährt, aber nicht, welche Fahrer welchen Weg nehmen. Ein Lehrbeispiel der Demo: zwei Strecken hintereinander, jede mit zwei gleichen Straßen nebeneinander. Im Ruhezustand fahren auf jeder der vier Straßen gleich viele. Wer von den Fahrern welche Straße nimmt, ist dabei egal: Es passen viele Verteilungen.
• „Das Verfahren mit Gedächtnis ist immer schneller.“ Im Mittel über viele erfundene Städte ist es klar schneller, aber nicht in jeder: In 2 von 40 Städten dauerte es bis zum feinen Ergebnis um zwei bis drei Runden länger als die Regel „Gesucht“.

Woran Sie das im Alltag erkennen

• Die Strecke, die das Navigationsgerät gestern als schnellste zeigte, ist heute voll, weil viele demselben Rat gefolgt sind.
• Zwei Wege zur Arbeit brauchen nach einer Weile fast gleich lange, weil Pendler vom langsameren zum schnelleren wechseln.

Wie ernst ist das Rechenbild zu nehmen?

Das Rechenbild kennt nur eine Fahrzeugart und keine Tageszeit. Echte Fahrer folgen auch Gewohnheiten. Gemessen ist die Rechendauer an erfundenen Städten, nicht an echten Verkehrsdaten.

Was Sie mitnehmen:

• Fragen Sie bei einer Zahl aus einer Verkehrsrechnung, wie fein gerechnet wurde und ob es um die Summe oder um eine einzelne Straße geht.
• Grobe Ergebnisse kommen schnell, feine kosten ein Mehrfaches. Lohnt sich die letzte Stelle für Ihre Frage?
• Was für alle zusammen am besten wäre, kann sich von dem unterscheiden, was jeder für sich wählt. Fragen Sie, welches von beiden gemeint ist.

Hinweis: Alle Demos rechnen mit synthetischen oder frei verfügbaren Beispieldaten und laufen auf einem externen Anbieter (Datenschutz). Bitte geben Sie darin keine vertraulichen oder personenbezogenen Daten ein. Die Ergebnisse gelten für die jeweilige Demo-Instanz und lassen sich nicht ungeprüft auf reale Fälle übertragen; für darauf gestützte Entscheidungen übernehme ich keine Gewähr.

Modell und Annahmen

Dieser Teil ist eigenständig lesbar. Er beschreibt die statische Verkehrsumlegung mit stetig teilbarer Nachfrage und das Frank-Wolfe-Verfahren mit drei Schrittweitenregeln.

• Netz und Nachfrage: ein gerichteter Graph mit Kanten \(e\); der Verkehr auf der Kante \(e\) heißt \(x_e\), der Vektor aller Kantenflüsse \(x\). Die Voreinstellung ist ein Stadtgitter aus 8 × 8 Kreuzungen mit Straßen in beide Richtungen (224 Kanten), 6 Zonen (Knoten mit Nachfrage) und 30 geordneten Zonenpaaren \(w\). Die Nachfrage \(q_w\) ist stetig teilbar (unendlich viele kleine Fahrer) und wird von einem Lastfaktor skaliert (voreingestellt 1,0). Dazu kommen zwei Lehrnetze: Pigou (zwei parallele Straßen von A nach B, Beschreibung unten) und „Zwei Stufen“ (A, M und B in einer Reihe: von A nach M zwei gleiche parallele Straßen, von M nach B ebenfalls zwei; die Nachfrage fährt von A nach B, und im Gleichgewicht trägt jede der vier Straßen 5).
• Fahrzeit (BPR-Form): \(t_e(x_e)=t^0_e+b_e\,(x_e/c_e)^p\) mit Freifahrtzeit \(t^0_e\) (im Gitter 2 bis 6), \(b_e=0{,}15\,t^0_e\), Kapazität \(c_e\) (20 bis 45) und \(p=4\); die Lehrnetze haben \(p=1\).
• Nutzergleichgewicht (Wardrop 1952): Für jedes Zonenpaar sind alle benutzten Wege gleich lang und nicht länger als jeder unbenutzte. Äquivalent dazu löst der Kantenverkehr ein konvexes Programm (Beckmann 1956). Die Kantenflüsse sind eindeutig, die Wegeflüsse im Allgemeinen nicht.
• Systemoptimum: die kleinste Gesamtfahrzeit \(\sum_e x_e t_e(x_e)\); es ist dasselbe Programm mit den Grenzkosten statt der Fahrzeit.
• Kennzahlen: die relative Lücke \(g_k\) (unten) und der Aufwand, gezählt in Kürzeste-Wege-Läufen (6 je Iteration, einer je Ursprungszone) und nie in Sekunden. \(k\ge0\) zählt die Iterationen; \(x^0\) ist der Alles-oder-nichts-Verkehr bei Freifahrtzeiten, und \(g_k\) gehört zum Verkehr \(x^k\).
• Messbedingungen: Das Standardnetz ist das Gitter mit der Voreinstellung (8 × 8, 6 Zonen, Last 1,0) für ein fest gewähltes Zufallsnetz, Frank-Wolfe mit exakter Schrittweite und höchstens 200 Iterationen. Zufällig erzeugt werden Freifahrtzeit und Kapazität jeder Straße, die Lage der Zonen und die ganzzahlige Nachfrage je Zonenpaar (zwischen 5 und 15, mal Lastfaktor). Verteilungen laufen über 40 feste Zufallsnetze (200 Iterationen), die Lastreihe über 5 Netze (bis 300 Iterationen). „Nicht erreicht“ zählt als Grenze plus eins (201 bzw. 301).

Die Formeln

Das Nutzergleichgewicht löst das Beckmann-Programm \(\min Z(x)\) unter Flusserhaltung je Zonenpaar. Seine Zielfunktion ist

\[\min_x\ Z(x)=\sum_e\int_0^{x_e}t_e(s)\,ds\]

Sind alle Fahrzeitfunktionen streng steigend (wie im Gitter), ist \(Z\) streng konvex in \(x\); daraus folgt die Eindeutigkeit der Kantenflüsse. Das Systemoptimum minimiert \(\sum_e x_e t_e(x_e)\). Das ist dasselbe Programm mit den Grenzkosten, die ein zusätzlicher Fahrer der Allgemeinheit verursacht:

\[t_e(x_e)+x_e t_e'(x_e)\]

Bei der BPR-Form sind sie \(t^0_e+b_e(p+1)(x_e/c_e)^p\). Frank-Wolfe rechnet in jeder Iteration mit den Kosten am aktuellen Verkehr \(x^k\) (im Systemoptimum mit den Grenzkosten): Der Alles-oder-nichts-Verkehr \(y^k\) legt jedes Zonenpaar komplett auf einen kürzesten Weg (ein Dijkstra-Lauf je Ursprungszone), und der Verkehr wandert ein Stück dorthin:

\[x^{k+1}=x^k+a_k(y^k-x^k)\]

Die Schrittweite \(a_k\) ist bei der exakten Regel die Nullstelle der Richtungsableitung (Bisektion), bei MSA \(1/(k+2)\) ohne Suche (der erste Schritt mischt je zur Hälfte) und bei der Gegenprobe fest 0,5. Das Maß für die Annäherung ist die relative Lücke, die in jeder Iteration kostenlos anfällt:

\[g_k=\big(t(x^k)^\top(x^k-y^k)\big)/\big(t(x^k)^\top x^k\big)\ge0\]

Dabei ist \(t(x^k)\) der Vektor der Fahrzeiten (im Systemoptimum der Grenzkosten; der Nenner ist dann keine Gesamtfahrzeit mehr, und die Schranke unten gilt für die Zielfunktion des Systemoptimums). Die Lücke ist 0 genau im Gleichgewicht und misst, wie viel Fahrzeit ein gleichzeitiger Wechsel aller auf die kürzesten Wege noch sparen würde, gerechnet zu den Zeiten vor dem Wechsel.

Das konjugierte Frank-Wolfe (Mitradjieva und Lindberg 2013) ersetzt \(y^k\) durch einen Zielpunkt \(s^k\), dessen Richtung \(s^k-x^k\) zur vorigen Zielrichtung \(s^{k-1}-x^k\) konjugiert ist (Begriff und Herleitung unten):

\[s^k=\alpha_k s^{k-1}+(1-\alpha_k)y^k\]

\[\alpha_k=\dfrac{(s^{k-1}-x^k)^\top H_k\,(y^k-x^k)}{(s^{k-1}-x^k)^\top H_k\,(y^k-s^{k-1})}\in[0,1-\delta]\]

Dabei ist \(H_k\) die diagonale Hesse-Matrix von \(Z\) am Punkt \(x^k\) und \(\delta\) eine sehr kleine positive Zahl; die Richtung ist \(s^k-x^k\), die Schrittweite wird wie bei Frank-Wolfe gesucht. Das Verfahren beginnt mit der Frank-Wolfe-Richtung neu (\(\alpha_k=0\)), wenn der Verkehr schon auf dem alten Zielpunkt liegt, wenn \(\alpha_k\) an die Grenze \(1-\delta\) stößt oder wenn die Richtung keine Abstiegsrichtung ist.

Herleitungen Schritt für Schritt

Die folgenden Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.

Alles-oder-nichts löst die linearisierte Aufgabe.

• Schritt 1: Es gilt \(\partial Z/\partial x_e=t_e(x_e)\), also ist \(t(x)\) der Gradient von \(Z\). Die linearisierte Aufgabe ist \(\min_y t(x)^\top y\) über alle zulässigen Verkehre \(y\).
• Schritt 2: Die Zulässigkeit (Flusserhaltung je Zonenpaar) trennt die Aufgabe nach Zonenpaaren. Je Zonenpaar \(w\) ist das Minimum erreicht, wenn die ganze Menge \(q_w\) auf einem kürzesten Weg bezüglich \(t(x)\) fährt. Das ist \(y^k\).
• Schritt 3: Da \(x^k\) selbst zulässig ist, gilt \(t(x^k)^\top(y^k-x^k)\le0\). Die Richtung \(y^k-x^k\) steigt also nicht an, und \(g_k\ge0\).

Die Lücke ist null genau im Gleichgewicht und begrenzt den Fehler von \(Z\).

• Schritt 1: \(t(x)^\top x\) ist die Summe der Wegezeiten, gewichtet mit den Wegeflüssen. \(t(x)^\top y\) ist dieselbe Summe, aber mit der kürzesten Wegezeit je Zonenpaar, also \(\sum_w q_w\,\tau_w\) mit der kürzesten Wegezeit \(\tau_w\). Daher ist \(t(x)^\top x\ge t(x)^\top y\).
• Schritt 2: Gleichheit gilt genau dann, wenn jeder benutzte Weg ein kürzester ist. Das ist Wardrops Bedingung, also ist \(g=0\) genau im Gleichgewicht.
• Schritt 3: Für das Gleichgewicht \(x^*\) liefert die Konvexität \(Z(x^*)\ge Z(x)+t(x)^\top(x^*-x)\ge Z(x)-t(x)^\top(x-y)\), denn \(y\) minimiert \(t(x)^\top y\). Also gilt \(Z(x)-Z(x^*)\le g\cdot t(x)^\top x\). Die Lücke begrenzt den Fehler der Beckmann-Zielfunktion, eine entsprechende Schranke für die Gesamtfahrzeit oder die Kantenflüsse liefert sie nicht; deren Fehler misst die Demo gesondert gegen eine sehr genaue Lösung.

MSA ist ein Mittelwert, der feste Schritt vergisst die Vergangenheit. Es gilt \(k\ge0\),\(x^0\) ist der Start und \(y^k\) der Alles-oder-nichts-Verkehr zu \(x^k\).

• Schritt 1: MSA mischt mit \(a_k=1/(k+2)\), also \(x^{k+1}=x^k+\tfrac{1}{k+2}\,(y^k-x^k)\). Für \(k=0\) ist \(x^1=\tfrac12(x^0+y^0)\).
• Schritt 2: Induktion: Gilt \(x^{k}=\tfrac1{k+1}\big(x^0+y^0+\dots+y^{k-1}\big)\), so folgt \(x^{k+1}=\tfrac{1}{k+2}\big((k+1)\,x^{k}+y^k\big)=\tfrac1{k+2}\big(x^0+y^0+\dots+y^{k}\big)\).
• Schritt 3: MSA ist also das Mittel aus dem Start und allen bisherigen Alles-oder-nichts-Verkehren. Frühe, an verstopften Straßen gewonnene Richtungen verlieren ihr Gewicht nur wie \(1/(k+2)\).
• Fester Schritt 0,5: Hier ist \(x^{k+1}=\tfrac12 x^k+\tfrac12 y^k\), der jüngste Alles-oder-nichts-Verkehr hat also in jeder Runde das Gewicht ein Halb. Solange sich \(y^k\) nicht dem aktuellen Verkehr nähert, kann der Verkehr nicht zur Ruhe kommen.

Konjugiert und die Formel für \(\alpha_k\). Zwei Richtungen \(u\) und \(w\) heißen konjugiert bezüglich \(H_k\), wenn \(u^\top H_k w=0\) gilt. Dann macht ein Schritt längs \(w\) nicht rückgängig, was längs \(u\) schon erreicht ist (gemeint ist die quadratische Näherung von \(Z\) mit der Matrix \(H_k\)); das ist die Rolle des „Gedächtnisses“.

• Schritt 1: Setze \(u=s^{k-1}-x^k\) und \(v=y^k-x^k\). Dann ist \(s^k-x^k=\alpha_k u+(1-\alpha_k)v\).
• Schritt 2: Konjugiertheit von \(s^k-x^k\) zu \(u\) heißt \(u^\top H_k\big(\alpha_k u+(1-\alpha_k)v\big)=0\), also \(\alpha_k\,(u^\top H_k u-u^\top H_k v)=-\,u^\top H_k v\).
• Schritt 3: Löst man nach \(\alpha_k\) auf und beachtet \(v-u=y^k-s^{k-1}\), erhält man \(\alpha_k=\dfrac{u^\top H_k v}{u^\top H_k (y^k-s^{k-1})}\), die oben gezeigte Formel.

Durchgerechnet: das Pigou-Netz. Zwei parallele Straßen von A nach B, die erste mit fester Fahrzeit 1, die zweite mit einer Fahrzeit gleich dem Verkehr auf ihr; die Nachfrage ist 1. Sei \(s\) der Anteil auf der zweiten Straße.

• Gleichgewicht: Bei Freifahrtzeiten ist die zweite Straße die kürzere, Alles-oder-nichts legt alles auf sie (0 Iterationen). Mit \(s=1\) braucht die zweite Straße die Zeit 1, genauso lang wie die erste. Niemand spart durch einen Wechsel, die Gesamtfahrzeit ist 1.
• Systemoptimum: Die Gesamtfahrzeit ist \(1\cdot(1-s)+s\cdot s=1-s+s^2\), minimal bei \(s=\tfrac12\) mit dem Wert 0,75. Mit Grenzkosten gerechnet: Die zweite Straße kostet \(t+x\,t'=2s\), gleich dem Wert 1 der ersten genau bei \(s=\tfrac12\).
• Preis der Anarchie: \(1/0{,}75=4/3\). Die Demo rechnet dieses Lehrnetz von Hand nach.

Befunde

Voraussetzungen der ersten Tabelle: Standardnetz, Nutzergleichgewicht, höchstens 200 Iterationen. Die Zahlen sind die Iterationen, nach denen die Lücke erstmals unter der Schwelle liegt; „–“ heißt, dass die Schwelle nicht erreicht wurde.

Schrittweite	Lücke unter 1e-2	unter 1e-3	unter 1e-4	unter 1e-5
exakte Suche	4	21	102	–
MSA (Schritt \(1/(k+2)\))	7	57	–	–
konjugiert (mit Suche)	4	15	24	69

Am Ende der 200 Iterationen liegt die Lücke bei der exakten Suche bei 5,8e-5, bei MSA bei 2,9e-4; die Gesamtfahrzeit beider ist nach diesen 200 Iterationen 6 898 (die 6 897 in der Zeile zum Preis der Anarchie stammt aus einem anderen Lauf, siehe dort). Das konjugierte Verfahren ist bei einer Lücke unter 1e-6 nach 145 Iterationen fertig. Rechnung dieser Seite: Von einer Stufe zur nächsten wächst die Iterationszahl der exakten Suche auf das Fünffache. Eine Schranke der Ordnung \(1/\varepsilon\) für die Iterationszahl legt grob den Faktor 10 je Dezimalstelle nahe, begrenzt aber nicht das Verhältnis zweier gemessener Zahlen. Im Standardnetz liegt es bei rund 5; in der Lastreihe bei Last 1,0 beträgt der Quotient der Mittel bis 1e-4 und bis 1e-3 (218 durch 23,6) mindestens das Neunfache, weil 218 selbst eine Untergrenze ist.

Die zweite Tabelle nennt weitere Messreihen mit ihren Voraussetzungen.

Frage	Befund
Wie hängt der Endspurt von der Last ab? (Frank-Wolfe mit Suche, Mittel über 5 Netze)	Iterationen bis 1e-3 bei Last 0,5 / 1,0 / 1,5 / 2,0: 2,0 / 23,6 / 117 / 249 (die 249 ist eine Untergrenze: 1 von 5 Netzen erreicht 1e-3 in 300 Iterationen nicht). Bis 1e-4: 4,2 bei Last 0,5 und 218 bei 1,0 (Untergrenze: 2 von 5 Netzen erreichen 1e-4 nicht); ab 1,5 wird 1e-4 in 300 Iterationen nicht erreicht. Im Standardnetz mit doppelter Last: 1e-2 nach 35 Iterationen, 1e-3 in 200 nicht mehr.
Wie genau muss man rechnen? (Standardnetz, exakte Suche, gegen eine sehr genaue Lösung: konjugiert bis Lücke 1e-9)	Bei Lücke 1e-2 (Iteration 4) liegt die Gesamtfahrzeit 1,6 % ihres Wertes daneben und der größte Kantenflussfehler bei 2,0 % der gesamten Nachfrage. Bei 1e-3 (Iteration 21): 0,07 % bzw. 0,45 %. Bei 1e-4 (Iteration 102): 0,015 % bzw. 0,074 %. Die Bezugsgrößen sind verschieden (Gesamtfahrzeit gegen gesamte Nachfrage); die Gesamtfahrzeit stimmt früh, die Kantenflüsse brauchen länger.
Ist das konjugierte Verfahren besser? (40 Netze, 200 Iterationen, Frank-Wolfe / MSA / konjugiert)	Mittel der Iterationen bis 1e-3: 35,3 / 55,3 / 13,3. Bis 1e-4: 159 / 183 / 37. Die Lücke 1e-4 wird in 22 / 31 / 0 von 40 Netzen nicht erreicht; die ersten beiden Mittel bis 1e-4 sind deshalb Untergrenzen. In 2 von 40 Netzen braucht das konjugierte Verfahren bis 1e-3 länger als die Suche (7 statt 5 und 11 statt 8 Iterationen).
Konvergiert der feste Schritt 0,5? (Standardnetz)	Nein: Nach 200 Iterationen liegt die Lücke bei 4,2e-2 und die Gesamtfahrzeit bei 7 275, das sind 5,5 % über dem Gleichgewicht. Beides sind Momentaufnahmen: Lücke und Gesamtfahrzeit schwanken von Iteration zu Iteration weiter, ohne zur Ruhe zu kommen.
Wie groß ist der Preis der Anarchie? (Gesamtfahrzeit im Gleichgewicht geteilt durch die im Systemoptimum)	Im Standardnetz 1,040 (6 897 gegen 6 632, beide mit dem konjugierten Verfahren bis zur Lücke 1e-6 gerechnet; nach genau 200 Iterationen weichen die Werte um wenige Einheiten ab); die höchste Auslastung einer Kante sinkt von 169 % auf 127 %. Im Mittel über 5 Netze bei Last 0,5 / 1,0 / 1,5 / 2,0 / 3,0: 1,005 / 1,026 / 1,056 / 1,066 / 1,065; der größte Einzelwert ist 1,115.
Sind die Kantenflüsse eindeutig? (Standardnetz)	Frank-Wolfe (1 500 Iterationen) und konjugiertes Frank-Wolfe (bis Lücke 1e-9) enden bei denselben Kantenflüssen, größte Abweichung 0,004 % der Nachfrage. Im Lehrnetz „Zwei Stufen“ trägt jede der vier Straßen 5, und viele verschiedene Wegeaufteilungen passen dazu (drei davon von Hand nachgerechnet).

Grenzen und was die Messung zeigt

• Stichprobe und Zählregel: Alle Zahlen gelten für erzeugte Gitter, nicht für ein reales Netz und nicht für Fremddaten. Die Lastreihe nutzt nur 5 Netze. Mittel mit „nicht erreicht = Grenze plus eins“ sind nach unten verzerrt, wenn viele Läufe die Grenze treffen; die 159 über 40 Netze ist in diesem Sinn eine Untergrenze des wahren Mittels (22 von 40 Läufen trafen die Grenze), ebenso die 218 bei Last 1,0 und die 249 bei Last 2,0.
• Rundung: Die Iterationszahlen gelten bis auf wenige Iterationen Rundungsunterschied.
• Verfahrensvergleich: Gezählt werden Iterationen und Kürzeste-Wege-Läufe, keine Rechenzeit. Pfadbasierte Verfahren erreichen hohe Genauigkeit schneller (Gradient Projection unterschreitet im Standardnetz 1e-4 nach 11 statt 102 Iterationen, für eine bestimmte Einstellung jenes Verfahrens; ein Schritt kostet dort anders), haben aber mit der Schrittweite eine eigene Schwachstelle. Algorithm B und TAPAS sind nicht umgesetzt. Mit Fremddaten wie dem Testnetz Sioux Falls wurde nicht verglichen.
• Konjugiertes Verfahren: Es brauchte die Absicherung durch den Neustart. Die erste Fassung deckelte \(\alpha_k\) nur bei \(1-\delta\) und blieb in 8 von 40 Netzen für immer stehen (bis 1e-4 im Mittel 70 statt 37 Iterationen); ein Vergleich mit einer pfadbasierten Lösung und einer unabhängig gerechneten Lücke deckte das auf.
• Modell: perfekte Information und unendlich viele kleine Fahrer (Wardrop); Lernen aus Erfahrung ist ein anderes Modell. Eine Fahrzeugklasse, statische Zuordnung, BPR-Fahrzeiten. Mehrklassen- und dynamische Umlegung sowie Maut und Kapazitätserweiterung sind nicht umgesetzt.
• Preis der Anarchie: Die Werte gelten für diese Gitter. Der Extremfall 4/3 des Pigou-Netzes (lineare Fahrzeiten) kommt hier nicht vor; für die BPR-Form mit \(p=4\) ist 4/3 keine allgemeine Obergrenze (aus dem Gedächtnis, nicht geprüft). Die Standardlast überlastet einzelne Kanten (höchste Auslastung 169 %); wie weit die Befunde auf weniger belastete Netze übertragbar sind, zeigt nur die Lastreihe von Last 0,5 bis 3,0.
• Lücke als Abbruchkriterium: Sie begrenzt den Fehler der Zielfunktion; für die Kantenflüsse liefert sie keine Schranke. Als Faustregel nur für diese Gitter: Für die Gesamtfahrzeit bringt schon die Lücke 1e-2 einen Fehler von nur 1,6 %. Wer Flüsse braucht, etwa für eine Maut oder eine Straßenplanung, rechnet weiter, bis der größte Kantenflussfehler (0,45 % der Nachfrage bei 1e-3, 0,074 % bei 1e-4) klein genug ist.

Quellen

• Wardrop (1952): Nutzergleichgewicht.
• Beckmann (1956), Beckmann, McGuire und Winsten (1956): konvexes Programm des Gleichgewichts und Systemoptimum.
• Pigou (1920): Grenzkosten und das Lehrnetz mit zwei Straßen.
• Mitradjieva und Lindberg (2013): konjugiertes Frank-Wolfe.
• Frank und Wolfe (1956): das Verfahren.

Namen und Jahre stammen aus der Demo; Titel und Fundstellen sind nicht nachgeschlagen, und der Eintrag Frank und Wolfe steht dort nicht, er ist aus dem Gedächtnis ergänzt.