Greedy-Matching verständlich erklärt

Ein Disponent ordnet Fahrzeuge Aufträgen zu und nimmt immer zuerst das günstigste mögliche Paar. Das klingt vernünftig und ist schnell, kann aber später die besseren Paare blockieren, weil nie etwas zurückgenommen wird. Diese Seite erklärt zuerst ohne Formeln, warum das Paare oder Geld kostet, und danach für Fachleute mit Modell, Formeln, Messwerten und Grenzen. Die zugehörige Demo spielt es an Fahrzeugen und Aufträgen durch.

Zuletzt aktualisiert: 28. Oktober 2026

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

Fahrzeuge, Aufträge und eine einfache Regel

Stellen Sie sich einen Disponenten vor, der morgens freie Fahrzeuge und offene Aufträge vor sich hat. Jedes Fahrzeug darf höchstens einen Auftrag übernehmen, und jeder Auftrag bekommt höchstens ein Fahrzeug. Außerdem fährt ein Fahrzeug nur zu Aufträgen, die in seiner Reichweite liegen, also nicht zu weit weg. Eine solche Menge von Paaren aus Fahrzeug und Auftrag heißt in der Fachsprache Zuordnung oder Matching. Jedes Paar hat Kosten, in der Demo die Anfahrtszeit.

Eine gute Zuordnung bedient zuerst möglichst viele Aufträge. Unter allen Lösungen mit gleich vielen Paaren ist die beste die mit der kürzesten Gesamtfahrzeit. Die einfachste Regel dafür lautet: Nimm immer das günstigste Paar, das noch geht, binde beide und mach weiter. Solche Regeln heißen gierig (englisch greedy): Sie treffen in jedem Schritt die im Moment beste Wahl und nehmen sie nie wieder zurück. Das ist schnell und leicht nachzuvollziehen.

Wo die billigste Wahl in die Falle führt

Das kleinste Beispiel der Demo hat zwei Fahrzeuge und zwei Aufträge. Denken Sie sich eine lange Straße. Ganz links steht der Lieferwagen Süd, dann folgt der Auftrag Hafen, dann der Lieferwagen Nord, ganz rechts der Auftrag Werk. Nord steht dem Hafen nur ein kleines Stück näher als dem Werk, also ist „Nord zum Hafen“ das billigste Paar, und die Regel nimmt es sofort. Für Süd bleibt dann nur das Werk am anderen Ende der Straße, die längste Fahrt von allen. Hätte Süd den nahen Hafen genommen und Nord das nahe Werk, wären beide Fahrten kurz gewesen. Die billige Wahl am Anfang erzwingt also eine teure am Ende.

Noch schärfer wirkt es bei der Zahl der Paare. Wieder stehen vier Punkte an einer Straße: der Lieferwagen West, der Auftrag Hafen, der Lieferwagen Mitte und der Auftrag Werk. West schafft es gerade noch bis zum Hafen, aber nicht weiter. Das Werk erreicht nur Mitte. Mitte steht dem Hafen am nächsten, also nimmt die Regel „Mitte zum Hafen“ zuerst. Jetzt ist der Hafen vergeben: West hat keinen Auftrag mehr in Reichweite, und das Werk hat kein Fahrzeug, das es erreicht. Ein Auftrag ist besetzt, wo zwei möglich gewesen wären.

Wann es besonders weh tut

Wie stark die Regel verliert, hängt von der Reichweite ab. Ist sie sehr knapp, gibt es kaum Auswahl, und die einfache Regel trifft oft schon die beste Zuordnung. Ist sie mittel, gibt es viele mögliche Paare, aber noch nicht für jeden Auftrag ein Fahrzeug, und frühe Paare blockieren am meisten. In der Demo gehen dort auf fast allen Testkarten Paare verloren. Ist alles erreichbar, werden zwar alle Aufträge bedient, aber die Fahrten sind insgesamt teurer als nötig. Der Verlust wandert dann von den Paaren zum Geld.

