Der Winterdienst verständlich erklärt

Nach dem Schneefall muss ein Räumfahrzeug jede Straße eines Stadtteils befahren und am Ende wieder am Ausgangspunkt stehen. Wie fährt es dabei möglichst wenig Umwege? Diese Seite zeigt, warum „immer zur nächsten Kreuzung“ teuer werden kann und wie sich die kürzeste Rundtour berechnen lässt.

Zuletzt aktualisiert: 11. November 2026

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

Ein Räumfahrzeug und jede Straße

Über Nacht hat es geschneit. Ein Räumfahrzeug soll einen Stadtteil freimachen. Jede Straße muss mindestens einmal befahren werden, sonst bleibt sie zugeschneit. Die großen Durchgangsstraßen heißen hier Hauptstraßen. Sie sind stark befahren und werden deshalb zweimal geräumt. Am Ende soll das Fahrzeug wieder dort stehen, wo es gestartet ist.

Gesucht ist die kürzeste Rundtour, die das schafft. Ein Teil der Strecke steht von vornherein fest: jede Straße so oft, wie sie geräumt werden muss. Das ist die Pflichtstrecke. Sie lässt sich nicht kürzen. Sparen kann man nur bei Wegen, auf denen nichts Neues geräumt wird, etwa über schon geräumte Straßen zur nächsten, die noch fehlt. Wir nennen sie Leerfahrten.

Die Seite erklärt das an einem vereinfachten Rechenbild (Fachwort: Modell). Das Straßennetz ist zufällig erzeugt, es fährt nur ein Fahrzeug, Einbahnstraßen gibt es nicht, und gerechnet wird nur mit der Länge der Wege. So lässt sich eine Frage sauber untersuchen: Wie viele Leerfahrten sind nötig, und wie plant man sie?

Warum an manchen Kreuzungen etwas hängen bleibt

Stellen Sie sich eine Kreuzung vor, an der drei Straßen zusammenkommen. Jede ist nur einmal zu räumen. Sie fahren auf der ersten Straße hinein und auf der zweiten wieder hinaus. Später kommen Sie auf der dritten Straße an. Nun stecken Sie fest: Alles ist geräumt, aber Sie müssen auf einer schon geräumten Straße weiter. Das ist eine Leerfahrt.

Der Grund ist einfach. Jede Durchfahrt braucht zwei Straßenenden, eines zum Hineinfahren und eines zum Hinausfahren. Bei einer ungeraden Zahl einfach zu räumender Straßen bleibt ein Ende übrig. Eine solche Kreuzung nennen wir ungerade.

Eine Straße, die von vornherein zweimal geräumt werden muss, macht eine Kreuzung nicht ungerade. Jede ihrer beiden Fahrten endet an der Kreuzung, zusammen sind das zwei Enden, die zueinander passen. Ob eine Kreuzung ungerade ist, hängt nur an der Zahl der einfach zu räumenden Straßen dort.

In jedem Straßennetz gibt es ungerade Kreuzungen nur in gerader Zahl. Jede Straße hat zwei Enden, alle Enden zusammen sind also eine gerade Zahl. Kreuzungen mit gerader Endenzahl ändern daran nichts.

Die Lösung: Man verbindet die ungeraden Kreuzungen paarweise. Für jedes Paar fährt das Fahrzeug einen zusätzlichen Weg von der einen zur anderen Kreuzung. Danach gehört an jeder Kreuzung zu jedem Hinein ein Hinaus, und alle Straßen lassen sich in einem Zug abfahren.

Daraus folgt etwas Wichtiges. Die Fahrreihenfolge, in der man die Straßen abfährt, ändert die Länge nicht, denn jede Fahrt zählt, wann auch immer sie kommt. Die Länge ist die Pflichtstrecke plus die zusätzlichen Wege. Entscheidend ist nur, welche ungeraden Kreuzungen man zu Paaren verbindet.

Das Paaren ist weniger harmlos, als es klingt. Vier ungerade Kreuzungen lassen sich auf drei Arten zu Paaren ordnen, sechs schon auf fünfzehn Arten. Mit jedem weiteren Paar wächst die Zahl der Möglichkeiten schnell. Je nach Wahl sind die zusätzlichen Wege unterschiedlich lang.

