@inproceedings{GrimmBorndoerferReutheretal.2019, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas}, title = {A Cut Separation Approach for the Rolling Stock Rotation Problem with Vehicle Maintenance}, volume = {75}, booktitle = {19th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2019)}, editor = {Cacchiani, Valentina and Marchetti-Spaccamela, Alberto}, publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik}, address = {Dagstuhl, Germany}, doi = {10.4230/OASIcs.ATMOS.2019.1}, pages = {1:1 -- 1:12}, year = {2019}, abstract = {For providing railway services the company's railway rolling stock is one if not the most important ingredient. It decides about the number of passenger or cargo trips the company can offer, about the quality a passenger experiences the train ride and it is often related to the image of the company itself. Thus, it is highly desired to have the available rolling stock in the best shape possible. Moreover, in many countries, as Germany where our industrial partner DB Fernverkehr AG (DBF) is located, laws enforce regular vehicle inspections to ensure the safety of the passengers. This leads to rolling stock optimization problems with complex rules for vehicle maintenance. This problem is well studied in the literature for example see [Mar{\´o}ti and Kroon, 2005; G{\´a}bor Mar{\´o}ti and Leo G. Kroon, 2007], or [Cordeau et al., 2001] for applications including vehicle maintenance. The contribution of this paper is a new algorithmic approach to solve the Rolling Stock Rotation Problem for the ICE high speed train fleet of DBF with included vehicle maintenance. It is based on a relaxation of a mixed integer linear programming model with an iterative cut generation to enforce the feasibility of a solution of the relaxation in the solution space of the original problem. The resulting mixed integer linear programming model is based on a hypergraph approach presented in [Ralf Bornd{\"o}rfer et al., 2015]. The new approach is tested on real world instances modeling different scenarios for the ICE high speed train network in Germany and compared to the approaches of [Reuther, 2017] that are in operation at DB Fernverkehr AG. The approach shows a significant reduction of the run time to produce solutions with comparable or even better objective function values.}, language = {en} } @inproceedings{BorndoerferKarbsteinMehrgahrdtetal.2016, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Mehrgahrdt, Julika and Reuther, Markus and Schlechte, Thomas}, title = {The Cycle Embedding Problem}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_65}, pages = {465 -- 472}, year = {2016}, abstract = {Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.}, language = {en} } @inproceedings{RenkenAhmadiBorndoerferetal.2018, author = {Renken, Malte and Ahmadi, Amin and Bornd{\"o}rfer, Ralf and Sahin, Guvenc and Schlechte, Thomas}, title = {Demand-Driven Line Planning with Selfish Routing}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_91}, pages = {687 -- 692}, year = {2018}, abstract = {Bus rapid transit systems in developing and newly industrialized countries are often operated at the limits of passenger capacity. In particular, demand during morning and afternoon peaks is hardly or even not covered with available line plans. In order to develop demand-driven line plans, we use two mathematical models in the form of integer programming problem formulations. While the actual demand data is specified with origin-destination pairs, the arc-based model considers the demand over the arcs derived from the origin-destination demand. In order to test the accuracy of the models in terms of demand satisfaction, we simulate the optimal solutions and compare number of transfers and travel times. We also question the effect of a selfish route choice behavior which in theory results in a Braess-like paradox by increasing the number of transfers when system capacity is increased with additional lines.}, language = {en} } @inproceedings{SchadeSchlechteWitzig2018, author = {Schade, Stanley and Schlechte, Thomas and Witzig, Jakob}, title = {Structure-based Decomposition for Pattern-Detection for Railway Timetables}, booktitle = {Operations Research Proceedings 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_95}, pages = {715 -- 721}, year = {2018}, abstract = {We consider the problem of pattern detection in large scale railway timetables. This problem arises in rolling stock optimization planning in order to identify invariant sections of the timetable for which a cyclic rotation plan is adequate. We propose a dual reduction technique which leads to an decomposition and enumeration method. Computational results for real world instances demonstrate that the method is able to produce optimal solutions as fast as standard MIP solvers.}, language = {en} } @inproceedings{BorndoerferBreuerGrimmetal.2018, author = {Bornd{\"o}rfer, Ralf and Breuer, Matthias and Grimm, Boris and Reuther, Markus and Schade, Stanley and Schlechte, Thomas}, title = {Timetable Sparsification by Rolling Stock Rotation Optimization}, booktitle = {Operations Research 2017}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-89920-6_96}, pages = {723 -- 728}, year = {2018}, abstract = {Rolling stock optimization is a task that naturally arises by operating a railway system. It could be seen with different level of details. From a strategic perspective to have a rough plan which types of fleets to be bought to a more operational perspective to decide which coaches have to be maintained first. This paper presents a new approach to deal with rolling stock optimisation in case of a (long term) strike. Instead of constructing a completely new timetable for the strike period, we propose a mixed integer programming model that is able to choose appropriate trips from a given timetable to construct efficient tours of railway vehicles covering an optimized subset of trips, in terms of deadhead kilometers and importance of the trips. The decision which trip is preferred over the other is made by a simple evaluation method that is deduced from the network and trip defining data.}, language = {en} } @misc{BorndoerferScheltenSchlechteetal.2005, author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8713}, number = {05-37}, year = {2005}, abstract = {The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.}, language = {en} } @phdthesis{Schlechte2012, author = {Schlechte, Thomas}, title = {Railway Track Allocation: Models and Algorithms}, publisher = {S{\"u}dwestdeutscher Verlag f{\"u}r Hochschulschriften}, address = {Saarbr{\"u}cken, Germany}, isbn = {978-3-8381-3222-8}, url = {http://nbn-resolving.de/urn:nbn:de:kobv:83-opus-34272}, school = {Technische Universit{\"a}t Berlin}, pages = {239}, year = {2012}, abstract = {This thesis is about mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. 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 sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland. The opening chapter gives a comprehensive overview on railway planning problems. This provides insights into the regulatory and technical framework, it discusses the interaction of several planning steps, and identifies optimization potentials in railway transportation. The remainder of the thesis is comprised of two major parts. The first part is concerned with modeling railway systems to allow for resource and capacity analysis. Railway capacity has basically two dimensions, a space dimension which are the physical infrastructure elements as well as a time dimension that refers to the train movements, i.e., occupation or blocking times, on the physical infrastructure. Railway safety systems operate on the same principle all over the world. A train has to reserve infrastructure blocks for some time to pass through. Two trains reserving the same block of the infrastructure within the same point in time is called block conflict. Therefore, models for railway capacity involve the definition and calculation of reasonable running and associated reservation and blocking times to allow for a conflict free allocation. In the second and main part of the thesis, the optimal track allocation problem for macroscopic models of the railway system is considered. The literature for related problems is surveyed. A graph-theoretic model for the track allocation problem is developed. In that model optimal track allocations correspond to conflict-free paths in special time-expanded graphs. Furthermore, we made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. Finally, we go back to practice and present in the last chapter several case studies using the tools netcast and tsopt. We provide a computational comparison of our new models and standard packing models used in the literature. Our computational experience indicates that our approach, i.e., ``configuration models'', outperforms other models. Moreover, the rapid branching heuristic and the bundle method enable us to produce high quality solutions for very large scale instances, which has not been possible before. In addition, we present results for a theoretical and rather visionary auction framework for track allocation. We discuss several auction design questions and analyze experiments of various auction simulations. The highlights are results for the Simplon corridor in Switzerland. We optimized the train traffic through this tunnel using our models and software tools. To the best knowledge of the author and confirmed by several railway practitioners this was the first time that fully automatically produced track allocations on a macroscopic scale fulfill the requirements of the originating microscopic model, withstand the evaluation in the microscopic simulation tool OpenTrack, and exploit the infrastructure capacity. This documents the success of our approach in practice and the usefulness and applicability of mathematical optimization to railway track allocation.}, language = {en} } @article{BorndoerferGroetschelLukacetal.2006, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Lukac, Sascha and Mitusch, Kay and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {An Auctioning Approach to Railway Slot Allocation}, volume = {1}, journal = {Competition and Regulation in Network Industries}, number = {2}, pages = {163 -- 196}, year = {2006}, language = {en} } @misc{EbertSchlechteSchwartz2025, author = {Ebert, Patricia and Schlechte, Thomas and Schwartz, Stephan}, title = {Scheduling for German Road Inspectors}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-101999}, year = {2025}, abstract = {For the yearly over 500,000 vehicle inspections of the German Federal Logistics and Mobility Office (BALM), crew rosters must be scheduled to efficiently achieve Germany's road inspection control targets. For that, we present a model to solve the respective duty scheduling and crew rostering problem in order to obtain duty rosters that comply with numerous legal regulations while maximizing the 'control success' to achieve the control targets. We formulate the Template Assignment Problem, which can be modelled as a large scale mixed-integer linear program. Here, feasible combinations of control topics are assigned to the duties using a hypergraph approach. The model is used in production by BALM, and we prove its effectiveness on a number of real-world instances.}, language = {en} } @misc{ReutherBorndoerferSchlechteetal.2012, author = {Reuther, Markus and Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Integrated Optimization of Rolling Stock Rotations for Intercity Railways}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16424}, year = {2012}, abstract = {This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques.}, language = {en} } @misc{BorndoerferFuegenschuhKlugetal.2013, 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}, year = {2013}, 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} } @misc{BorndoerferDenissenHelleretal.2021, 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}, year = {2021}, 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{HeinzSchlechteStephanetal.2011, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, issn = {1438-0064}, doi = {10.1007/s10601-011-9113-8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-14089}, number = {11-38}, year = {2011}, 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. The aim of this paper is to bring these different studies together. Moreover, we adapt the model of Forrest et al. 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. 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} } @misc{HarrodSchlechte2013, author = {Harrod, Steven and Schlechte, Thomas}, title = {A Direct Comparison of Physical Block Occupancy Versus Timed Block Occupancy in Train Timetabling Formulations}, issn = {1438-0064}, doi = {10.1016/j.tre.2013.04.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17946}, year = {2013}, 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, HGF, monitors physical occupation of controlled track segments. The results demonstrate that both ACP and HGF 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} } @misc{Schlechte2011, author = {Schlechte, Thomas}, title = {Railway Track Allocation - Simulation and Optimization}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13632}, number = {11-32}, year = {2011}, 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} } @misc{RaackRaymondWerneretal.2013, author = {Raack, Christian and Raymond, Annie and Werner, Axel and Schlechte, Thomas}, title = {Integer Programming and Sports Rankings}, issn = {1438-0064}, doi = {10.1515/jqas-2013-0111}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18068}, year = {2013}, abstract = {Sports rankings are obtained by applying a system of rules to evaluate the performance of the participants in a competition. We consider rankings that result from assigning an ordinal rank to each competitor according to their performance. We develop an integer programming model for rankings that allows us to calculate the number of points needed to guarantee a team the ith position, as well as the minimum number of points that could yield the ith place. The model is very general and can thus be applied to many types of sports. We discuss examples coming from football (soccer), ice hockey, and Formula~1. We answer various questions and debunk a few myths along the way. Are 40 points enough to avoid relegation in the Bundesliga? Do 95 points guarantee the participation of a team in the NHL playoffs? Moreover, in the season restructuration currently under consideration in the NHL, will it be easier or harder to access the playoffs? Is it possible to win the Formula~1 World Championship without winning at least one race or without even climbing once on the podium? Finally, we observe that the optimal solutions of the aforementioned model are associated to extreme situations which are unlikely to happen. Thus, to get closer to realistic scenarios, we enhance the model by adding some constraints inferred from the results of the previous years.}, language = {en} } @misc{Schlechte2012, author = {Schlechte, Thomas}, title = {Railway Track Allocation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16402}, year = {2012}, abstract = {This article gives an overview of the results of the author's PhD thesis. The thesis deals with the mathematical optimization for the efficient use of railway infrastructure. We address the optimal allocation of the available railway track capacity - the track allocation problem. This track allocation problem is a major challenge for a railway company, independent of whether a free market, a private monopoly, or a public monopoly is given. 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 sizes of the problem instances. Mathematical models and optimization techniques can result in huge gains for both railway customers and operators, e.g., in terms of cost reductions or service quality improvements. We tackle this challenge by developing novel mathematical models and associated innovative algorithmic solution methods for large scale instances. We made considerable progress on solving track allocation problems by two main features - a novel modeling approach for the macroscopic track allocation problem and algorithmic improvements based on the utilization of the bundle method. This allows us to produce for the first time reliable solutions for a real world instance, i.e., the Simplon corridor in Switzerland.}, language = {en} } @misc{BorndoerferErolGraffagninoetal.2010, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Aggregation Methods for Railway Networks}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11881}, number = {10-23}, year = {2010}, 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} } @misc{BorndoerferErolGraffagninoetal.2010, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon Railway Corridor}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, doi = {10.1007/s10479-012-1260-9}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11892}, number = {10-24}, year = {2010}, abstract = {This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters.}, language = {en} } @misc{BorndoerferSchlechteWeider2010, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Weider, Steffen}, title = {Railway Track Allocation by Rapid Branching}, organization = {Zuse Institut Berlin}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11864}, number = {10-22}, year = {2010}, abstract = {The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.}, 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}, 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} } @inproceedings{Schlechte2012, author = {Schlechte, Thomas}, title = {Railway Track Allocation}, booktitle = {Operations Research Proceedings}, doi = {10.1007/978-3-319-00795-314}, pages = {15 -- 20}, year = {2012}, language = {en} } @article{BorndoerferReutherSchlechteetal.2012, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Vehicle Rotation Planning for Intercity Railways}, journal = {Proceedings of Conference on Advanced Systems for Public Transport 2012 (CASPT12)}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, year = {2012}, abstract = {This paper provides a generic formulation for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a graph theoretical model and a Mixed-Integer-Programming formulation that integrate all main requirements of the considered Vehicle-Rotation-Planning problem (VRPP). We show that it is possible to solve this model for real-world instances provided by our industrial partner DB Fernverkehr AG using modern algorithms and computers.}, language = {en} } @article{BorndoerferLoebelReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {Rapid Branching}, volume = {5}, journal = {Public Transport}, number = {1}, editor = {Mu{\~n}oz, J. C. and Voß, S.}, publisher = {Springer Berlin Heidelberg}, pages = {3 -- 23}, year = {2013}, abstract = {We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.}, language = {en} } @article{HeinzSchlechteStephanetal.2012, author = {Heinz, Stefan and Schlechte, Thomas and Stephan, R{\"u}diger and Winkler, Michael}, title = {Solving steel mill slab design problems}, volume = {17}, journal = {Constraints}, number = {1}, doi = {10.1007/s10601-011-9113-8}, pages = {39 -- 50}, year = {2012}, 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{BorndoerferSchlechteSwarat2012, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas and Swarat, Elmar}, title = {Railway Track Allocation -- Simulation, Aggregation, and Optimization}, 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}, year = {2012}, 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} } @article{BorndoerferReutherSchlechteetal.2011, author = {Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Weider, Steffen}, title = {A Hypergraph Model for Railway Vehicle Rotation Planning}, volume = {OpenAccess Series in Informatics (OASIcs)}, journal = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, number = {20}, doi = {10.4230/OASIcs.ATMOS.2011.146}, pages = {146 -- 155}, year = {2011}, abstract = {We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the ``regularity'' of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.}, language = {en} } @article{Schlechte2011, author = {Schlechte, Thomas}, title = {Railway Track Allocation - Simulation and Optimization}, volume = {4}, journal = {Proceedings of 4th International Seminar on Railway Operations Modelling and Analysis (IAROR)}, year = {2011}, 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{SchlechteBorndoerferEroletal.2011, author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Swarat, Elmar}, title = {Micro-macro transformation of railway networks}, volume = {1}, journal = {Journal of Rail Transport Planning \& Management}, number = {1}, doi = {10.1016/j.jrtpm.2011.09.001}, pages = {38 -- 48}, year = {2011}, 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} } @misc{BlancoSchlechte2013, author = {Blanco, Marco and Schlechte, Thomas}, title = {Analysis of Micro-Macro Transformations of Railway Networks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42710}, year = {2013}, abstract = {A common technique in the solution of large or complex optimization problems is the use of micro-macro transformations. In this paper, we carry out a theoretical analysis of such transformations for the track allocation problem in railway networks. We prove that the cumulative rounding technique of Schlechte et al. satisfies two of three natural optimality criteria and that this performance cannot be improved. We also show that under extreme circumstances, this technique can perform inconvieniently by underestimating the global optimal value.}, language = {en} } @misc{BorndoerferMehrgardtReutheretal.2013, author = {Bornd{\"o}rfer, Ralf and Mehrgardt, Julika and Reuther, Markus and Schlechte, Thomas and Waas, Kerstin}, title = {Re-optimization of Rolling Stock Rotations}, issn = {1438-0064}, doi = {10.1007/978-3-319-07001-8_8}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-42569}, year = {2013}, abstract = {The Rolling Stock Rotation Problem is to schedule rail vehicles in order to cover timetabled trips by a cost optimal set of vehicle rotations. The problem integrates several facets of railway optimization, i.e., vehicle composition, maintenance constraints, and regularity aspects. In industrial applications existing schedules often have to be re-optimized to integrate timetable changes or construction sites. We present an integrated modeling and algorithmic approach for this task as well as computational results for industrial problem instances of DB Fernverkehr AG.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal.2016, 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}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, year = {2016}, 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} } @inproceedings{BorndoerferGrimmReutheretal.2015, author = {Bornd{\"o}rfer, Ralf and Grimm, Boris and Reuther, Markus and Schlechte, Thomas}, title = {Template based re-optimization of rolling stock rotations}, booktitle = {Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015)}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57539}, year = {2015}, abstract = {Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented.}, language = {en} } @article{BorndoerferErolGraffagninoetal.2012, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Graffagnino, Thomas and Schlechte, Thomas and Swarat, Elmar}, title = {Optimizing the Simplon railway corridor}, volume = {218}, journal = {Annals of Operations Research}, number = {1}, edition = {Annals of Operations Research}, publisher = {Springer US}, doi = {10.1007/s10479-012-1260-9}, pages = {93 -- 106}, year = {2012}, language = {en} } @inproceedings{BorndoerferErolSchlechte2009, author = {Bornd{\"o}rfer, Ralf and Erol, Berkan and Schlechte, Thomas}, title = {Optimization of macroscopic train schedules via TS-OPT}, booktitle = {Proceedings of the 3rd International Seminar on Railway Operations Modelling and Analysis - Engineering and Optimisation Approaches}, editor = {Hansen, I. and Wendler, E. and Weidmann, U. and L{\"u}thi, M. and Rodriguez, J. and Ricci, S. and Kroon, Leo}, address = {Z{\"u}rich, Switzerland}, year = {2009}, language = {en} } @inproceedings{SchlechteTanner2010, author = {Schlechte, Thomas and Tanner, Andreas}, title = {Railway capacity auctions with dual prices}, booktitle = {Selected Proceedings of the 12th World Conference on Transport Research}, year = {2010}, language = {en} } @inproceedings{ErolKlemenzSchlechteetal.2008, author = {Erol, Berkan and Klemenz, Marc and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {TTPlib 2008 - A Library for Train Timetabling Problems}, booktitle = {Computers in Railways XI}, editor = {Tomii, A. and Allan, J. and Arias, E. and Brebbia, C. and Goodman, C. and Rumsey, A. and Sciutto, G.}, publisher = {WIT Press}, year = {2008}, language = {en} } @inproceedings{BorndoerferSchlechte2007, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Models for Railway Track Allocation}, volume = {07001}, booktitle = {ATMOS 2007 - 7th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems}, editor = {Liebchen, Christian and Ahuja, Ravindra and Mesa, Juan}, publisher = {Internationales Begegnungs- und Forschungszentrum f{\"u}r Informatik (IBFI), Schloss Dagstuhl, Germany}, year = {2007}, language = {en} } @inproceedings{BorndoerferSchlechte2008, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Balancing Efficiency and Robustness}, booktitle = {MCDM for Sustainable Energy and Transportation Systems}, editor = {Ehrgott, Matthias and Naujoks, Boris and Stewart, Theo and Wallenius, Jyrki}, publisher = {Lecture Notes in Economics and Mathematical Systems}, year = {2008}, language = {en} } @misc{Schlechte2003, type = {Master Thesis}, author = {Schlechte, Thomas}, title = {Das Resource-Constraint-Shortest-Path-Problem und seine Anwendung in der {\"O}PNV-Dienstplanung}, year = {2003}, language = {en} } @article{GilgKlugMartienssenetal.2018, 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}, journal = {Journal of Rail Transport Planning \& Management}, doi = {10.1016/j.jrtpm.2017.12.004}, year = {2018}, 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} } @incollection{ReutherSchlechte2018, author = {Reuther, Markus and Schlechte, Thomas}, title = {Optimization of Rolling Stock Rotations}, volume = {268}, booktitle = {Handbook of Optimization in the Railway Industry}, publisher = {Springer International Publishing}, isbn = {978-3-319-72152-1}, doi = {https://doi.org/10.1007/978-3-319-72153-8}, pages = {213 -- 241}, year = {2018}, abstract = {This chapter shows a successful approach how to model and optimize rolling stock rotations that are required for the operation of a passenger timetable. The underlying mathematical optimization problem is described in detail and solved by RotOR, i.e., a complex optimization algorithm based on linear programming and combinatorial methods. RotOR is used by DB Fernverkehr AG (DBF) in order to optimize intercity express (ICE) rotations for the European high-speed network. We focus on main modeling and solving components, i.e. a hypergraph model and a coarse-to-fine column generation approach. Finally, the chapter concludes with a complex industrial re-optimization application showing the effectiveness of the approach for real world challenges.}, language = {en} } @inproceedings{FischerSchlechte2017, author = {Fischer, Frank and Schlechte, Thomas}, title = {Strong Relaxations for the Train Timetabling Problem using Connected Configurations}, volume = {59}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, isbn = {978-3-95977-042-2}, doi = {10.4230/OASIcs.ATMOS.2017.11}, year = {2017}, abstract = {The task of the train timetabling problem or track allocation problem is to find conflict free schedules for a set of trains with predefined routes in a railway network. Especially for non-periodic instances models based on time expanded networks are often used. Unfortunately, the linear programming relaxation of these models is often extremely weak because these models do not describe combinatorial relations like overtaking possibilities very well. In this paper we extend the model by so called connected configuration subproblems. These subproblems perfectly describe feasible schedules of a small subset of trains (2-3) on consecutive track segments. In a Lagrangian relaxation approach we solve several of these subproblems together in order to produce solutions which consist of combinatorially compatible schedules along the track segments. The computational results on a mostly single track corridor taken from the INFORMS RAS Problem Solving Competition 2012 data indicate that our new solution approach is rather strong. Indeed, for this instance the solution of the Lagrangian relaxation is already integral.}, language = {en} } @inproceedings{BlancoBorndoerferHoangetal.2017, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Maristany de las Casas, Pedro and Schlechte, Thomas and Schlobach, Swen}, title = {Cost Projection Methods for the Shortest Path Problem with Crossing Costs}, volume = {59}, booktitle = {17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2017)}, editor = {D'Angelo, Gianlorenzo and Dollevoet, Twan}, year = {2017}, abstract = {Real world routing problems, e.g., in the airline industry or in public and rail transit, can feature complex non-linear cost functions. An important case are costs for crossing regions, such as countries or fare zones. We introduce the shortest path problem with crossing costs (SPPCC) to address such situations; it generalizes the classical shortest path problem and variants such as the resource constrained shortest path problem and the minimum label path problem. Motivated by an application in flight trajectory optimization with overflight costs, we focus on the case in which the crossing costs of a region depend only on the nodes used to enter or exit it. We propose an exact Two-Layer-Dijkstra Algorithm as well as a novel cost-projection linearization technique that approximates crossing costs by shadow costs on individual arcs, thus reducing the SPPCC to a standard shortest path problem. We evaluate all algorithms' performance on real-world flight trajectory optimization instances, obtaining very good {\`a} posteriori error bounds.}, language = {en} } @inproceedings{BorndoerferArslanElijazyferetal.2017, author = {Bornd{\"o}rfer, Ralf and Arslan, Oytun and Elijazyfer, Ziena and G{\"u}ler, Hakan and Renken, Malte and Sahin, Guvenc and Schlechte, Thomas}, title = {Line Planning on Path Networks with Application to the Istanbul Metrob{\"u}s}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_32}, pages = {235 -- 241}, year = {2017}, abstract = {Bus rapid transit systems in developing and newly industrialized countries often consist of a trunk with a path topology. On this trunk, several overlapping lines are operated which provide direct connections. The demand varies heavily over the day, with morning and afternoon peaks typically in reverse directions. We propose an integer programming model for this problem, derive a structural property of line plans in the static (or single period) ``unimodal demand'' case, and consider approaches to the solution of the multi-period version that rely on clustering the demand into peak and off-peak service periods. An application to the Metrob{\"u}s system of Istanbul is discussed.}, language = {en} } @inproceedings{SchwartzSchlechteSwarat2017, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_30}, pages = {217 -- 223}, year = {2017}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @inproceedings{FischerGrimmKlugetal.2017, author = {Fischer, Frank and Grimm, Boris and Klug, Torsten and Schlechte, Thomas}, title = {A Re-optimization Approach for Train Dispatching}, booktitle = {Operations Research Proceedings 2016}, doi = {10.1007/978-3-319-55702-1_85}, pages = {645 -- 651}, year = {2017}, 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} } @misc{BlancoBorndoerferHoangetal.2016, author = {Blanco, Marco and Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung and Kaier, Anton and Schlechte, Thomas and Schlobach, Swen}, title = {The Shortest Path Problem with Crossing Costs}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61240}, year = {2016}, abstract = {We introduce the shortest path problem with crossing costs (SPPCC), a shortest path problem in a directed graph, in which the objective function is the sum of arc weights and crossing costs. The former are independently paid for each arc used by the path, the latter need to be paid every time the path intersects certain sets of arcs, which we call regions. The SPPCC generalizes not only the classical shortest path problem but also variants such as the resource constrained shortest path problem and the minimum label path problem. We use the SPPCC to model the flight trajectory optimization problem with overflight costs. In this paper, we provide a comprehensive analysis of the problem. In particular, we identify efficient exact and approximation algorithms for the cases that are most relevant in practice.}, language = {en} } @misc{SchwartzSchlechteSwarat2016, author = {Schwartz, Stephan and Schlechte, Thomas and Swarat, Elmar}, title = {Designing Inspector Rosters with Optimal Strategies}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61123}, year = {2016}, abstract = {We consider the problem of enforcing a toll on a transportation network with limited inspection resources. We formulate a game theoretic model to optimize the allocation of the inspectors, taking the reaction of the network users into account. The model includes several important aspects for practical operation of the control strategy, such as duty types for the inspectors. In contrast to an existing formulation using flows to describe the users' strategies we choose a path formulation and identify dominated user strategies to significantly reduce the problem size. Computational results suggest that our approach is better suited for practical instances.}, language = {en} } @article{BorndoerferKlugLamorgeseetal.2017, 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}, volume = {74}, journal = {Transportation Research Part C: Emerging Technologies}, number = {1}, doi = {10.1016/j.trc.2016.11.015}, pages = {196 -- 211}, year = {2017}, 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{GrimmBorndoerferReutheretal.2016, author = {Grimm, Boris and Bornd{\"o}rfer, Ralf and Reuther, Markus and Schlechte, Thomas and Schade, Stanley}, title = {Regularity patterns for rolling stock rotation optimization}, volume = {8}, booktitle = {8th International Conference on Applied Operational Research, Proceedings}, pages = {28 -- 32}, year = {2016}, abstract = {The operation of railways gives rise to many fundamental optimization problems. One of these problems is to cover a given set of timetabled trips by a set of rolling stock rotations. This is well known as the Rolling Stock Rotation Problem (RSRP). Most approaches in the literature focus primarily on modeling and minimizing the operational costs. However, an essential aspect for the industrial application is mostly neglected. As the RSRP follows timetabling and line planning, where periodicity is a highly desired property, it is also desired to carry over periodic structures to rolling stock rotations and following operations. We call this complex requirement regularity. Regularity turns out to be of essential interest, especially in the industrial scenarios that we tackle in cooperation with DB Fernverkehr AG. Moreover, regularity in the context of the RSRP has not been investigated thoroughly in the literature so far. We introduce three regularity patterns to tackle this requirement, namely regular trips, regular turns, and regular handouts. We present a two-stage approach in order to optimize all three regularity patterns. At first, we integrate regularity patterns into an integer programming approach for the minimization of the operational cost of rolling stock rotations. Afterwards regular handouts are computed. These handouts present the rotations of the first stage in the most regular way. Our computational results (i.e., rolling stock rotations evaluated by planners of DB Fernverkehr AG) show that the three regularity patterns and our concept are a valuable and, moreover, an essential contribution to rolling stock rotation optimization.}, language = {en} }