Elevator-Dispatch-Algorithmus

• Der Betrieb von Aufzügen ist nicht nur eine einfache Reaktion auf Rufe, sondern ein Optimierungsproblem der Disposition, bei dem die Anzahl der Kabinen, der Fahrgastfluss, die Auslastung und die Fahrtrichtung gemeinsam berücksichtigt werden
• SCAN für eine einzelne Kabine wechselt die Richtung erst am obersten Stockwerk, während LOOK am höchsten tatsächlich angeforderten Stockwerk umkehrt und damit den üblichen Erwartungen an den Aufzugsbetrieb näherkommt
• RSR (Relative System Response) für mehrere Kabinen bewertet unter anderem die voraussichtliche Ankunftszeit und die Auslastung, optimiert die Disposition alle 5 Sekunden neu und kann Fahrgäste einer verspäteten Kabine auf eine andere umverteilen
• Wenn Kabinen dauerhaft voll sind oder wegen hohen Fahrgastaufkommens und zu weniger Kabinen an jedem Stockwerk halten müssen, kann das einfache LOOK besser sein als das komplexere RSR
• Destination Dispatch, bei dem das Zielstockwerk vorab eingegeben wird, liefert zwar mehr Informationen, macht einen Wechsel der zugewiesenen Kabine aber schwierig; außer in einigen Fällen wie sehr hohen Gebäuden oder Gruppen mit 8 oder mehr Kabinen sind die Wartezeiten daher meist länger als bei herkömmlichen Auf- und Ab-Tasten

---

Wo wechselt eine einzelne Kabine die Richtung?

• Das 1961 patentierte SCAN startet in der Lobby, fährt bis zum obersten Stockwerk und wechselt dann die Richtung nach unten, wobei Fahrgäste entlang des Fahrwegs aufgenommen und abgesetzt werden
• LOOK fährt nicht zwangsläufig bis ganz nach oben, sondern nur bis zum höchsten angeforderten Stockwerk und kehrt dann um
• Die Aufzugsfahrweise, die die meisten Menschen kennen und erwarten, liegt im Allgemeinen näher bei LOOK

Grundlegende Disposition mehrerer Kabinen

• Gibt es mehrere Aufzüge, muss koordiniert werden, welche Kabine welchen Ruf übernimmt
• In Grundsystemen weist ein zentraler Scheduler jeder Kabine ihre Haltestellen zu und ordnet neue Rufe der nächstgelegenen Kabine zu
• Eine reine Distanz-basierte Disposition kann jedoch Situationen wie eine bereits volle nahe Kabine nur unzureichend berücksichtigen

Wie Wartezeiten bewertet werden

• Die naheliegendste Kennzahl zur Bewertung von Aufzugsalgorithmen ist die Wartezeit vom Ruf bis zur Ankunft der Kabine
• Einfach gemessen werden kann etwa der Anteil der Fälle, in denen eine Kabine innerhalb von 30 oder 90 Sekunden ankommt
• Für eine strengere Bewertung werden die Wartezeiten aus Tausenden Fahrten gesammelt und als Verteilung und Histogramm betrachtet
  • Bedeutet p90 = 2 Minuten, dass 90 % der Fahrgäste höchstens 2 Minuten gewartet haben
  • Bedeutet p50 = 1 Minute, dass in der Hälfte aller Rufe die Kabine innerhalb von 1 Minute ankam
• Fahrgäste erinnern sich tendenziell stärker an p90-Fälle, in denen sie ungewöhnlich lange warten mussten, als an die durchschnittliche Wartezeit

Je nach Tageszeit unterschiedlicher Fahrgastfluss

• In großen Bürogebäuden besteht der Verkehr am Morgen überwiegend aus Fahrten von der Lobby in die oberen Stockwerke
• Am Abend dominiert durch den Feierabendverkehr der Strom von oben nach unten
• Zur Mittagszeit mischen sich Auf- und Abwärtsfahrten, und in der übrigen Zeit gibt es viele Fahrten zwischen Stockwerken
• Die Verteilung der Wartezeiten variiert stark mit Tageszeit und Verkehrsmuster; insbesondere die Statistiken für den morgendlichen Berufsverkehr fallen schlecht aus