Drei Wege zu paaren

Das gierige Verfahren geht einfach vor. Es nimmt die erste ungerade Kreuzung auf seiner Liste und verbindet sie mit der, die auf dem Stadtplan am nächsten liegt, in der Luftlinie gemessen. Dann nimmt es die nächste freie Kreuzung der Liste und macht es genauso. Die Liste hat keine besondere Ordnung.

Das kann teuer werden, aus zwei Gründen. Erstens fährt das Fahrzeug nicht in der Luftlinie, sondern über die Straßen. Zwei Kreuzungen können nah beieinander liegen und doch nur über einen Umweg verbunden sein, weil keine durchgehende Straße dazwischen liegt. Zweitens nimmt, wer zuerst wählt, den anderen den besten Partner weg. Es können Kreuzungen übrig bleiben, die weit auseinander liegen und doch zusammen müssen. Das ist wie im Tanzkurs: Wer reihum jeweils die Nächststehende auffordert, kann am Ende zwei Menschen an gegenüberliegenden Wänden übrig haben. An der ganzen Tour fällt der Nachteil kleiner aus als an den Leerfahrten allein, denn die Pflichtstrecke bleibt gleich.

Beim Nachrechnen für diese Seite zeigte sich: Gab man dem gierigen Verfahren in den zufälligen Beispielnetzen den echten Straßenweg statt der Luftlinie, blieb der größere Teil des Nachteils bestehen. Die Luftlinie erklärt ihn also nur zum kleineren Teil, der Rest kommt vom gierigen Vorgehen selbst. Das ist eine Nachrechnung dieser Seite.

Das exakte Verfahren schaut nicht reihum, sondern auf alle Kreuzungen zugleich. Es rechnet für jedes Paar den echten Straßenweg aus und wählt die Paarung mit den insgesamt kürzesten Wegen. Dafür gibt es ein bewährtes Rechenverfahren (Fachwort: Matching). Es verbessert eine unfertige Paarung gezielt, statt blind zu probieren, und findet so die beste, ohne alle Möglichkeiten einzeln durchzugehen. Bei vielen anderen Tourenaufgaben, etwa wenn Kunden in frei wählbarer Reihenfolge anzufahren sind, kennt man kein so schnelles und sicheres Verfahren. Hier geht es, weil alle Straßen Pflicht sind und nur die Paarung zählt.

Ein drittes Verfahren, ein Suchverfahren, startet bei der gierigen Paarung und tauscht zufällig Partner. Es behält Verbesserungen, lässt anfangs aber auch kleine Verschlechterungen zu. Eine Garantie hat es nicht. In einem kleinen Testnetz fand es die beste Paarung bei mindestens einem von zehn Zufallsstarts (mehr verlangt die Prüfung nicht), in einem sehr großen Testnetz lag es nach der Prüfung nur wenig darüber.

Das Programm zum Ausprobieren

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum zweiten Teil. Zum Verstehen brauchen Sie die Demo nicht. Dort erzeugen Sie zufällige Stadtteile und sehen die drei Verfahren nebeneinander. Die Aussagen in diesem Teil beschreiben das Rechenbild, nicht echte Winterdienste.

Häufige Missverständnisse

• „Die gierige Paarung ist immer schlechter.“ Nein. In manchen Netzen trifft sie zufällig die beste Paarung. Besser als die exakte kann sie im Rechenbild nie sein, denn die exakte findet die beste Paarung.
• „Mehr Pflicht bedeutet mehr Leerfahrten.“ Nicht zwingend. Wie viel Leerfahrt nötig ist, hängt im Rechenbild nur daran, welche Kreuzungen ungerade sind und wie weit sie auseinander liegen. Wird eine einfache Straße zur Hauptstraße, wächst die Pflichtstrecke. Zugleich zählt sie bei der Frage, ob eine Kreuzung ungerade ist, nicht mehr mit. Dadurch werden an ihren Enden manche Kreuzungen gerade, andere ungerade.

Woran Sie das im Alltag erkennen

