Optimizing elevator control with a destination registration system

Abstract

In unserer modernen Gesellschaft sind Aufzüge aus größeren Gebäuden nicht mehr wegzudenken. Aufzugsgruppensteuerungssysteme sind Mehrfachaufzugsysteme, die den Personentransport in einem Gebäude optimieren und die Beförderungskapazität erhöhen. Während herkömmliche Aufzugssysteme einen einzelnen Knopf auf jeder Etage haben, um einen Aufzug zu rufen, verfügen modernere Systeme über ein Zielregistrierungssystem, bei dem die Fahrgäste vor dem Betreten des Aufzugs ihr gewünschtes Zielstockwerk auswählen können und dann einem Aufzug zugewiesen werden. Die Zuweisung von Fahrgästen zu Aufzügen kann als Optimierungsproblem betrachtet werden, bei dem das Ziel darin besteht, die durchschnittliche Wartezeit der Fahrgäste zu minimieren. In dieser Arbeit werden wir drei verschiedene Ansätze zur Lösung des Aufzugszuweisungsproblems für Aufzugssysteme mit einem Zielregistrierungssystem entwickeln. Der erste Ansatz ist ein gemischt-ganzzahliges lineares Programm (engl. mixed integer linear program, MILP), das das Problem zunächst als statisches Optimierungsproblem behandelt, bei dem alle Informationen über zukünftige Fahrgastankünfte im Voraus bekannt sind. Dieses MILP wird dann erweitert um es im dynamischen Optimierungsproblem, bei dem das System Entscheidungen nur auf der Grundlage der aktuellen Informationen über die Fahrgäste und Aufzüge treffen muss, auch einsetzen zu können. Gemischt-ganzzahlige lineare Programme sind exakte Methoden und können optimale Lösungen liefern, aber sie sind rechenintensiv und skalieren nicht gut mit der Größe des Systems. Für das statische Problem können wir ein gegebenes Szenario optimal lösen, während wir für das dynamische Problem einzelne Entscheidungspunkte optimal lösen können, aber die Gesamtlösung ist nicht garantiert optimal.Um die Bewegungen eines Aufzugs im Laufe der Zeit zu modellieren, verwendet das MILP einen Netzwerkflussgraphen und Miller-Tucker-Zemlin (MTZ) Ungleichungen um gültige Lösungen zu garantieren. Der zweite Ansatz, der sich auf das dynamische Problem konzentriert, ist eine greedy (gierige) Heuristik, um die Fahrgäste den Aufzügen nach einer gierigen Strategie zuzuweisen, wobei versucht wird, so viele Fahrgäste so schnell wie möglich abzuholen. Der Greedy-Algorithmus ist einfach und kann schnell Lösungen für das Problem finden, für komplexere Szenarien sinkt aber im Allgemeinen die Qualität der Lösung. Der dritte Ansatz ist ein Reinforcement Learning (RL) Ansatz, der einen Proximal Policy Optimization (PPO) Algorithmus verwendet und ebenfalls nur für die Lösung des dynamischen Problems entwickelt wurde. Um die Komplexität zu verringern, verwendet das Modell nicht die gesamte Zustandsinformation, sondern wertet Teilinformationen für jede gültige Aktion einzeln aus und wählt damit die beste Aktion für jeden Aufzug aus. Das Modell wird für bestimmte Szenarien trainiert, die reale Verkehrsmuster simulieren. Wir bewerten und vergleichen die drei Ansätze für verschiedene Szenarien, unterschiedliche Aufzugssystemgrößen und unterschiedliche Verkehrsmuster. Die Experimente zeigen, dass der dynamische MILP Ansatz für kleine Instanzen im Allgemeinen die besten Lösungen findet, aber rechenintensiv ist und bei größeren Instanzen nur schwer gültige Lösungen findet. Der greedy Ansatz ist in Bezug auf die Rechenzeit am effizientesten und liefert für die meisten der getesteten Instanzen sinnvolle Lösungen. Der Reinforcement Learning Ansatz reagiert empfindlich auf die Hyperparameter, welche für jedes System abgestimmt werden müssen, um gute Lösungen zu liefern. Die Leistung des RL Ansatzes übertrifft den Greedy-Ansatz für kleinere Systeme und Szenarien, in denen viele Fahrgäste gleichzeitig warten, verschlechtert sich jedoch mit zunehmender Systemgröße, insbesondere wenn die Anzahl der Aufzüge steigt.

Modern society relies on elevators for vertical transportation in high-rise buildings. Elevator Group Control Systems (EGCSs) are multi-elevator systems designed to optimize passenger transportation within a building, increasing efficiency and capacity. While traditional EGCSs have a single button on each floor to call an elevator, more advanced systems have a destination registration system, where passengers can select their desired destination floor before entering the elevator and are then assigned to an elevator. The assignment of passengers to elevators can be seen as an optimization problem, where the goal is to minimize the average waiting time of passengers. In this work, we will develop three different approaches to solve the elevator assignment problem for EGCSs with a destination registration system. The first approach is a mixed integer linear program (MILP) that tackles the problem first as a static optimization problem, where all the information about future passenger arrivals is known in advance, and then as a dynamic optimization problem, where the system has to make decisions only based on the current information about the passengers and elevators and the problem is re-solved when new requests become available. Mixed integer linear programs are exact methods and can provide optimal solutions, but they are computationally expensive and do not scale well with the size of the system. For the static problem, we can solve a given scenario optimally, while for the dynamic problem we can solve single decision points optimally, but the overall solution is not guaranteed to be optimal. To model the movement of an elevator over time, the MILP uses a network flow graph and Miller-Tucker-Zemlin (MTZ) constraints for ensuring feasible solutions. The second approach, focusing on the dynamic problem, is a greedy algorithm, which employs a heuristic to assign passengers to elevators based on a greedy strategy, trying to load as many passengers as fast as possible. The greedy algorithm is simple and generates solutions relatively quickly, but often struggles with finding good solutions for complex scenarios. The third approach is a reinforcement learning (RL) approach, which uses a Proximal Policy Optimization (PPO) algorithm and also only aims to solve the dynamic problem. To reduce complexity, rather than using the whole information of the state, the model evaluates only partial information for each valid action individually and picks the best action for each elevator. The model is trained for specific scenarios which simulate real-world traffic patterns. We evaluate and compare the three approaches on different scenarios, different elevator system sizes and different traffic patterns. The experiments show that the dynamic MILP approach generally performs the best for rather small instances in terms of solution quality, but is computationally expensive and struggles to find valid solutions for larger instances. The greedy approach is the most efficient in terms of computation time and provides good solutions for most of the tested instances. The reinforcement learning approach is sensitive to hyperparameters and needs to be fine-tuned for each system individually to provide good solutions. The RL approach outperforms the greedy approach for smaller systems and scenarios where many passengers are waiting at the same time, but gets worse with increasing system size, especially when the number of elevators increases.