Welche Kabine wählt RSR?

• Das RSR (Relative System Response) von Otis bewertet, wie geeignet jede Kabine für die Aufnahme eines Fahrgasts ist; je niedriger der Score, desto geeigneter
• Der Einsteige-Score wird aus mehreren Faktoren berechnet
  • Voraussichtliche Ankunftszeit bis zum gerufenen Stockwerk
  • Auslastungsstrafe abhängig von der Zahl der bereits beförderten Fahrgäste
  • Anti-Cluster-Strafe, wenn bereits eine Kabine in dieselbe Richtung zum selben Stockwerk unterwegs ist
  • Bonus bei übereinstimmender Fahrtrichtung
  • Bonus für eine inaktive Kabine innerhalb von zwei Stockwerken vom gerufenen Stockwerk
  • Bonus bei niedriger Auslastung
• Anti-Bunching unterdrückt zusätzliche Zuweisungen, wenn bereits eine andere Kabine in dieselbe Richtung zum selben Stockwerk fährt
• RSR optimiert die gesamte Disposition alle 5 Sekunden neu
  • Wenn Kabine A sich verspätet, können Fahrgäste, die ursprünglich von A aufgenommen werden sollten, Kabine B neu zugewiesen werden
  • Diese kontinuierliche Re-Optimierung ist der Schlüssel für einen reibungslosen Fahrgastfluss

Leistungsunterschiede zwischen LOOK und RSR

• Mit Analysewerkzeugen für Wartezeiten lassen sich die Anteile der Ankünfte innerhalb von 30 bzw. 90 Sekunden bei LOOK und RSR vergleichen
• Mit steigendem Fahrgastaufkommen überholt LOOK RSR
  • Wenn Kabinen ständig voll sind und an jedem Stockwerk halten, nimmt der Nutzen der zusätzlichen Regeln von RSR ab
• Auch in kleineren Gebäuden mit wenigen Aufzügen pro Gruppe ist LOOK oft besser als RSR, sodass ein einfacherer Ansatz passender sein kann
• Neben der Wartezeit lässt sich auch die Fahrzeit vom Einstieg bis zum Zielstockwerk messen
  • LOOK und RSR zeigen auch bei dieser Kennzahl unterschiedliche Eigenschaften, auf einen genauen Vergleich wird hier aber nicht eingegangen

Warum Destination Dispatch trotz mehr Informationen im Nachteil ist

• Destination Dispatch bedeutet, dass das Zielstockwerk zuerst an einem Kiosk auf jeder Etage eingegeben wird und dadurch der zu benutzende Aufzug festgelegt wird
• Das Optimierungssystem kennt damit schon vor Ankunft der Kabine alle Zielstockwerke der Fahrgäste, dennoch sind die Wartezeiten im Allgemeinen länger als beim herkömmlichen System mit Auf- und Ab-Tasten
• Es gibt Ausnahmen, in denen das Kiosk-System vorteilhaft ist, etwa in sehr hohen Gebäuden mit 8 oder mehr Aufzügen pro Gruppe
• Der Hauptgrund für die schlechtere Leistung ist die Unflexibilität der Disposition
  • Im herkömmlichen System können Fahrwege der Kabinen und Fahrgastzuweisungen alle 5 Sekunden neu optimiert werden
  • Beim Destination Dispatch müssen Fahrgäste die ihnen anfangs zugewiesene Kabine nehmen
  • Auch wenn sich die Betriebslage 30 Sekunden nach dem Ruf ändert, lässt sich die zugewiesene Kabine nicht flexibel wechseln
• Der Nachteil des Verlusts an Flexibilität bei der Umverteilung wiegt stärker als der Vorteil der zusätzlichen Information über das Ziel

Stellschrauben und Grenzen der Simulation

• In der Gesamtsimulation lassen sich Stockwerkszahl, Anzahl der Kabinen und Fahrgastaufkommen pro Minute variieren; betrachtet wird dabei der Anteil der Ankünfte innerhalb von 30 bzw. 90 Sekunden
• Reale Aufzugsalgorithmen berücksichtigen noch viele weitere Faktoren; der hier behandelte Bereich ist nur ein Teil des Gesamtfelds
• Eingaben über die Ruftasten werden zwar übermittelt, doch da der Aufzug mehrere Betriebsbedingungen gleichzeitig berechnet, kommt er möglicherweise nicht sofort an

