Sie drücken die Aufzugstaste und beobachten, wie die Stockwerksanzeige langsam Zahl für Zahl springt. Wahrscheinlich halten Sie das für Pech – in Wirklichkeit blicken Sie auf ein mathematisches Optimierungsproblem, das seit mehr als einem Jahrhundert erforscht wird.
Gestern (1. August) erreichte eine interaktive Erklärung von Aufzugsalgorithmen des Webentwicklers John Allsopp Platz 1 auf Hacker News und wird auch heute auf Lobsters lebhaft diskutiert (52 Punkte, 6 Kommentare). Der Beitrag verkündet keine spektakulären Neuigkeiten, sondern verwandelt die komplexe Logik der Aufzugssteuerung in einen anschaulichen, interaktiven Simulator. Seine Popularität verdankt er der Antwort auf eine Frage, die sich jeder schon einmal im Foyer gestellt hat: Hat der Fahrstuhl eigentlich gehört, dass ich gedrückt habe?
Ja, er hat es gehört. Er muss nur extrem viel bedenken.
Was Aufzüge optimieren: Warum Durchschnitte trügen
Stellen wir zunächst eine grundlegende Frage: Wie misst man überhaupt, ob ein Fahrstuhlalgorithmus gut funktioniert?
Die intuitive Antwort lautet „durchschnittliche Wartezeit“. Stellt man jedoch die Wartezeiten von Tausenden simulierten Fahrten in einem Verteilungsdiagramm dar, erweisen sich Durchschnittswerte als trügerisch. Johns Simulation nennt zwei zentrale Werte: Die p50-Wartezeit liegt bei 1 Minute – das bedeutet, dass die Hälfte aller Personen innerhalb einer Minute einsteigt. Die p90-Wartezeit liegt bei 2 Minuten, sprich 90 % der Fahrgäste warten maximal zwei Minuten.
In dieser einen Minute Differenz zwischen p50 und p90 verbirgt sich das wesentliche Geheimnis der Aufzugsbranche: Das menschliche Gehirn merkt sich keine Durchschnitte, sondern nur die schlimmsten Einzelfälle. Jene 10 % der extrem langen Wartezeiten nehmen im Gedächtnis einen überproportional großen Raum ein. Das Gefühl, „der Aufzug kommt einfach nie“, ist daher größtenteils eine Illusion, die durch statistische Verteilungen und kognitive Wahrnehmungsmuster entsteht. In Realität ist der Fahrstuhl in der Hälfte der Fälle nach einer Minute da.
Auch die ingenieurtechnischen Zielkonflikte sind vielschichtig: Durchschnittliche Wartezeit, maximale Wartezeit und Energieverbrauch stehen in direkter Konkurrenz zueinander. Schickt man Aufzüge stets zum nächstgelegenen Fahrgast, wird zwar die durchschnittliche Wartezeit am kürzesten, aber in Extremfällen wartet jemand auf einem anderen Stockwerk bis zu 5 Minuten. Ein Stück des Durchschnitts zu opfern, um unzumutbare Ausreißer zu eliminieren, ist die pragmatische Wahl fast aller Geschäftsgebäude. Es gibt kein Gratis-Mittagessen – die Hersteller wählen lediglich eine Optimierungsmatrix, an die man selten denkt.
Abb.: Aus Tausenden von Simulationen erstellte Wartezeitverteilung aus dem Originalartikel. Quelle: john.fun
Die älteste Regel: Bis zum Ende fahren, dann umkehren
Bevor Algorithmen die Steuerung übernahmen, saß im Fahrstuhl noch ein Mensch. Bis Mitte des 20. Jahrhunderts war der Beruf des Aufzugführers weit verbreitet: Er öffnete die Türen, fragte nach dem Zielstockwerk und steuerte die Kabine manuell. Mit der Automatisierung verschwand der Aufzugführer, die Regeln wurden in Maschinen gegossen und die Disponentenaufgabe wandelte sich vom menschlichen Ermessen zur reinen Mathematik.
Die ersten automatischen Regeln waren erstaunlich simpel. Beim 1961 patentierten SCAN-Algorithmus fährt der Aufzug von der Lobby aus kontinuierlich nach oben, nimmt unterwegs Personen auf und setzt sie ab, bis er das oberste Stockwerk erreicht. Erst dort kehrt er um und wiederholt den Vorgang abwärts. Später erkannten Entwickler, dass es unnötig ist, bis ganz nach oben zu fahren, wenn dort niemand mehr hin möchte – so entstand die verbesserte Variante LOOK: Der Aufzug fährt nur noch bis zum höchsten angeforderten Stockwerk und dreht dann um. Diese Logik halten die meisten Menschen heute für selbstverständlich, ohne zu ahnen, dass es sich um einen formalen Algorithmus handelt.
Dieser Algorithmus hat zudem einen berühmten Verwandten in der Informatik: Die Steuerung von Schreib-Lese-Köpfen bei Festplatten. Wenn ein mechanischer Festplattenkopf Daten auf den Magnetplatten sucht, bewegt er sich nach fast demselben Muster. Die Informatik hat die Bezeichnung direkt übernommen und nennt diesen Ansatz „Elevator-Algorithmus“. Ein über 60 Jahre altes Patent läuft somit heute noch gleichzeitig in Ihrer Festplatte und in den Aufzugsschächten Ihres Bürogebäudes – einfache Regeln überleben oft den Großteil moderner Software.
Regeln für einzelne Fahrstühle scheitern jedoch in der morgendlichen Stoßzeit. Stellen Sie sich ein Bürogebäude um 9:00 Uhr morgens vor: Hunderte Mitarbeiter drücken gleichzeitig in der Lobby die Aufwärts-Taste. Würde ein naives System alle Aufzüge direkt in die Lobby schicken, würden drei Kabinen gleichzeitig die Türen öffnen und halb leer gemeinsam nach oben fahren. Die Steuerung muss daher Dinge tun, die auf den ersten Blick unlogisch erscheinen: Sie schickt eine leere Kabine auf einen Umweg, um Fahrgäste auf einem anderen Stockwerk einzusammeln. Wenn Sie im 15. Stock stehen und der Fahrstuhl an Ihnen vorbeirauscht, hat er Ihr Signal nicht ignoriert – er führt lediglich einen übergeordneten, globalen Plan aus.
Abb.: Interaktive Demo auf der Startseite – ein einzelner Aufzug in einem 4-stöckigen Gebäude, 25-fach beschleunigt abspielbar. Quelle: john.fun
Koordination mehrerer Aufzüge: Neubewertung alle 5 Sekunden
Sobald mehrere Aufzüge parallel arbeiten, wird die Aufgabe dramatisch schwerer: Wer holt wen ab?
Moderne Gruppensteuerungen (wie der RSR-Algorithmus von Otis) nutzen ein Punktesystem. Jedem Aufzug wird kontinuierlich ein Bewertungsscore zugewiesen, der die geschätzte Ankunftszeit, die aktuelle Auslastung, die Vermeidung von Gruppenbildung mit anderen Kabinen, die Fahrtrichtung und freie Kapazitäten in der Nähe berücksichtigt. Der Aufzug mit dem niedrigsten Kostenscore erhält den Zuschlag. Die Eleganz dieses Systems liegt in der Fähigkeit zur Umentscheidung: Alle 5 Sekunden berechnet der Algorithmus das gesamte Gebäude neu. Wird Ihr zugewiesener Fahrstuhl durch blockierte Türen verzögert, kann Ihre Anforderung nahtlos an eine andere Kabine übergeben werden.
Johns Simulation liefert hier ein überraschendes Ergebnis: Bei extrem hohem Fahrgastaufkommen beginnt die einfache LOOK-Regel tatsächlich, komplexe Algorithmen wie RSR zu schlagen. Auch in kleineren Gebäuden mit wenigen Schächten sind einfache Regeln überlegen. „Manchmal ist es besser, Dinge einfach zu halten“ – diese schlichte Erkenntnis ist einer der wertvollsten Gedanken aus der gesamten Analyse.
Zielrufsteuerung: Mehr Informationen, aber langsamer?
In den letzten Jahren hat sich in modernen Bürokomplexen die sogenannte Zielrufsteuerung (Destination Dispatch) verbreitet. Bevor man den Aufzugsbereich betritt, wählt man auf einem Bildschirm in der Lobby das Zielstockwerk aus. Der Bildschirm weist einem dann eine bestimmte Kabine zu (z. B. „Bitte Aufzug 3 nutzen“). Das klingt auf dem Papier äußerst intelligent: Wenn das System im Voraus weiß, wohin jeder möchte, kann es die Routen doch viel besser planen?
Die Simulationsergebnisse zeigen genau das Gegenteil: In den allermeisten Szenarien ist die durchschnittliche Wartezeit bei der Zielrufsteuerung schlechter als bei herkömmlichen Auf/Ab-Tasten. Das einzige Szenario, in dem die Zielrufsteuerung gewinnt, sind Wolkenkratzer mit großen Aufzugsgruppen von 8 oder mehr Kabinen. Der Grund: Die Flexibilität, alle 5 Sekunden dynamisch neu zu optimieren, wird in dem Moment blockiert, in dem der Bildschirm den Fahrgast auf eine bestimmte Kabine festlegt. 30 Sekunden nach der Eingabe kann sich die Verkehrslage im Gebäude verändert haben, aber das System kann seine Zusage nicht mehr widerrufen.
Ingenieure auf Lobsters steuerten Erfahrungsberichte bei. Der Nutzer vbernat merkte an, dass die Zielrufsteuerung darauf angewiesen ist, dass jeder Fahrgast sein Ziel brav am Terminal eingibt. Ungeduldige Personen drücken oft mehrfach, woraufhin das System zwei Kabinen auf denselben Stock schickt. mitsuhiko (Autor des Flask-Frameworks) ergänzte, dass es in der Praxis häufig vorkommt, dass Fahrgäste in den falschen Aufzug einsteigen oder ihren zugewiesenen Fahrstuhl verpassen. Positiv bewertet wird das System in Kombination mit Hochhaus-Access-Cards: Beim Scannen wird sofort die passende Kabine zugewiesen, was den morgendlichen Ansturm beschleunigt. Der Preis dafür ist jedoch oft eine jahrelange Wartezeit von mehreren Minuten bei der Abwärtsfahrt am Feierabend, da das System seine gesamte Energie in die Bewältigung der morgendlichen Spitze steckt.
Dies führt zu einer wichtigen Erkenntnis: Dem System mehr Informationen zur Verfügung zu stellen, bedeutet nicht automatisch, dass es diese Informationen optimal nutzen kann. Das globale Optimum des Systems steht häufig im direkten Konflikt mit dem individuellen Wunsch „Der Fahrstuhl soll zuerst zu mir kommen“. Aus Sicht des Algorithmus ist Ihre persönliche Minute etwas völlig anderes als die addierte Wartezeit von Hunderten Menschen im Gebäude.
Warum sich das Warten so lang anfühlt: Die Psychologie des Wartens
Zu guter Letzt ein Blick auf die Psychologie: Aufzugshersteller erforschen seit Jahrzehnten die „gefühlte Wartezeit“. Die Psychologie zeigt, dass Zeit umso langsamer vergeht, je langweiliger das Warten empfunden wird. Ein klassischer architektonischer Kniff besteht darin, große Spiegel neben den Aufzugstüren anzubringen – eine Maßnahme, die von vielen Gebäudemanagern mit spürbarem Erfolg umgesetzt wurde. Die Frustration beim Warten entsteht also zur Hälfte durch den Algorithmus und zur Hälfte im eigenen Kopf.
Es gibt noch ein Phänomen, das viele rätseln lässt: Da Aufzüge genau gleich oft nach oben wie nach unten fahren – warum hat man gefühlt immer den Eindruck, dass der Fahrstuhl zuerst in die falsche Richtung unterwegs ist? Ein Teil der Erklärung liegt in den Stoßzeiten: Voll besetzte Aufzüge fahren an Zwischenstockwerken ohne Halt vorbei. Im Gedächtnis bleiben vor allem jene voll besetzten Kabinen haften, die vor den eigenen Augen vorbeirauschen.
Kehren wir zur Eingangsfrage zurück: Hat der Fahrstuhl Ihre Taste gehört? Ja, hat er. Er ist lediglich damit beschäftigt, Hunderttausende Kombinationen aus Zielen, Kabinenauslastung, Energieverbrauch und Fairness alle 5 Sekunden neu durchzurechnen. Wenn der Fahrstuhl das nächste Mal zuerst woanders hinfährt, betrachten Sie ihn als Disponenten im Dienste der globalen Optimierung: Auf seiner Rechnung steht Ihre einzelne Minute neben der Zeit von Hunderten anderen Menschen im Haus.
Referenzlinks:
- John Allsopp: Elevators (Interaktive Erklärung)
- Lobsters-Diskussion (s/jxqf1w/elevators)
- Wikipedia: Elevator algorithm
- Signal v. Noise: Defining the problem of elevator waiting times
- Scientific American: The reason why elevators feel slow
