Effiziente Reoptimierung in Branch&Bound-Verfahren für die Steuerung von Aufzügen

Please always quote using this URN: urn:nbn:de:0297-zib-42210
  • Heutzutage ist eine Vielzahl der mehrstöckigen Gebäude mit Personenaufzugsgruppen ausgestattet. Uns wohl bekannt sind die sogenannten konventionellen Systeme. Bei diesen Systemen betätigt jeder ankommende Passagier eine der beiden Richtungstasten und teilt dem dahinterstehenden Steuerungsalgorithmus seine gewünschte Startetage und Fahrtrichtung mit. Betreten wird der zuerst auf der Startetage ankommende Aufzug mit gleicher Fahrtrichtung und ausreichend Kapazität. Die entsprechende Zieletage wird dem System erst nach dem Betreten der Fahrgastkabine mitgeteilt. Neben diesen konventionellen Systemen gibt es Aufzugsgruppen mit Zielrufsteuerung. Die Besonderheit eines zielrufgesteuerten Systems ist, dass ein ankommender Passagier bereits auf der Startetage seine gewünschte Zieletage angibt und eine Rückmeldung vom System erhält, welchen Aufzug er nutzen soll. Diese Zuweisung durch das System hat das Ziel, die Warte- und Reisezeiten der Passagiere zu minimieren. Ein wesentlicher Faktor bei der Berechnung warte- und reisezeitminimaler Fahrpläne ist das momentane Verkehrsmuster. Eine Einteilung der Verkehrsszenarien lässt sich am besten bei Bürogebäuden vornehmen. So ist es typisch für die Morgenstunden, dass jeder Passagier auf einer Zugangsebene seine Fahrt beginnt und alle Passagiere die gleiche Fahrtrichtung haben. Unter einer Zugangsebene ist z. B. der Haupteingang oder ein Parkdeck zu verstehen. Ein weiterer wesentlicher Punkt bei Zielrufsystemen ist die Art der Zuweisung der Passagiere durch das System. Zum einen gibt es unmittelbar zuweisende (UZ-) Systeme. In einem UZ-System wird nach jeder Ankunft eines Passagiers eine Momentaufnahme des momentanen Verkehrs erstellt und es findet eine Neuplanung und Zuweisung statt. Eine solche Momentaufnahme werden wir im späteren Verkauf als Schnappschussproblem bezeichnen. Jeder Passagier bekommt im Anschluss an die Lösung des Schnappschussproblems eine Mitteilung vom System, z. B. über ein Display, welchen Aufzug er benutzen soll. Zum anderen gibt es verzögert zuweisende (VZ-) Systeme. In diesen Systemen wird die Erstellung und Lösung eines Schnappschussproblems bis kurz vor Ankunft eines Aufzuges auf einer Etage verzögert. In einem VZ-System teilt das System allen wartenden Passagieren die geplanten Zieletagen des ankommenden Aufzugs mit. Jeder Passagier, der einen Ruf getätigt hat und zu einer dieser Zieletagen fahren will, kann jetzt diesen Aufzug betreten. Durch die Verzögerung muss im Vergleich zu einem UZ-System eine weitaus größere Menge von Passagieren zugewiesen werden. Dadurch kann der Lösungsprozess bedeutend aufwändiger werden. Vorteil eines VZ-Systems ist hingegen der größere Freiheitsgrad bei der Optimierung, da aufgrund der späten Zuweisung die weitere Verkehrsentwicklung mit einbezogen werden kann. VZ-Systeme sind aufgrund des größeren Freiheitsgrades interessant für die Praxis ist, wir uns demzufolge in dieser Arbeit mit einer effizienteren Lösung dieser Art von Schnappschussproblemen befassen. Es genügt dabei den Lösungsprozess eines Schnappschussproblems zu betrachten. Das Ziel ist eine Reduzierung der benötigten Rechenzeit. Unter Reoptimierung verstehen wir die Konstruktion zulässiger Spalten in den jeweiligen Iterationsrunden der Spaltengenerierung innerhalb eines Schnappschussproblems. Als eine Iterationsrunde bezeichnet wir einer Menge zulässiger Touren mit negativen reduzierten Kosten. Eine effiziente Reoptimierung zeichnet sich durch die Wiederverwendung und Aufbereitung von Informationen aus vorangegangenen Iterationsrunden desselben Schnappschussproblems aus. Zu den wichtigen Informationen gehört der konstruierte Suchbaum der vorherigen Iterationsrunde mit seinen ausgeloteten (abgeschnittenen) Blättern sowie konstruierten Touren bzw. Spalten, welche in der Iterationsrunde ihrer Konstruktion nicht zur Lösung des Teilproblems der Spaltengenerierung beitrugen. Eine solche Wiederverwendung und Aufbereitung von Informationen nennen wir Warmstart.

Download full text files

Export metadata

  • Export Bibtex
Metadaten
Author:Jakob Witzig
Document Type:Bachelor's Thesis
MSC-Classification:00-XX GENERAL
68-XX COMPUTER SCIENCE (For papers involving machine computations and programs in a specific mathematical area, see Section -04 in that area)
Granting Institution:Technische Universität Berlin
Advisor:Benjamin Hiller
Date of final exam:2013/01/24
Publishing Institution:Zuse Institute Berlin (ZIB)
Date of first Publication:2013/08/29
Pagenumber:111

$Rev: 13581 $