@misc{HillerKlugTuchscherer, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, issn = {1438-0064}, doi = {10.1007/s10696-013-9175-6}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16485}, abstract = {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.}, language = {en} } @misc{BorndoerferFuegenschuhKlugetal., author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18991}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that a sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. Here macroscopic refers to an aggregation of complex real-world structures are into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We give a mixed-integer nonlinear programming~(MINLP) formulation for FTRP, which is a multi-commodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities are due to an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model~(MILP) by piecewise linear approximation. The latter is solved by a state of the art MILP solver for various real-world test instances.}, language = {en} } @inproceedings{HillerKlugTuchscherer2009, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improving the performance of elevator systems using exact reoptimization algorithms}, series = {Proceedings of MAPSP}, booktitle = {Proceedings of MAPSP}, pages = {224 -- 226}, year = {2009}, language = {en} } @inproceedings{HillerKlugTuchscherer2010, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improved destination call elevator control algorithms for up peak traffic}, series = {Operations Research Proceedings 2010}, booktitle = {Operations Research Proceedings 2010}, publisher = {Springer}, year = {2010}, language = {en} } @inproceedings{FischerGrimmKlugetal., author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, series = {Operations Research Proceedings 2016}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_85}, pages = {645 -- 651}, abstract = {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.}, language = {en} } @inproceedings{BorndoerferLamorgeseKlugetal.2015, author = {Bornd{\"o}rfer, Ralf and Lamorgese, Leonardo and Klug, Torsten and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, series = {Proceedings of the IAROR conference RailTokyo}, booktitle = {Proceedings of the IAROR conference RailTokyo}, year = {2015}, abstract = {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.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal., author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic}, series = {Transportation Science}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.}, language = {en} } @misc{FischerGrimmKlugetal., author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60493}, abstract = {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.}, language = {en} } @article{BorndoerferKlugLamorgeseetal., author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent success stories on integrated optimization of railway systems}, series = {Transportation Research Part C: Emerging Technologies}, volume = {74}, journal = {Transportation Research Part C: Emerging Technologies}, number = {1}, doi = {10.1016/j.trc.2016.11.015}, pages = {196 -- 211}, abstract = {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 customers 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 developing 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 (e.g. Cacchiani et al., 2014; Bornd{\"o}rfer et al., 2010), with a few notable exceptions. In this paper we address three individual 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 discuss 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 mathematical optimization can support the planning of railway resources. Thus, mathematical models and optimization can lead to a greater efficiency of railway operations and will serve as a powerful and innovative tool to meet recent challenges of the railway industry.}, language = {en} } @inproceedings{GilgKlugMartienssenetal., author = {Gilg, Brady and Klug, Torsten and Martienssen, Rosemarie and Paat, Joseph and Schlechte, Thomas and Schulz, Christof and Seymen, Sinan and Tesch, Alexander}, title = {Conflict-Free Railway Track Assignment at Depots}, series = {Proceedings of the IAROR conference RailLille}, booktitle = {Proceedings of the IAROR conference RailLille}, abstract = {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.}, language = {en} } @misc{GilgKlugMartienssenetal., author = {Gilg, Brady and Klug, Torsten and Martienssen, Rosemarie and Paat, Joseph and Schlechte, Thomas and Schulz, Christof and Seymen, Sinan and Tesch, Alexander}, title = {Conflict-Free Railway Track Assignment at Depots}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-63843}, abstract = {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.}, language = {en} } @article{HillerKlugTuchscherer, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {An Exact Reoptimization Algorithm for the Scheduling of Elevator Groups}, series = {Flexible Services and Manufacturing Journal}, journal = {Flexible Services and Manufacturing Journal}, doi = {10.1007/s10696-013-9175-6}, pages = {1 -- 24}, language = {en} } @incollection{Klug, author = {Klug, Torsten}, title = {Freight Train Routing}, series = {Handbook of Optimization in the Railway Industry}, volume = {268}, booktitle = {Handbook of Optimization in the Railway Industry}, publisher = {Springer International Publishing}, isbn = {978-3-319-72152-1}, doi = {10.1007/978-3-319-72153-8}, pages = {73 -- 92}, abstract = {This chapter is about strategic routing of freight trains in railway transportation networks with mixed traffic. A good utilization of a railway transportation network is important since in contrast to road and air traffic the routing through railway networks is more challenging and the extension of capacities is expensive and a long-term projects. Therefore, an optimized routing of freight trains have a great potential to exploit remaining capacity since the routing has fewer restrictions compared to passenger trains. In this chapter we describe the freight train routing problem in full detail and present a mixed-integer formulation. Wo focus on a strategic level that take into account the actual immutable passenger traffic. We conclude the chapter with a case study for the German railway network.}, language = {en} } @article{GilgKlugMartienssenetal., author = {Gilg, Brady and Klug, Torsten and Martienssen, Rosemarie and Paat, Joseph and Schlechte, Thomas and Schulz, Christof and Seymen, Senan and Tesch, Alexander}, title = {Conflict-free railway track assignment at depots}, series = {Journal of Rail Transport Planning \& Management}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2017.12.004}, abstract = {Managing rolling stock with no passengers aboard is a critical component of railway operations. One aspect of managing rolling stock 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 a 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 show that the TAP is NP-hard and present two integer programming models for solving the TAP. We compare both models on a theoretical level. Moreover, to our knowledge, we consider the first approach that integrates track lengths along with the three most common types of parking tracks FIFO, LIFO and FREE tracks in a common model. Furthermore, to optimize against uncertainty in the arrival times of the trains we extend our models by stochastic and robust modeling techniques. We conclude by giving computational results for both models, observing that they perform well on real timetables.}, language = {en} } @misc{BorndoerferKlugLamorgeseetal., author = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, title = {Recent Success Stories on Optimization of Railway Systems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53726}, abstract = {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.}, language = {en} } @book{AbbinkBaermannBešinovicetal., author = {Abbink, Erwin and B{\"a}rmann, Andreas and Bešinovic, Nikola and Bohlin, Markus and Cacchiani, Valentina and Caimi, Gabrio and de Fabris, Stefano and Dollevoet, Twan and Fischer, Frank and F{\"u}genschuh, Armin and Galli, Laura and Goverde, Rob M.P. and Hansmann, Ronny and Homfeld, Henning and Huisman, Dennis and Johann, Marc and Klug, Torsten and T{\"o}rnquist Krasemann, Johanna and Kroon, Leo and Lamorgese, Leonardo and Liers, Frauke and Mannino, Carlo and Medeossi, Giorgio and Pacciarelli, Dario and Reuther, Markus and Schlechte, Thomas and Schmidt, Marie and Sch{\"o}bel, Anita and Sch{\"u}lldorf, Hanno and Stieber, Anke and Stiller, Sebastian and Toth, Paolo and Zimmermann, Uwe}, title = {Handbook of Optimization in the Railway Industry}, volume = {268}, editor = {Bornd{\"o}rfer, Ralf and Klug, Torsten and Lamorgese, Leonardo and Mannino, Carlo and Reuther, Markus and Schlechte, Thomas}, publisher = {Springer Verlag}, isbn = {978-3-319-72152-1}, doi = {10.1007/978-3-319-72153-8}, abstract = {This book promotes the use of mathematical optimization and operations research methods in rail transportation. The editors assembled thirteen contributions from leading scholars to present a unified voice, standardize terminology, and assess the state-of-the-art. There are three main clusters of articles, corresponding to the classical stages of the planning process: strategic, tactical, and operational. These three clusters are further subdivided into five parts which correspond to the main phases of the railway network planning process: network assessment, capacity planning, timetabling, resource planning, and operational planning. Individual chapters cover: Simulation Capacity Assessment Network Design Train Routing Robust Timetabling Event Scheduling Track Allocation Blocking Shunting Rolling Stock Crew Scheduling Dispatching Delay Propagation}, language = {en} } @article{SchlechteBorndoerferDenissenetal., author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and S{\"o}hlke, Andreas and Steadman, William}, title = {Timetable Optimization for a Moving Block System}, series = {Journal of Rail Transport Planning \& Management}, volume = {22}, journal = {Journal of Rail Transport Planning \& Management}, issn = {2210-9706}, doi = {10.1016/j.jrtpm.2022.100315}, pages = {100315}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @misc{FuegenschuhJunoszaSzaniawskiKlugetal., author = {F{\"u}genschuh, Armin and Junosza-Szaniawski, Konstanty and Klug, Torsten and Kwasiborski, Slawomir and Schlechte, Thomas}, title = {Fastest, average and quantile schedule}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-53592}, abstract = {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.}, language = {en} } @misc{HillerKlugTuchscherer, author = {Hiller, Benjamin and Klug, Torsten and Tuchscherer, Andreas}, title = {Improving the performance of elevator systems using exact reoptimization algorithms}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11155}, number = {09-05}, abstract = {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.}, language = {en} } @misc{BorndoerferDenissenHelleretal., author = {Bornd{\"o}rfer, Ralf and Denißen, Jonas and Heller, Simon and Klug, Torsten and K{\"u}pper, Michael and Lindner, Niels and Reuther, Markus and Schlechte, Thomas and S{\"o}hlke, Andreas and Steadman, William}, title = {Microscopic Timetable Optimization for a Moving Block System}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82547}, abstract = {We present an optimization model which is capable of routing and ordering trains on a microscopic level under a moving block regime. Based on a general timetabling definition (GTTP) that allows the plug in of arbitrarily detailed methods to compute running and headway times, we describe a layered graph approach using velocity expansion, and develop a mixed integer linear programming formulation. Finally, we present promising results for a German corridor scenario with mixed traffic, indicating that applying branch-and-cut to our model is able to solve reasonably sized instances with up to hundred trains to optimality.}, language = {en} } @inproceedings{KlugJunoszaSzaniawskiKwasiborskietal., author = {Klug, Torsten and Junosza-Szaniawski, Konstanty and Kwasiborski, Slawomir and F{\"u}genschuh, Armin and Schlechte, Thomas}, title = {Fastest, Average and Quantile Schedule}, series = {SOFSEM 2015: Theory and Practice of Computer Science}, booktitle = {SOFSEM 2015: Theory and Practice of Computer Science}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/978-3-662-46078-8_17}, pages = {201 -- 216}, abstract = {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.}, language = {en} } @inproceedings{KlugReutherSchlechte, author = {Klug, Torsten and Reuther, Markus and Schlechte, Thomas}, title = {Does Laziness Pay Off? - A Lazy-Constraint Approach to Timetabling}, series = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, volume = {106}, booktitle = {22nd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2022)}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, doi = {10.4230/OASIcs.ATMOS.2022.11}, pages = {11:1 -- 11:8}, abstract = {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.}, language = {en} } @inproceedings{HillerKlugWitzig, author = {Hiller, Benjamin and Klug, Torsten and Witzig, Jakob}, title = {Reoptimization in branch-and-bound algorithms with an application to elevator control}, series = {Proceedings of the 12th International Symposium on Experimental Algorithms}, volume = {7933}, booktitle = {Proceedings of the 12th International Symposium on Experimental Algorithms}, doi = {10.1007/978-3-642-38527-8_33}, pages = {378 -- 389}, language = {en} } @misc{HillerKlugWitzig, author = {Hiller, Benjamin and Klug, Torsten and Witzig, Jakob}, title = {Reoptimization in branch-and-bound algorithms with an application to elevator control}, issn = {1438-0064}, doi = {10.1007/978-3-642-38527-8_33}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17876}, abstract = {We consider reoptimization (i.e. the solution of a problem based on information available from solving a similar problem) for branch-and-bound algorithms and propose a generic framework to construct a reoptimizing branch-and-bound algorithm. We apply this to an elevator scheduling algorithm solving similar subproblems to generate columns using branch-and-bound. Our results indicate that reoptimization techniques can substantially reduce the running times of the overall algorithm.}, language = {en} }