@article{SchlechteBorndoerferEroletal., author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Swarat, Elmar}, title = {Micro-macro transformation of railway networks}, series = {Journal of Rail Transport Planning \& Management}, volume = {1}, journal = {Journal of Rail Transport Planning \& Management}, number = {1}, doi = {10.1016/j.jrtpm.2011.09.001}, pages = {38 -- 48}, abstract = {In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.}, 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} } @article{Schlechte, author = {Schlechte, Thomas}, title = {Railway Track Allocation - Simulation and Optimization}, series = {Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR)}, volume = {4}, journal = {Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR)}, abstract = {Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway infrastructure provider. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market. This leads to an increase of slot requests and then it is natural that conflicts occur among them. Furthermore, railway infrastructure networks consist of very expensive assets, even more they are rigid due to the long-term upgrade process. In order to make best use of these valuable infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithmic methodology can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and a general framework to support the integration of simulation and optimization for railway capacity allocation.}, language = {en} } @article{SahinAhmadiBorndoerferetal., author = {Sahin, Guvenc and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Multi-period line planning with resource transfers}, series = {Transportation Research Part C: Emerging Technologies}, volume = {119}, journal = {Transportation Research Part C: Emerging Technologies}, doi = {10.1016/j.trc.2020.102726}, pages = {102726}, abstract = {Urban transportation systems are subject to a high level of variation and fluctuation in demand over the day. When this variation and fluctuation are observed in both time and space, it is crucial to develop line plans that are responsive to demand. A multi-period line planning approach that considers a changing demand during the planning horizon is proposed. If such systems are also subject to limitations of resources, a dynamic transfer of resources from one line to another throughout the planning horizon should also be considered. A mathematical modelling framework is developed to solve the line planning problem with a cost-oriented approach considering transfer of resources during a finite length planning horizon of multiple periods. We use real-life public transportation network data for our computational results. We analyze whether or not multi-period solutions outperform single period solutions in terms of feasibility and relevant costs. The importance of demand variation on multi-period solutions is investigated. We evaluate the impact of resource transfer constraints on the effectiveness of solutions. We also study the effect of period lengths along with the problem parameters that are significant for and sensitive to the optimality of solutions.}, language = {en} } @article{RaackRaymondSchlechteetal.2013, author = {Raack, Christian and Raymond, Annie and Schlechte, Thomas and Werner, Axel}, title = {Standings in sports competitions using integer programming}, series = {Journal of Quantitative Analysis in Sports}, volume = {10}, journal = {Journal of Quantitative Analysis in Sports}, number = {2}, publisher = {De Gruyter}, doi = {10.1515/jqas-2013-0111}, pages = {131 -- 137}, year = {2013}, language = {en} } @article{HeinzSchlechteStephanetal., author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, series = {Constraints}, volume = {17}, journal = {Constraints}, number = {1}, doi = {10.1007/s10601-011-9113-8}, pages = {39 -- 50}, abstract = {The steel mill slab design problem from the CSPLIB is a combinatorial optimization problem motivated by an application of the steel industry. It has been widely studied in the constraint programming community. Several methods were proposed to solve this problem. A steel mill slab library was created which contains 380 instances. A closely related binpacking problem called the multiple knapsack problem with color constraints, originated from the same industrial problem, was discussed in the integer programming community. In particular, a simple integer program for this problem has been given by Forrest et al. (INFORMS J Comput 18:129-134, 2006). The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. (INFORMS J Comput 18:129-134, 2006) for the steel mill slab design problem. Using this model and a state-of-the-art integer program solver all instances of the steel mill slab library can be solved efficiently to optimality. We improved, thereby, the solution values of 76 instances compared to previous results (Schaus et al., Constraints 16:125-147, 2010). Finally, we consider a recently introduced variant of the steel mill slab design problem, where within all solutions which minimize the leftover one is interested in a solution which requires a minimum number of slabs. For that variant we introduce two approaches and solve all instances of the steel mill slab library with this slightly changed objective function to optimality.}, language = {en} } @article{HarrodSchlechte, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, series = {Transportation Research Part E: Logistics and Transportation Review}, volume = {54}, journal = {Transportation Research Part E: Logistics and Transportation Review}, doi = {10.1016/j.tre.2013.04.003}, pages = {50 -- 66}, abstract = {Two fundamental mathematical formulations for railway timetabling are compared on a common set of sample problems, representing both multiple track high density services in Europe and single track bidirectional operations in North America. One formulation, ACP, enforces against conflicts by constraining time intervals between trains, while the other formulation, RCHF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and RCHF return comparable solutions in the aggregate, with some significant differences in select instances, and a pattern of significant differences in performance and constraint enforcement overall.}, 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} } @article{BreugemSchlechteSchulzetal., author = {Breugem, Thomas and Schlechte, Thomas and Schulz, Christof and Bornd{\"o}rfer, Ralf}, title = {A three-phase heuristic for the Fairness-Oriented Crew Rostering Problem}, series = {Computers \& Operations Research}, volume = {154}, journal = {Computers \& Operations Research}, doi = {https://doi.org/10.1016/j.cor.2023.106186}, abstract = {The Fairness-Oriented Crew Rostering Problem (FCRP) considers the joint optimization of attractiveness and fairness in cyclic crew rostering. Like many problems in scheduling and logistics, the combinatorial complexity of cyclic rostering causes exact methods to fail for large-scale practical instances. In case of the FCRP, this is accentuated by the additionally imposed fairness requirements. Hence, heuristic methods are necessary. We present a three-phase heuristic for the FCRP combining column generation techniques with variable-depth neighborhood search. The heuristic exploits different mathematical formulations to find feasible solutions and to search for improvements. We apply our methodology to practical instances from Netherlands Railways (NS), the main passenger railway operator in the Netherlands Our results show the three-phase heuristic finds good solutions for most instances and outperforms a state-of-the-art commercial solver.}, language = {en} } @article{BorndoerferSchlechteSwarat, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {Railway Track Allocation -- Simulation, Aggregation, and Optimization}, series = {Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011)}, volume = {2}, journal = {Proc. 1st International Workshop on High-speed and Intercity Railways (IWHIR 2011)}, number = {148}, doi = {10.1007/978-3-642-27963-8}, pages = {53 -- 70}, abstract = {Today the railway timetabling process and the track allocation is one of the most challenging problems to solve by a railway company. Especially due to the deregulation of the transport market in the recent years several suppliers of railway traffic have entered the market in Europe. This leads to more potential conflicts between trains caused by an increasing demand of train paths. Planning and operating railway transportation systems is extremely hard due to the combinatorial complexity of the underlying discrete optimization problems, the technical intricacies, and the immense size of the problem instances. In order to make best use of the infrastructure and to ensure economic operation, efficient planning of the railway operation is indispensable. Mathematical optimization models and algorithms can help to automatize and tackle these challenges. Our contribution in this paper is to present a renewed planning process due to the liberalization in Europe and an associated concept for track allocation, that consists of three important parts, simulation, aggregation, and optimization. Furthermore, we present results of our general framework for real world data.}, language = {en} }