[GN⁺]

Hacker-News-Meinungen

• Über ungefähr die Hälfte des vergangenen halben Jahrhunderts wurden Aufzüge ohne Computer nur mit Relais gesteuert; auch solche Algorithmen waren als fest verdrahtete Logikschaltungen umgesetzt.
  Interessante Details wie Schaltpläne findet man in alten Patenten von Otis.

• Im Informatikunterricht in der Highschool habe ich als persönliches Projekt mehrere Simulationen von Aufzug-Algorithmen implementiert.
  Rotierende Festplatten ähneln einem sehr langen Aufzug, der sich statt vertikal um die Spindel wickelt; SCAN ist tatsächlich ein Algorithmus für Disk Scheduling: https://en.wikipedia.org/wiki/Elevator_algorithm

  • An der Uni haben wir ein ähnliches Projekt mit Mikrocontrollern und LEDs gemacht; das hat großen Spaß gemacht.

• Ich frage mich, ob das Ergebnis, dass Zielwahlsteuerung insgesamt schlecht sei, daher kommt, dass die Zielgeschosse zufällig gesetzt wurden.
  In realen Gebäuden fahren die meisten Menschen, die nicht im Erdgeschoss sind, ins Erdgeschoss; und im Erdgeschoss neigen Menschen, die auf derselben Etage arbeiten, dazu, zur Mittagspause gemeinsam hinauszugehen und gemeinsam auf dieselbe Etage zurückzukehren. Zielwahlsteuerung kann große Gruppen mit demselben Ziel zusammenfassen und ist für solche Muster vorteilhaft.

  • Für Hotels ist das eine noch weniger passende Annahme. Morgens bewegt man sich nicht nur von der Lobby zu den Zimmern, sondern fährt zum Frühstück hinunter, wieder hinauf und erneut hinunter, es entsteht also Verkehr in beide Richtungen.
    Manche Hotels passen bei kioskartigen Systemen je nach Frühstücksandrang sogar die Benutzeroberfläche an.
  • Auch Kreuzfahrtschiffe mit Zielwahlsteuerung waren deutlich angenehmer. Auf Schiffen mit älteren Algorithmen ist das Warten zu Stoßzeiten schmerzhaft, aber immerhin führt es dazu, dass man mehr Treppen benutzt.
  • Eine einzelne Person in einem oberen Stockwerk fährt viel wahrscheinlicher ins Erdgeschoss zurück als ein oder zwei Etagen nach oben oder unten, aber die wartenden Fahrgäste in der Simulation scheinen das nicht richtig abzubilden.
    Auch Clustering-Effekte von Menschen, die zum Mittagessen gehen oder zurückkommen, gibt es tatsächlich; sie sind mittags deutlicher als morgens oder abends.
  • Dass sich im Erdgeschoss große Gruppen mit demselben Ziel bewegen, halte ich für einen der wichtigsten Gründe, warum Zielwahlsteuerung besser ist.
    Es gibt auch Artikel darüber, dass sich nach der Umstellung von Büros oder Hotels auf dieses Verfahren die Wartezeiten stark verkürzt haben.
  • Ich frage mich, ob das daran liegt, dass als Bewertungsmaßstab die Wartezeit und nicht die Fahrzeit verwendet wurde. Zielwahlsteuerung reduziert unnötige Zwischenstopps während der Fahrt.
    Auch ein kürzlich besuchter Neubau nutzte dieses System. Mein Mitbewohner aus Studienzeiten, der Elektrotechnik studierte, baute eine Aufzugschaltung auf einem Breadboard mit Ruftastern, Motor und einer transparenten Scheibe mit schwarzen Quadraten zur Positionserkennung; es war vermutlich ein einfacher Algorithmus.

