Pricing aus Dualpreisen verständlich erklärt

Ein Disponent rechnet jedem Kunden einen Wert zu und sucht eine Tour, die weniger kostet, als ihre Kunden an Wert einbringen. Rechnet er das als Wegsuche, kann das gewohnte Verfahren für kürzeste Wege den besten Weg verfehlen. Die Seite zeigt, warum, und was stattdessen funktioniert.

Zuletzt aktualisiert: 11. November 2026

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

Ein Disponent und die Werte seiner Kunden

Ein Disponent plant die Touren eines Fuhrparks. Eine Tour führt vom Depot (dem Lager) über einige Kunden und zurück und muss Grenzen einhalten: Jeder Kunde hat ein Zeitfenster, jeder Lkw darf nur bis zu einer Höchstlast laden. Weil es zu viele denkbare Touren gibt, plant er nur mit denen, die er kennt, am Anfang mit Einzelfahrten (Depot, ein Kunde, Depot).

Zum Plan gehört für jeden Kunden ein Wert: ungefähr, wie viel der Plan sparen würde, fiele dieser Kunde weg (Fachleute sagen Dualpreis). Genau gilt das am Anfang: Dann besteht der Plan nur aus Einzelfahrten, und der Wert eines Kunden ist, was seine Einzelfahrt kostet. Eine neue Tour lohnt sich, wenn sie weniger kostet, als ihre Kunden an Wert einbringen.

Plan und Suche im Wechsel

Das Verfahren wechselt zwischen zwei Teilen. Der Plan (Fachwort: Master) wählt aus den bekannten Touren die billigste Zusammenstellung, die jeden Kunden bedient. Die Suche (Fachwort: Pricing) fragt dann: Gibt es eine neue Tour, die weniger kostet, als ihre Kunden an Wert einbringen? Wenn ja, kommen die besten davon in den Plan, und eine neue Runde beginnt.

Das geht, bis keine Tour mehr lohnt. Dann steht eine Untergrenze fest (Fachwort: Schranke): So wenig muss jeder Plan aus ganzen Touren mindestens kosten, sofern die Suche keine lohnende Tour übersehen hat.

Wie die Suche aus Werten Längen macht

Die Suche ist eine Wegsuche: Sie sucht eine Tour, also einen Weg vom Depot über Kunden zurück ins Depot. Jede Fahrt von einem Halt zum nächsten kostet ihre Strecke, und der Wert des Zielkunden wird gutgeschrieben. Als Länge einer Fahrt zählt hier die Strecke minus der Wert des Ziels. Eine Tour lohnt sich, wenn die Längen ihrer Fahrten zusammen unter null liegen.

Längen unter null gibt es gleich zu Beginn. Die Seite rechnet alles an einem Handbeispiel durch: ein Depot und 7 Kunden mit festen Lasten und Zeitfenstern (Zahlen im zweiten Teil). In der ersten Runde ist der Wert eines Kunden die Hin- und Rückfahrt zu ihm, die Fahrt vom Depot zu ihm kostet aber nur die einfache Strecke: Strecke minus Wert ergibt eine Länge unter null, bei allen 7 Kunden. Das kann auch bei Rundfahrten zwischen zwei Kunden so sein. Dürfte ein Kunde beliebig oft vorkommen und gäbe es keine Grenzen, würde jede weitere solche Runde die Tour kürzer machen, und es gäbe keine beste. Das verhindert schon die Regel „jeder Kunde höchstens einmal“, ebenso die Grenzen (Höchstlast, Zeitfenster).

Warum der Notizzettel versagt

Für kürzeste Wege nimmt man gewöhnlich das Verfahren von Dijkstra (siehe Dijkstra-Algorithmus). Es führt einen Notizzettel: Neben jedem Kunden steht die beste bisher bekannte Länge vom Depot dorthin, und es hakt den Kunden mit der kleinsten Länge endgültig ab. Das darf es, weil bei Längen von null oder mehr ein Umweg nie etwas einspart.

Bei Längen unter null kann das falsch sein. Beispiel mit ausgedachten Längen für zwei Kunden A und B:

Fahrt	Länge
Depot → A	−5
Depot → B	−3
A → B	4
B → A	−4

Dijkstra hakt A zuerst ab (−5 ist die kleinste Länge). Über B käme man aber mit −3 + (−4) = −7 zu A. Der Umweg spart etwas, doch A ist schon abgehakt. Im Handbeispiel passiert das wirklich: Dijkstra liefert eine Tour der Länge −24, doch alle Touren durchzuzählen (jeder Kunde höchstens einmal) findet −28. Beide Rechnungen lassen Höchstlast und Zeitfenster außen vor, denn Dijkstra kennt sie nicht; der Vergleich zeigt, dass es schon bei den Längen allein danebenliegt.

Was stattdessen funktioniert

Statt eines Zettels je Kunde führt man eine Karte je angefangener Tour: Wo steht der Lkw, welche Zeit ist vergangen, was ist geladen, was hat sie gekostet, welche Kunden hat sie schon besucht? Diese sind für sie gesperrt. Eine Karte wird weggeworfen, wenn eine andere am selben Halt in allem mindestens so gut ist: nicht später, nicht schwerer beladen, nicht teurer, keinen Kunden gesperrt, den die andere noch besuchen darf (Fachwort: Dominanz, siehe Dominanz bei Teilwegen).

