ng-Routen verständlich erklärt
Ein Fahrer beliefert Kunden und merkt sich nicht jeden Halt, sondern nur, welche der nächstgelegenen Kunden er gerade erst hatte. Ein Kunde darf wieder angefahren werden, sobald dazwischen ein Halt kam, in dessen Nähe er nicht liegt. Diese Seite erklärt dieses begrenzte Gedächtnis (Fachname: ng-Routen), wie viel davon genügt und was Messungen dazu zeigen.
Zuletzt aktualisiert:
Ein Wort unbekannt? Das Begriffsverzeichnis erklärt es in wenigen Sätzen.
Ein Fahrer und seine Preisliste
Ein Fahrer beliefert Kunden. Jeder Kunde hat ein Zeitfenster: Nur dann darf der Fahrer ihn bedienen. Ein Planungsprogramm setzt aus möglichen Touren den Plan für alle Fahrer zusammen und sucht dafür immer wieder neue, lohnende Touren.
Dazu bekommt jeder Kunde einen Preis (Fachwort: Dualpreis): So viel ist es dem Plan gerade wert, dass dieser Kunde bedient wird. Eine Tour wird so bewertet: gefahrene Strecke minus die Preise der besuchten Kunden. Beispiel: Strecke 5, Preise 2 und 4, das ergibt 5 − 2 − 4 = −1. Unter null lohnt sich die Tour und kommt in die Auswahl, aus der die Planung wählt. Dann rechnet das Programm die Preise neu und sucht erneut, bis keine Tour mehr lohnt. Diese Suche heißt Preisproblem.
Am Ende der Suche steht eine Untergrenze: Sie sagt, wie billig der Gesamtplan mindestens werden kann. Je höher, desto nützlicher. Findet die Suche scheinbar lohnende Touren, die es in Wirklichkeit nicht sind, rechnet sie zu billig, und die Untergrenze kann niedriger werden.
Zwei bequeme Regeln mit je einem Haken
Regel A: Ein Kunde darf immer wieder vorkommen, nur nicht gleich nach sich selbst. Kehrt die Tour so zu einem Kunden zurück, heißt das Kreis. Die Suche wird in den Zufallsbeispielen der Demo billiger (im kleinen Handbeispiel nicht), aber ein Kunde wird nur einmal bedient, die Rechnung zieht seinen Preis bei jedem Besuch ab. Beispiel: Kunde A hat den Preis 5, hin und zurück sind es 6: 6 − 5 = 1, kein Gewinn. Mit Abstecher zu einem nahen Kunden B (Preis 1) und zurück zu A kommen 2 Strecke dazu, A wird aber noch einmal abgezogen: 8 − 5 − 1 − 5 = −3. Die Tour scheint sich zu lohnen, obwohl A nur einmal bedient wird; solche Scheintouren können die Untergrenze senken.
Regel B: Jeder Kunde höchstens einmal. Das Programm baut Touren Halt für Halt auf, und einen angefangenen Weg nennen wir Teilweg. Bei Regel B muss es sich zu jedem Teilweg die ganze Liste der besuchten Kunden merken, und bei vielen Kunden und breiten Zeitfenstern wird die Suche sehr teuer. Erklärung dieser Seite, nicht gemessen: Ein Teilweg mit der Liste {1, 2} kann einen mit {1, 2, 3} aussortieren, wenn er sonst nicht schlechter ist; bei {1, 2} und {1, 3} geht das nicht. Lange Listen lassen also mehr Teilwege übrig.
Der Mittelweg: ein Zettel mit kleiner Liste
Jeder Kunde hat eine Nachbarschaft: er selbst und seine nächstgelegenen Kunden. Die Größe heißt k: Bei 1 gehört nur der Kunde selbst dazu, bei 3 er und die zwei nächsten. Die Regel: Ein Kunde darf erst wieder besucht werden, wenn dazwischen ein Kunde kam, in dessen Nachbarschaft er nicht liegt.
Dafür führt der Fahrer einen Zettel mit den gesperrten Kunden. An jedem Halt prüft er erst, ob der Kunde auf dem Zettel steht: Dann ist die Tour verboten. Sonst streicht er jeden Namen, der nicht zur Nachbarschaft dieses Kunden gehört, und schreibt den Kunden dazu.
Beispiel aus der Demo, einem Programm zum Ausprobieren zu dieser Seite; Nachbarschaften aus zwei Kunden: Zu Kunde 6 gehören 6 und 7, zu Kunde 3 die Kunden 3 und 4, zu Kunde 5 die Kunden 3 und 5. Die Nachbarschaft muss nicht gegenseitig sein: 3 gehört zu der von 5, 5 aber nicht zu der von 3. Tour 7-6-7: Nach Halt 7 steht {7} auf dem Zettel, nach Halt 6 steht {6, 7}; 7 ist gesperrt, verboten. Tour 5-3-5-1: Nach Halt 5 steht {5}. Bei Halt 3 fällt 5 weg (nicht in der Nachbarschaft von 3): {3}. Kunde 5 ist frei, danach steht {3, 5}, Kunde 1 ist frei: erlaubt.
Wie groß soll die Nachbarschaft sein?
Die Größe ist ein Regler zwischen den Regeln: Ganz klein ist es Regel A, umfasst sie alle Kunden, ist es Regel B. Dazwischen steigt die Untergrenze mit der Größe oder bleibt gleich, nie liegt sie über der von Regel B (bewiesen im Fachteil). Der Preis: Bei den Zufallsbeispielen mit 30 Kunden prüft das Programm mit größerer Nachbarschaft im Mittel mehr Teilwege.
Gemessen, jeweils mit Vergleichsgröße:
- Handbeispiel, 7 Kunden: Ab 3 Kunden in der Nachbarschaft ist die Untergrenze so hoch wie bei Regel B, mit weniger liegt sie tiefer.
- 30 Kunden, Zufallsbeispiele mit breiten Zeitfenstern: Mit 5 statt 8 Kunden in der Nachbarschaft lag die Untergrenze im Mittel unter 1 % tiefer, auch im ungünstigsten Beispiel (bezogen auf die Untergrenze bei 8).
- 50 und 100 Kunden: Regel B ließ sich fast nie zu Ende rechnen, darum dient eine sehr große Nachbarschaft als Vergleich. Gegen sie lag die Untergrenze bei 5 in allen gemessenen Fällen unter 1 % tiefer.
- Engste Zeitfenster der Demo (20 Zeiteinheiten lang): Für die Untergrenze genügte schon die kleinste Nachbarschaft, verglichen mit der größten gerechneten; mehr Teilwege kostete eine größere trotzdem (bei 100 Kunden gemessen).
Häufige Missverständnisse
- „Das Gedächtnis sind die letzten Halte.“ Nein. Ein Kunde in der Nähe bleibt auch nach vielen Halten gesperrt, solange er in der Nachbarschaft jedes Halts dazwischen liegt; einer, der nicht zu den nächsten Kunden des folgenden Halts gehört, fällt schon dort vom Zettel.
- „Mit 5 Nachbarn genügt es immer.“ Nein. Bei 20 Kunden und breiten Zeitfenstern lag die Untergrenze mit 5 in zwei von sechs Zufallsbeispielen tiefer als bei Regel B.
Woran Sie das im Alltag erkennen
- Wird die Suche bei vielen Kunden und breiten Zeitfenstern zu teuer, lohnt die Frage, ob sich das Programm jeden besuchten Kunden merken muss.
Wie ernst ist das Rechenbild zu nehmen?
Außer im Handbeispiel sind Kunden und Zeitfenster zufällig erzeugt (im Stil bekannter Testaufgaben), je Fall sechs bis zwölf Beispiele. Gezählt werden Teilwege, nicht Sekunden.
Was Sie mitnehmen:
- Fragen Sie bei jeder Zahl, womit verglichen wird.
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. Alle Zahlen stammen aus den Messreihen der Demo und gelten nur für die genannten Instanzen. „ng“ ist der Name der Wegklasse in der Literatur (Baldacci u. a. 2011); die Seite löst ihn nicht auf.
- Rahmen: Spaltenerzeugung mit einem Überdeckungs-Master \(\min \sum_r c_r x_r\) unter \(\sum_r \beta_{jr} x_r \ge 1\) für alle Kunden \(j\) und \(x \ge 0\); dabei ist \(\beta_{jr}\) die Zahl der Besuche von \(j\) im Weg \(r\) und \(c_r\) dessen Länge. Der Master liefert Dualpreise \(\pi_j\), das Preisproblem sucht den Weg mit den kleinsten reduzierten Kosten. Eine Runde ist ein Durchlauf aus Master und Preisproblem; die Rechnung endet, wenn kein Weg negative reduzierte Kosten hat. Ihr Zielwert ist die Schranke \(z\), eine Untergrenze für die Gesamtplanung: Jeder elementare Weg gehört zu den erlaubten Wegen jeder Gedächtnisgröße, die Schranke kann also nicht über dem Wert der Gesamtplanung liegen.
- Instanz: ein Depot \(0\) und \(n\) Kunden \(1, \dots, n\). \(d_{ij}\) ist die Entfernung von \(i\) nach \(j\), zugleich Fahrzeit und Kosten je Strecke; \(q_j\) die Last des Kunden \(j\), \(Q\) die Kapazität; \([e_j, l_j]\) das Zeitfenster (frühester und spätester Beginn der Bedienung bei \(j\)); Warten vor \(e_j\) ist kostenlos. \(s\) ist die Bedienzeit je Kunde (je Instanz ein fester Wert), \(H\) der Horizont (späteste Rückkehr ins Depot), \(\pi_j\) der Dualpreis von \(j\) mit \(\pi_0 = 0\).
- Handbeispiel: Depot und 7 Kunden, Manhattan-Abstand auf einem Gitter, alle Zahlen ganz, \(s = 2\), \(Q = 6\), \(H = 38\); die Dualpreise der ersten Runde sind das Zweifache des Abstands zum Depot. Die Daten stehen in der Tabelle unten.
- Zufallsinstanzen: im Stil der Solomon-Instanzen, aber nicht deren Originale: Quadrat 100 × 100, Fahrzeit gleich Entfernung, \(s = 10\), \(Q = 70\), \(H = 300\), Fensterbreite 20, 40 oder 100 (Breite des Zeitfensters), Kunden zufällig verteilt oder in fünf Gruppen („gruppiert“).
- Nachbarschaft und Gedächtnis: Kunde \(j\) und seine \(k-1\) nächsten Kunden nach Abstand; bei Gleichstand der Abstände hat die kleinere Nummer Vorrang. \(k = 1\) verbietet nur „\(i\) direkt nach \(i\)“, \(k = n\) ist elementar (jeder Kunde höchstens einmal). Ein Weg ist erlaubt, wenn er die Gedächtnisregel einhält, und zulässig, wenn er außerdem Last, Zeitfenster und Horizont einhält. „k-Zyklen“ heißt das Verbot kurzer Kreise mit dem Parameter \(K\) (Kontrast unten).
- Messreihen: Eine Zelle ist eine Kombination aus Kundenzahl, Fensterbreite und Verteilung (zufällig oder gruppiert); der Bezug einer Lücke ist die Schranke, gegen die sie gemessen wird. Gezählt werden erzeugte Labels (jedes erzeugte Label, auch ein sofort gestrichenes, plus das Start-Label), keine Sekunden. Reihen: 24 Instanzen mit 30 Kunden (Bezug ng \(k = 8\)); 10 bis 30 Kunden mit 6 Instanzen je Zelle (Bezug elementar); 50 und 100 Kunden mit 12 Instanzen je Zelle (Bezug \(k = 16\)); dazu eine DSSR-Reihe.
Daten des Handbeispiels (Depot im Punkt \((0, 0)\); Entfernungen als Manhattan-Abstand):
| Kunde | Punkt | Last | Zeitfenster [früh, spät] | Dualpreis (Runde 1) |
|---|---|---|---|---|
| 1 | (−1, 2) | 1 | [18, 28] | 6 |
| 2 | (0, 3) | 3 | [3, 16] | 6 |
| 3 | (−3, −2) | 3 | [5, 15] | 10 |
| 4 | (−1, −2) | 3 | [20, 28] | 6 |
| 5 | (−2, −1) | 1 | [3, 12] | 6 |
| 6 | (2, 1) | 1 | [11, 21] | 6 |
| 7 | (3, 2) | 2 | [8, 20] | 10 |
Die Formeln
Reduzierte Kosten eines Wegs \(r = (0, j_1, \dots, j_m, 0)\) mit \(j_0 = j_{m+1} = 0\) (Depot): Weglänge minus die Dualpreise aller Besuche. Ein Weg mit negativen reduzierten Kosten ist eine neue Spalte für den Master.
\[\bar c(r) = \sum_{t=0}^{m} d_{j_t j_{t+1}} - \sum_{t=1}^{m} \pi_{j_t}\]
Label und Gedächtnis. Ein Label ist ein Teilweg vom Depot bis zu einem Kunden, beschrieben durch \((T, C, R, M)\): Zeit, reduzierte Kosten, verbrauchte Last und Gedächtnis \(M\), die Menge der Kunden, die als Nächstes verboten sind. Nach dem Besuch von \(j\) bleibt vom Gedächtnis nur, was in der Nachbarschaft \(N_j\) liegt, dazu kommt \(j\) selbst:
\[N_j = \{j\} \cup \{\text{die } k-1 \text{ nächsten Kunden von } j\}, \qquad M' = (M \cap N_j) \cup \{j\}\]
Ein Kunde \(j\) darf als Nächster nur gewählt werden, wenn \(j \notin M\) gilt. Wegen \(i \in M\) nach jedem Besuch von \(i\) ist „\(i\) direkt nach \(i\)“ immer verboten.
Fortsetzung eines Labels \((T, C, R, M)\) am Knoten \(i\) zum Kunden \(j \notin M\); der Faktor \([i \ne 0]\) ist 1 außer im Depot, wo keine Bedienzeit anfällt:
\[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\]
Die Fortsetzung ist zulässig, 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\) ist.
Dominanz (am selben Kunden): Label \(L_1\) macht \(L_2\) überflüssig, wenn es in allen vier Größen mindestens so gut ist, das Gedächtnis eingeschlossen; bei Gleichstand bleibt das ältere Label.
\[L_1 \preceq L_2 \iff C_1 \le C_2, \quad T_1 \le T_2, \quad R_1 \le R_2, \quad M_1 \subseteq M_2\]
Dieselbe Regel als Eigenschaft des ganzen Wegs (ohne Labels): Ein Weg ist erlaubt, wenn für jede Wiederholung eines Kunden \(j\) (frühere Stelle \(a\), spätere Stelle \(b\)) eine Stelle \(t\) mit \(a < t < b\) und \(j \notin N_{j_t}\) existiert. Mit dieser Fassung zählt die Demo alle erlaubten Wege auf und prüft damit das Label-Verfahren.
Schranke und Lücke. Die Wegmengen der Größen \(k\) liegen ineinander (die erlaubten Wege bei \(k+1\) sind auch bei \(k\) erlaubt), deshalb gilt
\[z(1) \le z(2) \le \dots \le z(n) = z_{\text{elementar}}\]
Die Lücke gegen eine Bezugsschranke \(z_{\text{ref}}\) ist \((z_{\text{ref}} - z(k)) / z_{\text{ref}}\), in Prozent der Bezugsschranke. Eine negative Lücke heißt, dass die Schranke über der Bezugsschranke liegt.
k-Zyklen (Kontrast): Ein Weg ist erlaubt, wenn für jede Wiederholung eines Kunden \(j_a = j_b \ne 0\) mit \(a < b\) gilt \(b - a > K\), das heißt, alle Kreise mit höchstens \(K\) Kanten sind verboten (das Depot zählt nicht). Als Gedächtnis halten die Labels die Mengen \(S_1, \dots, S_K\) der letzten \(1, \dots, K\) besuchten Kunden; nächster Kunde \(j\) ist verboten, wenn \(j \in S_K\). Nach dem Besuch von \(j\) ist \(S_1' = \{j\}\) und \(S_i' = \{j\} \cup S_{i-1}\) für \(i = 2, \dots, K\). Die Dominanz verlangt \(S_i^{(1)} \subseteq S_i^{(2)}\) für \(i = 2, \dots, K\) (die Mengen \(S_1\) sind am selben Kunden gleich). Das ist die Regel der Demo, nicht die von Irnich und Villeneuve (2006).
Herleitungen Schritt für Schritt
Die Herleitungen sind Rechnungen dieser Seite, keine Messungen der Demo.
Warum die Dominanz nichts verliert.
- Schritt 1: Aus \(M_1 \subseteq M_2\) folgt \((M_1 \cap N_j) \cup \{j\} \subseteq (M_2 \cap N_j) \cup \{j\}\) für jede Fortsetzung \(j\): Schneiden mit \(N_j\) und Hinzufügen von \(j\) erhalten die Teilmengenbeziehung.
- Schritt 2: Jede Fortsetzung von \(L_2\) ist daher auch für \(L_1\) erlaubt, denn \(j \notin M_2\) ergibt \(j \notin M_1\).
- Schritt 3: \(L_1\) kommt früher oder gleich spät an, und weil Warten erlaubt ist, hält es Zeitfenster und Horizont ein, wo \(L_2\) sie einhält. Es hat höchstens so viel Last verbraucht und kostet nicht mehr. Die Kosten einer Fortsetzung hängen nicht vom Zeitpunkt ab (Warten ist kostenlos). Jede Fortsetzung von \(L_2\) gibt es also auch für \(L_1\), nicht teurer, und das Streichen von \(L_2\) ändert das Optimum nicht.
- Bedingung: Das gilt für die Gedächtnisregel und die Dominanzregel, wie sie oben stehen.
Warum die Dominanzregel der k-Zyklen gültig ist.
- Schritt 1: Gilt \(S_i^{(1)} \subseteq S_i^{(2)}\) für alle \(i\) und ist \(j \notin S_K^{(2)}\), dann ist \(j \notin S_K^{(1)}\): Jede Fortsetzung von \(L_2\) ist auch für \(L_1\) erlaubt.
- Schritt 2: Nach der Fortsetzung gilt \(\{j\} \cup S_{i-1}^{(1)} \subseteq \{j\} \cup S_{i-1}^{(2)}\) für \(i = 2, \dots, K\), und \(S_1'\) ist in beiden Fällen \(\{j\}\). Die Teilmengenbeziehung bleibt also entlang jeder Fortsetzung erhalten.
- Schritt 3: Kosten, Zeit und Last wie bei der Gedächtnisregel oben. Damit verliert das Streichen auch hier das Optimum nicht. Die Regel ist damit gültig, aber nicht als die stärkste mögliche gezeigt; zusätzlich ist sie gegen die Aufzählung getestet.
Warum die Schranke mit \(k\) steigt und nie über der elementaren liegt.
- Schritt 1: Die Nachbarschaft \(N_j^{(k)}\) ist der Anfang der festen Reihenfolge aller Kunden nach (Abstand zu \(j\), Nummer), mit \(j\) selbst vorn (Abstand 0): die ersten \(k\) Einträge. Also gilt \(N_j^{(k)} \subseteq N_j^{(k+1)}\).
- Schritt 2: Das Gedächtnis beginnt leer. Gilt \(M^{(k)} \subseteq M^{(k+1)}\) vor einem Besuch von \(j\), dann gilt es danach, weil \((M \cap N_j) \cup \{j\}\) in \(M\) und \(N_j\) wächst. Entlang jedes Wegs ist das Gedächtnis bei \(k+1\) also eine Obermenge.
- Schritt 3: Jeder bei \(k+1\) erlaubte Weg ist deshalb auch bei \(k\) erlaubt. Bei \(k\) stehen dem Master mindestens dieselben Spalten zur Verfügung, sein Minimum ist höchstens so groß, also \(z(k) \le z(k+1)\).
- Schritt 4: Bei \(k = n\) enthält \(N_j\) alle Kunden, \(M' = M \cup \{j\}\): Jeder Besuch bleibt gemerkt, das ist die elementare Regel. Ein elementarer Weg verletzt keine Gedächtnisregel, ist also bei jedem \(k\) erlaubt; daraus folgt \(z(k) \le z_{\text{elementar}}\).
- Bedingung: Das Preisproblem muss exakt sein, damit \(z(k)\) das LP-Optimum über alle erlaubten Wege ist. Die Demo hat das am Handbeispiel gegen eine Aufzählung aller zulässigen Wege geprüft (siehe Befunde).
Durchgerechnet: das Gedächtnis entlang zweier Wege
Rechnung dieser Seite mit den Nachbarschaften des Handbeispiels bei \(k = 2\): \(N_1 = N_2 = \{1,2\}\), \(N_3 = N_4 = \{3,4\}\), \(N_5 = \{3,5\}\), \(N_6 = N_7 = \{6,7\}\). Die Nachbarschaft ist nicht symmetrisch: Kunde 5 hat Kunde 3 als Nachbarn, Kunde 3 aber den Kunden 4.
- Weg 7-6-7: Start \(M = \emptyset\). Nach 7: \(M = \{7\}\). Nach 6: \((\{7\} \cap \{6,7\}) \cup \{6\} = \{6,7\}\). Der dritte Besuch gilt Kunde 7, und \(7 \in M\): verboten.
- Weg 5-3-5-1: Nach 5: \(M = \{5\}\). Nach 3: \((\{5\} \cap \{3,4\}) \cup \{3\} = \{3\}\), die 5 ist vergessen. Der dritte Besuch gilt Kunde 5, \(5 \notin M\): erlaubt. Nach 5: \((\{3\} \cap \{3,5\}) \cup \{5\} = \{3,5\}\). Kunde 1 liegt nicht in \(M\): erlaubt.
Die Tabelle zeigt für drei Wege, ob die jeweilige Gedächtnisregel sie erlaubt; ob Last, Zeitfenster und Horizont eingehalten werden, sagt sie nicht.
| Weg | ng \(k = 1\) | ng \(k = 2\) | ng \(k = 3\) | k-Zyklen \(K = 2\) | k-Zyklen \(K = 3\) |
|---|---|---|---|---|---|
| 7-6-7 | erlaubt | verboten | verboten | verboten | verboten |
| 5-3-5-1 | erlaubt | erlaubt | verboten | verboten | verboten |
| 7-6-1-7 | erlaubt | erlaubt | erlaubt | erlaubt | verboten |
Beim Weg 5-3-5-1 hat der Kreis 5-3-5 zwei Kanten: \(K = 2\) verbietet ihn, ng \(k = 2\) erlaubt ihn, weil 5 nach 3 vergessen ist. Bei \(k = 3\) gehören zu \(N_3\) außer 3 selbst die Kunden 4 und 5 (Abstand je 2 zu Kunde 3, bei Gleichstand zählt die kleinere Nummer zuerst), daher ist 5-3-5-1 dort verboten. Beim Weg 7-6-1-7 hat der Kreis drei Kanten: \(K = 3\) verbietet ihn, ng erlaubt ihn bei \(k = 1\), 2 und 3. Bei ng entscheidet die Nachbarschaft, bei k-Zyklen allein die Zahl der Kanten des Kreises.
Befunde
Handbeispiel (7 Kunden). Runde 1 ist ein einziger Aufruf des Preisproblems mit den Dualpreisen der ersten Runde; die Spalten zeigen den besten Weg dieser Runde, die Zahl der zulässigen Wege und, für die Spaltenerzeugung bis zum Ende (je Runde die beste neue Spalte, Master mit exakten Brüchen), Schranke, Runden und erzeugte Labels insgesamt. Die Lücke bezieht sich auf die elementare Schranke 30. Die Labels hängen von diesen Voraussetzungen ab: Mit mehr neuen Spalten je Runde ergeben sich andere Zahlen, die Schranken bleiben gleich.
| ng \(k\) | Bester Weg, Runde 1 | Reduzierte Kosten | Zulässige Wege | Schranke | Runden | Labels gesamt | Lücke (%) |
|---|---|---|---|---|---|---|---|
| 1 | 7-6-7-6 | −18 | 89 | 83/3 (≈ 27,67) | 8 | 416 | 7,78 |
| 2 | 5-3-5-1 | −14 | 82 | 86/3 (≈ 28,67) | 8 | 382 | 4,44 |
| 3 | 2-7-6 | −10 | 79 | 30 | 8 | 370 | 0,00 |
| 4 | 2-7-6 | −10 | 79 | 30 | 8 | 370 | 0,00 |
| 5 | 2-7-6 | −10 | 79 | 30 | 7 | 326 | 0,00 |
| 6 | 2-7-6 | −10 | 79 | 30 | 7 | 326 | 0,00 |
| 7 (elementar) | 2-7-6 | −10 | 79 | 30 | 7 | 326 | 0,00 |
Hier sinken die Labels mit \(k\), aber nur bei einer neuen Spalte je Runde (mit bis zu 15 Spalten je Runde: 209, 199, 147, 146, 148, 149, 151, nicht fallend); bei den Zufallsinstanzen mit 30 Kunden steigen sie im Mittel. Weitere Befunde, jeweils für die genannte Messreihe; die Lücke steht im Mittel (Maximum) in Prozent der Bezugsschranke:
| Frage | Befund |
|---|---|
| Stimmt das Label-Verfahren mit der Aufzählung überein? (Handbeispiel) | Für jedes der 9 Gedächtnisse (ng \(k = 1\) bis 7, k-Zyklen \(K = 2\) und 3) ergibt der Master über alle zulässigen Wege dieselbe Schranke und denselben besten Wert wie die Spaltenerzeugung mit Labels. |
| Einzelne Zufallsinstanz: 30 Kunden, Breite 100, Zufalls-Seed 1 (Bezug ist das größte gerechnete \(k\), hier 12) | Die Schranke bei \(k = 1\) liegt 5,45 % unter der bei \(k = 12\) und ist ab \(k = 4\) gleich der bei \(k = 12\); erzeugte Labels 44 946 bei \(k = 1\), 131 082 bei \(k = 12\). |
| Wie viel Gedächtnis genügt bei 30 Kunden? (24 Instanzen, Breite 100, Zufalls-Seeds 0 bis 11, je 12 zufällig und gruppiert, Bezug ng \(k = 8\)) | Lücke ng \(k = 1, 2, 3, 4, 5\): 3,563 (7,157), 0,920 (2,365), 0,460 (1,116), 0,199 (0,938), 0,115 (0,898). Der größte Sprung liegt zwischen \(k = 1\) und 2. Labels im Verhältnis zu ng \(k = 8\) (Mittel der je Instanz gebildeten Verhältnisse): 0,50, 0,59, 0,69, 0,73, 0,80. |
| Gegen die elementare Schranke (30 Kunden, zufällig, 6 Instanzen je Breite, Zufalls-Seeds 0 bis 5; nur Instanzen mit fertigem elementarem Lauf) | Breite 40 (6 Instanzen): \(k = 1\) 0,24 (0,72), ab \(k = 3\) 0,00. Breite 100 (3 von 6 Instanzen, Zufalls-Seeds 0, 1 und 5): \(k = 1\) 4,82 (6,80), \(k = 3\) 0,52 (0,96), ab \(k = 5\) 0,00. Labels (Median) bei Breite 100: 57 330 bei \(k = 1\) und 92 038 bei \(k = 5\) (je über alle 6 Läufe), 140 285 elementar (über die 3 fertigen Läufe). |
| Kleinere Kundenzahlen: \(k = 5\) gegen elementar (10 bis 25 Kunden, 6 Instanzen je Zelle, alle elementaren Läufe fertig) | Gleich der elementaren Schranke bei 10 und 15 Kunden und bei Breite 40 für alle Kundenzahlen. Bei Breite 100 und 20 bzw. 25 Kunden in je 2 von 6 Instanzen nicht: Lücke 0,07 (0,25) bzw. 0,18 (0,64). |
| 50 und 100 Kunden, Bezug \(k = 16\) (8 Zellen: 50 Kunden mit Breite 40 und 100, 100 Kunden mit Breite 20 und 40, je zufällig und gruppiert; 12 Instanzen je Zelle) | Lücke bei \(k = 5\) im Mittel je Zelle bis 0,24, im Einzelfall bis 0,67 (50 Kunden, Breite 100, gruppiert). Bei \(k = 8\) im Mittel bis 0,07, im Einzelfall bis 0,30. Die elementare Rechnung brach in 94 von 96 Läufen ab (8 Zellen mit je 12 Instanzen); \(k = 16\) ist selbst nur eine ng-Relaxation. |
| Was kostet ein größeres Gedächtnis an Labels? (dieselben 8 Zellen) | Die Labels von \(k = 16\) sind je Zelle im Median das 1,48- bis 2,37-Fache der Labels von \(k = 5\). Der Anteil dominierter Labels liegt über alle Zellen und alle \(k\) bis 16 zwischen 77,7 und 96,0 % und sinkt mit \(k\). |
| Enge Fenster (100 Kunden, Breite 20; 30 Kunden, Breite 20, Zufalls-Seeds 1 bis 8) | Die Lücke ist schon bei \(k = 1\) gleich 0: in 24 von 24 Instanzen bei 100 Kunden (Bezug \(k = 16\)), in 8 von 8 bei 30 Kunden (Bezug das größte gerechnete \(k\), dort 5; nicht die elementare Schranke). Bei 100 Kunden und Breite 20 brauchte \(k = 16\) trotzdem das 1,87- (gruppiert) bzw. 1,72-Fache (zufällig) der Labels von \(k = 5\). Deutung, nicht gemessen: Die Fenster sind so eng, dass Kreise kaum möglich sind. |
Kontrast: k-Zyklen statt Nachbarschaft
Die naheliegende Alternative zum Gedächtnis ist, alle kurzen Kreise zu verbieten. Gemessen ist hier die Dominanzregel dieser Demo (Suffixmengen der letzten \(K\) Kunden), nicht die von Irnich und Villeneuve (2006); mit deren Regel könnten die k-Zyklen weniger Labels brauchen und der Kontrast kleiner ausfallen. Grundlage sind dieselben 24 Instanzen mit 30 Kunden, Bezug ng \(k = 8\); die Paarvergleiche zählen nur Instanzen, in denen beide Läufe fertig wurden:
| Vergleich | Instanzen | Schranke der k-Zyklen höher / gleich / tiefer | Labels k-Zyklen / ng (Mittel) |
|---|---|---|---|
| \(K = 2\) gegen ng \(k = 2\) | 24 | 23 / 0 / 1 | 2,91 |
| \(K = 3\) gegen ng \(k = 3\) | 22 | 20 / 2 / 0 | 5,02 |
| \(K = 4\) gegen ng \(k = 4\) | 15 | 7 / 8 / 0 | 4,60 |
| \(K = 2\) gegen ng \(k = 5\) | 24 | 2 / 2 / 20 | 2,12 |
Bei \(K = 2\) und 3 ist die Schranke der k-Zyklen bei gleichem Parameter fast immer höher, bei \(K = 4\) in 7 von 15 Instanzen (sonst gleich). Dafür braucht sie ein Mehrfaches der Labels. Bei ähnlicher Lücke zu ng \(k = 8\) kostet ng weniger: ng \(k = 3\) liegt im Mittel bei 0,460 % mit dem 0,69-Fachen der Labels, \(K = 2\) bei 0,469 % mit dem 1,69-Fachen. ng \(k = 5\) liegt bei 0,115 % mit dem 0,80-Fachen der Labels, \(K = 3\) mit etwas kleinerer Lücke bei 0,073 % und dem 3,52-Fachen; dieses Mittel läuft über 22 Instanzen, die der ng-Zeilen über 24. \(K = 4\) brach bei den gruppierten Instanzen in 9 von 12 Fällen an der Zeitgrenze der Messung ab (zufällig: 0 von 12). Die Schranke von \(K = 4\) liegt in 2 der 15 fertigen Instanzen über der von ng \(k = 8\) (größte Überschreitung 0,055 %), die von \(K = 3\) in 1 der 22, derselben Instanz.
DSSR: warum die Demo dazu nur einen Absatz zeigt. Die Decremental State Space Relaxation (DSSR) nimmt die Elementarität erst dort wieder auf, wo ein Kreis auftritt. Die Demo hat eine eigene Variante nach dem Abstract von Righini und Salani (2008) an 72 festen Dualpreis-Sätzen gemessen (Dualpreise aus Runde 2, Runde 4 und vom Ende der Spaltenerzeugung mit ng \(k = 5\); 30 Kunden, Breite 100). Sie lieferte in 66 von 66 Sätzen denselben Wert wie die elementare Rechnung (in 6 Sätzen war diese abgebrochen) und brauchte im Mittel das 6,3-Fache der Labels von ng \(k = 5\). ng \(k = 5\) verfehlte den Wert der DSSR-Rechnung (die reduzierten Kosten) in 24 von 72 Sätzen (Runde 2: 13, Runde 4: 11, am Ende 0 von 24). Am Ende der Spaltenerzeugung kostete DSSR das 11,6-Fache. Gemessen wurde pro Aufruf des Preisproblems, nicht in der ganzen Schleife; die Reihe stammt aus der Messdatei und ist nicht neu gerechnet. Andere Runden und andere DSSR-Fassungen sind nicht gemessen; ein eigenes Verfahren zeigt die Demo deshalb nicht.
Was die Messung zeigt und wo die Grenzen liegen
Was sie belegt:
- Am Handbeispiel steigt die Schranke mit \(k\) und ist ab \(k = 3\) gleich der elementaren; das Label-Verfahren stimmt für alle 9 Gedächtnisse mit der Aufzählung aller Wege überein.
- Bei 30 Kunden und Breite 100 liegt bei \(k = 5\) die Schranke im Mittel nur 0,115 % unter der von \(k = 8\) (in Prozent der Schranke von \(k = 8\); Maximum 0,898 %), der größte Sprung ist der von \(k = 1\) auf 2.
- Bei 50 und 100 Kunden liegt \(k = 5\) in allen acht Zellen im Mittel höchstens 0,24 % und im Einzelfall höchstens 0,67 % unter \(k = 16\).
- Die Zeilen der Messreihen wurden mit dem Kern der Demo nachgerechnet: 780 von 996 in der Messung fertigen Läufen, Schranke, Labels und Runden gleich. Die übrigen 216 Läufe (100 Kunden, Zufalls-Seeds 3 bis 11) stammen nur aus der Messdatei. Das gilt für Python 3.14.6, SciPy 1.18.1 und Windows; die Schranke ist der Zielwert eines LP und hängt nicht vom Weg des Lösers ab, Runden und Labels können auf anderen Versionen leicht abweichen.
Was sie nicht belegt:
- „\(k = 5\) reicht“ allgemein: Es gilt nur im Sinn der Zahlen oben und hängt an der Fensterbreite. Bei 20 und 25 Kunden und Breite 100 liegt \(k = 5\) in 2 von 6 Instanzen unter der elementaren Schranke.
- Der Bezug: Als Bezug gibt es die elementare Schranke nur bis 30 Kunden, und bei Breite 100 wurde sie nur in 3 von 6 Instanzen fertig. Ab 50 Kunden ist \(k = 16\) der Bezug; wie weit \(k = 16\) selbst unter der elementaren Schranke liegt, ist nicht gemessen.
- Enge Fenster: Die Zellen mit Breite 20 sagen nichts über die Wirkung von \(k\) auf die Schranke, weil die Lücke dort schon bei \(k = 1\) null ist. Die Erklärung mit den engen Fenstern ist eine Deutung. Ursachen auf dieser Seite sind überhaupt Deutungen, gemessen sind die Zählungen.
- Rechenzeit: Die Demo macht keine Aussage über Rechenzeit; gezählt werden Labels, nicht Sekunden. Die Zahl der Dominanzprüfungen je Label ist nicht gezählt; dass sie mit der Größe des Gedächtnisses wächst, ist eine Überlegung dieser Seite, nicht gemessen.
- Stichprobe: Eigene Instanzen im Stil der Solomon-Instanzen, nicht die Originale; 6 bis 12 Instanzen je Zelle (24 beim Kontrast), Mittel und Maxima ohne Konfidenzaussage.
- Gemessene Verfahren: Nachbarschaft nach Entfernung, Überdeckungs-Master, die eigene Dominanzregel für k-Zyklen und die eigene DSSR-Variante. Andere Nachbarschaften, Partitionierung, nichtmetrische Kosten, Instanzen mit mehr als 100 Kunden und Dualpreise aus einem Verzweigungsbaum sind nicht gemessen.
- Abgebrochene Läufe: Läufe, die an der Zeitgrenze der Messung abbrachen, sind nicht eingerechnet; dass sie abbrachen, hing von der Last des Rechners ab.
Erweiterungen und Verweise
Verwandte Demos dieser Website:
- Davor: Die dominanz-labels-demo erklärt die Labels und ihre Dominanz, die kreise-im-pricing-demo zeigt die Kreise im Preisproblem und die elementar-pricing-demo die Wand der elementaren Rechnung.
- Anwendung: Die crew-pairing-demo zeigt das Preisproblem in einem Fall, der Besatzungsplanung im Zugverkehr.
- Nicht verwechseln: Die hub-labeling-demo meint etwas anderes, nämlich vorberechnete Listen für schnelle Abfragen kürzester Wege; hier sind Labels Teilwege.
Quellen
- Baldacci, Mingozzi, Roberti (2011): New route relaxation and pricing strategies for the vehicle routing problem. Operations Research 59(5):1269-1283 (ng-Routen).
- Irnich, Villeneuve (2006): INFORMS Journal on Computing 18(3):391-406 (Verbot von Kreisen mit höchstens \(k\) Kanten, eigene Dominanzregel).
- Righini, Salani (2008): New dynamic programming algorithms for the resource constrained elementary shortest path problem. Networks 51(3):155-170 (DSSR).
- Christofides, Mingozzi, Toth (1981): State-space relaxation procedures for the computation of bounds to routing problems. Networks 11(2):145-164 (Vorläufer).
- Pessoa, Sadykov, Uchoa, Vanderbeck (2020): A generic exact solver for vehicle routing and related problems. Mathematical Programming 183:483-523 (nennt Baldacci u. a. als Ursprung der ng-Pfade).
- Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/ng-routen-demo.
Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Die Angaben stammen aus der Dokumentation der Demo; dort sind Autoren, Zeitschrift und Jahr per Abstract und Suchtreffer geprüft, die Volltexte bis auf den Hinweis auf den Ursprung der ng-Routen bei Pessoa u. a. nicht gelesen, und die Demo übernimmt keine Zahl daraus. Die Befundtabellen geben die Messreihen der Demo wieder; Herleitungen, die Gedächtnisspur an den beiden Wegen und die Nachbarschaft \(N_3\) bei \(k = 3\) sind Rechnungen dieser Seite.