Anordnen: relaxieren und runden erklärt
Stellen Sie sich vor: Auf einer kleinen Platine sollen Bauteile auf die Plätze eines Rasters kommen, und manche Bauteile tauschen viel miteinander aus. Sie setzen sie so, dass die stark verbundenen nahe beieinander liegen, tauschen zwei Bauteile, und es wird besser, bis nichts mehr hilft. Ein Kollege fragt: „Geht es noch kürzer?“ Wie wollen Sie ihm zeigen, dass keine Anordnung besser ist, ohne alle durchzuprobieren?
Das ist ein Anordnungsproblem: Die Kosten einer Anordnung sind der Verkehr zwischen zwei Bauteilen mal der Abstand ihrer Plätze, summiert über alle Paare. Jede gefundene Anordnung zeigt, was sich erreichen lässt. Eine Schranke ist das Gegenstück: eine Zahl, unter die keine Anordnung fallen kann. Die Leitfrage dieser Linie lautet: Wie dicht liegt die beste beweisbare Schranke am Besten, und was kostet es, sie zu bekommen?
Fünfzehn Stücke gehen dem nach, in drei Gruppen. Die erste rechnet kleine Aufgaben ganz durch und sucht dann Schranken, indem sie das Problem immer anders vereinfacht und das Ergebnis danach wieder auf eine echte Anordnung zurückführt. Die zweite lässt die Bauteile zunächst überall sitzen, verteilt sie Schritt für Schritt auf die Plätze und verbessert zuletzt durch Tauschen. Die dritte stellt alle Verfahren nebeneinander. Drei Stücke sind als optional gekennzeichnet. Wie sich eine Zahl beweisen lässt, unter die keine Anordnung fällt, erzählt die Erklärseite Die Schranke ohne Aufzählen, und wie zwei einzeln lösbare Entscheidungen zusammen hängen bleiben, die Seite Zuordnung und Reihenfolge, jeweils zuerst mit Bildern aus dem Alltag. Zur Tor-Zuordnung gibt es die Fall-Demo Tor-Zuordnung.
Was diese Linie ist und was nicht: Es sind Modelle mit gewählten Annahmen. Alle Befunde stammen von erfundenen Verbindungsmustern und erfundenen Anschlüssen, nicht von echten Platinen. Die meisten Messungen betreffen kleine Aufgaben, einzelne Stücke gehen bis 16 und bis 25 Bauteile. Sie sagen nichts darüber, welches Verfahren bei einem echten Fall am besten passt.
In short: Covers placing components on a board or in a hall: the quadratic assignment problem, lower bounds from assignment, eigenvalue, linear and semidefinite relaxations, branch and bound, analytical placement with legalization and detailed placement, and choosing a method by measurement.
Hintergrund zum Thema: Lagerlogistik.
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
Die Schranke ohne Aufzählen verständlich erklärt
Wie sich eine Untergrenze für die kürzesten Verbindungen beweisen lässt, ohne alle Anordnungen durchzurechnen, und warum sie unter dem Besten bleibt: erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln und Messwerten.
Zuordnung und Reihenfolge verständlich erklärt
Warum ein Bestückkopf mit zwei einzeln lösbaren Entscheidungen, Zuführplatz und Reihenfolge, beim abwechselnden Verbessern an einem Punkt stehen bleibt, der nicht der beste ist, und was eine vereinfachte Rechnung dagegen leistet: erst für Einsteiger ohne Formeln, dann für Fachleute mit Formeln und Messwerten.
Von der Aufzählung zur Verfahrenswahl: relaxieren, runden, verbessern
Die Wurzel ist das quadratische Zuordnungsproblem an einer Mini-Halle: Alle Anordnungen lassen sich zählen, und die Tauschlandschaft zeigt lokale Optima. Von dort fragt die Instanzstruktur, was Aufgaben schwer macht, und die Gilmore–Lawler-Schranke beweist zum ersten Mal etwas ohne Aufzählung. Auf ihr bauen drei Wege auf: die Linearisierung vergisst weniger, die Eigenwertschranke nutzt das Spektrum statt der Zuordnung, die doppeltstochastische Relaxation lockert die Menge statt der Zielfunktion. Die SDP-Schranke setzt die Leiter nach oben fort. Branch and Bound führt die Schranken im Suchbaum zusammen, und die Symmetrie im Baum spart dort gleichwertige Äste.
Ein zweiter Strang lockert die Orte: Die quadratische Platzierung lässt Bauteile an beliebigen Punkten sitzen, die Look-ahead-Legalisierung bindet die Rundung in einer Schleife zurück, die Dichtestrafe ersetzt die harte Rundung durch ein weiches Feld, die Detailplatzierung verbessert das Ergebnis durch Tauschen. Die Kopplung von Zuordnung und Reihenfolge greift die Zuordnungsrelaxation für eine zweite Entscheidung auf. Die Verfahrenswahl führt zuletzt die Wege zusammen und stellt Beweis, Platzierung und Tauschsuche nebeneinander.
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
Gestrichelt umrandet sind Demos aus anderen Linien: die Ungarische Methode aus dem Matching, Frank-Wolfe aus dem Netzwerkfluss, MaxCut als SDP aus der Konvexen Optimierung, Branch and Bound am Rucksack aus der Exakten Suche, Graphen zeichnen aus Planarität und Zeichnen, Simulated Annealing aus den Trajektorien-Metaheuristiken und Burnside und Pólya aus dem Abzählen. Doppelt umrandet sind Branch and Bound und die Verfahrenswahl, in denen mehrere Wege zusammenlaufen. Die Stücke SDP-Schranke, Symmetrie im Baum und Zuordnung und Reihenfolge sind optional.
Verwandt in anderen Linien
- Matching-Algorithmen — Die Ungarische Methode löst die lineare Zuordnung, die in dieser Linie als Baustein steckt: in der Gilmore–Lawler-Schranke, im Frank-Wolfe-Schritt der doppeltstochastischen Relaxation und in der Rundung der quadratischen Platzierung.
- Trajektorien-Metaheuristiken — Die Detailplatzierung wendet Tauschabstieg und Annealing nicht an einer Lieferroute an, sondern an einer Leiterplatte; das Simulated Annealing der Trajektorien-Metaheuristiken erklärt das Verfahren selbst. Eine gute Startlösung aus der Platzierung spart dort Bewertungen, doch gleich gute Ergebnisse aus Zufall brauchen mehrere Neustarts.
- Standortplanung — Die kapazitierte Standortplanung zeigt, wie viel der LP-Lücke eine Lagrange-Schranke schließt, wenn jeder Kunde genau einmal bedient wird. Hängen die Kosten dagegen an Paaren von Bauteilen (Fluss mal Abstand), liegt die Gilmore–Lawler-Schranke bei sechs und acht Bauteilen im Median 7 bis 9 Prozent unter dem Optimum.
- Planarität und Zeichnen — Die Graphen-Zeichnen-Demo ordnet Knoten mit Federmodell und Stress, damit ein Netz lesbar wird. Die quadratische Platzierung minimiert dagegen die Abstandsquadrate zwischen verbundenen Bauteilen als lineares Gleichungssystem, braucht feste Anschlüsse, damit nicht alles auf einen Punkt fällt, und rundet danach auf Plätze.
- Netzwerkfluss — Frank-Wolfe legt den Verkehr schrittweise auf die gerade schnellsten Wege und mischt ihn ein. Die doppeltstochastische Relaxation nutzt dasselbe Verfahren für Zuordnungsmatrizen, nur ist jeder Schritt hier eine lineare Zuordnung statt eines kürzesten Wegs.
- Konvexe und konische Optimierung — Die MaxCut-Relaxation als SDP projiziert auf den Kegel der positiv semidefiniten Matrizen; dieselbe Rechnung steckt in der SDP-Schranke dieser Linie, deren ADMM aber eine eigene, auf die große Matrix zugeschnittene Fassung ist und nicht der ADMM der Konvexen Optimierung.
- Abzählen und erzeugende Funktionen — Die Burnside-Demo zählt Objekte bis auf Symmetrie, die Isomorphieausschluss-Demo bricht Symmetrie im Suchen. Die Demo Symmetrie im Baum wendet beides auf einen Branch-and-Bound-Baum an: Spiegelungen und Drehungen des Rasters sparen höchstens die Größe der Platzgruppe.
- Exakte Suche — Der Suchbaum am Rucksack zeigt, wie Pruning mit starker und schwacher Schranke wirkt. Die Demo Branch and Bound mit Schranke setzt dasselbe Prinzip auf die Zuordnung von Bauteilen an und misst, welche Schranke an Knoten und Zeit lohnt.
- Tourenbildung: eine Reihenfolge, optimal zerlegt — Das Muster, die Regel vor der Messung festzulegen und Zeit gegen Abstand zum Besten zu legen, überträgt Tourenbildung: Verfahrenswahl auf Touren; dort ist die Referenz selbst nur ein Lauf von PyVRP.
QAP an einer Mini-Halle: Die ganze Tauschlandschaft
Verfolgen Sie, wie bei einer kleinen Platine alle Anordnungen der Bauteile aufgezählt werden, solange es höchstens neun sind: Die Kosten sind Fluss mal Abstand über alle Paare, und eine Tauschsuche bleibt in einem lokalen Optimum stehen, das nicht das beste sein muss. Im Standardfall mit acht Bauteilen findet ein Abstieg in 26,6 Prozent der Startanordnungen das Optimum. Der Haken: Das ist eine einzelne, nicht typische Instanz.
Demo starten →Instanzstruktur: Was macht Instanzen schwer?
Sehen Sie, wie dieselbe Aufgabe an sechs erfundenen Arten von Verbindungsmustern zwischen den Bauteilen abschneidet, etwa gleichmäßig verteilt oder in zwei Gruppen, und ob eine einfache Kennzahl der Flüsse die Schwierigkeit der Tauschsuche voraussagt. Die Familie erklärt etwa ein Fünftel der Streuung des Erfolgs. Der Haken: Die Rangfolge der Familien ändert sich zwischen sechs und acht Bauteilen, und die Kennzahlen sagen den Erfolg nicht stabil voraus.
Demo starten →Gilmore–Lawler: Eine Schranke ohne Aufzählung
Verfolgen Sie, wie sich ohne Aufzählung eine Zahl beweisen lässt, unter die keine Anordnung fallen kann: Jedes Bauteil wird für seinen Platz einzeln bewertet, als bräuchten die übrigen keine verschiedenen Plätze, und eine lineare Zuordnung liefert die Schranke. Bei sechs und acht Bauteilen liegt sie im Median 7 bis 9 Prozent unter dem Optimum. Der Haken: Scharf ist sie nur selten, und die gerundete Anordnung liegt weit darüber.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Eigenwertschranke: Das Spektrum als Schranke
Sehen Sie, wie sich statt einer Zuordnung die Eigenwerte der Fluss- und der Abstandsmatrix als Schranke nutzen lassen, ohne dass etwas aufgezählt wird. Die reine Eigenwertschranke liegt in allen 420 gerechneten Instanzen unter null und ist damit wertlos, erst die Projektion macht sie in einer vereinfachten Fassung nützlich. Der Haken: Ob sie Gilmore–Lawler schlägt, hängt von der Familie ab, keine Schranke gewinnt überall.
Demo starten →Linearisierung: Mehr Schranke, größeres Programm
Verfolgen Sie, wie jedes Produkt aus zwei Bauteil-Platz-Paaren eine eigene Variable bekommt und so ein lineares Programm die Schranke verstärkt: Bei acht Bauteilen liegt sie im Median nur 1,5 Prozent unter dem Optimum, gegen 9 Prozent bei Gilmore–Lawler. Der Haken: Das Programm wächst mit der vierten Potenz der Bauteilzahl, und ein einfaches Dual-Ascent-Verfahren holt meist nur einen Teil davon.
Demo starten →Doppeltstochastische Relaxation: Menge statt Zielfunktion
Sehen Sie, was passiert, wenn man nicht die Kosten, sondern die Menge der Anordnungen lockert: Statt einer festen Zuordnung ist jede Mischung erlaubt, danach wird zurückgerundet. Die einfache konvexe Fassung liefert nur eine grobe Schranke und trifft gerundet das Optimum bei sechs Bauteilen in 3 von 120 Instanzen. Der Haken: Die nichtkonvexe Fassung braucht viele Zufallsstarts, und ein einzelner Start gelingt seltener als ein Tauschabstieg, bei ungleichem Aufwand.
Demo starten →SDP-Schranke: Wie weit kommt die Matrix?
Optional: Sehen Sie, wie die Anordnung zu einer großen Matrix angehoben und die Bedingung Rang eins fallen gelassen wird. Mit zusätzlicher Nichtnegativität ist das im Median die stärkste Schranke der Leiter: bei acht Bauteilen 0,00 Prozent unter dem Optimum, wo Gilmore–Lawler 8,3 lässt. Der Haken: Ohne diese Bedingung liegt sie bei acht Bauteilen in 10 von 30 Instanzen unter Gilmore–Lawler, und das Runden der Lösung ist schwach.
Demo starten →Branch and Bound: Welche Schranke lohnt im Baum?
Verfolgen Sie, wie die Schranken in einem Suchbaum arbeiten, der Bauteil für Bauteil Plätze belegt und jeden Ast abschneidet, dessen Schranke nicht unter der besten bekannten Anordnung liegt. Im Standardfall mit acht Bauteilen hat der volle Baum 109 600 Knoten, mit der Gilmore–Lawler-Schranke werden nur 64 bewertet. Der Haken: Eine stärkere Wurzelschranke anderer Art heißt nicht weniger Knoten, und bei zwölf Bauteilen erreichen einzelne Bäume die Obergrenze.
Demo starten →Quadratische Platzierung: Reelle Orte statt Plätze
Sehen Sie, was geschieht, wenn Bauteile nicht auf Rasterplätzen, sondern an beliebigen Punkten sitzen dürfen: Die Summe der Abstandsquadrate ist ein lineares Gleichungssystem, und ohne feste Anschlüsse fallen alle Bauteile auf einen Punkt. Mit Anschlüssen rundet eine Zuordnung auf eine brauchbare Anordnung, im Median 6 bis 14 Prozent über dem Optimum gegen 26 bis 38 bei Zufall. Der Haken: Die Anschlüsse sind erfunden.
Demo starten →Look-ahead-Legalisierung: Runden in der Schleife
Verfolgen Sie, wie die Rundung auf Plätze in einer Schleife an die Platzierung zurückgebunden wird und die Lücke zwischen unterer Länge und oberen Kosten schrumpft. Der Haken: Das liegt vor allem am wachsenden Ankergewicht, die Anordnung ändert sich im Median in keiner Runde. Mit Umgewichtung wird sie bei zwei Anschlüssen in 42 von 120 Instanzen besser, die Lücke zum Optimum sinkt von 14,5 auf 10,8 Prozent.
Demo starten →Dichte und Drahtlänge: Weiche Strafe statt harter Rundung
Sehen Sie, ob eine weiche Strafe für zu dichte Stellen die harte Verteilung auf Plätze ersetzen kann: Die Bauteile wirken wie elektrische Ladungen, deren Feld sie auseinanderschiebt. Bei acht Bauteilen liegt die Lücke zum Optimum im Median bei 3,9 Prozent, ohne Strafe bei 7,7. Der Haken: Das Verfahren braucht rund 900 Auswertungen und zwei Hilfen, und bei sechzehn Bauteilen ist der Vorsprung vor einer lokalen Strafe nicht mehr zu erkennen.
Demo starten →Detailplatzierung: Die letzte Meile
Verfolgen Sie, wie ein Tauschabstieg und ein Annealing, das auch Verschlechterungen zulässt, eine gerundete Anordnung weiter verbessern. Bei acht Bauteilen bleibt nach dem Abstieg aus der Rundung im Median 0,0 Prozent Lücke, bei zwölf 1,9. Eine gute Startlösung spart Bewertungen, doch gleich gute Ergebnisse aus Zufall brauchen mehrere Neustarts. Der Haken: Das Annealing ist eine einfache Eigenfassung, die Anschlüsse sind erfunden.
Demo starten →Symmetrie im Baum: Gleiche Anordnungen nur einmal
Optional: Sehen Sie, wie sich Spiegelungen und Drehungen des Rasters im Suchbaum nutzen lassen: Gleichwertige Anordnungen werden nur einmal verfolgt, ohne dass in den Messungen das Optimum verloren geht. Der Baum schrumpft dabei höchstens um die Größe der Platzgruppe, bei Rechtecken um 4, beim Quadrat um 8. Der Haken: Die Flüsse der sechs Familien haben fast nie Symmetrie, große Gewinne zeigen nur erfundene symmetrische Flüsse.
Demo starten →Zuordnung und Reihenfolge: Beides gekoppelt
Optional: Verfolgen Sie, wie ein Bestückkopf entscheidet, welcher Bauteiltyp an welchen Zuführplatz kommt und in welcher Reihenfolge er anfährt. Wechselweises Optimieren bleibt aus der Maschinenpraxis in 176 von 240 erfundenen Instanzen an einem Fixpunkt über dem Optimum hängen; die gerundete Schwerpunkt-Zuordnung ist in 239 von ihnen optimal. Der Haken: Die untere Schranke ist schwach, und die Maschinenpraxis ist nur eine Stand-in-Regel.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Verfahrenswahl beim Anordnen: Welches Verfahren wann
Verfolgen Sie, wie sich die Verfahren der Reihe an denselben Instanzen vergleichen lassen: Finden heißt, eine gute Anordnung zu liefern, Beweisen, dass keine bessere existiert. Bis zwölf Bauteile schlagen 20 Neustarts des Tauschabstiegs jede Relaxation deutlich; ab 25 ist die Schleife mit Annealing im Mittel etwas besser. Der Haken: Die Kreuzung gehört zu dieser Python-Fassung und liegt zwischen 20 und 25 Bauteilen.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle fünfzehn Stücke: Er fragt danach, ob eine Schranke oder eine Lösung gebraucht wird, wie viele Bauteile es sind und wie knapp die Zeit ist, nicht nach dem Verfahren.
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 Grenzen bei zwölf, sechzehn und zwanzig Bauteilen sind die der gemessenen Größen an erfundenen Familien und gelten für diese Python-Fassung; die Kreuzung der Zeit liegt zwischen zwanzig und fünfundzwanzig Bauteilen. Wo mehrere Stücke passen, hilft die Verfahrenswahl.
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.
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.
Ressourcenwege und Spaltenerzeugung
Wie findet man unter unüberschaubar vielen möglichen Touren die mit dem größten Nutzen, wenn jede Zeit- und Lastgrenzen einhalten muss? Dreizehn Demos vom Weg mit Grenze bis zur Wahl des Verfahrens.
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.