TY - CHAP A1 - Fischer, Frank A1 - Grimm, Boris A1 - Klug, Torsten A1 - Schlechte, Thomas T1 - A Re-optimization Approach for Train Dispatching T2 - Operations Research Proceedings 2016 N2 - The Train Dispatching Problem (TDP) is to schedule trains through a network in a cost optimal way. Due to disturbances during operation existing track allocations often have to be re-scheduled and integrated into the timetable. This has to be done in seconds and with minimal timetable changes to guarantee smooth and conflict free operation. We present an integrated modeling approach for the re-optimization task using Mixed Integer Programming. Finally, we provide computational results for scenarios provided by the INFORMS RAS Problem Soling Competition 2012. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_85 SP - 645 EP - 651 ER - TY - CHAP A1 - Gilg, Brady A1 - Klug, Torsten A1 - Martienssen, Rosemarie A1 - Paat, Joseph A1 - Schlechte, Thomas A1 - Schulz, Christof A1 - Seymen, Sinan A1 - Tesch, Alexander T1 - Conflict-Free Railway Track Assignment at Depots T2 - Proceedings of the IAROR conference RailLille N2 - Managing rolling stock with no passengers aboard is a critical component of railway operations. In particular, one problem is to park the rolling stock on a given set of tracks at the end of a day or service. Depending on the parking assignment, shunting may be required in order for a parked train to depart or for an incoming train to park. Given a collection of tracks M and a collection of trains T with fixed arrival-departure timetable, the train assignment problem (TAP) is to determine the maximum number of trains from T that can be parked on M according to the timetable and without the use of shunting. Hence, efficiently solving the TAP allows to quickly compute feasible parking schedules that do not require further shunting adjustments. In this paper, we present two integer programming models for solving the TAP. To our knowledge, this is the first integrated approach that considers track lengths along with the three most common types of parking tracks. We compare these models on a theoretical level. We also prove that a decision version of the TAP is NP-complete, justifying the use of integer programming techniques. Using stochastic and robust modelling techniques, both models produce parking assignments that are optimized and robust according to random train delays. We conclude with computational results for both models, observing that they perform well on real timetables. Y1 - 2017 ER - TY - CHAP A1 - Klug, Torsten A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling T2 - 22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022) N2 - Timetabling is a classical and complex task for public transport operators as well as for railway undertakings. The general question is: Which vehicle is taking which route through the transportation network in which order? In this paper, we consider the special setting to find optimal timetables for railway systems under a moving block regime. We directly set up on our work of [8 ], i.e., we consider the same model formulation and real-world instances of a moving block headway system. In this paper, we present a repair heuristic and a lazy-constraint approach utilizing the callback features of Gurobi, see [3]. We provide an experimental study of the different algorithmic approaches for a railway network with 100 and up to 300 train requests. The computational results show that the lazy-constraint approach together with the repair heuristic significantly improves our previous approaches. Y1 - 2022 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2022.11 VL - 106 SP - 11:1 EP - 11:8 PB - Schloss Dagstuhl -- Leibniz-Zentrum für Informatik ER - TY - CHAP A1 - Klug, Torsten A1 - Junosza-Szaniawski, Konstanty A1 - Kwasiborski, Slawomir A1 - Fügenschuh, Armin A1 - Schlechte, Thomas T1 - Fastest, Average and Quantile Schedule T2 - SOFSEM 2015: Theory and Practice of Computer Science N2 - We consider problems concerning the scheduling of a set of trains on a single track. For every pair of trains there is a minimum headway, which every train must wait before it enters the track after another train. The speed of each train is also given. Hence for every schedule - a sequence of trains - we may compute the time that is at least needed for all trains to travel along the track in the given order. We give the solution to three problems: the fastest schedule, the average schedule, and the problem of quantile schedules. The last problem is a question about the smallest upper bound on the time of a given fraction of all possible schedules. We show how these problems are related to the travelling salesman problem. We prove NP-completeness of the fastest schedule problem, NP-hardness of quantile of schedules problem, and polynomiality of the average schedule problem. We also describe some algorithms for all three problems. In the solution of the quantile problem we give an algorithm, based on a reverse search method, generating with polynomial delay all Eulerian multigraphs with the given degree sequence and a bound on the number of such multigraphs. A better bound is left as an open question. KW - scheduling KW - eulerian multigraphs Y1 - 2015 U6 - https://doi.org/10.1007/978-3-662-46078-8_17 SP - 201 EP - 216 PB - Springer Berlin Heidelberg 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 - 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 - Borndörfer, Ralf A1 - Lamorgese, Leonardo A1 - Klug, Torsten A1 - Mannino, Carlo A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Recent Success Stories on Optimization of Railway Systems T2 - Proceedings of the IAROR conference RailTokyo N2 - Planning and operating railway transportation systems is an extremely hard task due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. Because of that, however, mathematical models and optimization techniques can result in large gains for both railway cus- tomers and operators, e.g., in terms of cost reductions or service quality improvements. In the last years a large and growing group of researchers in the OR community have devoted their attention to this domain devel- oping mathematical models and optimization approaches to tackle many of the relevant problems in the railway planning process. However, there is still a gap to bridge between theory and practice, with a few notable exceptions. In this paper we address three success stories, namely, long-term freight train routing (part I), mid-term rolling stock rotation planning (part II), and real-time train dispatching (part III). In each case, we describe real-life, successful implementations. We will dis- cuss the individual problem setting, survey the optimization literature, and focus on particular aspects addressed by the mathematical models. We demonstrate on concrete applications how mathematical optimization can support railway planning and operations. This gives proof that math- ematical optimization can support the planning of rolling stock resources. Thus, mathematical models and optimization can lead to a greater effi- ciency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry. Y1 - 2015 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Witzig, Jakob T1 - Reoptimization in branch-and-bound algorithms with an application to elevator control T2 - Proceedings of the 12th International Symposium on Experimental Algorithms Y1 - 2013 U6 - https://doi.org/10.1007/978-3-642-38527-8_33 VL - 7933 SP - 378 EP - 389 ER -