@misc{FrieseRambau, author = {Friese, Philipp and Rambau, J{\"o}rg}, title = {Online-Optimization of Multi-Elevator Transport Systems with Reoptimization Algorithms based on Set-Partitioning Models}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8373}, number = {05-03}, abstract = {We develop and experimentally compare policies for the control of a system of \$k\$ elevators with capacity one in a transport environment with \$\ell\$ floors, an idealized version of a pallet elevator system in a large distribution center of the Herlitz PBS AG in Falkensee. Each elevator in the idealized system has an individual waiting queue of infinite capacity. On each floor, requests arrive over time in global waiting queues of infinite capacity. The goal is to find a policy that, without any knowledge about future requests, assigns an elevator to each req uest and a schedule to each elevator so that certain expected cost functions (e.g., the average or the maximal flow times) are minimized. We show that a reoptimization policy for minimizing average sq uared waiting times can be implemented to run in real-time (\$1\,s\$) using dynamic column generation. Moreover, in discrete event simulations with Poisson input it outperforms other commonly used polic ies like multi-server variants of greedy and nearest neighbor.}, language = {en} } @misc{HillerTuchscherer, author = {Hiller, Benjamin and Tuchscherer, Andreas}, title = {Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10108}, number = {07-26}, abstract = {Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.}, language = {en} }