TY - CHAP A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers T2 - Operations Research Proceedings Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2007/1025/ SP - 357 EP - 362 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Krumke, Sven A1 - Saliba, Sleman A1 - Tuchscherer, Andreas T1 - Randomized Online Algorithms for Dynamic Multi-Period Routing Problems T2 - Proceedings of MAPSP Y1 - 2009 SP - 71 EP - 73 ER - TY - JOUR A1 - Heinz, Stefan A1 - Kaibel, Volker A1 - Peinhardt, Matthias A1 - Rambau, Jörg A1 - Tuchscherer, Andreas T1 - LP-Based Local Approximation for Markov Decision Problems Y1 - 2006 IS - 343 PB - Matheon ER - TY - CHAP A1 - Tuchscherer, Andreas ED - Fleuren, Hein ED - den Hertog, Dick ED - Kort, Peter T1 - Dynamical configuration of transparent optical telecommunication networks T2 - Operations Research Proceedings Y1 - 2004 SP - 25 EP - 32 PB - Springer ER - TY - CHAP A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Poensgen, Diana A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Tuchscherer, Andreas ED - Cinkler, Tibor ED - Jakab, Tivadar ED - Tapolcai, Jànos ED - Gàspàr, Csaba T1 - Dynamic routing algorithms in transparent optical networks T2 - Proceedings of the 7th IFIP Working Conference on Optical Network Design & Modelling (ONDM 2003) Y1 - 2003 UR - http://opus.kobv.de/zib/volltexte/2002/703/ SP - 293 EP - 312 PB - Kluwer Academic Press ER - TY - GEN A1 - Achterberg, Tobias A1 - Koch, Thorsten A1 - Tuchscherer, Andreas T1 - On the Effects of Minor Changes in Model Formulations N2 - Starting with the description of the Traveling Salesmen Problem formulation as given by van Vyve and Wolsey in the article Approximate extended formulations'', we investigate the effects of small variations onto the performance of contemporary mixed integer programming solvers. We will show that even minor changes in the formulation of the model can result in performance difference of more than a factor of 1000. As the results show it is not obvious which changes will result in performance improvements and which not. T3 - ZIB-Report - 08-29 Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10808 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers N2 - 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. T3 - ZIB-Report - 07-26 KW - Aufzugsgruppensteuerung KW - Zielrufsteuerung KW - Echzeitoptimierung KW - Online-Optimierung KW - elevator group control KW - destination call system KW - real time optimation KW - online optimization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10108 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups N2 - The task of an elevator control is to schedule the elevators of a group such that small waiting and travel times for the passengers are obtained. We present an exact reoptimization algorithm for this problem. A reoptimization algorithm computes a new schedule for the elevator group each time a new passenger arrives. Our algorithm uses column generation techniques and is, to the best of our knowledge, the first exact reoptimization algorithms for a group of passenger elevators. To solve the column generation problem, we propose a Branch & Bound method. T3 - ZIB-Report - 12-43 KW - elevator control, online optimization, reoptimization algorithms, column generation Y1 - 2012 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-16485 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Krumke, Sven A1 - Saliba, Sleman A1 - Tuchscherer, Andreas T1 - Randomized Online Algorithms for Dynamic Multi-Period Routing Problems N2 - The Dynamic Multi-Period Routing Problem DMPRP introduced by Angelelli et al. gives a model for a two-stage online-offline routing problem. At the beginning of each time period a set of customers becomes known. The customers need to be served either in the current time period or in the following. Postponed customers have to be served in the next time period. The decision whether to postpone a customer has to be done online. At the end of each time period, an optimal tour for the customers assigned to this period has to be computed and this computation can be done offline. The objective of the problem is to minimize the distance traveled over all planning periods assuming optimal routes for the customers selected in each period. We provide the first randomized online algorithms for the DMPRP which beat the known lower bounds for deterministic algorithms. For the special case of two planning periods we provide lower bounds on the competitive ratio of any randomized online algorithm against the oblivious adversary. We identify a randomized algorithm that achieves the optimal competitive ratio of $\frac{1+\sqrt{2}}{2}$ for two time periods on the real line. For three time periods, we give a randomized algorithm that is strictly better than any deterministic algorithm. T3 - ZIB-Report - 09-03 KW - Online-Optimierung KW - Randomisierte Algorithmen KW - Zweistufiges Problem KW - Traveling-Salesman-Problem KW - online optimization KW - randomized algorithm KW - two-stage problem KW - traveling salesman problem Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11132 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - Improving the performance of elevator systems using exact reoptimization algorithms N2 - This extended abstract is about algorithms for controlling elevator systems employing destination hall calls, i.e. the passenger provides his destination floor when calling an elevator. We present the first exact algorithm for controlling a group of elevators and report on simulation results indicating that destination hall call systems outperform conventional systems. T3 - ZIB-Report - 09-05 KW - Aufzugssteuerung KW - Onlineoptimierung KW - Exakte Reoptimierung KW - elevator control KW - online optimization KW - exact reoptimation Y1 - 2009 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11155 SN - 1438-0064 ER - TY - THES A1 - Tuchscherer, Andreas T1 - Dynamical Configuration of Transparent Optical Telecommunication Networks N2 - All-optical telecommunication networks allow for switching connections by lightpaths which can pass several network links without any opto-electronic conversion. Upon arrival of a connection request, it must be decided online, i.e., without knowledge of future requests, if it is accepted and in that case on which lightpaths the connection is routed. This online problem with the goal of maximizing the total profit gained by accepted requests is called Dynamic Singleclass Call Admission Problem (DSCA). We present existing and new algorithms for the DSCA as well as their theoretical and practical evaluation. KW - Online-Optimierung KW - Online Optimization Y1 - 2003 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10214 ER -