Die Demo zeigt zwei gierige Regeln: Die eine nimmt das günstigste Paar zuerst, die andere geht die Aufträge der Reihe nach durch und gibt jedem das günstigste freie Fahrzeug. In der Demo ist keine der beiden überall besser.

Eine Sicherheit gibt es immer: Die gierige Regel erreicht nie weniger als die Hälfte der Paare, die überhaupt möglich sind. Der Grund: Am Ende berührt jedes mögliche Paar ein Fahrzeug oder einen Auftrag, der schon vergeben ist, sonst hätte die Regel es noch genommen. Jedes gewählte Paar vergibt aber nur ein Fahrzeug und einen Auftrag und kann daher höchstens zwei Paaren der besten Lösung im Weg stehen. Die Hälfte erreicht die Regel nur in eigens konstruierten Beispielen, nicht auf Zufallskarten. Über die Kosten sagt diese Sicherheit nichts.

Was hilft?

Die Schwäche liegt im Wort „nie“. Darf man eine Zuordnung wieder aufmachen, lässt sie sich verbessern. Im Beispiel mit West, Mitte, Hafen und Werk geht das so: West übernimmt den Hafen, dadurch wird Mitte frei und fährt zum Werk. Danach sind beide Aufträge besetzt statt einem. Eine solche Kette von Umbesetzungen heißt Verbesserungsweg. Die Demo macht sie sichtbar, indem sie die gierige Zuordnung über die beste legt.

Eine zweite Idee ist, nicht Paar für Paar zu entscheiden, sondern die Kosten aller Paare gemeinsam zu betrachten und gleich die Zuordnung mit der kleinsten Gesamtsumme zu suchen. Das braucht mehr Rechenaufwand als die einfache Regel.

Was man daraus für eine Entscheidung mitnimmt: Eine Regel, die in jedem Schritt das Beste wählt und nichts zurücknimmt, taugt als schneller Anfang, aber „im Moment am besten“ ist nicht „insgesamt am besten“. Im eigenen Betrieb erkennen Sie die Falle an Aufträgen, die unbesetzt bleiben, obwohl Fahrzeuge frei sind: Die freien Fahrzeuge erreichen sie nicht, und die Fahrzeuge, die es könnten, sind schon anderswo gebunden. Dann lohnt es sich, die Zuweisung probeweise noch einmal aufzumachen.

Wie ernst ist das Modell zu nehmen?

Die Demo ist ein stark vereinfachtes Modell: Fahrzeuge und Aufträge sind Punkte auf einer quadratischen Karte, die Kosten sind die aufgerundete Anfahrtszeit, und es gibt keine Zeitfenster, keine Kapazitäten und keine Wünsche der Beteiligten. Alle Daten sind synthetisch. Die Demo zeigt, wie die Mechanik wirkt, nicht wie viel eine echte Disposition sparen würde.

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 fasst die formale Beschreibung der Demo zusammen; die vollständige Fassung steht im Expander „📐 Mathematische Formulierung“ der Demo.

• Karte: Fahrzeuge \(V\) und Aufträge \(O\) auf ganzzahligen Koordinaten 0–100; die Kosten \(c_{ij}=\lceil d_{ij}\rceil\) sind die aufgerundete Entfernung (per isqrt, ohne Gleitkomma). Ein Paar ist möglich, wenn die Entfernung höchstens die Reichweite \(R\) beträgt, also \((i,j)\in E\) mit \(d_{ij}\le R\). Ballung in ganzen Prozent zieht die Punkte um drei Zentren. Standard: 20 Fahrzeuge, 20 Aufträge, Karte 100 × 100.
• Bewertung lexikografisch: erst möglichst viele Paare, dann die geringste Kostensumme. Kosten sind nur bei gleicher Paarzahl vergleichbar.
• Zwei Regeln: „Billigste Kante zuerst“ sortiert die möglichen Paare nach (Kosten, Fahrzeug, Auftrag) und nimmt jedes, dessen Enden frei sind. „Auftrag für Auftrag“ geht die Aufträge nach Nummer durch; jeder bekommt das freie mögliche Fahrzeug mit den geringsten Kosten. Beide liefern maximale Paarungen.
• Zufall: Die Karten kommen aus einem eigenen Ganzzahl-Generator (SplitMix64 auf Python-Ints) statt aus numpy.random, weil numpy keine über Versionen stabilen Zufallsströme garantiert. So sind Zufalls-Seeds, Voreinstellungen und jede genannte Zahl auf Windows und Linux dieselben.

