TY - GEN A1 - Hülsermann, Ralf A1 - Jäger, Monika A1 - Krumke, Sven A1 - Poensgen, Diana A1 - Rambau, Jörg A1 - Tuchscherer, Andreas T1 - Dynamic Routing Algorithms in Transparent Optical Networks An Experimental Study Based on Real Data N2 - Today's telecommunication networks are configured statically. Whenever a connection is established, the customer has permanent access to it. However, it is observed that usually the connection is not used continuously. At this point, dynamic provisioning could increase the utilization of network resources. WDM based Optical Transport Networks (OTNs) will shortly allow for fast dynamic network reconfiguration. This enables optical broadband leased line services on demand. Since service requests competing for network resources may lead to service blocking, it is vital to use appropriate strategies for routing and wavelength assignment in transparent optical networks. We simulate the service blocking probabilities of various dynamic algorithms for this problem using a well-founded traffic model for two realistic networks. One of the algorithms using shortest path routings performs best on all instances. Surprisingly, the tie-breaking rule between equally short paths in different wavelengths decides between success or failure. T3 - ZIB-Report - 02-35 KW - Dynamic Network Configuration KW - Routing and Wavelength Allocation KW - Transparent Optical Networks KW - Blocking Probability KW - Simulation Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7025 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 - 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 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark T1 - The Online Target Date Assignment Problem N2 - Many online problems encountered in real-life involve a two-stage decision process: upon arrival of a new request, an irrevocable first-stage decision (the assignment of a specific resource to the request) must be made immediately, while in a second stage process, certain ``subinstances'' (that is, the instances of all requests assigned to a particular resource) can be solved to optimality (offline) later. We introduce the novel concept of an \emph{Online Target Date Assignment Problem} (\textsc{OnlineTDAP}) as a general framework for online problems with this nature. Requests for the \textsc{OnlineTDAP} become known at certain dates. An online algorithm has to assign a target date to each request, specifying on which date the request should be processed (e.\,g., an appointment with a customer for a washing machine repair). The cost at a target date is given by the \emph{downstream cost}, the optimal cost of processing all requests at that date w.\,r.\,t.\ some fixed downstream offline optimization problem (e.\,g., the cost of an optimal dispatch for service technicians). We provide general competitive algorithms for the \textsc{OnlineTDAP} independently of the particular downstream problem, when the overall objective is to minimize either the sum or the maximum of all downstream costs. As the first basic examples, we analyze the competitive ratios of our algorithms for the par ticular academic downstream problems of bin-packing, nonpreemptive scheduling on identical parallel machines, and routing a traveling salesman. T3 - ZIB-Report - 05-61 KW - Online Algorithms KW - Online Target Date Assignment Problem Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8945 ER - TY - GEN A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Combinatorial Online Optimization: Elevators & Yellow Angels N2 - In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon. T3 - ZIB-Report - 07-36 KW - Online-Optimierung KW - Aufzugssteuerung KW - Dispatching von Fahrzeugen KW - online optimization KW - elevator control KW - vehicle dispatching Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10360 SN - 1438-0064 ER - TY - THES A1 - Tuchscherer, Andreas T1 - Local Evaluation of Policies for Discounted Markov Decision Problems N2 - Providing realistic performance indicators of online algorithms for a given online optimization problem is a difficult task in general. Due to significant drawbacks of other concepts like competitive analysis, Markov decision problems (MDPs) may yield an attractive alternative whenever reasonable stochastic information about future requests is available. However, the number of states in MDPs emerging from real applications is usually exponential in the original input parameters. Therefore, the standard methods for analyzing policies, i.e., online algorithms in our context, are infeasible. In this thesis we propose a new computational tool to evaluate the behavior of policies for discounted MDPs locally, i.e., depending on a particular initial state. The method is based on a column generation algorithm for approximating the total expected discounted cost of an unknown optimal policy, a concrete policy, or a single action (which assumes actions at other states to be made according to an optimal policy). The algorithm determines an $\varepsilon$-approximation by inspecting only relatively small local parts of the total state space. We prove that the number of states required for providing the approximation is independent of the total number of states, which underlines the practicability of the algorithm. The approximations obtained by our algorithm are typically much better than the theoretical bounds obtained by other approaches. We investigate the pricing problem and the structure of the linear programs encountered in the column generation. Moreover, we propose and analyze different extensions of the basic algorithm in order to achieve good approximations fast. The potential of our analysis tool is exemplified for discounted MDPs emerging from different online optimization problems, namely online bin coloring, online target date assignment, and online elevator control. The results of the experiments are quite encouraging: our method is mostly capable to provide performance indicators for online algorithms that much better reflect observations made in simulations than competitive analysis does. Moreover, the analysis allows to reveal weaknesses of the considered online algorithms. This way, we developed a new online algorithm for the online bin coloring problem that outperforms existing ones in our analyses and simulations. KW - Markov decision problem KW - online optimization KW - linear programming KW - column generation KW - performance guarantees Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11963 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 - JOUR A1 - Grötschel, Martin A1 - Hinrichs, Hinrich A1 - Schröer, Klaus A1 - Tuchscherer, Andreas T1 - Ein gemischt-ganzzahliges lineares Optimierungsmodell für ein Laserschweißproblem im Karosseriebau JF - Zeitschrift für wirtschaftlichen Fabrikbetrieb (ZWF) Karosseriebau Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2006/915/ VL - 101 IS - 5 SP - 260 EP - 264 ER - 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 - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - Improving the performance of elevator systems using exact reoptimization algorithms T2 - Proceedings of MAPSP Y1 - 2009 UR - http://opus.kobv.de/zib/volltexte/2009/1161/ SP - 224 EP - 226 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - Improved destination call elevator control algorithms for up peak traffic T2 - Operations Research Proceedings 2010 Y1 - 2010 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 - 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 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark ED - Erlebach, Thomas ED - Persiano, Giuseppe T1 - The Online Target Date Assignment Problem T2 - Proc. 3rd Workshop on Approximation and Online Algorithms Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/894/ VL - 3879 SP - 230 EP - 243 PB - Springer 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 - JOUR A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups JF - Flexible Services and Manufacturing Journal Y1 - 2013 U6 - https://doi.org/10.1007/s10696-013-9175-6 SP - 1 EP - 24 ER - TY - CHAP A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas ED - Lucas, Klaus ED - Roosen, Peter T1 - Structuring a Dynamic Environment T2 - Emergence, Analysis and Evolution of Structures. Concepts and Strategies Across Disciplines Y1 - 2009 UR - http://www.springer.com/engineering/book/978-3-642-00869-6 U6 - https://doi.org/10.1007/978-3-642-00870-2 SP - 199 EP - 214 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers T2 - Operations Research Proceedings 2007 Y1 - 2008 SP - 357 EP - 362 PB - Springer 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 - 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 - TY - GEN A1 - Grötschel, Martin A1 - Hinrichs, Hinrich A1 - Schröer, Klaus A1 - Tuchscherer, Andreas T1 - Ein gemischt-ganzzahliges lineares Optimierungsmodell für ein Laserschweißproblem im Karosseriebau N2 - Wir beschäftigen uns mit dem Problem der Betriebsplanung von Laserschweißrobotern im Karosseriebau. Gegeben ist eine Menge von Schweißnähten, die innerhalb einer Fertigungszelle an einem Karosserieteil gefertigt werden müssen. Die Schweißnähte werden durch mehrere parallel betriebene Roboter bearbeitet. Die Aufgabe besteht darin, für jeden Roboter eine Reihenfolge und eine zeitliche Koordinierung seiner Bewegungen zu finden, so dass alle Schweißnähte innerhalb der Taktzeit der Fertigungszelle bearbeitet werden und so wenig Laserquellen wie möglich eingesetzt werden. Dabei müssen einige Nebenbedingungen berücksichtigt werden. Für dieses spezielle Schweißproblem haben wir eine Formulierung als gemischt-ganzzahliges lineares Programm entwickelt, welches sich für die untersuchten praktischen Fälle sehr schnell lösen lässt. T3 - ZIB-Report - 06-21 KW - Laserschweißen KW - Gemischt-ganzzahlige Optimierung Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9141 ER - TY - GEN 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 N2 - The standard computational methods for computing the optimal value functions of Markov Decision Problems (MDP) require the exploration of the entire state space. This is practically infeasible for applications with huge numbers of states as they arise, e.\,g., from modeling the decisions in online optimization problems by MDPs. Exploiting column generation techniques, we propose and apply an LP-based method to determine an $\varepsilon$-approximation of the optimal value function at a given state by inspecting only states in a small neighborhood. In the context of online optimization problems, we use these methods in order to evaluate the quality of concrete policies with respect to given initial states. Moreover, the tools can also be used to obtain evidence of the impact of single decisions. This way, they can be utilized in the design of policies. T3 - ZIB-Report - 06-20 KW - Markov decision problem KW - linear programming KW - column generation Y1 - 2006 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9131 ER -