Dominanz bei Teilwegen verständlich erklärt

Beim Planen von Lieferfahrten führen oft zwei Teilwege zum selben Kunden, und einer ist in allem nicht besser als der andere. Den darf man vergessen. Diese Seite zeigt, wann das erlaubt ist und was geschieht, wenn man nur auf die Kosten schaut.

Zuletzt aktualisiert: 11. November 2026

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

Zwei Teilwege zum selben Kunden

Stellen Sie sich einen Lieferwagen vor, der mehrere Kunden beliefert, jeden höchstens einmal, und am Ende ins Depot zurückkehrt. Jeder Kunde hat ein Zeitfenster, und der Wagen fasst nur eine bestimmte Last. Ein Disponent hat zwei Teilwege entworfen, die beide beim Kunden Z enden. Für jeden notiert er vier Angaben: die Kosten bisher (gefahrene Strecke minus eine Prämie für jeden belieferten Kunden, die die übergeordnete Planung festlegt; kleiner ist besser, auch negative Werte kommen vor), die Ankunftszeit bei Z, die schon geladene Last und die belieferten Kunden.

Ein Beispiel: Teilweg A hat 90 Euro gekostet und kommt am späten Nachmittag bei Z an. Teilweg B hat 70 Euro gekostet und kommt am frühen Nachmittag an. Beide haben gleich viel Last geladen, und B hat keinen Kunden beliefert, den A nicht auch beliefert hätte. B ist also billiger, früher da und sonst nicht schlechter. Alles, was der Wagen von Z aus noch tun kann, geht mit B mindestens ebenso gut. Teilweg A darf gestrichen werden. Das Fachwort dafür: B dominiert A.

Gestrichen wird nur, wenn alles stimmt

Im Beispiel kommt ein dritter Teilweg C dazu: Er hat nur 60 Euro gekostet, kommt aber erst am Abend bei Z an. Wer nur auf die Kosten schaut, würde B streichen, denn C ist billiger. Doch vielleicht schließt das Zeitfenster von Z schon am Nachmittag, dann kann nur B noch beliefern. Billig allein reicht nicht. Man muss alle vier Angaben vergleichen:

• Kosten: Der bleibende Teilweg darf nicht teurer sein als der gestrichene.
• Zeit: Wer später ankommt, verpasst vielleicht ein Zeitfenster. Wer früher ankommt, kann einfach warten, und das kostet in dieser Rechnung nichts.
• Last: Wer schon viel geladen hat, hat für weitere Kunden weniger Platz übrig.
• Belieferte Kunden: Wer einen Kunden schon beliefert hat, den der beste Gesamtweg noch braucht, kann ihn nicht noch einmal beliefern.

Gestrichen wird also nur, wenn der andere Teilweg in allen vier Angaben mindestens so gut ist. Sind beide in allem gleich, bleibt der ältere, sonst würden sich zwei gleiche gegenseitig streichen.

Wie ein Rechner das nutzt

Ein Rechner sucht so den besten Weg unter sehr vielen möglichen. Er hält jeden Teilweg mit den vier Angaben fest und verlängert ihn Kunde für Kunde. Ohne Streichen entstehen schnell sehr viele Teilwege. Darum prüft er an jedem Kunden, ob ein Teilweg von einem anderen dominiert wird, und streicht ihn dann.

Ein Programm zum Ausprobieren, kurz die Demo, zählt nach, was das Streichen bringt und was es kosten kann. Gezählt werden die erzeugten Teilwege, keine Sekunden.

Was die Zählung zeigt

In der Demo wurden 180 Fälle mit je 7 Kunden durchgerechnet und mit einer Suche verglichen, die alle möglichen Wege durchprobiert. Wer alle vier Angaben verglich, fand in allen 180 Fällen den besten Weg. Wer nur die Kosten verglich, verfehlte ihn in 67 dieser Fälle. In allen 67 fand der Rechner trotzdem noch einen Weg mit negativen Kosten, aber nicht den besten.

Dafür spart das Streichen Arbeit. Je breiter die Zeitfenster und je mehr Kunden, desto mehr Wege sind möglich. In der Demo erzeugte die Rechnung ohne Streichen bei 7 Kunden und engeren Zeitfenstern typischerweise gut ein Drittel mehr Teilwege, bei 20 Kunden und weiten Zeitfenstern mehr als dreimal so viele.

