Online-Algorithmen und Wettbewerbsanalyse erklärt
Ein Betrieb entscheidet laufend, bevor er weiß, was kommt: ob er einen Stapler mietet oder kauft, welcher Artikel den Schnellzugriffsplatz räumt, in welchen Container ein Frachtstück kommt, welche Buchung er annimmt, welches Servicefahrzeug zu einem Einsatz fährt. Diese Linie misst solche Entscheidungen mit der Wettbewerbsanalyse: Sie vergleicht die Regel ohne Kenntnis der Zukunft mit dem, was man bei Kenntnis der ganzen Folge getan hätte, und fragt nach dem schlechtesten Verhältnis über alle Folgen.
Die sieben Stücke haben eine Wurzel, drei Äste und einen Zusammenfluss. Eine Garantie gilt gegen einen Gegner, der die Folge gegen die Regel baut; der Betrieb ist aber meist kein Gegner. Jede Demo misst deshalb beides, die Garantie und den typischen Fall, und das Schlussstück fragt, wie weit man einer Vorhersage folgen darf. Alle Ergebnisse sind Befunde an erfundenen Folgen, keine Aussagen über echte Aufträge, Lager oder Fracht.
In short: Interactive demos on online algorithms and competitive analysis: making decisions before the input is known and comparing them with the offline optimum. They cover ski rental, paging, online bin packing, online allocation with prices, the secretary problem, k-server and algorithms with predictions.
Hintergrund zum Thema: Luftfracht · 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
Ski-Rental verständlich erklärt
Warum man einen Stapler oder eine Lagerfläche mieten sollte, bis die Miete den Kaufpreis erreicht, was das im schlimmsten Fall kostet und was ein ausgeloster Kaufzeitpunkt verbessert: erst für Einsteiger ohne Formeln, dann für Fachleute mit Modell, Formeln und Messwerten.
Die sieben Stücke im Überblick
Die Wurzel ist Ski-Rental: Mieten oder Kaufen führt an einer einzigen Anschaffung das Wettbewerbsverhältnis, den Gegner und die Zufallsregel ein. Von dort führen drei Äste. Paging macht aus der Anschaffung viele gleichzeitige Entscheidungen, wer im Speicher bleibt, und führt zum k-Server-Problem, in dem die Wege verschieden lang sind. Online-Packen legt Stücke in Behälter mit begrenztem Platz. Online-Allokation nimmt Buchungen mit Preisen für knappen Platz an und führt zum Sekretärproblem, in dem nur eine einzige Wahl bleibt und die Frage lautet, was man über die Angebote weiß.
Zusammenfluss ist das Schlussstück Vorhersagen: Es nimmt Ski-Rental und Paging und fragt, wie weit man einer Vorhersage trauen darf, wenn die Garantie bis dahin gegen einen Gegner gemessen wurde. Die grauen Bausteine kommen aus anderen Linien: Online-Matching ordnet Aufträge Fahrzeugen zu, LPT sortiert vor dem Planen, die rollierende Planung nimmt einen bekannten Prozess an, und die Prognoseintervalle sagen, wie verlässlich eine Vorhersage ist.
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 beheben eine Schwäche des Vorgängers, gestrichelte Doppelpfeile sind Kontraste (gleiche Aufgabe, andere Bauweise), gepunktete Pfeile übernehmen nur eine Idee, hervorgehobene Knoten sind Zusammenflüsse, 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
- Matching-Algorithmen — Die Online-Matching-Demo ordnet nacheinander eintreffende Aufträge sofort und unwiderruflich Fahrzeugen zu und misst gegen die Ungarische Methode; bei 20 Fahrzeugen und 20 Aufträgen findet Greedy 89,0 % der möglichen Paare. Im k-Server-Problem dieser Linie bleibt das Fahrzeug dagegen am Einsatzort stehen und steht für den nächsten Einsatz bereit, im statischen Matching fährt es höchstens einen Auftrag.
- Optimierung unter Unsicherheit — Die Rolling-Horizon-Demo plant einen Artikel über zwölf Perioden immer wieder neu, mit einem bekannten Zufallsprozess der Nachfrage und ohne Gegner; die Vorhersagen dieser Linie nehmen dagegen eine Vorhersage von unbekannter Güte und fragen, wie weit man ihr folgen darf, ohne die Garantie für den schlimmsten Fall zu verlieren.
- Klassische Scheduling-Theorie — Die LPT-Demo stellt dem Sortieren nach Länge eine beliebige und eine zufällige Reihenfolge gegenüber: Bei 20 Aufträgen auf 3 Maschinen liegt die größte Maschinenlast ohne Sortierung 5,9 % über der von LPT. Beim Online-Packen dieser Linie kostet die Reihenfolge allein noch mehr: Dieselben 1800 Stücke brauchen aufsteigend das 1,667-Fache des Optimums, gemischt das 1,017-Fache.
- Spieltheorie — Die No-Regret-Demo lässt Lkw aus Erfahrung ein Tor wählen und misst, wie viel Wartezeit im Rückblick gegenüber dem besten festen Tor verloren ging; die Ski-Rental-Demo dieser Linie misst dagegen den Quotienten zu dem, was man mit Kenntnis der ganzen Folge gezahlt hätte.
- Reinforcement Learning — Die Bandit-Demo lernt durch wiederholtes Ausprobieren, welche von zehn Ladestationen die beste ist, und misst den entgangenen Ertrag gegen die beste feste Station. Die Demos dieser Linie lernen nicht, sondern messen feste Regeln am Optimum mit Vorwissen; die Vorhersagen spielen eine Vorhersage mit gesetzter Fehlerquote ein, statt sie zu lernen.
- Zeitreihen-Prognose — Die Prognoseintervall-Demo prüft, ob ein Intervall mit der Nennabdeckung 80 % wirklich vier von fünf Ist-Werten enthält; die Vorhersagen dieser Linie zeigen, dass das beste Vertrauen in eine Vorhersage die Fehlerquote voraussetzt, die man in der Praxis erst schätzen muss.
- Warteschlangentheorie und Simulation — Die Erlang-B-Demo rechnet für ein Gate mit begrenztem Platz aus, wie viele Lkw abgewiesen werden, wenn sie zufällig mit bekannter Rate ankommen; die Online-Allokation dieser Linie lehnt Buchungen auf knappem Platz ab und prüft Regeln, die die Verteilung der Anfragen nicht voraussetzen.
- Regeln setzen, verhandeln, kontrollieren — Die Einzelgut-Auktion legt bei bekannten Verteilungen der Werte ein Mindestgebot fest, das bei Gleichverteilung auf 0 bis 100 Euro und Eigenwert 0 bei 50 Euro liegt; das Sekretärproblem dieser Linie wählt bei bekannten Verteilungen ebenfalls über eine einzige Schwelle, die die Hälfte dessen sichert, was ein Prophet erreichen würde.
- Marktmechanismen: Preise, Auktionen und Handelsregeln — Die Online-Allokation nimmt Buchungen an, wenn ihr Wert die Schattenpreise des knappen Platzes übersteigt, und fragt, was ohne diese Preise bleibt; der Fisher-Markt dieser Linie berechnet solche Preise für knappe Slots aus Budgets und Nutzen.
Ski-Rental: mieten oder kaufen, ohne die Dauer zu kennen
Verfolgen Sie, wie ein Betrieb entscheidet, ob er einen Stapler mietet oder kauft, ohne zu wissen, wie lange der Auftrag dauert. Die Regel „mieten, bis die Miete den Kaufpreis erreicht, dann kaufen“ kostet im schlimmsten Fall bei einem Kaufpreis von 20 Tagesmieten das 1,95-Fache des Optimums mit Vorwissen. Der Haken: Bei gleichverteilten langen Aufträgen von im Mittel 80 Tagen liegt sie ganz ohne Gegner bei 1,890, kaum darunter.
Verständlich erklärt: erst für Einsteiger, dann für Fachleute
Demo starten →Paging: wer muss weichen, wenn der Platz knapp ist?
Sehen Sie, wie ein Vorwärtslager mit wenigen Schnellzugriffsplätzen entscheidet, welcher Artikel für einen neuen weichen muss: der am längsten ungenutzte, der am längsten gelagerte oder der am seltensten gefragte. Fragt eine Folge reihum einen Artikel mehr an, als Plätze da sind, fehlt bei allen dreien jeder Zugriff; ein Zufallsverfahren bleibt dagegen weit unter dem Faktor der Platzzahl. Der Haken: Die Häufigkeitsregel hält bei wechselndem Sortiment alte Renner fest.
Demo starten →Online-Packen: Frachtstücke ans Tor, ohne die späteren zu kennen
Verfolgen Sie, wie Frachtstücke nacheinander ans Tor kommen und jedes sofort und endgültig in einen Container gelegt wird. Bei gleichverteilten Größen und 1000 Stücken liegt First Fit im Mittel nur beim 1,041-Fachen einer vorab sortierten Packung, Next Fit beim 1,318-Fachen. Der Haken: Eine gegen die Regeln gebaute Folge mit 600 Stücken je Größe treibt alle vier Regeln auf das 1,667-Fache des Optimums.
Demo starten →Online-Allokation: Buchungen mit Preisen statt mit Glück annehmen
Sehen Sie, wie Buchungen für Laderaum auf vier Teilstrecken sofort angenommen oder abgelehnt werden und wie Preise für den knappen Platz entscheiden. Bei zufälliger Reihenfolge, 1000 Buchungen und Platz für 0,3 der Nachfrage erreicht ein Verfahren, das die Preise aus dem Gesehenen lernt, im Mittel 0,871 des Optimums, „wer zuerst kommt“ 0,640. Der Haken: Kommen die wertvollsten Buchungen zuerst, nimmt das Lernverfahren hier nichts mehr an (0,000).
Demo starten →Sekretärproblem und Prophet: Angebote einholen, ohne zurück zu können
Verfolgen Sie, wie man aus nacheinander eintreffenden Angeboten genau eines wählt, das sofort genommen oder für immer verworfen wird. Wer die ersten 37 von 100 Angeboten nur ansieht und dann das erste nimmt, das besser ist als alle bisherigen, findet bei zufälliger Reihenfolge in 37,1 % der Fälle das beste. Der Haken: Ist die Folge aufsteigend sortiert, wählt dieselbe Regel in 0,0 % der Fälle das beste.
Demo starten →k-Server: wer fährt hin, wenn ein Einsatz kommt?
Sehen Sie, wie auf einer Autobahn Servicefahrzeuge zu Einsätzen geschickt werden, die man vorher nicht kennt; das hingefahrene Fahrzeug bleibt dort stehen. Das nächste Fahrzeug zu schicken kostet bei 1000 Einsätzen an zwei abwechselnd angefragten Orten 2003 statt 10, Double Coverage (zwei Fahrzeuge fahren zugleich hin) bleibt beim Quotienten 1,00. Der Haken: Gleichverteilt und mit drei Fahrzeugen kostet Double Coverage im Mittel gut 60 % mehr als Greedy.
Demo starten →Vorhersagen: wie viel darf man einer Vorhersage trauen?
Verfolgen Sie, wie weit man beim Mieten oder Kaufen einer Vorhersage folgen darf: Ein Regler λ gewichtet sie in der Kaufregel. Bei einem Kaufpreis von 20 Tagesmieten kostet λ = 0,10 bei richtiger Vorhersage höchstens das 1,05-Fache des Optimums, bei falscher Vorhersage aber ein Vielfaches davon. Der Haken: Beim Paging mit Arbeitsmengen (k = 10) ist die ungeschützte Vorhersage ab 25 % falschen Vorhersagen klar schlechter als LRU.
Demo starten →Welches Stück passt zu meiner Frage?
Ein Entscheidungsbaum über alle sieben Stücke, entlang der Frage, was ohne Kenntnis der Zukunft entschieden werden muss: eine einzelne Entscheidung, die Vergabe von knappem Platz oder der Umgang mit einer Vorhersage.
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).
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.
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.
Warteschlangentheorie und Simulation
Ein Terminal-Gate, dreizehn Stücke und ein Zusatzstück: jedes hebt genau eine Annahme der Formel davor auf, bis zum Netz aus Gate, Kran und Stapel und seinem Ersatzmodell.
Mittelwerte und Lagemaße
Welche Zahl steht für die Mitte der Daten, wie genau rechnet man sie, und was geschieht bei Ausreißern, Quotienten, Uhrzeiten und Standorten in der Ebene? Sieben Stücke vom Mittelwert bis zur Mitte im Raum.
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.
Mehrkriterien-Ranking
Eine neutrale Entscheidungsmatrix, fünfzehn Stücke: von der Pareto-Dominanz über Gewichte, AHP, TOPSIS und Outranking bis zu unsicheren Gewichten, DEA, Gruppen und dem Verfahrensvergleich.
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.
Abzählen und erzeugende Funktionen
Wie viele Möglichkeiten gibt es, wie schnell wachsen sie, und wann lohnt sich welches Zählverfahren? Sechzehn Stücke von der Rekursion über erzeugende Funktionen und Symmetrie bis zum Entscheidungsdiagramm und zur Verfahrenswahl.