Blog durchsuchen
Profil

큈넬 티로 wohnt in Seoul und arbeitet über
geometrische Topologie.

Kommentare

« vorheriger Beitrag  · nächster Beitrag »

02.03.09 · 08:21 Uhr

Wo bleibt der Aufzug?

Kategorie: Technik  ·  Kommentare: 13

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."


krumke_echtzeit.jpg
Quelle: Zuse-Institut

hauptmeier_simulation.jpg
Quelle: Zuse-Institut

 

Autor: Thilo· 13 Kommentare· Permalink· Trackback-URL

Tags: · · ·

Kommentare (13)

Author Profile Page Jörg· 02.03.09 · 08:40 Uhr

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.

Kommentar-Direktlink Popeye· 02.03.09 · 11:07 Uhr

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?

Kommentar-Direktlink A. T.· 02.03.09 · 11:10 Uhr

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.

Kommentar-Direktlink Matthias Rampke· 02.03.09 · 14:51 Uhr

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.

Kommentar-Direktlink Oliver· 03.03.09 · 13:21 Uhr

Hallo.
Ich denke die Sirius Kybernetik Corporation hat schon einen solchen
"vorher-wissenden" Aufzug entwickelt :-)

LOL!

Kommentar-Direktlink Ralf· 02.04.09 · 00:10 Uhr

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

Author Profile Page Thilo Kuessner· 10.06.09 · 16:38 Uhr

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

Kommentar-Direktlink zalim· 16.04.10 · 10:39 Uhr

danke

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

Kommentar-Direktlink Dung Trinh Thi· 18.07.11 · 23:33 Uhr

this is great article. i found it by google .

Kommentar-Direktlink Ly Anh Tuan· 20.07.11 · 20:31 Uhr

Great Article . Thanks much .

Kommentar-Direktlink Ly Anh Tuan· 20.07.11 · 20:39 Uhr

Great Article . Thanks much .

Kommentar-Direktlink Treppenlift· 18.08.11 · 22:31 Uhr

danke für die info

Kommentar schreiben

Netiquette·AGB

 

ScienceBlogs.com

mehr auf www.scienceblogs.com »