Der Haken: Weniger Teilwege heißen nicht automatisch weniger Rechenzeit, denn die Prüfung kostet selbst Zeit. Bei 20 Kunden und weiten Zeitfenstern war die Rechnung mit Prüfung in einer einzelnen Zeitmessung auf einem ausgelasteten Rechner langsamer als ohne. Über Rechenzeiten sagt die Demo nichts Allgemeines.

Häufige Missverständnisse

• „Der teurere Teilweg kann immer weg.“ Nein. Ist er früher da oder hat er weniger geladen, kann er den besseren Weg noch ermöglichen. Die Kosten sind nur eine von vier Angaben.
• „Streichen riskiert den besten Weg.“ Nur, wenn man zu großzügig streicht. Mit allen vier Angaben geht nichts verloren, sofern Warten erlaubt und kostenlos ist und keine weiteren Grenzen gelten. Die Begründung steht im Teil für Fachleute.
• „Früher ankommen ist immer besser.“ Hier ist früher ankommen nie schlechter, aber nur, weil Warten nichts kostet. Wo Warten Geld kostet, gilt der Satz nicht ohne Weiteres; das wurde nicht gemessen.

Woran Sie das im Alltag erkennen

• Sie vergleichen zwei Zugverbindungen bis zum selben Umsteigebahnhof. Die eine ist teurer, kommt später an und hat keinen Vorteil. Die streichen Sie sofort.
• Die billigere, aber spätere Verbindung streichen Sie nicht, bevor Sie wissen, ob Sie damit den Anschlusszug noch erreichen.

Wie ernst sind diese Beispiele zu nehmen?

Die Fälle sind erfunden: ein kleines Beispiel mit sechs Kunden zum Nachrechnen und zufällig erzeugte Fälle, keine echten Lieferdaten. Die Zahlen gelten für diese Fälle und zeigen die Größenordnung.

Was Sie mitnehmen:

• Ein Teilweg darf nur gestrichen werden, wenn ein anderer am selben Kunden in allen Angaben mindestens so gut ist, nicht nur bei den Kosten.
• Fragen Sie bei jeder Streichregel, welche Angabe sie weglässt und was sie dadurch verlieren kann.
• Weniger Teilwege sind nicht automatisch weniger Rechenzeit.

Zu dieser Seite gehört die Demo. Der erste Knopf unten öffnet sie, der zweite führt zum Teil für Fachleute.

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 das Preisproblem der Spaltenerzeugung: Ein Hauptplan (der Master) wählt Routen und rechnet jedem Kunden einen Dualpreis zu; das Preisproblem sucht eine neue Route, deren Strecke weniger kostet, als ihre Kunden an Dualpreisen einbringen, also den Weg mit den kleinsten reduzierten Kosten unter Zeitfenstern, Last und höchstens einem Besuch je Kunde (elementar). Die Demo, ein Programm zum Ausprobieren, zählt dazu Labels. Alle Zahlen gelten nur für die genannten Instanzen und Regeln.