• Wer jede Gasse einer Altstadt ablaufen will und am Ende zum Auto zurückmuss, plant genau diese Aufgabe. Briefträger, Straßenreinigung und Zählerablesung stehen vor derselben Frage.
• Das Kinderrätsel „Haus vom Nikolaus“ lässt sich in einem Zug zeichnen, weil nur zwei Ecken eine ungerade Zahl von Linien haben. Dort beginnt und endet der Zug.

Wie ernst ist das Rechenbild zu nehmen?

Die Straßennetze sind zufällig erzeugt und keinem echten Stadtplan nachgebaut. Es fährt ein Fahrzeug, und Einbahnstraßen, Fahrtrichtung, Streumenge und Zeit fehlen, nur die Länge zählt. Die Aussagen gelten daher für dieses Rechenbild und wären für einen echten Winterdienst ein Baustein.

Was Sie mitnehmen:

• Fragen Sie bei jeder Tour, die alles abfahren muss, an welchen Stellen etwas ungerade bleibt. Dort entscheidet sich, wie viel Umweg nötig ist.
• Der Griff nach dem Nächstliegenden spart nicht automatisch Strecke. Fragen Sie, wer am Ende übrig bleibt.
• Prüfen Sie vor dem Optimieren, was wirklich frei wählbar ist. Steht die Pflicht fest, bleibt manchmal nur eine Wahl übrig, und das macht die Aufgabe lösbar.

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. Das Modell ist ein synthetisches Straßennetz; alle Aussagen gelten nur für Netze, die so erzeugt werden.

• Aufgabe: Gegeben ist ein zusammenhängender, ungerichteter Graph \(G=(V,E)\) mit Kreuzungen \(V\) und Straßen \(E\). Jede Straße \(e\) hat eine Länge \(\ell_e > 0\) und eine Pflichtzahl \(r_e \ge 1\). Gesucht ist ein geschlossener Kantenzug minimaler Länge, der jede Straße \(e\) mindestens \(r_e\)-mal nutzt. Das ist das verallgemeinerte Chinesische Postbotenproblem (Route Inspection Problem); mit \(r_e = 1\) für alle Straßen ist es das klassische.
• Netz: Die Kreuzungen liegen zufällig und gleichverteilt in einem Quadrat von sechs Kilometern Seitenlänge, mit einem freien Rand von dreihundert Metern. Jede Kreuzung wird mit ihren \(k\) nächsten Nachbarn (euklidischer Abstand) verbunden; die Länge \(\ell_e\) ist dieser Abstand. Zerfällt das Netz, werden die jeweils nächstgelegenen Kreuzungen zweier getrennter Teile verbunden, bis es zusammenhängt. Einstellbar sind die Zahl der Kreuzungen (von acht bis zweihundert, voreingestellt zwanzig), \(k\) (von zwei bis sechs, voreingestellt drei), der Anteil der Hauptstraßen (von null bis zur Hälfte aller Straßen in Schritten von fünf Prozentpunkten, voreingestellt ein Fünftel) und der Startwert des Zufallsgenerators (voreingestellt null).
• Hauptstraßen: Der eingestellte Anteil der längsten Straßen erhält \(r_e = 2\), alle übrigen \(r_e = 1\). Die Annahme dahinter: Verbindende Achsen sind lang, kurze Straßen liegen im Wohnblock. Das ist eine Setzung des Generators, keine Beobachtung.
• Fahrzeug und Kosten: ein Fahrzeug, keine Fahrtrichtung, keine Ladung (Salz, Treibstoff), keine Zeit, kein ausgezeichneter Startpunkt. Kosten sind Längen; ein Kilometer Leerfahrt kostet so viel wie ein Kilometer Räumfahrt.
• Gemeinsames Gerüst: Alle drei Verfahren bilden den Pflicht-Multigraphen \(G_r\) (jede Straße \(e\) in \(r_e\) Kopien). Der Grad einer Kreuzung \(v\) in \(G_r\) ist \(\sum_{e \ni v} r_e\); \(T\) sei die Menge der Kreuzungen mit ungeradem Grad. Dann berechnen sie die kürzesten Wege \(d(u,v)\) zwischen allen Kreuzungen aus \(T\) in \(G\) (Dijkstra), paaren \(T\), fahren je Paar den kürzesten Weg einmal zusätzlich (die Leerfahrten) und lesen mit dem Hierholzer-Verfahren einen Eulerkreis ab. Die Verfahren unterscheiden sich nur in der Paarung \(M\):
• Gierig: Die erste noch freie Kreuzung aus \(T\) (in der Nummerierung der Kreuzungen, der Listenreihenfolge, die willkürlich ist) wird mit der nach Luftlinie nächsten noch freien Kreuzung gepaart, dann folgt die nächste freie. Bezahlt wird der Straßenweg \(d(u,v)\), nicht die Luftlinie.
• Exakt: Minimum-Weight Perfect Matching auf dem vollständigen Graphen über \(T\) mit den Gewichten \(d(u,v)\). Eine Standardfunktion (eulerize in NetworkX) wird bewusst nicht benutzt: Sie paart nach Kantenzahl statt nach Länge und wäre bei ungleich langen Straßen falsch.
• Suchverfahren: Simulated Annealing über die Paarungen. Es startet bei der gierigen Paarung, wählt in jedem Schritt zwei Paare und tauscht deren Partner. Verbesserungen werden angenommen, Verschlechterungen mit einer Wahrscheinlichkeit, die mit sinkender Temperatur kleiner wird. Die Zahl der Schritte ist hundertzwanzigmal \(|T|^2\), mindestens aber dreitausend; die Temperatur sinkt linear von eins auf null. Der Zufallsgenerator läuft mit festem Startwert.