Die Formeln

Ein Matching \(M\subseteq E\) enthält jedes Fahrzeug und jeden Auftrag höchstens einmal, mit \(x_{ij}=1\) für gewählte Paare:

\[\sum_{j} x_{ij}\le 1\ \ \forall i,\qquad \sum_{i} x_{ij}\le 1\ \ \forall j,\qquad x_{ij}\in\{0,1\}.\]

Das Ziel ist lexikografisch: erst \(|M|\) maximieren, dann \(c(M)=\sum_{(i,j)\in M}c_{ij}\) minimieren. Mit \(B > \min(|V|,|O|)\cdot\max c\) ist das gleichwertig zu \(\max\ \sum_{(i,j)\in M}(B-c_{ij})\). Die Regel „Billigste Kante zuerst“ kostet \(O(|E|\log|E|)\), die Regel „Auftrag für Auftrag“ \(O(|V|\,|O|)\).

Garantie. Beide Regeln liefern ein maximales Matching \(G\), also ohne Kante mit zwei freien Enden. Für ein größtmögliches \(M^*\) berührt jede Kante von \(M^*\) mindestens eine von \(G\) belegte Ecke, und jede Kante von \(G\) belegt zwei Ecken, berührt also höchstens zwei Kanten von \(M^*\). Daraus folgt \(|M^*|\le 2\,|G|\), also \(|G|\ge \tfrac{1}{2}\,|M^*|\). Die Schranke ist scharf: Der Pfad \(V_1 - O_1 - V_2 - O_2\) mit billiger Mittelkante gibt \(|G|=1\) bei \(|M^*|=2\), und \(k\) getrennte Pfade geben \(k\) gegen \(2k\). Über die Kosten sagt die Garantie nichts: Bei gleicher Paarzahl kann Greedy beliebig teurer sein.

Symmetrische Differenz. Für zwei Matchings \(G\) und \(M^*\) hat \(G\,\triangle\,M^*\) in jeder Ecke Grad höchstens 2 und zerfällt in Wege und gerade Kreise, deren Kanten abwechselnd aus \(G\) und \(M^*\) stammen. Ein Weg mit einer \(M^*\)-Kante mehr ist ein augmentierender Weg für \(G\); ihre Zahl ist \(|M^*|-|G|\), und weil \(G\) maximal ist, hat jeder mindestens drei Kanten.

Messlatte. Das Optimum kommt aus einer exakten Referenz: einer quadratischen Zuordnung, in der jedes unmögliche Paar \(B\) kostet, damit zuerst die Paarzahl maximiert wird; ganzzahlig und deterministisch, \(O(N^3)\). Sie dient nur zum Messen; das Verfahren ist Thema der Ungarischen Methode.

Befunde

Bis auf die ersten beiden Zeilen (feste Lehrbuchkarten) stammen alle Zahlen aus den Tests der Demo (tests/test_claims.py) über 100 feste Karten (Seeds 100000–100099). Standard ist 20 Fahrzeuge, 20 Aufträge, Karte 100 × 100, Kosten = Anfahrtszeit in aufgerundeten Minuten; abweichende Einstellungen stehen in der jeweiligen Zeile.