Längen unter null stören hier nicht: Zeit und Ladung wachsen mit jeder Fahrt und sind begrenzt, also gibt es keine endlosen Runden; im Handbeispiel kommt zudem kein Kunde mehr als einmal vor. Zuerst wird die Karte mit der kleinsten Zeit weiterverfolgt, nicht die mit der kleinsten Länge (Fachwort für das Verfahren: Labeling). Im Handbeispiel findet es die beste fahrbare Tour, ihre Länge ist −10. Das liegt über −28, weil Höchstlast und Zeitfenster manche Touren ausschließen.

Hilft es, die Werte zu glätten?

Die Werte springen von Runde zu Runde. Man könnte der Suche darum statt der neuesten Werte eine Mischung mit den Werten, mit denen die Suche in der letzten Runde gerechnet hat geben und hoffen, dass weniger Runden nötig sind (Fachwort: Glättung). Gemessen wurden drei Mischungen: zu gleichen Teilen sowie zwei, bei denen die alten Werte überwiegen. Zu gleichen Teilen blieb die Rundenzahl im Mittel etwa gleich; bei den anderen beiden waren es bei 20 Kunden in 11 von 12 Fällen mehr Runden als ohne Mischung.

Häufige Missverständnisse

• „Dijkstra ist ein schlechtes Verfahren.“ Nein. Bei Längen von null oder mehr arbeitet es richtig. Es braucht nur diese Voraussetzung.

Woran Sie das im Alltag erkennen

• Sie bringen Pfandflaschen zurück und bekommen Geld. Das wirkt in der Rechnung wie eine Länge unter null, genauso wie die Fahrt zu einem Kunden, dessen Wert die Strecke übersteigt.

Wie ernst ist das Rechenbild zu nehmen?

Alle Fälle sind klein oder selbst erzeugt, die Messungen beruhen auf höchstens 12 Fällen je Zelle. Über einen echten Fuhrpark sagen sie nichts.

Zu dieser Seite gehört ein Programm zum Ausprobieren, die Demo. Der Knopf „Demo ausprobieren“ öffnet sie, „Weiter zum Fachteil“ führt zum Teil für Fachleute. Zum Verstehen brauchen Sie die Demo nicht.

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. Zur Seite gehört ein Programm zum Ausprobieren, die Demo; die Zahlen stammen aus deren Rechnungen und Messreihen und gelten nur für die hier genannten Fälle.

Ablauf der Spaltenerzeugung für eine Tourenplanung mit Last und Zeitfenstern. Eine Runde löst den Master über die bekannten Touren (Spalten) und liest daraus die Dualpreise der Kunden. Das Pricing sucht damit Touren mit negativen reduzierten Kosten (Definition unten), und die besten werden als neue Spalten angehängt. Ende ist, wenn das Pricing keine solche Tour mehr findet; der Master-Wert der letzten Runde heißt Schranke (Begründung unten). Bei den Kundeninstanzen nimmt eine Runde aus den besten 15 Routen des Pricings diejenigen, die auch unter den echten Dualpreisen negative reduzierte Kosten haben; in der Handrechnung ist es je Runde die beste neue Spalte.

• Handbeispiel: Depot (0, 0) und 7 Kunden, ganze Zahlen. Entfernung, Fahrzeit und Kosten sind der Manhattan-Abstand, die Bedienzeit beträgt 2, die Kapazität 6, die Rückkehr zum Depot ist bis 38 zulässig. Das Fenster eines Kunden gilt für den Beginn der Bedienung: früher ankommen heißt warten, später ankommen ist unzulässig.
• Kundeninstanzen: selbst erzeugt im Stil der Solomon-Benchmarks (nicht die Originalinstanzen). Das Depot liegt in der Mitte eines Quadrats von 100 × 100, die Entfernung ist der euklidische Abstand und die Fahrzeit ist gleich der Entfernung, die Bedienzeit beträgt 10, der Horizont 300, die Kapazität 70, die Last je Kunde 5 bis 25, die Fensterbreite 40 bis 100 (Messreihen bis 200). Die Messreihen verwenden zusätzlich gruppierte Kunden und einen langen Horizont (500, Kapazität 120).
• Master: Überdeckung (jeder Kunde mindestens einmal) oder Partitionierung (genau einmal), gelöst als LP mit HiGHS über scipy. Start sind die Einzelfahrten Depot, Kunde, Depot. Die Dualpreise sind die Schattenpreise der Kunden-Zeilen.
• Pricing: Labeling mit Last, Zeitfenstern, Horizont und Dominanz. In der Live-Rechnung ist es elementar (jeder Kunde höchstens einmal); die Messreihen mit 30 Kunden rechnen mit einem Gedächtnis aus den 5 nächsten Kunden (k = 5; beim Vergleich der Master auch k = 1 und 8), das Kreise nicht ganz ausschließt.
• Messgrößen: Runden, Pricing-Aufrufe und erzeugte Labels, nicht Sekunden. Live wird nur bis 20 Kunden gerechnet. Die Messreihen sind fest: mit 30 Kunden 5 bzw. 6 Instanzen je Zelle, bei der Glättung mit 20 Kunden 12 (Zufalls-Seeds ab 0). Angegeben sind Mittel, Mediane und Zählungen an diesen Instanzen.

