In den nächsten 2 Wochen werden bei mir im Institut beide(!) Fahrstühle repariert. Auch wenn ich nur im 5. Stock sitze und nicht wie einige Kollegen im 8.: Da bleib ich doch lieber zuhause und beschäftige mich mit mathematischer Fahrstuhl-Theorie.

Einen mathematischen Beweis dafür, daß man besser nicht beide Fahrstühle gleichzeitig reparieren sollte, hat wohl noch niemand gefunden.

Über das Thema ‘Optimerung von Fahrstuhlsteuerungen’ gibt es aber tatsächlich mathematische Forschungsarbeiten.

Das hat zwar nichts mit meinem aktuellen Problem zu tun, ist aber jedenfalls auch interessant. Das Thema Echtzeitsteuerung von Aufzugsystemen ist 1995-2001 von einer Arbeitsgruppe am Berliner Zuse-Institut bearbeitet worden.

Der allgemein-verständliche Artikel “Wo bleibt der Aufzug?” faßt einige der Ergebnisse zusammen, ebenso wie die beiden unten abgebildeten Poster. (Siehe auch die Webseite von Jörg Rambau.)

Bei der Fahrstuhlsteuerung handelt es sich um ein sogenanntes Online-Problem, d.h. bei Beginn des Berechnungsvorgangs sind nicht alle Eingabedaten verfügbar (weil ja in Echtzeit ständig neue Anfragen dazukommen). Eine wichtige Frage ist natürlich, wie man die verschiedenen Möglichkeiten bewertet, also wie man bestimmt, ob eine Route besser ist als eine andere.
Das theoretische Verfahren zur Analyse der Online-Algorithmen heißt kompetitive Analyse: man vergleicht den Zielfunktionswert (die Zufriedenheit der Fahrgäste) einer vom Online-Algorithmus generierten Lösung bei Eingabe einer Anfrage-Sequenz mit dem Wert einer optimalen Offline-Lösung.
Ascheuer, Krumke und Rambau haben 1998 einen 2-kompetitiven Algorithmus für die Fahrstuhlsteuerung entwickelt, d.h. die vom Algorithmus vorgeschlagene Online-Lösung ist immer höchstens um einen Faktor 2 schlechter als die jeweilige Offline-Lösung.
Aus dem Artikel “Wo bleibt der Aufzug?”:
Die theoretischen Resultate sind teilweise so schwach, daß sie für die Praxis kaum Entscheidungshilfen liefern. Häufig ist der einzige Ausweg Validierung und Evaluierung durch Simulation.
Grundlage fur eine aussagekräftige Simulation ist Zugang zu realistischen Daten. Für verschiedene Aufzugsysteme wurde aufbauend auf AMSEL ein Simulationssystem entwickelt, mit dem das Verhalten der Algorithmen in praktischen Situationen evaluiert werden kann. Einige der für die Zielfunktion Makespan kompetitiven Algorithmen zeigten dabei auch gutes praktisches Verhalten für andere Zielfunktionen, die für die Praxis interessanter sind.
[…]
Während kompetitive Analyse alleine oftmals zuwenig Information uber die Leistungsfähigkeit von Algorithmen liefert, gewinnt man doch Einsicht in die Problemstruktur. Die Kombination aus theoretischer Analyse und Simulation führt dann häufig auch zu praktikablen Algorithmen, deren Lösungen (durch Simulation empirisch bewertet) erheblich besser sind als man theoretisch garantieren kann.
Unser Fahrstuhlproblem vom Anfang kann man in der Praxis also durchaus zufriedenstellend bewältigen, wenn man anhand repräsentativer Datensatze anwendungsspezische Online-Heuristiken entwirft. Gegen unerwartet massiven Andrang, z.B. direkt vor Arbeitsbeginn, oder bewußt böswillige Datensätze ist jedoch auch der beste Algorithmus machtlos.”

i-e2d9fcad8d568fb0f23f7973f3709d5a-krumke_echtzeit.jpg

Quelle: Zuse-Institut

i-6d80c4d61678900bec7f3d1fee7fa780-hauptmeier_simulation.jpg

Quelle: Zuse-Institut