Frage	Befund
Ist Greedy optimal?	Nein. Auf der kleinsten Lehrbuchkarte (2 Fahrzeuge, 2 Aufträge) zahlen beide Regeln 18 statt 10 Minuten (80 % mehr): Die Kante für 4 Minuten wird zuerst gewählt und erzwingt die für 14.
Wie schlecht kann Greedy bei der Paarzahl sein?	Nie unter die Hälfte (getestet, auch erschöpfend für alle Paarmengen auf 3 × 3 und 3 × 4 Karten). Die Hälfte erreicht es nur auf konstruierten Karten: drei Pfade aus vier Punkten geben 3 statt 6 Paare. Auf Zufallskarten liegt die schlechteste Karte weit darüber (bei mittlerer Reichweite bei 75 %).
Mittlere Reichweite (40 Minuten)	„Billigste Kante zuerst“ verliert auf 99 von 100 Karten Paare: im Mittel 16,7 statt 19,5 (86 %).
Alles erreichbar (Reichweite 150)	Alle 20 Aufträge werden bedient, aber im Median 14 % teurer als das Optimum (Regel „Auftrag für Auftrag“: 21 %); auf keiner der 100 Karten optimal.
Sehr knappe Reichweite (10 Minuten)	Nur wenige Paare sind möglich: „Billigste Kante zuerst“ findet auf 79 von 100 Karten genau das Optimum (auf 20 verliert es Paare).
Drei Stadtteile (Ballung 100 %, Reichweite 30)	Der Verlust wandert von den Paaren zum Geld: 52 von 100 Karten verlieren Paare (ohne Ballung 96), 44 zahlen bei gleicher Paarzahl mehr.
Wenige Fahrzeuge (10 zu 20 Aufträgen, alles erreichbar)	„Auftrag für Auftrag“ zahlt im Median 109 % mehr als das Optimum, „Billigste Kante zuerst“ nur 1,6 %: Die ersten Aufträge bekommen die Fahrzeuge, statt dass die zehn günstigsten bedient werden.
Welche Regel ist besser?	Keine dominiert (Paare zuerst, dann Kosten): Bei Reichweite 40 ist „Auftrag für Auftrag“ auf 54 von 100 Karten besser, bei Reichweite 150 „Billigste Kante zuerst“ auf 85 von 100.

Zwei Annahmen aus der Planung widerlegte die Vormessung der Demo: Bei großer Reichweite ist Greedy nicht fast optimal (die Mehrkosten wachsen laut README mit der Kartengröße), und „Billigste Kante zuerst“ ist nicht pauschal die klügere Regel, denn sie behält bei mittlerer Reichweite etwas weniger Paare als „Auftrag für Auftrag“.

Grenzen

• Synthetische Daten: Alle Karten sind erzeugt, die Befunde gelten für die genannten Einstellungen und die 100 festen Karten, nicht für ein reales Netz.
• Nur zwei einfache Regeln: Die Demo zeigt „Billigste Kante zuerst“ und „Auftrag für Auftrag“; andere gierige Regeln, etwa mit Vorausschau, kommen nicht vor.
• Kosten und Paare getrennt: Kosten sind nur bei gleicher Paarzahl vergleichbar. Bei weniger Paaren sind die Kosten trivial niedriger und sagen nichts über die Qualität.
• Die Hälfte ist konstruiert: Die Garantie ist scharf, aber nur auf eigens gebauten Karten; Zufallskarten liegen weit darüber.
• Nicht enthalten: Präferenzen der Beteiligten, feste Reihenfolge der Aufträge als Teil des Problems, zwei getrennte Seiten (Fahrer, die sich untereinander paaren). Jede dieser Annahmen hebt ein Folgestück der Reihe auf.

Quellen

• Berge, C. (1957): Two theorems in graph theory. Proceedings of the National Academy of Sciences 43(9), 842–844 (Satz zur Symmetrischen Differenz zweier Matchings).
• Quelltext, Tests und Messungen der Demo: github.com/sebastian-hanisch/greedy-matching-demo.

Die genannte Arbeit wurde für diese Seite nicht nachgeschlagen; der Hinweis auf Berge stammt aus dem Quelltext der Demo, die README nennt keine Literatur.