Die Daten des Handbeispiels:

Kunde	Lage	Last	Fenster für den Beginn der Bedienung
1	(−1, 2)	1	[18, 28]
2	(0, 3)	3	[3, 16]
3	(−3, −2)	3	[5, 15]
4	(−1, −2)	3	[20, 28]
5	(−2, −1)	1	[3, 12]
6	(2, 1)	1	[11, 21]
7	(3, 2)	2	[8, 20]

Die Formeln

Bezeichnungen: 0 ist das Depot, \(1,\dots,n\) sind die Kunden. \(d_{ij}\) ist die Entfernung (zugleich Fahrzeit und Kosten) von \(i\) nach \(j\), \(q_j\) die Last von Kunde \(j\), \(Q\) die Kapazität, \(\sigma\) die Bedienzeit, \([a_j, b_j]\) das Zeitfenster für den Beginn der Bedienung bei Kunde \(j\) und \(H\) der Horizont für die Rückkehr. \(R\) ist die Menge der bekannten Touren (Spalten), \(c_r\) sind die Kosten der Tour \(r\), \(A_{jr}\) zählt, wie oft \(r\) den Kunden \(j\) besucht, und \(x_r\) ist die Menge, mit der \(r\) im Master gewählt wird.

Master (Überdeckung) und sein duales Problem:

\[\min \sum_{r \in R} c_r x_r \quad \text{unter} \quad \sum_{r \in R} A_{jr}\, x_r \ge 1 \;\; (j = 1,\dots,n), \quad x \ge 0\]

\[\max \sum_{j=1}^{n} \pi_j \quad \text{unter} \quad \sum_{j=1}^{n} A_{jr}\, \pi_j \le c_r \;\; (r \in R), \quad \pi \ge 0\]

\(\pi_j\) ist der Dualpreis von Kunde \(j\): der Schattenpreis der Zeile, die verlangt, dass \(j\) bedient wird; das Depot hat keinen Dualpreis, \(\pi_0 = 0\). Bei der Partitionierung steht \(=1\) statt \(\ge 1\), und \(\pi\) ist nicht vorzeichenbeschränkt.

Reduzierte Kosten und Bogenlängen. Eine Tour \(0 \to j_1 \to \dots \to j_m \to 0\) hat die reduzierten Kosten

\[\bar c = \sum_{i=0}^{m} d_{j_i j_{i+1}} - \sum_{i=1}^{m} \pi_{j_i} = \sum_{i=0}^{m-1} \ell_{j_i j_{i+1}} + d_{j_m 0}, \qquad \ell_{ij} = d_{ij} - \pi_j \quad (j_0 = j_{m+1} = 0)\]

Sie ist eine neue Spalte, wenn \(\bar c < 0\). Wegen \(\pi_0 = 0\) ist die Länge der Rückfahrt ins Depot nur die Entfernung. Ein Hin-und-zurück-Kreis \(i \to j \to i\) hat die Länge

\[\ell_{ij} + \ell_{ji} = 2\,d_{ij} - \pi_i - \pi_j\]

Das Netz von Dijkstra besteht aus dem Depot, den Kunden und einem Endknoten, zu dem jeder Kunde \(i\) einen Bogen der Länge \(d_{i0}\) hat; die Länge einer Tour ist der Abstand des Endknotens, die Rückfahrt ist also eingerechnet. Dijkstra setzt für jeden Knoten \(v\) den Abstand genau einmal fest. Das ist gesichert, wenn \(\ell_{ij} \ge 0\) für alle Bögen gilt: Dann kann ein späterer Weg zu \(v\) nicht kürzer werden als der abgeschlossene.

Verlängerung im Labeling. Ein Label \((t, c, q, M)\) beschreibt einen Teilweg: \(t\) ist die Zeit, \(c\) die reduzierten Kosten des Teilwegs (nicht zu verwechseln mit den Kosten \(c_r\) einer Tour), \(q\) die Last und \(M\) die Menge der gesperrten Kunden. \(N_k(j)\) sind die \(k\) nächsten Kunden von \(j\) einschließlich \(j\) (Gedächtnis; \(k = n\) heißt elementar). Aus einem Label am Knoten \(i\) entsteht über den Kunden \(j\) mit \(j \notin M\) das Label

\[t' = \max\bigl(t + \sigma_i + d_{ij},\; a_j\bigr), \quad c' = c + d_{ij} - \pi_j, \quad q' = q + q_j, \quad M' = (M \cap N_k(j)) \cup \{j\}\]