Die Formeln

Zielfunktion. Mit \(x_e\) als Zahl der Durchläufe der Straße \(e\) im Kantenzug:

\[\min \sum_{e \in E} x_e \, \ell_e \qquad \text{s.t.} \quad x_e \geq r_e \;\; \forall e \in E\]

Zusätzlich muss der Multigraph, der jede Straße \(e\) genau \(x_e\)-mal enthält, zusammenhängen und an jeder Kreuzung geraden Grad haben. Das ist nach dem Satz von Euler genau dann der Fall, wenn ein geschlossener Kantenzug existiert, der jede Kopie genau einmal nutzt. Der Zusammenhang folgt hier schon aus \(x_e \ge r_e \ge 1\) und dem Zusammenhang von \(G\).

Länge einer Tour. Wird eine Paarung \(M\) von \(T\) gewählt und für jedes Paar \(\{u,v\} \in M\) ein kürzester Weg einmal zusätzlich gefahren, so hat der Eulerkreis die Länge

\(L = \sum_{e} r_e \ell_e + \sum_{\{u,v\} \in M} d(u,v).\)

Der erste Summand ist die Pflichtstrecke, eine Untergrenze für jede zulässige Tour; beim Paaren ändert sie sich nicht. Der zweite Summand sind die Leerfahrten. Er hängt nur von \(M\) ab, nicht von der Reihenfolge, in der der Eulerkreis die Straßen durchläuft.

Optimale Paarung. Gesucht ist \(\min_M \sum_{\{u,v\} \in M} d(u,v)\) über alle perfekten Paarungen \(M\) von \(T\) (jede Kreuzung aus \(T\) kommt genau einmal vor). Dabei ist \(|T|\) gerade, weil die Summe aller Grade gerade ist (jede Kopie hat zwei Enden).

Herleitungen Schritt für Schritt

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

Welche Kreuzungen ungerade sind.

• Schritt 1: Eine Straße mit \(r_e = 2\) trägt 2 zum Grad ihrer beiden Enden bei, also nichts zur Parität. Für die erzeugten Netze (nur \(r_e \in \{1, 2\}\)) gilt daher \(v \in T\) genau dann, wenn die Zahl der Straßen mit \(r_e = 1\) an \(v\) ungerade ist.
• Schritt 2: Wird eine einfache Straße zur Hauptstraße, wechselt an ihren beiden Enden die Zugehörigkeit zu \(T\). Die Pflichtstrecke wächst um \(\ell_e\). Ob die Leerfahrten wachsen oder sinken, hängt davon ab, welche Kreuzungen dazukommen und welche wegfallen.