• Netz: ein Depot \(0\) und Kunden \(1,\dots,n\) mit Entfernung \(d_{ij}\) (gleich der Fahrzeit; sie geht als Streckenkosten in \(C'\) und als Fahrzeit in \(T'\) ein), Last \(q_j\) (nicht negativ), Zeitfenster \([e_j, l_j]\) für den Beginn der Bedienung und Dualpreis \(\pi_j\) (\(\pi_0 = 0\)); dazu Kapazität \(Q\), Bedienzeit \(s\) je Kunde und Horizont \(H\) (späteste Rückkehr ins Depot). Wer vor \(e_j\) ankommt, wartet kostenlos. Der Dualpreis ist der Betrag, den die übergeordnete Planung (der Master der Spaltenerzeugung) einem Kunden zurechnet.
• Label: Ein Label am Kunden \(i\) ist \((T, C, R, V)\): Zeit \(T\) (Beginn der Bedienung), reduzierte Kosten \(C\), verbrauchte Last \(R\) und die Menge \(V\) der besuchten Kunden (das Gedächtnis). Das Start-Label im Depot ist \((0, 0, 0, \emptyset)\). Das Verfahren verlängert Labels in Zeitreihenfolge um je einen Kunden. Ein neues Label wird verworfen, wenn ein lebendes Label am selben Kunden es dominiert; sonst verdrängt es alle lebenden Labels, die es dominiert. Gestrichen ist also das dominierte Label, nicht das dominierende.
• Instanzen: (a) Das Handbeispiel mit 6 Kunden, Manhattan-Abstand auf einem Gitter, nur ganze Zahlen, Bedienzeit 2, Horizont 36, Kapazität 12 (Daten im Abschnitt „Das Handbeispiel zum Nachrechnen“). (b) Zufallsinstanzen im Stil der Solomon-Instanzen (einer verbreiteten Sammlung von Testinstanzen für Touren mit Zeitfenstern; Quadrat 100 × 100, Fahrzeit gleich Entfernung, Bedienzeit 10, Kapazität 70, Horizont 300, Fensterbreite höchstens 30, 80 oder 200; die Fenster werden auf die erreichbare Zeitspanne beschnitten: nicht früher als die Fahrzeit vom Depot, nicht später als der Horizont minus Bedienzeit und Rückfahrt), nicht die Originalinstanzen, mit zufälligen Dualpreisen (gleichverteilt zwischen 20 und 70). (c) Die Gegenprobe ist ein anderes Modell: \(d_{ij}\) ist dort eine zufällige Fahrzeit, nicht aus Punkten berechnet und nicht symmetrisch; die Dreiecksungleichung (ein Umweg über einen dritten Punkt ist nie kürzer als der direkte Weg) ist nicht erzwungen. Auch dort geht \(d_{ij}\) wie sonst als Kosten in \(C'\) und als Fahrzeit in \(T'\) ein (6 Kunden, Fensterbreite 30).
• Regeln: keine Dominanz, nur Kosten, Kosten + Zeit, Kosten + Last, Kosten + Gedächtnis (besuchte Kunden als Teilmenge), Kosten + Zeit + Last und die volle Regel; in der Regel-Tabelle zwei weitere Mischformen. Als Bezug dient die Aufzählung (das Orakel), eine Tiefensuche über alle Routen ohne Labels; eine Route besucht mindestens einen Kunden.
• Gedächtnis k: Mit k gleich der Kundenzahl bleibt jeder besuchte Kunde im Gedächtnis (elementar: jeder Kunde höchstens einmal). Bei k = 3 behält ein Label besuchte Kunden nur, solange sie zu den 3 nächsten Kunden jedes weiteren Halts gehören (den Kunden selbst eingerechnet; bei gleicher Entfernung zählt die kleinere Kundennummer zuerst); sonst darf der Kunde wiederkehren (nicht elementar).
• Zählung: Gezählt werden erzeugte Labels, jedes erzeugte, auch ein sofort gestrichenes, plus das Start-Label, keine Sekunden. Alle Zählungen gelten für feste Zufalls-Seeds, also dieselben Instanzen bei jedem Lauf, in Python.

Die Formeln

Reduzierte Kosten einer Route \(r = (j_0 = 0, j_1, \dots, j_m, j_{m+1} = 0)\):

\[\bar c(r) = \sum_{t=0}^{m} d_{j_t j_{t+1}} - \sum_{t=1}^{m} \pi_{j_t}\]

Fortsetzung eines Labels \((T, C, R, V)\) am Knoten \(i\) zum Kunden \(j \notin V\) (mit der Iverson-Klammer \(s\,[i \ne 0]\): \([i \ne 0]\) ist 1, wenn \(i \ne 0\), sonst 0; im Depot entfällt die Bedienzeit):

\[T' = \max\bigl(e_j,\; T + s\,[i \ne 0] + d_{ij}\bigr), \quad C' = C + d_{ij} - \pi_j, \quad R' = R + q_j, \quad V' = V \cup \{j\}\]