• Wer neu in das Thema Aufzug-Scheduling einsteigt, dem empfehle ich dieses Spiel: https://play.elevatorsaga.com/

  • Die Prämisse ist einfach, aber mit steigenden Levels wird es befriedigend schwierig, und durch ein wenig zufällige Ausfälle wird es noch herausfordernder. Ich wünschte, es gäbe mehr solcher Spiele.
  • Es wirkt sehr gut gemacht, aber ich mag trotzdem https://en.wikipedia.org/wiki/Elevator_Action lieber.
  • Großartig, aber für mich ist SimTower das beste Aufzug-Scheduling-Spiel.
  • Jedes Mal, wenn ich in einem Konferenzhotel auf den Aufzug warte, suche ich dieses Spiel wieder heraus.
  • Ich habe mich immer gefragt, ob ein Spiel, in dem man einen Aufzug-Scheduler selbst programmiert, Spaß machen würde, und dachte, niemand hätte so etwas gebaut; ich freue mich, dass ich falschlag.

• Bei der Entwicklung des Aufzugsteuerungs- und Automatisierungsspiels Sky Lobby für iOS und Android habe ich viel über dieses Problem nachgedacht.
  Wir haben einen LOOK-ähnlichen Algorithmus gewählt, der den Bewegungen am nächsten kommt, die Spieler erwarten; wenn die Auswahl uneindeutig war, priorisierten wir die Etage, die schon lange wartet, um den im Spiel wichtigen p90-Wert zu verbessern. Fügt man jedoch doppelstöckige Aufzüge hinzu, die zwei Etagen gleichzeitig bedienen, Umsteigeetagen zwischen Schächten und Expressschächte, wird deutlich unklarer, welcher Algorithmus optimal oder am intuitivsten ist. Da es ein Spiel und kein reales System war, fanden wir eine ausreichend gute Heuristik und ermöglichten den Spielern, den Fahrplan manuell zu überschreiben, wenn er ihnen nicht gefiel; damit waren die meisten zufrieden.

• Jedes Mal, wenn ich auf einen Aufzug warte, denke ich daran, wie knifflig es sein muss, einen Algorithmus zu entwickeln, der die Wartezeit bis zum Einsteigen und bis zum Erreichen des Ziels minimiert.
  Manchmal frage ich mich sogar, ob die Leute, die das implementiert haben, absichtlich sadistische Bösewichte sind, die einen länger warten lassen.

  • Es wäre gut, wenn der Aufzug auch die Fahrgastlast berücksichtigen würde.
    Am Morgen nach einer großen Konferenz wollten alle nach unten, aber ein voller Aufzug hielt pflichtbewusst auf jeder Etage. Wenn ein Aufzug für 10 Personen bereits Fahrgäste von 10 gerufenen Etagen aufgenommen hat, sollte er direkt ins Erdgeschoss fahren und 5 Minuten sparen können, statt auf jeder Etage „Kein Platz, ich nehme den nächsten“ zu wiederholen. Besonders wenn eine mobilitätseingeschränkte Person im 2. Stock ein Flugzeug erreichen muss, wird das zu einem ernsten Problem.
  • Ich habe mehrfach externe Integrationssoftware entwickelt, die andere Geräte mit Aufzügen verbindet.
    Wenn man die Positionen und Bewegungen aller Aufzüge sieht, ist der Fahrplan erstaunlich dicht. In der Lobby fühlt sich das Warten endlos an, aber aus Dispositionssicht ist ununterbrochen Aktivität vorhanden, und während der Nutzungszeiten des Gebäudes stehen die Aufzüge fast nie untätig herum. Schon das Beobachten des Statuspanels ist interessant. Außerdem bedeutet es, wenn ein Aufzugstechniker sagt „Treffen wir uns früh morgens“, meist etwa 4 Uhr morgens; sie wollen fertig sein, bevor die Leute zur Arbeit kommen.
  • Nicht weil Aufzug-Scheduling-Software träge wäre, sondern weil darin bereits enorm viel Überlegung steckt.
    Aufzüge sind teuer, und Gebäudeeigentümer investieren nicht impulsiv zu viel; daher wird normalerweise nur die Mindestzahl an Aufzügen installiert, die die erwartete Nachfrage bewältigt, manchmal sogar weniger.
  • Neben Wartezeiten könnten auch Zielfunktionen wie Verschleiß und Energieverbrauch optimiert werden.