Kommentare (15)

  1. #1 Jörg
    2. März 2009

    Ich hab mich in meinem alten Haus ja schon immer gefragt, warum der Aufzug nicht morgens in der Mitte und abends unten steht, statt immer im 5ten wenn ich unten fahren wollte und im Erdgeschoss wenn ich vom 5ten fahren wollte…aber ansonsten war der auch toll designed, weil man vom Eingang auf jeden Fall Treppen steigen musste, weil der zur anderen Seite aufging und der Haupteingang quasi ein halbes Stock tiefer als das Erdgeschoss lag…
    Jedenfalls war meine Idee für eine einfache (!) Aufzugsteuerung, dass der selbst “umparkt” wenn er Pause hat, und zwar dorthin, wo in einem Zeitfenster der Mittelwert der einsteigenden Menschen losfahren will.

  2. #2 Jörg
    2. März 2009

    Ich hab mich in meinem alten Haus ja schon immer gefragt, warum der Aufzug nicht morgens in der Mitte und abends unten steht, statt immer im 5ten wenn ich unten fahren wollte und im Erdgeschoss wenn ich vom 5ten fahren wollte…aber ansonsten war der auch toll designed, weil man vom Eingang auf jeden Fall Treppen steigen musste, weil der zur anderen Seite aufging und der Haupteingang quasi ein halbes Stock tiefer als das Erdgeschoss lag…
    Jedenfalls war meine Idee für eine einfache (!) Aufzugsteuerung, dass der selbst “umparkt” wenn er Pause hat, und zwar dorthin, wo in einem Zeitfenster der Mittelwert der einsteigenden Menschen losfahren will.

  3. #3 Jörg
    2. März 2009

    Ich hab mich in meinem alten Haus ja schon immer gefragt, warum der Aufzug nicht morgens in der Mitte und abends unten steht, statt immer im 5ten wenn ich unten fahren wollte und im Erdgeschoss wenn ich vom 5ten fahren wollte…aber ansonsten war der auch toll designed, weil man vom Eingang auf jeden Fall Treppen steigen musste, weil der zur anderen Seite aufging und der Haupteingang quasi ein halbes Stock tiefer als das Erdgeschoss lag…
    Jedenfalls war meine Idee für eine einfache (!) Aufzugsteuerung, dass der selbst “umparkt” wenn er Pause hat, und zwar dorthin, wo in einem Zeitfenster der Mittelwert der einsteigenden Menschen losfahren will.

  4. #4 Popeye
    2. März 2009

    Also ich sitze zwar im Glashaus, aber laut Deinem Bild könnte Dir Treppensteigen durchaus gut tun! (-;
    Ich habe mal gehört, die meisten Erfindungen wurden aus Bequemlichkeit gemacht, stimmt Ihr dem zu?

  5. #5 A. T.
    2. März 2009

    In einem Hotel in England habe ich einmal die Krönung intelligenter Fahrstuhlsteuerung erlebt.
    Jeden morgen gibt es in diesem (hohen) Hotel hunderte Leute, die in die Stadt möchten. Dazu müssen sie natürlich mit dem Fahrstuhl ins Erdgeschoss fahren. Sind dort alle ausgestiegen, fährt der Fahrstuhl wieder hoch, sobald er angefordert wird. Dann hält er in der ersten Etage, in der Leute warten, an, lässt sie einsteigen und fährt wieder runter. Dieses geniale System führt dazu, dass sich in den 6. Stock (wo mein Zimmer war) nur alle zehn minuten mal ein Fahrstuhl verirrte. Wie es in den Etagen 10 oder 15 aussieht, möchte ich mir gar nicht vorstellen.

    Was auf jeden Fall in dem Modell berücksichtig werden sollte ist der Anteil von Fahrgästen, die beim Aussteigen den Fahrstuhl in hohe Etagen schicken, um den Leuten dort auch eine Chance zu geben Fahrstuhl zu fahren.

  6. #6 Matthias Rampke
    2. März 2009

    Das System, das ich bei Fahrstühlen am häufigsten beobachte und auch für recht sinnvoll halte, ist eine Art Zustandsmaschine:

    er fährt immer entweder “rauf” oder “runter” (und hält dabei überall, wohin gerufen oder geschickt wurde), solange bis es in diese Richtung keinen Ruf mehr gibt, dann kehrt er um. Wenn es gar keinen ausstehenden Ruf mehr gibt bleibt er stehen und/oder fährt nach einer gewissen Zeit in eine Ruhestellung (meist unten).

    In Zeiten hoher Belastung fährt er dann eben immer von ganz unten nach ganz oben und wieder zurück, bei minimaler Auslastung direkt erst zum Start-, von da zum Zielort (weil ja der Fahrende drinnen dann den Zielort drückt).

    Außerdem ist die Implementierung ziemlich trivial: der Zustand besteht zu jedem Zeitpunkt nur aus der Position, aktuellen Fahrtrichtung, und den anzufahrenden Stockwerken. Die Elektronik muss sich weder vergangene Entscheidungen merken noch Vorhersagen über die Zukunft machen, aus diesem Zustand lässt sich jederzeit die nächste Aktion ermitteln.

  7. #7 Oliver
    3. März 2009

    Hallo.
    Ich denke die Sirius Kybernetik Corporation hat schon einen solchen
    “vorher-wissenden” Aufzug entwickelt 🙂

    LOL!

  8. #8 Ralf
    2. April 2009

    Vielleicht ist es auch ganz profan die Möglichkeit, in ein Fitnessprogramm einzusteigen? 😉

  9. #9 Thilo Kuessner
    10. Juni 2009

    Jetzt greift man bei uns am Institut zu ganz neuen Lösungen:
    http://www.uni-muenster.de/WWUmwelt/wwurunsup.html

  10. #11 zalim
    16. April 2010

    danke

    Ist zwar Werbung, paßt aber wenigstens zum Thema. Ich laß es mal ausnahmsweise stehe. TK

  11. #12 Dung Trinh Thi
    18. Juli 2011

    this is great article. i found it by google .

  12. #13 Ly Anh Tuan
    20. Juli 2011

    Great Article . Thanks much .

  13. #14 Ly Anh Tuan
    20. Juli 2011

    Great Article . Thanks much .

  14. #15 Treppenlift
    18. August 2011

    danke für die info