Die Formel für \(V'\) gilt elementar (\(k = n\)). Bei Gedächtnis \(k\) wird die Menge beim Fortsetzen auf die \(k\) nächsten Kunden von \(j\) eingeschränkt: \(V' = (V \cap N_k(j)) \cup \{j\}\), mit \(N_k(j)\) als Menge der \(k\) nächsten Kunden von \(j\) einschließlich \(j\). Zulässig ist die Fortsetzung, wenn \(T + s\,[i \ne 0] + d_{ij} \le l_j\) und \(R' \le Q\) gelten. Zurück ins Depot geht es, wenn

\[T + s + d_{i0} \le H\]

Die fertige Route eines Labels am Kunden \(i\) hat die reduzierten Kosten \(C + d_{i0}\): Das Label selbst enthält die Rückfahrt noch nicht, \(\bar c(r)\) schon.

Dominanz (volle Regel): \(L_1\) dominiert \(L_2\) am selben Kunden, wenn

\[L_1 \preceq L_2 \iff C_1 \le C_2, \quad T_1 \le T_2, \quad R_1 \le R_2, \quad V_1 \subseteq V_2\]

Dann wird \(L_2\) gestrichen. Bei Gleichstand in allen vier Größen bleibt das ältere Label. Die Regel gilt unter der Bedingung, dass Warten vor \(e_j\) erlaubt und kostenlos ist und keine weiteren Grenzen hinzukommen.

Herleitung: warum die volle Regel nichts verliert

Die folgenden Schritte schreiben das Argument aus. Die ausgedachten Zahlen im zweiten Teil sind Rechnung dieser Seite, keine Messung.

• Schritt 1 (Zeit): Gilt \(T_1 \le T_2\), dann gilt für jede Fortsetzung zu \(j\) auch \(\max(e_j, T_1 + s\,[i \ne 0] + d_{ij}) \le \max(e_j, T_2 + s\,[i \ne 0] + d_{ij})\), denn das Maximum fällt nicht, wenn ein Argument wächst. Ist die Fortsetzung für \(L_2\) zulässig, hält \(L_1\) also Fenster \(l_j\) und Horizont \(H\) ebenfalls ein; das gilt Station für Station. Bedingung: Warten ist erlaubt, nur deshalb ist früher ankommen nie schlechter.
• Schritt 2 (Last): Aus \(R_1 \le R_2\) folgt \(R_1 + q_j \le R_2 + q_j \le Q\) entlang jeder Fortsetzung.
• Schritt 3 (Gedächtnis): Aus \(V_1 \subseteq V_2\) folgt: Jeder Kunde \(j \notin V_2\) ist auch nicht in \(V_1\), und die Teilmengenbeziehung bleibt nach jeder gemeinsamen Fortsetzung erhalten, auch bei \(V' = (V \cap N_k(j)) \cup \{j\}\), denn Schnitt und Vereinigung erhalten \(\subseteq\). Mit weniger besuchten Kunden hat \(L_1\) mehr freie Kunden.
• Schritt 4 (Kosten): Die Zuwächse \(d_{ij} - \pi_j\) hängen nur von der Fortsetzung ab, nicht vom Label, und die Rückfahrt \(d_{i0}\) am Ende ist für beide Labels an demselben Kunden gleich. Aus \(C_1 \le C_2\) folgt, dass die fertige Route von \(L_1\) (\(C_1\) plus Zuwächse plus Rückfahrt) nicht teurer ist als die von \(L_2\).
• Schluss: Jede zulässige Fortsetzung von \(L_2\) ist für \(L_1\) zulässig und nicht teurer; \(L_2\) darf gestrichen werden, ohne das Optimum zu verlieren. Bei Gleichstand bleibt das ältere Label, damit sich zwei gleiche nicht gegenseitig streichen.

Last neben Gedächtnis. Elementar ist \(R = \sum_{j \in V} q_j\), denn jeder Kunde kommt höchstens einmal vor. Bei nicht negativen Lasten folgt \(R_1 \le R_2\) dann schon aus \(V_1 \subseteq V_2\): Schritt 2 ist elementar eine Folge von Schritt 3, und die Last-Bedingung ändert neben dem Gedächtnis nichts. Das zeigen die Zählungen: Die Regeln „Kosten + Gedächtnis“ und „Kosten + Last + Gedächtnis“ erzeugen in den 180 Fällen der Regel-Tabelle im Median, Mittel und Maximum gleich viele Labels (im Handbeispiel je 45 erzeugte und 15 gestrichene, siehe die Handbeispiel-Tabelle unter Befunde), und „Kosten + Zeit + Gedächtnis“ gleicht der vollen Regel. Bei Gedächtnis \(k < n\) vergisst \(V\) Kunden, die Last nicht; bei \(k = 3\) unterscheiden sich die Zahlen der erzeugten und der gestrichenen Labels (als Paar) von „Kosten + Gedächtnis“ und „Kosten + Last + Gedächtnis“ in 173 der 180 Fälle (Nachzählung dieser Seite mit dem Code der Demo).

Wo eine Bedingung fehlt, bricht der Beweisschritt. Drei ausgedachte Fälle (nicht aus den Instanzen), je \(C_1 \le C_2\), sodass der Kostenvergleich \(L_2\) streicht. Für die Last gilt das elementar nur ohne Gedächtnisvergleich (bei \(k < n\) auch mit ihm, siehe den vorigen Absatz):

• Zeit nicht geprüft: \(T_1 = 5\), \(T_2 = 3\), die Fortsetzung zu \(j\) dauert \(s\,[i \ne 0] + d_{ij} = 2\), \(e_j \le 5\) und \(l_j = 6\). Für \(L_2\) ist die Ankunft 5 und zulässig, für \(L_1\) ist sie 7 und verletzt das Fenster.
• Last nicht geprüft (und kein Gedächtnisvergleich): \(R_1 = 5\), \(R_2 = 3\), \(q_j = 2\), \(Q = 6\). Für \(L_2\) ergibt sich 5, für \(L_1\) ergibt sich 7, und die Kapazität ist überschritten.
• Gedächtnis nicht geprüft: Hat \(L_1\) den Kunden \(j\) schon besucht (\(j \in V_1\), \(j \notin V_2\)) und braucht der beste Weg \(j\) als nächsten Halt, kann \(L_1\) ihn nicht mehr anfahren.

Das Handbeispiel zum Nachrechnen

Das Depot liegt auf dem Gitterpunkt (5, 5). Die Entfernung zwischen zwei Punkten ist der Manhattan-Abstand \(|x_1 - x_2| + |y_1 - y_2|\) und zugleich die Fahrzeit. Bedienzeit \(s = 2\), Horizont \(H = 36\), Kapazität \(Q = 12\). Routen stehen als Kundenfolge ohne Depot: 6-2-3-5 heißt Depot, Kunde 6, 2, 3, 5, Depot.

Kunde	Punkt	Last \(q_j\)	Fenster \([e_j, l_j]\)	Dualpreis \(\pi_j\)
1	(7, 3)	2	[6, 16]	8
2	(1, 9)	3	[8, 16]	12
3	(1, 10)	3	[9, 18]	12
4	(6, 7)	6	[17, 27]	9
5	(5, 10)	2	[16, 26]	9
6	(1, 7)	2	[10, 20]	7

Der beste Weg 6-2-3-5. Strecke: \(6 + 2 + 1 + 4 + 5 = 18\). Dualpreise: \(7 + 12 + 12 + 9 = 40\). Reduzierte Kosten: \(18 - 40 = -22\). Zeiten: Ankunft bei Kunde 6 zur Zeit 6, das Fenster beginnt bei 10, also beginnt die Bedienung bei 10; bei Kunde 2: \(10 + 2 + 2 = 14\) (Fenster [8, 16]); bei Kunde 3: \(14 + 2 + 1 = 17\) (Fenster [9, 18]); bei Kunde 5: \(17 + 2 + 4 = 23\) (Fenster [16, 26]); Rückkehr ins Depot: \(23 + 2 + 5 = 30 \le 36\). Last: \(2 + 3 + 3 + 2 = 10 \le 12\). Die Aufzählung findet 52 zulässige Routen; keine hat kleinere reduzierte Kosten, und der beste Weg ist eindeutig.

Wo „nur Kosten“ den besten Weg verliert. Zwei Streichungen dieses Beispiels, mit den Labels in der Form (Zeit, Kosten, Last, besuchte Kunden):

• Nur Kosten: Das Label des Weges 6 (Zeit 10, Kosten −1, Last 2, besucht {6}) wird vom Label des Weges 2-6 (Zeit 12, Kosten −9, Last 5, besucht {2, 6}) gestrichen, weil −9 ≤ −1. Das dominierende Label ist später, hat mehr Last und schon Kunde 2 besucht; der beste Weg braucht Kunde 2 aber nach der 6. Gefunden wird 2-3-6-5 mit −16 (einer von zwei Wegen mit −16, der andere ist 3-2-6-5).
• Kosten + Zeit: Das Label des Weges 6-2 (Zeit 14, Kosten −11, Last 5, besucht {2, 6}) wird vom Label des Weges 3-2 (Zeit 12, Kosten −14, Last 6, besucht {2, 3}) gestrichen, weil −14 ≤ −11 und 12 ≤ 14. Das dominierende Label hat mehr Last und Kunde 3 schon besucht; der beste Weg braucht Kunde 3 als nächsten Halt. Gefunden wird 2-6-3-5 mit −18.

Befunde

Handbeispiel (6 Kunden, elementar). Erzeugte und gestrichene Labels je Regel, und der Weg, den die Regel findet.

Regel	Labels erzeugt / gestrichen	gefundener Weg (reduzierte Kosten)
keine Dominanz	53 / 0	6-2-3-5 (−22)
nur Kosten	18 / 11	2-3-6-5 (−16; einer von zwei Wegen mit −16)
Kosten + Zeit	35 / 19	2-6-3-5 (−18)
Kosten + Last	41 / 20	6-2-3-5 (−22)
Kosten + Gedächtnis	45 / 15	6-2-3-5 (−22)
Kosten + Zeit + Last	42 / 20	6-2-3-5 (−22)
Kosten + Zeit + Gedächtnis	45 / 15	6-2-3-5 (−22)
Kosten + Last + Gedächtnis	45 / 15	6-2-3-5 (−22)
volle Regel	45 / 15	6-2-3-5 (−22)

Regel-Tabelle. 180 Fälle: 60 Zufallsinstanzen mit 7 Kunden, je mit den Fensterbreiten 30, 80 und 200, zufällige Dualpreise. „Elementar“ vergleicht gegen die Aufzählung aller Routen, „k = 3“ gegen das Ergebnis ohne Dominanz bei k = 3. Labels: Median / Mittel / Maximum über die 180 Fälle (Mediane gerundet, wo der Median das Mittel zweier Werte ist).

Regel	elementar: Weg verfehlt	elementar: Labels Median / Mittel / Maximum	k = 3: weicht ab
keine Dominanz	0 (0,0 %)	85 / 188,1 / 1 404	0 (0,0 %)
nur Kosten	67 (37,2 %)	26 / 27,4 / 49	72 (40,0 %)
Kosten + Zeit	37 (20,6 %)	42 / 51,4 / 150	35 (19,4 %)
Kosten + Last	20 (11,1 %)	52 / 66,7 / 203	22 (12,2 %)
Kosten + Gedächtnis	0 (0,0 %)	58 / 91,8 / 378	31 (17,2 %)
Kosten + Zeit + Last	12 (6,7 %)	56 / 73,5 / 253	14 (7,8 %)
Kosten + Zeit + Gedächtnis	0 (0,0 %)	58 / 94,5 / 403	10 (5,6 %)
Kosten + Last + Gedächtnis	0 (0,0 %)	58 / 91,8 / 378	2 (1,1 %)
volle Dominanz	0 (0,0 %)	58 / 94,5 / 403	0 (0,0 %)

Wo „nur Kosten“ den besten Weg verfehlt (67 Fälle), findet die Regel im Median 87,6 % des besten reduzierten Kostenwertes (beide Werte sind negativ, 100 % hieße gleich gut; Minimum 18,3 %). In allen 67 Fällen ist der gefundene Weg noch eine verbessernde Route, also eine Route mit negativen reduzierten Kosten.

Frage	Befund
Gegenprobe in einem anderen Modell (zufällige, nicht symmetrische Fahrzeiten, Dreiecksungleichung nicht erzwungen): Verfehlt „Kosten + Gedächtnis“ den besten Weg? (3 000 Zufallsinstanzen mit 6 Kunden, Fensterbreite 30, Zufalls-Seeds 0 bis 2999, elementar, Bezug Aufzählung)	Verfehlte Wege: nur Kosten 413, Kosten + Zeit 144, Kosten + Last 42, Kosten + Gedächtnis 1 (Zufalls-Seed 209), Kosten + Zeit + Last 0, volle Regel 0.
Wie viel mehr Labels ohne Dominanz? (die 180 Fälle, Fensterbreiten gemischt)	Je Fall im Median das 1,42-Fache der Labels der vollen Regel (Minimum 1,00, Maximum 4,86).
Wie wächst der Faktor (Labels ohne durch Labels mit voller Dominanz)? (je Kombination aus Kundenzahl und Fensterbreite 10 Instanzen, Zufalls-Seeds 0 bis 9, elementar)	Bei 7 Kunden im Median 1,35 (Breite 80) bzw. 2,08 (Breite 200), bei 20 Kunden 2,36 bzw. 3,49; größter Einzelfaktor 6,02 (Breite 200, 14 Kunden).
Welcher Anteil der Labels wird gestrichen? (30 Kunden, ganze Spaltenerzeugung, nicht elementar mit Gedächtnis k = 1, 3, 5, Fensterbreite 40, 100, 200, je 6 Instanzen)	Mit voller Dominanz 78,2 bis 91,4 % der erzeugten Labels (Mittel der Anteile je Lauf, über die Läufe ohne Abbruch).
Was passiert in der Spaltenerzeugung? Der Master ist hier eine LP-Relaxation der Überdeckung: Er wählt aus den bisher gefundenen Routen eine billigste, auch anteilige Überdeckung der Kunden. Die Rechnung endet, wenn das Label-Verfahren keinen Weg mit negativen reduzierten Kosten mehr findet; ihr Zielwert bei Abbruch ist die Schranke. (10 Instanzen mit 10 Kunden, Fensterbreite 80, elementar, Dualpreise aus dem Master)	Mit „nur Kosten“ endet sie in 5 von 10 Instanzen bei einer höheren Schranke als mit der vollen Regel: im Mittel über alle 10 Instanzen (die gleichen zählen als 0) um 1,216 %, höchstens um 8,476 %, jeweils bezogen auf die Schranke der vollen Regel. Eine höhere Schranke liegt über dem LP-Wert des vollständigen Masters (mit allen Routen) und ist darum keine gültige Untergrenze mehr, weil dem Label-Verfahren Wege fehlten; die volle Regel liefert hier den wahren LP-Wert, sofern sie jedes Mal den besten Weg findet.
Wie ist es mit der Rechenzeit? (eine einzelne Messung, 20 Kunden, Breite 200, 10 Instanzen, ausgelasteter Rechner)	In dieser einen Messung war die Rechnung mit voller Dominanz langsamer: 26,4 s mit gegen 4,2 s ohne Dominanz (Summe über die 10 Instanzen, nicht je Instanz). Das widerspricht nicht den weniger erzeugten Labels (Faktor 3,49 im Median bei 20 Kunden und Breite 200): Die Prüfung kostet je Label Zeit (Deutung der Demo). Sekunden hängen vom Rechner ab; es gibt keine allgemeine Aussage über Rechenzeit.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• In den 180 Fällen mit 7 Kunden (elementar, Fahrzeit gleich Entfernung, zufällige Dualpreise) weicht die volle Regel in keinem Fall vom Ergebnis der Aufzählung ab, „nur Kosten“ in 67, „Kosten + Zeit“ in 37, „Kosten + Last“ in 20, „Kosten + Zeit + Last“ in 12; die Regeln mit Gedächtnis in keinem.
• Bei Gedächtnis k = 3 weichen vom Ergebnis ohne Dominanz alle Regeln ab außer der vollen (der Bezug „keine Dominanz“ selbst nicht gerechnet): „Kosten + Gedächtnis“ in 31, „Kosten + Zeit + Gedächtnis“ in 10, „Kosten + Last + Gedächtnis“ in 2 der 180 Fälle. Dort ändert also auch die Last-Bedingung neben dem Gedächtnis etwas; elementar tut sie es nicht (siehe Herleitung).
• Am Handbeispiel verfehlen „nur Kosten“ und „Kosten + Zeit“ den besten Weg; die Labels stehen im Abschnitt zum Nachrechnen.
• Mit „nur Kosten“ kann die Schranke der Spaltenerzeugung zu hoch ausfallen: in 5 von 10 Instanzen mit 10 Kunden, Breite 80, elementar.

Was sie nicht belegt:

• „Kosten + Gedächtnis“ ist kein Satz: Die Regel verfehlt den besten Weg bei 7 Kunden in 0 von 180 Fällen (Fahrzeit gleich Entfernung); in der Gegenprobe, einem anderen Modell mit zufälligen, nicht symmetrischen Fahrzeiten, gibt es 1 Fall. Ob die Dreiecksungleichung die Ursache ist, ist nicht untersucht.
• Rechenzeit: Gezählt werden Labels, nicht Sekunden. Die Dominanzprüfung kostet in reinem Python je Label Zeit (Deutung der Demo); die eine Messung bei 20 Kunden und Breite 200 zeigt, dass die Prüfung mehr Zeit kosten kann, als die gesparten Labels einbringen. Eine allgemeine Aussage über die Rechenzeit, in die eine oder andere Richtung, folgt daraus nicht.
• Warten und weitere Grenzen: Warten ist hier erlaubt und kostenlos; ohne Warten gilt „früher ankommen ist nie schlechter“ nicht. Weitere Grenzen wie die Fahrerzeit brauchen weitere Bedingungen. Beides ist nicht gemessen.
• Dualpreise: In der Regel-Tabelle und in den Wachstumsreihen bis 20 Kunden sind sie zufällig gezogen, nicht die einer echten Spaltenerzeugung; die Messung zur Spaltenerzeugung (10 Kunden) und die Anteile bei 30 Kunden rechnen die ganze Spaltenerzeugung. Deren Zahlen hängen vom Weg des Master-Problems ab und können mit einer anderen Version der Bibliothek leicht abweichen.
• Größe und Herkunft der Instanzen: Eigene Instanzen im Stil der Solomon-Instanzen, nicht die Originalinstanzen. Die Regel-Tabelle hat nur 7 Kunden, die Wachstumsreihen höchstens 20, die Spaltenerzeugung 10 Kunden. Bei 30 Kunden ist nur der Anteil gestrichener Labels gemessen, nicht der Faktor.
• Andere Dominanzregeln: Gemessen sind genau die Regeln dieser Seite, nicht andere Regeln aus der Literatur (etwa mit Erweiterungsfunktionen oder bei mehr als zwei Grenzen).
• Ursachen: Wo hier ein „weil“ steht, ist es eine Deutung; gemessen sind die Zählungen.

Erweiterungen und Verweise

Verwandte Seiten und Demos dieser Website:

• Dominanz zwischen zwei Kosten: Die multicriteria-demo zeigt die Pareto-Front (die Wege, von denen keiner in zwei Kosten zugleich besser ist als ein anderer); hier kommen Verbrauch gegen eine Grenze und die besuchten Kunden dazu. Eine Erklärseite dazu steht unter Pareto-Dominanz.
• Die Anwendung in einem Fall: Die crew-pairing-demo nutzt Dominanz im Preisproblem der Besatzungsplanung im Zugverkehr (dort nicht gemessen); die Erklärseite dazu ist Crew Pairing.
• Spaltenerzeugung mit kürzestem Weg: Die mcf-column-generation-demo zeigt ein Preisproblem ohne Ressourcen.
• Nicht verwechseln: Die hub-labeling-demo meint etwas anderes: vorberechnete Listen für schnelle Abfragen kürzester Wege. Hier sind Labels Teilwege.

Quellen

• Desrochers, Soumis (1988): A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR (Labels beim Weg mit Zeitfenstern).
• Feillet, Dejax, Gendreau, Gueguen (2004): An exact algorithm for the elementary shortest path problem with resource constraints. Networks (Elementarität als Ressource, Dominanz mit Besuchsmengen).
• Irnich, Desaulniers (2005): Shortest path problems with resource constraints. Kapitel 2 in Column Generation, Springer (Dominanz mit Erweiterungsfunktionen).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/dominanz-labels-demo.

Autoren, Titel, Zeitschrift und Jahr der genannten Arbeiten wurden laut Demo per Suchtreffer geprüft; die Volltexte sind nicht gelesen, und aus ihnen ist keine Zahl übernommen. Die Befunde geben die Messreihen der Demo wieder; die ausgedachten Zahlen der Herleitung, die Rechnung zum besten Weg des Handbeispiels, die Nachzählung zu k = 3 sind Rechnung dieser Seite.