Warum nur die Paarung zählt (Skizze im Sinn von Edmonds und Johnson).

• Schritt 1: Setze \(y_e = x_e - r_e \ge 0\) (zusätzliche Durchläufe). Gerader Grad an \(v\) verlangt, dass \(\sum_{e \ni v} y_e\) genau für \(v \in T\) ungerade ist. Die Menge \(J\) der Straßen mit ungeradem \(y_e\) hat also genau an den Kreuzungen aus \(T\) ungeraden Grad; man nennt sie einen \(T\)-Join.
• Schritt 2: Aus \(y_e \ge 2\) lässt sich 2 abziehen: Die Paritäten bleiben, \(x_e \ge r_e\) bleibt, die Länge sinkt wegen \(\ell_e > 0\). Im Optimum ist daher \(y_e \in \{0, 1\}\), und die Zusatzlänge ist die Länge eines \(T\)-Joins \(J\).
• Schritt 3: Ein \(T\)-Join lässt sich in kantendisjunkte Wege zerlegen, die die Kreuzungen aus \(T\) paarweise verbinden, plus Kreise (bekannter Hilfssatz, hier nicht bewiesen). Jeder dieser Wege ist mindestens so lang wie der kürzeste Weg zwischen seinen Enden, also ist \(J\) mindestens so lang wie das Gewicht der zugehörigen Paarung, und diese mindestens so lang wie das Minimum über alle Paarungen.
• Schritt 4: Umgekehrt ergibt jede Paarung \(M\), mit ihren kürzesten Wegen gebildet und mod 2 überlagert (symmetrische Differenz), einen \(T\)-Join, der höchstens \(\sum d(u,v)\) lang ist. Die kürzeste Zusatzlänge ist also genau das Minimum der Paarungskosten.
• Folgerung: Das Optimum ist die Pflichtstrecke plus das Gewicht eines Minimum-Weight Perfect Matchings auf \(T\) mit den Gewichten \(d(u,v)\). Es ist mit dem Blossom-Verfahren in polynomieller Zeit lösbar (nach meiner Erinnerung wächst der Aufwand des Matchings mit der dritten Potenz von \(|T|\)). Bedingung: ungerichtetes Netz, \(\ell_e > 0\) und \(r_e \ge 1\); für gerichtete oder gemischte Netze gilt das nicht in dieser Form.

Wie viele Paarungen gibt es? Bei \(|T| = 2m\) hat die erste Kreuzung \(2m-1\) mögliche Partner, die nächste freie \(2m-3\) und so weiter. Es sind \((2m-1)(2m-3)\cdots 1\) Paarungen: drei, fünfzehn, hundertfünf und neunhundertfünfundvierzig bei vier, sechs, acht und zehn ungeraden Kreuzungen. Im Vorgabefall (zwanzig Kreuzungen) liegt \(|T|\) in der Nachrechnung unten im Mittel bei gut elf. Aufzählen taugt als Kontrolle in kleinen Netzen, nicht in großen.

Durchgerechnete Beispiele

Die drei Beispiele sind ausgedacht (Rechnungen dieser Seite, keine Messungen der Demo).

Parität. An einer Kreuzung treffen drei Straßen zusammen. Sind alle einfach, ist der Grad 3, ungerade, die Kreuzung gehört zu \(T\). Ist eine davon Hauptstraße, ist der Grad \(1 + 1 + 2 = 4\), gerade, sie gehört nicht zu \(T\).

Reihenfolge allein. Vier ungerade Kreuzungen \(a, b, c, d\) liegen an einer geraden Straße bei den Kilometern 2, 0, 3 und 5; die Liste ist in dieser Reihenfolge angelegt. Luftlinie und Straßenweg sind hier gleich. Das gierige Verfahren paart \(a\) mit der nächsten freien Kreuzung \(c\) (Abstand 1); übrig bleibt das Paar \(b, d\) (Abstand 5). Es kostet \(1 + 5 = 6\). Die drei möglichen Paarungen kosten \(\{ab, cd\}\): \(2 + 2 = 4\), \(\{ac, bd\}\): \(1 + 5 = 6\) und \(\{ad, bc\}\): \(3 + 3 = 6\). Das Minimum ist 4, die gierige Leerfahrt also das Anderthalbfache.