nur falls \(t + \sigma_i + d_{ij} \le b_j\) und \(q' \le Q\) gilt (\(\sigma_i = \sigma\) für einen Kunden, 0 am Depot). Die Tour darf ins Depot zurück, wenn \(t + \sigma + d_{j0} \le H\). Das Startlabel am Depot ist \((t, c, q, M) = (0, 0, 0, \emptyset)\).

Dominanz. Das Label \((t, c, q, M)\) dominiert \((t', c', q', M')\) am selben Kunden, wenn

\[c \le c', \quad t \le t', \quad q \le q', \quad M \subseteq M'\]

gilt. Bei gleichen Werten bleibt das früher erzeugte Label.

Glättung. Das Pricing rechnet nicht mit den echten Dualpreisen \(\pi\), sondern mit

\[\tilde\pi = \alpha\,\pi^{\text{Vorrunde}} + (1-\alpha)\,\pi\]

wobei \(\pi^{\text{Vorrunde}}\) die Preise sind, mit denen das letzte Pricing der Vorrunde gerechnet hat (geglättete Preise, nach einem Fehlgriff die echten). In der ersten Runde gibt es keine Vorrunde, dort rechnet das Pricing mit den echten \(\pi\). Eine Spalte wird nur angehängt, wenn ihre reduzierten Kosten unter den echten \(\pi\) negativ sind; sonst folgt ein Fehlgriff und sofort eine Rechnung mit \(\alpha = 0\).

Herleitungen Schritt für Schritt

Die folgenden Rechnungen stammen von dieser Seite, es sind keine Messungen der Demo.

Warum in der ersten Runde die Bögen vom Depot negativ sind.

• Schritt 1: Im ersten Master deckt jede Spalte genau einen Kunden: die Einzelfahrt \(0 \to j \to 0\) mit Kosten \(c_j = 2\,d_{0j}\). In der dualen Nebenbedingung zu dieser Spalte steht nur \(\pi_j\), also \(\pi_j \le c_j\). Der Zielwert \(\sum_j \pi_j\) wird am größten für \(\pi_j = c_j\).
• Schritt 2: Dann ist \(\ell_{0j} = d_{0j} - \pi_j = -d_{0j}\), negativ für jeden Kunden mit Abstand ungleich null vom Depot. Im Handbeispiel sind das die sieben Bögen mit den Längen −3, −3, −5, −3, −3, −3, −5.
• Schritt 3: Die Rundfahrt \(i \to j \to i\) hat in der ersten Runde die Länge \(2\,d_{ij} - 2\,d_{0i} - 2\,d_{0j}\). Nach der Dreiecksungleichung \(d_{ij} \le d_{0i} + d_{0j}\) ist sie nie positiv, und sie ist negativ, solange das Depot nicht auf einem kürzesten Weg zwischen \(i\) und \(j\) liegt. Im Handbeispiel trifft das auf 12 von 21 Paaren zu; für die übrigen folgt die Länge 0 (Folgerung dieser Seite).

Warum Dijkstra Längen von null oder mehr braucht.

• Schritt 1: Dijkstra schließt in jedem Schritt den offenen Knoten \(v\) mit dem kleinsten vorläufigen Abstand ab. Jeder andere Weg zu \(v\) verlässt den abgeschlossenen Bereich zuerst über einen offenen Knoten \(w\), dessen vorläufiger Abstand mindestens so groß ist wie der von \(v\).
• Schritt 2: Gilt \(\ell \ge 0\) auf allen Bögen, kann der Rest des Weges von \(w\) nach \(v\) den Abstand nicht verringern, also ist \(v\) richtig abgeschlossen. Liegt im Rest ein negativer Bogen, entfällt dieser Schluss, und der Weg über \(w\) kann kürzer sein.
• Schritt 3: Das ist eine hinreichende Bedingung, keine notwendige. Ob Dijkstra bei einer bestimmten Instanz mit negativen Längen trotzdem trifft, hängt von der Instanz ab; im Handbeispiel trifft es nicht.
• Schritt 4: Ist ein Hin-und-zurück-Kreis negativ, gibt es unter den Wegen mit Wiederholungen keinen kürzesten Weg, denn jede weitere Runde im Kreis senkt die Länge.

Warum das Labeling mit negativen Längen zurechtkommt, und was die Schranke ist.

• Schritt 1 (Reihenfolge): Das Labeling verlängert das offene Label mit der kleinsten Zeit, nicht das mit den kleinsten Kosten. Jede Verlängerung erhöht die Zeit um mindestens \(\sigma_i + d_{ij}\): von einem Kunden aus um mindestens \(\sigma > 0\) (so in allen Instanzen der Demo), vom Depot aus um \(d_{0j} > 0\). Es entstehen also nur Labels mit größerer Zeit als das verlängerte: Jedes Label wird einmal in zeitlicher Reihenfolge verlängert, und kein später erzeugtes kann davor liegen. Die Kosten spielen für diese Reihenfolge keine Rolle, negative Längen stören sie nicht. (Dijkstra ordnet dagegen nach den Kosten, und genau das bricht bei negativen Längen.)
• Schritt 2 (Endlichkeit): Die Zeit wächst bei jeder Verlängerung und ist durch die Fensterenden und den Horizont \(H\) beschränkt, die Last durch \(Q\). Es gibt also nur endlich viele Verlängerungen, auch wenn Kreise zulässig wären.
• Schritt 3 (Dominanz): Gilt \(c \le c'\), \(t \le t'\), \(q \le q'\) und \(M \subseteq M'\), ist jede Fortsetzung des zweiten Labels auch für das erste zulässig: Es kommt früher an (die Verlängerung \(\max(t + \sigma_i + d_{ij}, a_j)\) nimmt mit \(t\) nicht ab, ein kleineres \(t\) gibt also höchstens eine frühere Ankunft), die Last ist kleiner, und es ist kein Kunde gesperrt, den das zweite noch besuchen darf (\(M \subseteq M'\)). Die Fortsetzung kostet dieselben Längen, das erste Label bleibt also nicht teurer. Das zweite Label kann gestrichen werden, ohne den besten Weg zu verlieren.
• Schritt 4 (Schranke): Findet das Pricing keine Tour mit \(\bar c < 0\), erfüllen die Dualpreise \(\sum_j A_{jr}\,\pi_j \le c_r\) für alle zulässigen Touren \(r\). Sie sind dann auch im dualen Problem über alle Touren zulässig, und ihr Zielwert \(\sum_j \pi_j\) ist der Master-Wert. Nach schwacher Dualität ist er höchstens so groß wie das LP über alle Touren; weil der Master nur einen Teil dieser Touren nutzt, ist er mindestens so groß. Beide Werte sind also gleich: Die Schranke ist der Wert des LP über alle Touren (im Handbeispiel gibt ein Master über alle 79 zulässigen Wege ebenfalls 30) und damit eine Untergrenze für jeden ganzzahligen Plan. Bedingung: Das Pricing muss die beste Tour finden. Bei einem Gedächtnis \(k < n\) lässt es Touren mit Kreisen zu; die Schranke gilt dann für diese größere Tourenmenge und ist höchstens so hoch wie die elementare. Dazu passt, dass ein Test der Demo ein größeres Gedächtnis mit höherer oder gleicher Schranke verlangt.

Durchgerechnet: das Handbeispiel in der ersten Runde

Dualpreise. Die Einzelfahrten kosten 6, 6, 10, 6, 6, 6, 10 (zwei mal der Abstand zum Depot 3, 3, 5, 3, 3, 3, 5), zusammen 50. Der Master der ersten Runde hat nur diese Spalten, seine Dualpreise sind genau diese Kosten: \(\pi = (6, 6, 10, 6, 6, 6, 10)\), Master-Wert 50.

Dijkstra mit Entfernung minus Dualpreis. Kunde 3 hat den Abstand 5 vom Depot, also \(\ell_{03} = 5 - 10 = -5\); er wird als Erster mit Abstand −5 abgeschlossen. Kunde 7 hat ebenfalls −5; bei Gleichstand kommt der Knoten mit der kleineren Nummer zuerst. Die Zahlen −24 und 21 unten gelten für diese Reihenfolge: Mit Kunde 7 zuerst fände Dijkstra den Weg 7-6-3-5-4-1-2 mit Länge −22 und 20 verpassten Verbesserungen, und auch dann nicht den besten einfachen Weg (−28). Über den Bogen von Kunde 3 zu Kunde 4 (Länge \(2 - 6 = -4\)) erhält Kunde 4 den Abstand −9. Der Bogen von Kunde 4 zu Kunde 3 hat die Länge \(2 - 10 = -8\) und würde Kunde 3 auf \(-9 + (-8) = -17\) verbessern, doch Kunde 3 ist abgeschlossen und wird nicht mehr geändert. Es gehen 21 solcher Verbesserungen verloren. Dijkstra liefert den Weg 3-4-5-1-7-6-2 mit Länge −24; die Aufzählung aller einfachen Wege (jeder Kunde höchstens einmal, ohne Last und Fenster) findet 4-3-5-1-2-7-6 mit Länge −28. Beide Wege sind unzulässig: der von Dijkstra wegen der Last (7 > 6 bei Kunde 5), der beste einfache Weg ohne Grenzen wegen des Fensters (Ankunft 24 > Fensterende 15 bei Kunde 3). Die Aufzählung zählt 13 699 einfache Wege.

Der kleinste Kreis. Bei den Kunden 3 und 4 hat die Rundfahrt die kleinste Länge: \(2 \cdot 2 - 10 - 6 = -12\); dasselbe gilt für die Paare 3 und 5 sowie 6 und 7 (Rechnung dieser Seite).

Labeling mit den Dualpreisen der ersten Runde. Es erzeugt 56 Labels, davon 20 sofort verworfen (neu und von einem lebenden Label dominiert, etwa das Label 0-2-3 vom Label 0-3: Kosten −5 ≤ −5, Zeit 5 ≤ 13, Last 3 ≤ 6, Menge {3} ⊆ {2, 3}), 0 später verdrängt, 36 am Ende übrig. Der beste Wert ist −10, zum Beispiel mit dem Weg 2-7-6: Fahrt 3 + 4 + 2 + 3 = 12, Dualpreise 6 + 10 + 6 = 22, also \(\bar c = 12 - 22 = -10\); Ankunft bei Kunde 2 zur Zeit 3, bei Kunde 7 zur Zeit 9, bei Kunde 6 zur Zeit 13, Last 3, 5, 6. Die Wege 6-7-1 und 5-6-7-1 haben ebenfalls −10. Die Tiefensuche über alle zulässigen elementaren Wege zählt 79 Wege, der beste Wert ist −10 (drei Wege); das Labeling liefert davon 35 (die übrigen hängen an dominierten Labels), und 58 der 79 haben negative reduzierte Kosten.

Spaltenerzeugung mit exaktem Master (Brüche, Pricing = Labeling, je Runde die beste neue Spalte): 7 Runden, Master-Werte 50, 40, 32, 32, 32, 30, 30, neue Spalten 2-7-6, 5-3-1, 2-1, 3-4, 5-4-1, 6-7-1. Die Schranke ist 30. Die Endlösung besteht aus 2-7-6 mit Menge 1 und 5-3-1, 3-4 und 5-4-1 mit je 1/2; jeder Kunde wird genau einmal überdeckt. Ein Master über alle 79 zulässigen Wege als Spalten gibt ebenfalls 30, und mit den Dualpreisen der letzten Runde hat keiner der 79 Wege negative reduzierte Kosten. Gebraucht wurden 6 neue Spalten zusätzlich zu den 7 Einzelfahrten, im Endmaster stehen also 13 der 79 Wege. Mit HiGHS als Master (Überdeckung und Partitionierung) ist die Schranke ebenfalls 30; die Zahl der Runden hängt von den gewählten Dualpreisen ab, weil der Master entartet ist, und steht dort nicht fest.

Befunde

Alle Zahlen sind Messungen an festen Instanzen (Zufalls-Seeds siehe Modell); Mittel und Mediane laufen über die Instanzen einer Zeile. Eine ganze Spaltenerzeugung live (elementares Pricing, Überdeckungs-Master; der Master-Wert der ersten Runde ist die Summe der Einzelfahrten):

Kunden, Fensterbreite (Zufalls-Seed)	Master-Wert der ersten Runde	Schranke am Ende (Master-Wert der letzten Runde)
12 Kunden, Fensterbreite 100 (7)	909,75	497,87
20 Kunden, Fensterbreite 40 (7)	1 612,66	710,77
20 Kunden, Fensterbreite 100 (3)	1 468,28	509,43

Negative Bogenlängen (30 Kunden, Fensterbreite 100, 6 Instanzen mit den Zufalls-Seeds 0 bis 5, Pricing mit Gedächtnis k = 5, Überdeckungs-Master; reine Rechnung an den Dualpreisen):

Runde	Bögen Depot → Kunde negativ (Mittel)	Bögen Kunde → Kunde negativ (Mittel)	Kundenpaare mit negativem Kreis (Mittel)
erste (nur Einzelfahrten im Master)	30,0 von 30	675,7 von 870 (77,7 %)	435,0 von 435
letzte (Ende der Spaltenerzeugung)	4,8 von 30	149,2 von 870 (17,1 %)	69,5 von 435

In der ersten Runde sind in allen 6 Instanzen alle 30 Bögen vom Depot und alle 435 Kundenpaare negativ.

Runden und Spalten einer ganzen Spaltenerzeugung (30 Kunden, Gedächtnis k = 5, Überdeckungs-Master, 6 Instanzen je Fensterbreite; die Spalten schließen die 30 Einzelfahrten vom Start ein, die Labels sind die erzeugten Labels der ganzen Spaltenerzeugung):

Fensterbreite	Runden (Median)	Runden (Minimum)	Runden (Maximum)	Spalten am Ende (Median)	Labels (Median)
40	18,0	11	31	239,0	29 470,5
100	20,0	15	29	282,5	102 175
200	23,5	23	35	338,5	348 765,5

Der Median der Runden steigt von Breite 40 über 100 auf 200 von Stufe zu Stufe. Ein Median aus 6 Instanzen ist das Mittel der beiden mittleren Werte, daher die Nachkommastelle. Wie viele zulässige Wege es bei 30 Kunden insgesamt gibt, ist nicht gezählt; „nur ein Bruchteil der Wege wird gebraucht“ ist nur für das Handbeispiel belegt (13 von 79 Wegen).

Glättung der Dualpreise (einfache Glättung zur Vorrunde, Gedächtnis k = 5, Fensterbreite 100, Überdeckungs-Master, Zufalls-Seeds ab 0; dieselbe Schranke in allen Instanzen und allen \(\alpha\)). Erst 20 Kunden, 12 Instanzen:

\(\alpha\)	Runden (Mittel)	Runden (Maximum)	Pricing-Aufrufe (Mittel)	Fehlgriffe (Mittel)	weniger / gleich / mehr Runden als bei \(\alpha = 0\)
0	13,7	17	13,7	0,0	0 / 12 / 0
0,5	13,7	22	17,5	3,8	5 / 2 / 5
0,8	18,4	28	23,6	5,2	1 / 0 / 11
0,9	23,2	30	32,2	9,0	0 / 1 / 11

Dann 30 Kunden, 6 Instanzen:

\(\alpha\)	Runden (Mittel)	Runden (Maximum)	Pricing-Aufrufe (Mittel)	Fehlgriffe (Mittel)	weniger / gleich / mehr Runden als bei \(\alpha = 0\)
0	20,5	29	20,5	0,0	0 / 6 / 0
0,5	19,8	28	22,8	3,0	3 / 0 / 3
0,8	24,3	34	29,7	5,3	0 / 0 / 6
0,9	34,2	50	43,2	9,0	0 / 0 / 6

Bei \(\alpha = 0{,}5\) sind die mittleren Runden etwa gleich wie ohne Glättung (innerhalb von 10 %: 13,7 gegen 13,7 bei 20 Kunden, 19,8 gegen 20,5 bei 30 Kunden), die Pricing-Aufrufe sind im Mittel mehr (17,5 gegen 13,7 und 22,8 gegen 20,5). Einzelne Instanzen liegen dabei besser, andere schlechter. Bei \(\alpha = 0{,}8\) und \(\alpha = 0{,}9\) braucht die Glättung bei 20 Kunden in 11 von 12 Instanzen mehr Runden als ohne Glättung, bei 30 Kunden in 6 von 6. Die Pricing-Aufrufe sind je Instanz genau die Summe aus Runden und Fehlgriffen (in den Tabellenmitteln bis auf Rundung), weil nach einem Fehlgriff in derselben Runde sofort ungeglättet gerechnet wird: Ein Fehlgriff kostet einen zusätzlichen Aufruf, aber keine zusätzliche Runde. Warum starke Glättung Runden kostet, zeigt die Messung nicht. Deutung (nicht gemessen): Die Spalten, die das Pricing unter stark geglätteten Preisen findet, bringen dem Master weniger als solche unter den aktuellen Dualpreisen.

Überdeckung gegen Partitionierung (30 Kunden, je 5 Instanzen mit den Zufalls-Seeds 0 bis 4, Pricing mit Gedächtnis k = 1, 5 und 8, Fensterbreite 100, Schranke mit beiden Mastern; bei \(k = 1\) ist nur der aktuelle Kunde gesperrt, Hin-und-zurück-Kreise sind also zulässig, Folgerung aus der Formel für \(M'\)):

Instanztyp	Gedächtnis k	Paare	größte Abweichung der Schranke	Schranke Überdeckung (Mittel)
zufällig verteilt, Horizont 300, Kapazität 70	1	5	0,000000	760,61
zufällig verteilt, Horizont 300, Kapazität 70	5	5	0,000000	786,13
zufällig verteilt, Horizont 300, Kapazität 70	8	5	0,000000	787,17
gruppiert um fünf Zentren, Horizont 300, Kapazität 70	1	5	0,000000	462,80
gruppiert um fünf Zentren, Horizont 300, Kapazität 70	5	5	0,000000	473,01
gruppiert um fünf Zentren, Horizont 300, Kapazität 70	8	5	0,000000	473,90
zufällig verteilt, Horizont 500, Kapazität 120	1	5	0,000000	695,49
zufällig verteilt, Horizont 500, Kapazität 120	5	5	0,000000	726,12
zufällig verteilt, Horizont 500, Kapazität 120	8	5	0,000000	726,68

In allen 45 Paaren ist die Schranke mit Überdeckung und mit Partitionierung gleich (größte Abweichung unter 0,000001); das gilt für metrische Kosten (Entfernungen). Als mögliche Erklärung (Deutung, nicht gemessen): Bei metrischen Kosten macht das Auslassen eines Kunden aus einer Tour sie nicht teurer, und sie bleibt zulässig, deshalb hilft das Überdecken bei den gemessenen Instanzen nicht. Im Handbeispiel gilt dieselbe Schranke 30 mit beiden Mastern. Ein Test prüft außerdem an 30 kleinen Instanzen mit 6 Kunden, dass das LP über alle zulässigen Wege bei Überdeckung und Partitionierung denselben Wert gibt.

Gegenprobe mit einer zweiten Implementierung. Das Labeling gibt auf 180 Fällen (60 Instanzen mit 7 Kunden und je 3 Fensterbreiten, zufällige Dualpreise) denselben besten Wert wie die Tiefensuche über alle zulässigen elementaren Wege und liefert nur Routen, die auch die Tiefensuche findet; gibt es keinen zulässigen Weg, liefert auch das Labeling keinen. Eine zweite Implementierung mit Mengen und Brüchen zählt auf 40 weiteren Instanzen und im Handbeispiel dieselben erzeugten und dominierten Labels.

Vergleich mit einer früheren Messreihe. Vor dem Bau der Demo gab es eine Messreihe der Planung mit anderen Instanzen (erzeugt mit Pythons random.Random) und einem anderen Rechenkern; ihre Zahlen sind aus den Rohdateien übernommen und nicht neu gerechnet. Auf ihren 6 Instanzen (30 Kunden, Breite 100, k = 5) liefert der Rechenkern der Demo dieselbe Schranke wie die frühere Messreihe (auf 4 Stellen). Die Richtung der Befunde ist gleich, die Zahlen unterscheiden sich um einige Prozent bis einige Runden, etwa bei den Runden (Median, Breite 40, 100, 200): 15,0, 19,5, 23,0 früher gegen 18,0, 20,0, 23,5 hier.

Was die Messung zeigt und wo die Grenzen liegen

Was sie belegt:

• Im Handbeispiel verfehlt Dijkstra mit den Längen Entfernung minus Dualpreis den besten einfachen Weg (−24 gegen −28, ohne Last und Zeitfenster gerechnet). Das Labeling liefert den besten zulässigen Weg (−10, Gegenprobe über alle 79 zulässigen Wege), und die Spaltenerzeugung endet bei der Schranke 30, die auch ein Master über alle 79 Wege ergibt.
• In der ersten Runde sind in den 6 Instanzen mit 30 Kunden alle 30 Bögen vom Depot und alle 435 Kundenpaare negativ; am Ende der Spaltenerzeugung sind es im Mittel noch 17,1 % der Bögen zwischen Kunden.
• Die einfache Glättung zur Vorrunde spart in diesen Messreihen im Mittel keine Runden (gemessen sind nur \(\alpha = 0{,}5\), \(0{,}8\) und \(0{,}9\)): etwa gleich viele bei \(\alpha = 0{,}5\) (mit mehr Pricing-Aufrufen), mehr bei \(\alpha \ge 0{,}8\).
• Mit metrischen Kosten sind die Schranken bei Überdeckung und Partitionierung in allen 45 Paaren gleich.
• Das Labeling stimmt auf 180 Fällen mit der Tiefensuche überein.

Was sie nicht belegt:

• Stabilisierung im Allgemeinen: Gemessen ist nur die einfache Glättung zur Vorrunde, nicht die Verfahren von Wentges (Zentrum = bestes bisheriges Dual) und von du Merle u. a. (Strafen im Dualraum). Die Aussage gilt für diese Regel, diese Instanzen und diesen Master.
• Verteilung: Es sind 5, 6 bzw. 12 Instanzen je Zelle. Mittel, Median und Maximum sagen nichts über die ganze Verteilung; bei Breite 40 reichen die Runden von 11 bis 31, die Spanne ist also groß.
• Elementarität: Die Live-Rechnung ist elementar, die Messreihen mit 30 Kunden rechnen mit k = 5 (beim Vergleich der Master auch k = 1 und 8) und lassen Kreise nicht ganz aus. Was die Elementarität kostet und wie Kreise verhindert werden, zeigt die Demo nicht.
• Kostenstruktur: Überdeckung gegen Partitionierung wurde nur mit metrischen Kosten verglichen. Mit Festkosten je Fahrzeug oder Kosten ohne Dreiecksungleichung ist die gleiche Schranke nicht belegt.
• Löser und Rechner: Runden und Spalten hängen vom LP-Löser ab, weil der Master oft mehrere gleich gute Dualpreise hat (Entartung) und HiGHS je nach Version eine davon wählt; die Schranke hängt nicht davon ab. Die 7 Runden des Handbeispiels gelten für den exakten Master. Sekunden sind nicht festgeschrieben.
• Reichweite: Die Instanzen sind selbst erzeugt und nicht die Solomon-Originale, live wird nur bis 20 Kunden gerechnet. Die Zahlen sagen nichts über öffentliche Benchmarks, andere Programmiersprachen, andere LP-Löser oder andere Rechner.
• Was fehlt: ganzzahlige Lösungen (Branch-and-Price), mehrere begrenzte Größen über Zeit und Last hinaus, Festkosten je Fahrzeug, Sekunden als Messgröße.

Erweiterungen und Verweise

Verwandte Seiten und Demos dieser Website:

• Grundlagen: Die Erklärseite Schattenpreise und Dualität erklärt den Dualpreis, die Erklärseite zum Dijkstra-Algorithmus das Verfahren mit seinem Haken, die Erklärseite zur Dominanz bei Teilwegen das Streichen von Teilwegen.
• Dasselbe Pricing in einem Fall: Die Erklärseite Crew Pairing zeigt ein solches Pricing im Zugverkehr; Zahlen von dort werden hier nicht übernommen.
• Master und Dualpreise am Zuschnitt: Die column-generation-demo erklärt Master, Dualpreise und die Rundungslücke (den Abstand zwischen LP-Wert und bestem ganzzahligen Plan) am Cutting Stock mit einem Rucksack als Pricing. Die mcf-column-generation-demo formuliert das Pricing als Dijkstra mit nichtnegativen Längen (Kosten plus Preis) im Netzwerkfluss.
• Labeling mit Grenzen: Die Demos weg-mit-grenzen, dominanz-labels, zeitfenster-labeling und mehrere-grenzen erklären das Labeling mit einer Grenze, mit Dominanz, mit Zeitfenstern und mit mehreren Grenzen; diese Demo wendet es auf Dualpreise an.

Quellen

• Dantzig, Wolfe (1960): Decomposition Principle for Linear Programs. Operations Research 8(1) (Spaltenerzeugung am LP).
• Gilmore, Gomory (1961): Operations Research 9(6) (erste Anwendung am Cutting Stock; Pricing ist ein Rucksack).
• Desrochers, Soumis (1988): A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26 (Label-Setting mit Zeitfenstern).
• Lübbecke, Desrosiers (2005): Selected Topics in Column Generation. Operations Research 53(6) (duale Sicht, Entartung, Stabilisierung).
• du Merle, Villeneuve, Desrosiers, Hansen (1999): Discrete Mathematics 194(1 bis 3) (stabilisierte Spaltenerzeugung, Strafen im Dualraum).
• Irnich, Desaulniers (2005): Shortest Path Problems with Resource Constraints. In: Column Generation, Springer (Standardreferenz).
• Quelltext, Messreihen und Tests der Demo: github.com/sebastian-hanisch/pricing-dualpreise-demo.

Die genannten Arbeiten wurden für diese Seite nicht nachgeschlagen. Laut dem Literaturvermerk der Demo wurde von allen nur Abstract oder Suchtreffer gesehen, bei Irnich und Desaulniers nur das Zitat; keine Zahl der Demo stammt aus der Literatur. Die einfache Glättung (nach Neame) und das Verfahren von Wentges sind aus dem Gedächtnis genannt und nicht geprüft. Die Befundtabellen geben die Messreihen der Demo wieder; die Herleitungen sind Rechnungen dieser Seite.