• Über vier Aufzügen werden jeweils die geplanten Halteetagen angezeigt, und während man wartet, ändert sich die Zuordnung von Aufzug und Etage; darüber wird man per Ton informiert. Das wirkt wie eine Funktion, die optimale Disposition ermöglichen soll.

• Das größte Problem bei Aufzügen sind weniger die Algorithmen als Menschen, die das Konzept nicht verstehen, je nach gewünschter Fahrtrichtung den Hoch- oder Runter-Knopf zu drücken.
  Wenn sie „damit er schneller kommt“ beide Knöpfe drücken, fahren sie in der Hälfte der Fälle zuerst in die falsche Richtung und fügen den bereits eingestiegenen Leuten zusätzliche unnötige Stopps hinzu.

  • Ich glaube nicht, dass ich je jemanden gesehen habe, der das tatsächlich macht.
  • In solchen Situationen kommt man oft zur Antwort, wenn man nicht annimmt, dass die Leute es nicht verstehen, sondern rückwärts überlegt, warum es rational sein könnte, falls sie es verstehen.
    Es ähnelt vermutlich der Psychologie einer Fake-Ladeanzeige. Ohne bekannte Ankunftszeit zu warten ist langweilig und frustrierend, aber wenn man in einem Aufzug sitzt, der sich bewegt, selbst in die falsche Richtung, fühlt es sich nach Fortschritt an. Auch wenn es am Ende länger dauert, ist ein Zustand, in dem etwas passiert, weniger frustrierend.
  • Wenn sich die Tür öffnet, fragen manche die Leute drinnen auch, ob er nach oben oder unten fährt. Direkt davor wird ein Richtungspfeil angezeigt.
  • Wenn man von einer unteren Etage nach unten will und gerade Auscheck-Stoßzeit ist, können die abwärts fahrenden Aufzüge ständig voll sein.
    Wenn es dagegen wenig Nachfrage nach oben gibt, kann es eine rationale Strategie sein, zuerst nach oben einzusteigen und die komplette Runde mitzufahren, statt zu warten und zu hoffen, dass irgendwann Platz frei wird.
  • In stark ausgelasteten Gebäuden zu Stoßzeiten reicht die Aufzugkapazität oft nicht aus; wenn man ins Erdgeschoss will, kann es im schlimmsten Fall bessere Ergebnisse bringen oder im Durchschnitt schneller sein, zuerst hoch- und dann wieder herunterzufahren.
    Dann ist das Drücken beider Hoch-/Runter-Knöpfe nicht dumm, sondern logisch.

• Unabhängig von der Leistungsfähigkeit des Algorithmus ist auch die Psychologie der wahrgenommenen Wartezeit wichtig.
  Wenn man untätig wartet, ist das sehr ärgerlich; wenn man in derselben Zeit etwas tut, fühlt es sich nach Fortschritt an und die Unzufriedenheit sinkt. Auch an Flughäfen gibt es das Beispiel, dass Passagiere zufriedener waren, als man absichtlich einen längeren, indirekten Weg schuf, statt sie direkt vom Gate zum Gepäckband gehen und dort bis zum ersten Koffer warten zu lassen, obwohl die Gesamtdauer gleich blieb.

• Bei verschiedenen Aufzug-Algorithmen werden der gesamte Verschleiß und die Wartungskosten oft nicht diskutiert.
  Mehr Bewegung kann dazu führen, dass Hydrauliköl früher gewechselt werden muss und Teile schneller ausfallen. Effiziente Algorithmen positionieren Aufzüge je nach Tageszeit oder Position anderer Kabinen auch vorab um; wenn beispielsweise ein Aufzug herunterkommt, kann man einen anderen nach oben schicken. Algorithmen auf Basis von Bedarfssignalen minimieren solche Bewegungen. Wichtig ist ein Gleichgewicht, bei dem man Wartung reduziert, auch wenn die Wartezeit steigt; der Gebäudeeigentümer, der die Kosten trägt, misst den Wartezeiten der Fahrgäste möglicherweise nicht denselben Stellenwert bei.

  • Während der Wartung muss ein Aufzug außer Betrieb genommen werden, wodurch auch die durchschnittliche Wartezeit in diesem Zeitraum steigt.