Luftlinie gegen Straßenweg. Die Kreuzungen \(A\) und \(C\) liegen 1 Kilometer Luftlinie auseinander, ohne durchgehende Straße; der Weg zwischen ihnen ist 8 Kilometer lang. Weiter seien die Wege \(A\)–\(B\) und \(C\)–\(D\) je 3 Kilometer und \(B\)–\(D\) 5 Kilometer lang. Der Weg \(A\)–\(C\) führt über eine weit entfernte Querung; die Strecke über \(B\) und \(D\) wäre mit elf Kilometern noch länger. Steht \(A\) zuerst auf der Liste und ist \(C\) nach Luftlinie ihr nächster Nachbar, paart die gierige Regel \(A\) mit \(C\) (8) und danach \(B\) mit \(D\) (5): zusammen dreizehn. Die Paarung \(\{A\text{–}B, C\text{–}D\}\) kostet \(3 + 3 = 6\).

Befunde

Prüfungen der Demo (automatische Tests). Sie prüfen Gleichheiten und Schwellen, keine Mittelwerte.

Frage	Befund	Voraussetzung
Ist die exakte Tour optimal?	Ihre Gesamtlänge stimmt mit dem Optimum eines unabhängigen ganzzahligen Programms überein (Variablen \(x_e\), Gradbedingung, ohne kürzeste Wege und ohne Matching).	Sechzehn Netze mit acht bis vierzig Kreuzungen, zwei bis sechs Nachbarn, Hauptstraßenanteil null bis zur Hälfte, je ein Startwert; Gleichheit bis auf Rundung. Das Programm erlaubt je Straße bis zu zwei zusätzliche Durchläufe; nach der Herleitung genügt einer, die Grenze ist also großzügig.
Findet das exakte Verfahren die beste Paarung?	Ja, die Paarungskosten stimmen mit der Aufzählung aller perfekten Paarungen überein.	Vier kleine Netze mit acht bis zehn Kreuzungen, zwei oder drei Nachbarn, ein Fünftel Hauptstraßen.
Ist die gierige Tour je kürzer als die exakte?	Nein. Gierige Tour und Suchverfahren sind in allen geprüften Netzen mindestens so lang wie das Optimum, auch die Leerfahrten der gierigen Paarung mindestens so lang wie die exakten. Das folgt schon aus der Optimalität der exakten Paarung; die Tests prüfen damit zugleich die Umsetzung.	Dieselben sechzehn Netze; zusätzlich sechs Netze für den Vergleich der Leerfahrten.
Wie groß ist der Rückstand im Testnetz?	Die Leerfahrten der gierigen Paarung sind länger als das Anderthalbfache der exakten (der Test verlangt nur diese Schwelle).	Zwölf Kreuzungen, drei Nachbarn, ein Zehntel Hauptstraßen, Startwert vier.
Wie gut ist das Suchverfahren?	Im kleinen Netz erreicht mindestens einer von zehn Startwerten das Optimum der Leerfahrten (die Prüfung verlangt nur das). Im großen Netz liegen die Leerfahrten des Suchverfahrens höchstens ein Zehntel über den exakten (Schwelle des Tests).	Klein: das Testnetz oben. Groß: zweihundert Kreuzungen, drei Nachbarn, ein Fünftel Hauptstraßen, Startwert null.

Nachrechnung dieser Seite (keine Messung der Demo). Die Netze wurden nach derselben Vorschrift nachgebaut (Startwerte null bis neunundneunzig, je hundert Netze, drei Nachbarn), die exakte Paarung durch Aufzählung mit Zwischenspeicher bestimmt und die gierige Paarung wie oben beschrieben. Probe: Im Testnetz oben ergibt die Nachrechnung ein Verhältnis der Leerfahrten zwischen dem Anderthalbfachen und dem Doppelten (näher am Doppelten), vereinbar mit der Schwelle des Tests. Die Zahlen unten sind gerundet und deshalb in Wörtern gesetzt. Gemittelt wird die Prozentlücke je Netz, bezogen auf die exakten Leerfahrten dieses Netzes; in allen Netzen gab es ungerade Kreuzungen.

