Ressourcenwege und Spaltenerzeugung: Wege mit Grenzen erklärt
Stellen Sie sich vor: Ein Disponent plant die Touren eines Fuhrparks. Es gibt so viele mögliche Touren, dass niemand sie alle aufschreiben kann, und jede muss Grenzen einhalten: Jeder Kunde hat ein Zeitfenster, jeder Lkw lädt nur bis zu einem Limit. Er sucht die Auswahl mit den geringsten Gesamtkosten. Wie findet er gezielt die eine Tour, die dem Plan als Nächstes am meisten nützt?
Das ist die Aufgabe der Spaltenerzeugung: Ein Hauptplan, der Master, wählt aus den bisher bekannten Touren die billigste Überdeckung der Kunden und nennt für jeden Kunden einen Preis, den Dualpreis: den Betrag, den der Plan ihm gerade zurechnet. Ein Hilfsproblem, das Pricing, sucht dann eine neue Tour, die weniger Strecke kostet, als ihre Kunden an Dualpreisen einbringen. Diese Tour ist ein Weg mit Zeit- und Lastgrenzen, ein Ressourcenweg. Die Leitfrage dieser Linie lautet: Wie findet man den besten Weg unter solchen Grenzen, wie hält man die Suche klein, und welcher Kniff lohnt bei welcher Aufgabe?
Dreizehn Stücke gehen dem nach, in vier Gruppen. Die erste legt das Fundament: ein Weg mit Zeitgrenze, die Frage, wann ein Teilweg gestrichen werden darf, Zeitfenster und mehrere Grenzen zugleich. Die zweite macht daraus das Pricing: Die Preise des Masters machen viele Streckenlängen negativ, und dann reicht das übliche Verfahren für kürzeste Wege, Dijkstra, nicht mehr. Die dritte fragt, ob ein Kunde mehrfach vorkommen darf, von erlaubten Kreisen bis zu einem begrenzten Gedächtnis. Die vierte sammelt Kniffe gegen die Rechenlast: von beiden Enden rechnen, Teilwege in Fächer sortieren, überflüssige Strecken streichen, erst grob und dann exakt rechnen; das letzte Stück wählt den passenden. Wie ein solches Pricing im Zugverkehr aussieht, erzählt die Erklärseite zu Crew Pairing.
Was diese Linie ist und was nicht: Es sind eigene Beispiele, ein kleines Handnetz zum Nachrechnen und selbst erzeugte Kundeninstanzen im Stil bekannter Benchmarks, nicht deren Originalinstanzen; die meisten Messreihen haben 30 Kunden und wenige Instanzen je Zelle. Gezählt werden erzeugte Labels, also Teilwege mit ihren Kosten und Verbräuchen, nicht Sekunden. Ein vollständiges Verfahren mit ganzzahliger Lösung (Branch-and-Price) ist nicht gebaut, die Linie zeigt nur das Pricing und die Schranke, den Wert des Masters am Ende der Rechnung. Sie sagt nichts über echte Fälle.
In short: Covers the pricing problem of column generation in vehicle routing: a shortest path with time and load limits, solved by labeling with dominance. Compares ways to keep it small, from cycles and ng-routes to bidirectional labeling and edge elimination, and ends with choosing a method.
Hintergrund zum Thema: Tourenplanung optimieren · Schienenverkehr optimieren.
Diese Seite gehört zu Algorithmen und Verfahren erklärt. So lesen Sie sie: Das Diagramm zeigt, wie die Stücke zusammenhängen. Jede Kachel darunter öffnet eine interaktive Demo, wo es eine gibt, mit einer Erklärseite für Einsteiger und Fachleute. Auf der Suche nach einer Lösung für ein konkretes Problem? Zu den Interaktiven Demos.
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.
Zuletzt aktualisiert:
Welches Verfahren passt zu Ihrem Fall? Zum Entscheidungsbaum ↓
Zum Nachlesen: erst einfach, dann fachlich
Dominanz bei Teilwegen verständlich erklärt
Wann ist ein Teilweg überflüssig, weil ein anderer am selben Kunden in allem mindestens so gut ist, und was geht verloren, wenn man nur auf die Kosten schaut? Erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Zählungen.
Pricing aus Dualpreisen verständlich erklärt
Warum der Hauptplan Längen unter null erzeugt, das übliche Verfahren für kürzeste Wege dann den besten Weg verfehlen kann und ob das Glätten der Preise Runden spart: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
ng-Routen verständlich erklärt
Ein Fahrer merkt sich nur, welche der nächsten Kunden er schon hatte: Wie viel Gedächtnis braucht die Suche nach der besten Tour, und was kostet es? Erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln, Messwerten und Grenzen.
Die 13 Stücke im Überblick
Der Graph zeigt, wie die dreizehn Stücke zusammenhängen. Am Anfang steht der Weg mit Grenze. Von dort führt eine Kette durch die Grundlagen (Dominanz, Zeitfenster, mehrere Grenzen) zum Pricing aus Dualpreisen und weiter durch die Fragen nach Kreisen und Elementarität bis zu den ng-Routen. Jeder Pfeil nennt, was beim Vorgänger offen blieb, zum Beispiel dass die Dualpreise nur aus der ersten Runde stammen oder dass es gegen die Wand der elementaren Rechnung keine Abhilfe gibt. Von den mehreren Grenzen zweigt ein zweiter Strang ab: das Rechnen von beiden Enden, die Eimer und die Kantenstreichung. Aus dem Pricing führt ein dritter Weg zum heuristischen Pricing. Die Stränge laufen in der Verfahrenswahl zusammen.
Zwischen dem bidirektionalen Labeling und den Eimern steht ein Kontrast: Es sind zwei verschiedene Mittel gegen dieselbe Label-Zahl. Der Kontrast-Tab zu den k-Zyklen steckt in der ng-Routen-Demo und hat keinen eigenen Knoten. Vier Bausteine kommen aus anderen Linien: Dijkstra mit einem Wert je Knoten, das Mehrkriterien-Routing mit der Pareto-Front, die Column Generation am Zuschnitt mit einem Rucksack als Pricing und die Pfad-Formulierung im Netzwerkfluss mit Dijkstra als Pricing. Die Anwendung in einem Fall zeigt die Crew-Pairing-Demo: Dort ist das Pricing ein Label-Verfahren für die Besatzungsplanung im Zugverkehr.
Die Kästen sind klickbar und öffnen die jeweilige Demo direkt.
- behebt eine Schwäche des Vorgängers oder baut darauf auf
- Gegenstück: derselbe Zweck, andere Bauweise (kein Fix)
- übernimmt nur eine Idee
- Zusammenfluss mehrerer Stränge
- Baustein aus einer anderen Linie
Durchgezogene Pfeile nennen eine Schwäche des Vorgängers, der gestrichelte Doppelpfeil ist ein Kontrast (derselbe Zweck, andere Bauweise), gepunktete Pfeile übernehmen nur eine Idee. Doppelt umrandet ist die Verfahrenswahl, graue gestrichelte Knoten sind Bausteine aus anderen Linien. Die Stücke lassen sich in beliebiger Reihenfolge lesen, ein Pfeil ist keine vorgeschriebene Reihenfolge.
Verwandt in anderen Linien
- Tourenbildung: eine Reihenfolge, optimal zerlegt — Die Linie Tourenbildung bildet Touren aus einer Reihenfolge aller Kunden: Riesentour und Split zerlegt sie mit einem kürzesten Weg in einem Hilfsgraphen, dessen Bögen Routen sind, und Zeitfenster und Split fragt, was enge Fenster dort ändern. Hier sucht das Pricing dagegen die eine Tour, die mit den Preisen des Masters am meisten nützt, und rechnet dafür mit Zeit- und Lastgrenzen im Label selbst.
- Exakte Suche — Die Column-Generation-Demo der Linie Exakte Suche zeigt Master, Dualpreise und die Rundungslücke am Zuschnitt, mit einem Rucksack als Pricing; Branch and Price erzeugt die Spalten dort im ganzen Suchbaum. Hier wird das Pricing ein kürzester Weg mit Grenzen, und gerechnet wird nur die Schranke des Masters, kein Branch-and-Price.
- Kürzeste Wege — Die Dijkstra-Demo der Linie Kürzeste Wege führt je Knoten einen Wert; in Pricing aus Dualpreisen reicht das nicht mehr, weil die Längen Entfernung minus Dualpreis sind und negativ werden. Mehrkriterien-Routing zeigt das Label-Setting für die ganze Pareto-Front (Zeit gegen CO₂); im Ressourcenweg wirkt die Grenze dagegen im Verfahren: Labels über der Grenze entstehen nicht. Die Pfad-Formulierung im Netzwerkfluss hat Dijkstra mit nichtnegativen Längen als Pricing.
Ressourcenweg: der billigste Weg mit Grenze
Verfolgen Sie, wie in einem Netz der billigste Weg bei einer Zeitgrenze gesucht wird: Statt einer Zahl je Knoten führt jeder eine Liste von Labels aus Kosten und verbrauchter Zeit, damit die Grenze hält. Bei 20 Kunden wächst die Zahl der Labels im Median von 874 bei Zeitgrenze 150 auf 5.284 bei 200. Der Haken: Nur die Zeit ist begrenzt, mit mehr Kunden ist sie nicht gemessen.
Demo starten →Dominanz: wann darf ein Label gehen?
Verfolgen Sie, wann ein Label gestrichen werden darf: nur, wenn ein anderes am selben Kunden bei Kosten, Zeit, Last und besuchten Kunden mindestens so gut ist. Wer nur die Kosten vergleicht, verfehlt bei 7 Kunden in 67 von 180 Fällen den besten Weg, die volle Regel in keinem. Der Haken: In dieser Fassung war die Rechnung mit Dominanz bei den größten Instanzen in einer Einzelmessung langsamer als ohne.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Zeitfenster und Warten im Label-Setting
Sehen Sie, was Zeitfenster ändern: Wer zu früh kommt, wartet kostenlos bis zum Fensterbeginn, wer zu spät kommt, scheidet aus. Je breiter die Fenster, desto mehr Labels: Bei 30 zufällig verteilten Kunden wächst ihre Zahl in einem Pricing-Aufruf im Median von 1.413 bei Breite 20 auf 42.510 bei Breite 200. Der Haken: Das gilt für diese Messreihen ohne Wartekosten, nicht allgemein.
Demo starten →Mehrere Grenzen: Zeit, Last, Fahrerzeit
Sehen Sie, was jede Grenze neben der Zeit kostet, etwa Last und Fahrerzeit: Jede gehört ins Label, und die Dominanz muss sie alle vergleichen. Bei 30 Kunden, nie bindenden Grenzen und unabhängigen Verbräuchen wachsen die Labels etwa linear von 7.672 auf 37.692, die Dominanzvergleiche aber überlinear von 75.968 auf 8.131.986. Der Haken: Eine bindende Grenze kann sogar weniger Labels erzeugen, vermutlich weil sie Wege abschneidet.
Demo starten →Pricing aus Dualpreisen: wenn das Standardverfahren für kürzeste Wege versagt
Verfolgen Sie, wie das Pricing aus den Preisen des Masters Streckenlängen macht: Entfernung minus Dualpreis, und viele werden negativ. Dann schließt Dijkstra einen Knoten zu früh ab. Im Handbeispiel mit 7 Kunden verfehlt es den besten einfachen Weg (Länge −24 statt −28), das Labeling findet den besten zulässigen. Der Haken: Die einfache Glättung der Dualpreise spart im Mittel keine Runden (bei Gewicht 0,5 etwa gleich viele, ab 0,8 mehr).
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Kreise im Pricing: wie oft, und was kosten sie?
Verfolgen Sie, wie das Pricing Kreise erlaubt: Ein Kunde darf mehrfach vorkommen, nur nicht direkt hintereinander. Das macht die Suche einfach, die Schranke des Masters liegt dafür tiefer. Bei 30 Kunden und Fensterbreite 100 enthalten 71,7 % der neuen Touren einen Kreis, die Schranke liegt im Mittel 3,33 % unter der Schranke ohne Kreise. Der Haken: Bei schmalen Fenstern kommen Kreise selten vor.
Demo starten →Elementarität im Pricing: die Wand
Verfolgen Sie, was es kostet, Kreise ganz zu verbieten: Jedes Label muss die schon besuchten Kunden mitführen und darf nur gehen, wenn dessen Menge in der des anderen steckt. Bei 20 Kunden und Fensterbreite 100 sind je Label 346,4 Dominanzvergleiche nötig, mit begrenztem Gedächtnis 11,5. Der Haken: Bei 30 Kunden und breiten Fenstern brachen viele elementare Läufe an der Zeitgrenze ab, abhängig von Rechner und Last.
Demo starten →ng-Routen: wie viel Gedächtnis braucht das Preisproblem?
Verfolgen Sie, wie ein Label mit begrenztem Gedächtnis einen Kunden erst wieder besuchen darf, wenn dazwischen ein Kunde kam, in dessen Nachbarschaft er nicht liegt. Bei 30 Kunden und Breite 100 liegt die Schranke mit kleinstem Gedächtnis im Mittel 3,563 % unter der mit acht, mit fünf nur 0,115 %. Der Haken: Dass ein kleines Gedächtnis reicht, gilt nur mit Zusatz, und bei engen Fenstern spielt es keine Rolle.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Bidirektionales Labeling: von beiden Enden rechnen, in der Mitte verbinden
Verfolgen Sie, wie das Pricing zusätzlich vom Ende des Zeithorizonts rückwärts rechnet und beide Hälften in der Mitte verbindet. Bei 30 Kunden bleiben mit dem Halbweg in der Mitte im Median 0,27 der Labels des einseitigen Verfahrens, in allen 480 Läufen weniger. Der Haken: Das Verbinden kostet im Median das 9,8-Fache der einseitigen Label-Zahl an Paaren, und eine einfache dynamische Wahl des Halbwegs bringt gegenüber der Mitte nichts.
Demo starten →Eimer im Labeling: wie viel sparen sie wirklich?
Verfolgen Sie, wie die lebenden Labels eines Kunden nach Zeit und Last in Fächer, sogenannte Eimer, sortiert werden, damit die Dominanzprüfung weniger Labels ansehen muss. Das Ergebnis bleibt in allen Läufen gleich; bei 30 Kunden sparen Zeit-Eimer im Median bis zu 19,2 % der Vergleiche. Der Haken: Mit einer angenommenen Verwaltung von 0,1 Vergleichen je Schritt bleiben höchstens 6,6 %, bei sehr schmalen Eimern kostet sie mehr, als sie spart.
Demo starten →Kantenstreichung im Pricing: welche Kanten sind überflüssig?
Sehen Sie, wie eine untere und eine obere Schranke verraten, welche Kanten nie in einer besseren ganzzahligen Lösung vorkommen: Sie fallen weg, wenn die beste Route durch sie schlechter ist als die Lücke. Bei 30 Kunden entfallen mit der exakten Lücke (bewiesenes Optimum vorausgesetzt) im Mittel 46 bis 61 % der Kanten. Der Haken: Das gilt nur bei den Dualpreisen der Konvergenz, und eine zu kleine Schwelle verliert das Optimum.
Demo starten →Heuristisches Pricing: erst gelockert, exakt nur zum Beweis
Verfolgen Sie, wie das Pricing zuerst mit einem Etikettenlimit rechnet, bei dem jeder Kunde nur wenige Labels behält, und das exakte Pricing erst läuft, wenn die Heuristik nichts mehr findet. Bei 30 Kunden und Fensterbreite 100 braucht das strengste Limit im Mittel 0,52 der Labels, die Endschranke bleibt gleich. Der Haken: Es braucht 36 % mehr Runden, also mehr Master-Rechnungen; die Zeitersparnis ist nur als Größenordnung gemessen.
Demo starten →Verfahrenswahl im Pricing: welche Bausteine für welche Aufgabe?
Verfolgen Sie, wie ein Entscheidungsbaum für eine gegebene Pricing-Aufgabe, also Kundenzahl, Fensterbreite und Zahl der Grenzen, die Bausteine dieser Linie zuschaltet: Er liest nur Messwerte der anderen Demos und nennt zu jeder Empfehlung Zahl, Voraussetzung und Quelle. Bei Breite 20 und 100 Kunden genügte in allen 24 gemessenen Instanzen k = 1. Der Haken: Die Wirkung der Bausteine zusammen ist nicht gemessen, und die Master-Seite ist nicht gebaut.
Demo starten →Welches Stück passt zu meiner Frage?
Stellen Sie sich eine Pricing-Aufgabe vor, die zu langsam oder zu ungenau ist. Der Baum führt von Ihrer Frage zum passenden Stück: Geht es darum, den Weg mit Grenzen zu verstehen, um die Preise des Masters, um die Frage, ob ein Kunde mehrfach vorkommen darf, um Kundenzahl und Fensterbreite oder um einen Kniff gegen die Rechenlast?
Welches Stück passt zu meiner Frage?
Beige Kästen sind Fragen (nicht klickbar), weiße Kästen sind Ergebnisse (klickbar, sie öffnen die jeweilige Demo). Der Baum ordnet nach der Frage, nicht nach Güte. Die Größen, bei denen die Aussagen gelten, stehen in den Demos: meist 30 Kunden und wenige Instanzen je Zelle, eigene Instanzen, nicht die Originalinstanzen.
Weitere Linien in diesem Bereich
Exakte Suche
Bewiesen beste statt nur guter Lösungen: zwei Linien, Rucksack und Cutting Stock, von Branch & Bound bis Column Generation und Branch & Price.
Lineare Programmierung
Was steckt in einem LP-Löser? Elf Stücke vom Tableau-Simplex über Schattenpreise und Innere Punkte bis zum Crossover, alle von Grund auf geschrieben und gemessen.
Nichtlineare Optimierung
Wie findet man ein Minimum, wenn nichts linear ist? Acht Stücke vom ersten Schritt bergab über Krümmung und Nebenbedingungen bis zur Brücke ins Deep Learning, jedes mit gemessenem statt behauptetem Befund.
Konvexe und konische Optimierung
Wann ist ein Ergebnis beweisbar optimal, wie rechnet ein Löser mit Kegeln, und welcher Löser passt zu welcher Aufgabe? Sechzehn Stücke von der Lücke als Beweis bis zur Verfahrenswahl.
Anordnen: relaxieren und runden
Wie weit unter dem Besten liegt die beste Zahl, die man beweisen kann, und wie rundet man eine Lockerung zurück auf eine Anordnung? Fünfzehn Stücke von der Mini-Halle bis zur Verfahrenswahl.
Populations-Metaheuristiken
Wie durchsucht eine ganze Population den Lösungsraum? Elf Verfahren von der Kreuzung über Kovarianzmatrizen bis zu Pheromonspuren, jedes mit seiner gemessenen Grenze.
Trajektorien-Metaheuristiken
Wie kommt eine einzelne Lösung über ihr erstes lokales Optimum hinaus? Zwölf Verfahren von Verschlechterungen akzeptieren bis Destroy-and-Repair, jedes mit seiner gemessenen Grenze.
Heuristische Baumsuche
Was bleibt von der Suche, wenn man das Optimum nicht abwarten kann? Acht Verfahren von der gierigen Suche bis Monte Carlo Tree Search, jedes mit seiner gemessenen Grenze.
Novelty Search und Quality-Diversity
Ein Hof-Roboter im täuschenden Labyrinth, zwölf Stücke: von der Sackgasse der Fitness über Novelty Search und MAP-Elites bis zu Go-Explore, Routing und POET.
Standortplanung
Welche Standorte eröffnen, wenn jeder Kunde zum nächsten offenen geht? Sechs Stücke von der einfachen Fixkosten-Entscheidung über Kapazität, Maximum statt Summe und Lagerbestand bis zum Wettbewerb zweier Spieler und zum Hub mit Rabatt.
Klassische Scheduling-Theorie
Ein wachsendes Beispiel von einer Maschine bis zum allgemeinen Ressourcenmodell: elf Stücke, jedes hebt genau eine Annahme des vorigen auf.
Optimierung unter Unsicherheit
Eine Kapazität, die vor der unbekannten Nachfrage gewählt wird, sechs Stücke: vom Wert der Information über Stichprobe, CVaR, Robustheit und Garantie bis zur rollierenden Planung.
Bayessche Optimierung und Gauß-Prozesse
Eine teure Simulation, sieben Stücke: vom Gauß-Prozess und der erwarteten Verbesserung über Rauschen und Nebenbedingungen bis zu hohen Dimensionen, parallelen Läufen und mehreren Genauigkeiten.
Online-Algorithmen
Wie man entscheidet, bevor die Zukunft bekannt ist, und was die Garantie für den schlimmsten Fall im Betrieb kostet: sieben Stücke von Mieten oder Kaufen bis zu Vorhersagen.
Zielfunktionsdesign
Was ändert sich, wenn nur das Ziel wechselt? Vierzehn Stücke von der Wahl zwischen Summe und Maximum über Fairness und Ersatzziele bis zur Frage, wie man ein Ziel vor dem Einsatz testet.
Bestandspolitiken
Wie viel bestellen, wenn jede Periode zählt? Sieben Demos mit demselben Artikel: von der Rückwärtsrechnung über Fixkosten, Lieferzeit, Verderb und zwei Lager bis zur Frage, welche einfache Regel reicht.
Komplexitätsklassen
Was sagt es aus, wenn ein Problem als NP-schwer gilt, und welcher Ausweg passt zu welchem Grund der Härte? Zehn Stücke über Reduktionen, typische Instanzen, große Zahlen, Garantien, Parameter, Zufall, Zählen, Spiele und lokale Optima.
SAT und Constraint Programming
Wie merkt sich ein Löser, warum eine Sackgasse eine war? Sechzehn Stücke vom Konfliktlernen über Beweise, Zähler und Symmetrie bis zu Mengen- und Maschinenschlüssen, lokaler Suche und der Wahl der Modellwelt.
Packen: Reihenfolge und Platzierungsregel
Wie packt man Pakete, Rechtecke und Quader in wenige Behälter, und wie nah am Besten liegt eine einfache Regel? Vierzehn Stücke von der Sortierung bis zur Verfahrenswahl.
Umstauen: Untergrenze und Suche
Wie viele Container müssen mindestens umgestapelt werden, und wann lohnt sich die Suche nach dem Besten? Fünfzehn Stücke von der einfachen Regel bis zur Verfahrenswahl.
Tourenbildung: eine Reihenfolge, optimal zerlegt
Wie bildet man Touren aus einer einzigen Reihenfolge aller Kunden, und wann schlagen Savings, Sweep oder Suche sie? Fünfzehn Demos von der Aufzählung bis zur Verfahrenswahl.
Takt und Periodizität
Ein Fahrplan, der sich jede Stunde wiederholt: vier Stücke von den Zeitabständen über die Wartezeit der Umsteiger und die Kreisgleichungen bis zum Betriebstag.