Frage	Befund	Voraussetzung
Wie oft ist die gierige Tour länger als die exakte?	Gut die Hälfte der Netze bei zwölf Kreuzungen, gut drei Viertel bei zwanzig, über neun Zehntel bei dreißig; in keinem Netz kürzer.	Ein Fünftel Hauptstraßen.
Wie groß ist der Rückstand der Leerfahrten?	Bei zwanzig Kreuzungen im Mittel gut ein Drittel, im Median ein Fünftel, im ungünstigsten Netz hat die gierige Paarung fast das Vierfache der exakten Leerfahrten (ein Rückstand von fast dreihundert Prozent). Der Median wächst mit der Größe: unter einem Zehntel bei zwölf, gut ein Drittel bei dreißig Kreuzungen.	Ein Fünftel Hauptstraßen.
Wie wirkt das auf die Gesamtlänge?	Die gierige Tour ist im Mittel knapp vier Prozent länger als die exakte, höchstens gut ein Viertel. Bezug: Pflichtstrecke plus exakte Leerfahrten.	Zwanzig Kreuzungen, ein Fünftel Hauptstraßen.
Wie wirkt der Hauptstraßenanteil?	Die exakten Leerfahrten im Verhältnis zur Pflichtstrecke sinken: knapp ein Fünftel ohne Hauptstraßen, gut ein Zehntel bei einem Fünftel, unter einem Zehntel bei der Hälfte.	Zwanzig Kreuzungen.
Wie viel erklärt die Luftlinie?	Paart man gierig in derselben Reihenfolge, aber nach Straßenweg, ist die Tour noch in knapp drei Vierteln der Netze länger als die exakte. Der mittlere Rückstand der Leerfahrten liegt dann bei fast einem Viertel, bei Luftlinie bei gut einem Drittel. Von hundert Netzen war die Straßenweg-Variante in sechzehn besser als die Luftlinie-Variante, in fünf schlechter und in den übrigen neunundsiebzig gleich gut.	Zwanzig Kreuzungen, ein Fünftel Hauptstraßen.
Wie viel bleibt ohne Listenreihenfolge?	Paart man stets das billigste noch freie Paar nach Straßenweg, ist die Tour in drei Vierteln der Netze länger als die exakte. Der mittlere Rückstand der Leerfahrten liegt dann bei knapp einem Fünftel, der Median bei gut einem Achtel.	Zwanzig Kreuzungen, ein Fünftel Hauptstraßen.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Die exakte Paarung liefert im Modell die kürzeste Tour: durch die Herleitung oben, die Aufzählung in kleinen Netzen und den Vergleich mit einem unabhängigen Programm.
• Die gierige Paarung fährt in diesen Netzen im Mittel mehr als ein Drittel mehr Leerfahrten als die exakte (zwanzig Kreuzungen, ein Fünftel Hauptstraßen), und der Anteil der betroffenen Netze wächst in der Nachrechnung mit der Größe. Sie war in den geprüften Netzen nie kürzer.
• Gemessen an der Gesamtlänge ist der Rückstand viel kleiner als an den Leerfahrten (beide Zahlen oben), weil die Pflichtstrecke den größten Teil der Tour ausmacht. Eine Prozentlücke, die an den Leerfahrten groß wirkt, sagt wenig über die Gesamtkosten.

Was sie nicht belegt, und Grenzen:

• Ursache des Rückstands: Die Demo führt ihn auf den Unterschied zwischen Luftlinie und Straßenweg zurück. Die Nachrechnung stützt das nur zum kleineren Teil: Auch mit Straßenweg bleibt der größere Teil bestehen, und selbst ohne Listenreihenfolge (billigstes freies Paar zuerst) bleibt ein Rückstand. Die gierige Regel selbst (wer zuerst wählt, nimmt den anderen den besten Partner) wirkt vermutlich stärker als die Listenreihenfolge allein; das ist eine Vermutung, keine Messung. Die Demo trennt diese Wirkungen nicht, und die Nachrechnung ist ein eigener Aufbau, kein Test der Demo.
• Netzfamilie: Zufällige Nachbarnetze, Hauptstraßen als die längsten Straßen. Gitternetze oder echte Stadtpläne sind nicht geprüft; ob der Rückstand dort ähnlich ausfällt, ist offen.
• Suchverfahren: Die Demo nennt eine eigene Prüfreihe (fast alle von dreihundert kleinen und mittleren Netzen mit derselben Paarung wie das exakte Verfahren, bei sehr großen Netzen oft darüber, bis etwa ein Sechstel mehr Leerfahrten). Sie ist weder hier noch in den Tests nachgeprüft.
• Modellrand: ungerichtet; die zwei Durchläufe einer Hauptstraße haben keine Richtung (gemeint sein könnten beide Richtungen oder beide Fahrbahnen; das Modell sieht das nicht vor). Ein Fahrzeug, kein Depot, keine Kapazität (Salz), keine Zeit oder Priorität (etwa Hauptstraßen zuerst). Leerfahrten kosten wie Räumfahrten; in der Praxis ist ein Fahrzeug ohne Pflug vermutlich schneller.
• Optimalität: Sie gilt für dieses Modell (ungerichtet, \(\ell_e > 0\), \(r_e \ge 1\)), nicht für einen echten Einsatzplan. Rechenzeiten sind hier nicht gemessen.
• Mittelwerte: Die Nachrechnung nutzt hundert Netze je Einstellung; der Mittelwert der Lücken wird von wenigen Netzen mit sehr großen Lücken angehoben (ohne die fünf größten sinkt er bei zwanzig Kreuzungen von gut einem Drittel auf gut ein Viertel), daher stehen auch Mediane da.

Erweiterungen und Verweise

Naheliegende Erweiterungen sind gerichtete Straßen und zwei Fahrbahnen, Kapazitäten (Salzvorrat, Tank), mehrere Fahrzeuge, Zeiten und Prioritäten. Verwandtes:

• Dasselbe Verfahren auf festen Netzen: Die arc-routing-demo nutzt dasselbe Lösungsverfahren, aber mit festen Netzen statt frei einstellbarer Größe (nur als Quelltext auf GitHub, nicht als Demo auf dieser Website).
• Knotenrouting: Die vrp-demo besucht bestimmte Kunden statt jeder Straße; die Seite Tourenplanung verständlich erklärt erklärt sie. Dort ist die Reihenfolge frei, und ein vergleichbar schnelles exaktes Verfahren ist nicht bekannt.
• Dieselbe Falle in anderer Aufgabe: Greedy-Matching verständlich erklärt zeigt, wie „billigste Kante zuerst“ bei der Zuordnung von Fahrzeugen zu Aufträgen Geld verschenkt.

Quellen

• Edmonds, Johnson (1973): Matching, Euler tours and the Chinese postman. Mathematical Programming 5(1), 88–124.
• Kwan Mei-Ko (1962): Graphic programming using odd or even points. Chinese Mathematics 1 (Ursprung der Aufgabe, Name „Chinesisches Postbotenproblem“).
• Edmonds (1965): Paths, trees, and flowers. Canadian Journal of Mathematics 17 (Blossom-Verfahren für das Matching).
• Euler (1736, gedruckt 1741): Solutio problematis ad geometriam situs pertinentis (Königsberger Brücken; Bedingung für Eulerkreise).
• Papadimitriou (1976): On the complexity of edge traversing. Journal of the ACM 23 (gemischtes Problem ist schwer).
• Quelltext und Tests der Demo: github.com/sebastian-hanisch/gcpp-demo.

Nur Edmonds und Johnson (1973) steht in der Demo; die übrigen Angaben stammen aus dem Gedächtnis und sind nicht nachgeschlagen. Die Prüfungen in der ersten Tabelle geben die automatischen Tests der Demo wieder; Herleitungen, Beispiele und die zweite Tabelle sind Rechnungen dieser Seite.