Transcription
Railway Track Allocation: Models andAlgorithmsvorgelegt vonDipl.-Math. oec. Thomas Schlechteaus Halle an der SaaleVon der Fakultät II – Mathematik und Naturwissenschaftender Technischen Universität Berlinzur Erlangung des akademischen GradesDoktor der Naturwissenschaften– Dr. rer. nat. –genehmigte DissertationPromotionsausschussBerichter: Prof. Dr. Dr. h. c. mult. Martin GrötschelPD Dr. habil. Ralf BorndörferVorsitzender: Prof. Dr. Fredi TröltzschTag der wissenschaftlichen Aussprache: 21.12.2011Berlin 2012D 83
Railway Track Allocation: Modelsand AlgorithmsThomas Schlechte
PrefaceThe “heart” of a railway system is the timetable. Each railway operator has to decide on the timetable to offer and on the rolling stock tooperate the trips of the trains. For the railway infrastructure managerthe picture is slightly different – trains have to be allocated to railway tracks and times, called slots such that all passenger and freighttransport operators are satisfied and all train movements can be carried out safely. This problem is called the track allocation problem. Mythesis deals with integer programming models and algorithmic solutionmethods for the track allocation problem in real world railway systems.My work on this topic has been initiated and motivated by the interdisciplinary research project “railway slot allocation” or in German“Trassenbörse”.1 This project investigated the question whether a competitive marketing of a railway infrastructure can be achieved using anauction-based allocation of railway slots. The idea is that competingtrain operating companies (TOCs) can bid for any imaginable use ofthe infrastructure. Possible conflicts will be resolved in favor of theparty with the higher willingness to pay, which leads directly to thequestion of finding revenue maximal track allocations. Moreover afair and transparent mechanism “cries” out for exact optimization approaches, because otherwise the resulting allocation is hardly acceptable and applicable in practice. This leads to challenging questionsin economics, railway engineering, and mathematical optimization. Inparticular, developing models that build a bridge between the abstractworld of mathematics and the technical world of railway operationswas an exciting task.I worked on the “Trassenbörse” project with partners from different areas, namely, on economic problems with the Workgroup for Economicand Infrastructure Policy (WIP) at the Technical University of Berlin(TU Berlin), on railway aspects with the Chair of Track and Railway Operations (SFWBB) at TU Berlin, the Institute of Transport,Railway Construction and Operation (IVE) at the Leibniz UniversitätHannover, and the Management Consultants Ilgmann Miethner Partner (IMP).1This project was funded by the Federal Ministry of Education and Research(BMBF), Grant number 19M2019 and the Federal Ministry of Economics and Technology (BMWi), Grant number 19M4031A and Grant number 19M7015B.i
This thesis is written from the common perspective of all persons Iworked closely with, especially the project heads Ralf Borndörfer andMartin Grötschel, project partners Gottfried Ilgmann and KlemensPolatschek, and the ZIB colleagues Berkan Erol, Elmar Swarat, andSteffen Weider.The highlight of the project was a cooperation with the SchweizerischeBundesbahnen (SBB) on optimizing the cargo traffic through the Simplon tunnel, one of the major transit routes in the Alps. This real worldapplication was challenging in many ways. It provides the opportunityto verify the usefulness of our methods and algorithms by computinghigh quality solutions in a fully automatic way.The material covered in this thesis has been presented at several international conferences, e.g., European Conference on Operational Research (EURO 2009, 2010), Conference on Transportation Schedulingand Disruption Handling, Workshop on Algorithmic Approaches forTransportation Modeling, Optimization, and System (ATMOS 2007,2010), International Seminar on Railway Operations Modeling andAnalysis (ISROR 2007, 2009, 2011), Symposium on Operations Research (OR 2005, 2006, 2007, 2008), International Conference on Computer System Design and Operation in the Railway and other TransitSystems (COMPRAIL), International Conference on Multiple CriteriaDecision Making (MCDM), World Conference on Transport Research(WCTR). Significant parts have already been published in various refereed conference proceedings and journals:.Borndörfer et al. (2006) [34],Borndörfer et al. (2005) [33],Borndörfer & Schlechte (2007) [31],Borndörfer & Schlechte (2007) [30],Erol et al. (2008) [85],Schlechte & Borndörfer (2008) [188],Borndörfer, Mura & Schlechte (2009) [40],Borndörfer, Erol & Schlechte (2009) [38],Schlechte & Tanner (2010) [189]3 ,Borndörfer, Schlechte & Weider (2010) [43],Schlechte et al. (2011) [190],1and Borndörfer et al. (2010) [42]2 .1accepted by Journal of Rail Transport Planning & Management.accepted by Annals of Operations Research.3submitted to Research in Transportation Economics.2ii
Research Goals and ContributionsThe goal of the thesis is to solve real world track allocation problemsby exact integer programming methods. In order to establish a fair andtransparent railway slot allocation, exact optimization approaches arerequired, as well as accurate and reliable railway models. Integer programming based methods can provide excellent guarantees in practice.We successfully identified and tackled several tasks to achieve theseambitious goals:1. applying a novel modeling approach to the track allocation problem called “configuration” models and providing a mathematicalanalysis of the associated polyhedron,2. developing a sophisticated integer programming approach called“rapid branching” that highly utilizes the column generation technique and the bundle method to tackle large scale track allocationinstances,3. developing a Micro-Macro Transformation, i.e., a bottom-up aggregation, approach to railway models of different scale to produce a reliable macroscopic problem formulation of the track allocation problem,4. providing a study comparing the proposed methodology to formerapproaches, and,5. carrying out a comprehensive real world data study for the Simplon corridor in Switzerland of the “entire” optimal railway trackallocation framework.In addition, we present extensions to incorporate aspects of robustnessand we provide an integration and empirical analysis of railway slotallocation in an auction based framework.Thesis StructureA rough outline of the thesis is shown in Figure 1. It follows the“solution cycle of applied mathematics”. In a first step the real worldproblem is analyzed, then the track allocation problem is translatedinto a suitable mathematical model, then a method to solve the modelsiii
in an efficient way is developed, followed by applying the developedmethodology in practice to evaluate its performance. Finally, the loopis closed by re-translating the results back to the real world applicationand analyze them together with experts and practitioners.Main concepts on planning problems in railway transportation are presented in Chapter I. Railway modeling and infrastructure capacity isthe main topic of Chapter II. Chapter III focuses on the mathematicalmodeling and the solution of the track allocation problem. Finally,Chapter IV presents results for real world data as well as for ambitioushypothetical auctioning instances.iv
Chapter IPlanning in RailwayTransportation12345678IntroductionPlanning ProcessNetwork DesignFreight Service Network DesignLine PlanningTimetablingRolling Stock PlanningCrew SchedulingChapter IIRailway Modeling1 Microscopic Railway Modeling2 Macroscopic Railway Modeling3 Final Remarks and OutlookChapter IIIRailway TrackAllocation1 The Track Allocation Problem2 Integer Programming Models3 Branch and PriceChapter IVCase Studies1234Model ComparisonAlgorithmic IngredientsAuction ExperimentsThe Simplon CorridorFigure 1: Structure of the thesis.v
AbstractThis thesis is about mathematical optimization for the efficient useof railway infrastructure. We address the optimal allocation of theavailable railway track capacity – the track allocation problem. Thistrack 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 transportationsystems is extremely hard due to the combinatorial complexity of theunderlying discrete optimization problems, the technical intricacies,and the immense sizes of the problem instances. Mathematical modelsand optimization techniques can result in huge gains for both railwaycustomers and operators, e.g., in terms of cost reductions or servicequality improvements. We tackle this challenge by developing novelmathematical models and associated innovative algorithmic solutionmethods for large scale instances. This allows us to produce for thefirst time reliable solutions for a real world instance, i.e., the Simploncorridor in Switzerland.The opening chapter gives a comprehensive overview on railway planning problems. This provides insights into the regulatory and technicalframework, it discusses the interaction of several planning steps, andidentifies optimization potentials in railway transportation. The remainder of the thesis is comprised of two major parts.The first part (Chapter II) is concerned with modeling railway systems to allow for resource and capacity analysis. Railway capacity hasbasically two dimensions, a space dimension which are the physical infrastructure elements as well as a time dimension that refers to thetrain movements, i.e., occupation or blocking times, on the physicalinfrastructure. Railway safety systems operate on the same principleall over the world. A train has to reserve infrastructure blocks forsome time to pass through. Two trains reserving the same block ofthe 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 blockingtimes to allow for a conflict free allocation.There are microscopic models that describe the railway system extremely detailed and thorough. Microscopic models have the advantagevii
that the calculation of the running times and the energy consumptionof the trains is very accurate. A major strength of microscopic modelsis that almost all technical details and local peculiarities are adjustableand are taken into account. We describe the railway system on a microscopic scale that covers the behavior of trains and the safety systemcompletely and correctly. Those models of the railway infrastructureare already very large even for very small parts of the network. Thereason is that all signals, incline changes, and switches around a railwaystation have to be modeled to allow for precise running time calculations of trains. In general microscopic models are used in simulationtools which are nowadays present at almost all railway companies allover the world. The most important field of application is to validatea single timetable and to decide whether a timetable is operable andrealizable in practice. However, microscopic models are inappropriatefor mathematical optimization because of the size and the high levelof detail. Hence, most optimization approaches consider simplified, socalled macroscopic, models. The challenging part is to construct a reliable macroscopic model for the associated microscopic model and tofacilitate the transition between both models of different scale.In order to allocate railway capacity significant parts of the microscopicmodel can be transformed into aggregated resource consumption inspace and time. We develop a general macroscopic representation ofrailway systems which is based on minimal headway times for enteringtracks of train routes and which is able to cope with all relevant railwaysafety systems. We introduce a novel bottom-up approach to generatea macroscopic model by an automatic aggregation of simulation dataproduced by any microscopic model. The transformation aggregatesand shrinks the infrastructure network to a smaller representation, i.e.,it conserves all resource and capacity aspects of the results of the microscopic simulation by conservative rounding of all times. The mainadvantage of our approach is that we can guarantee that our macroscopic results, i.e., train routes, are feasible after re-transformation forthe original microscopic model. Because of the conservative roundingmacroscopic models tend to underestimate the capacity. We can control the accuracy of our macroscopic model by changing the used timediscretization. Finally, we provide a priori error estimations of ourtransformation algorithm, i.e., in terms of exceeding of running andheadway times.In the second and main part (Chapter III) of the thesis, the optimaltrack allocation problem for macroscopic models of the railway sysviii
tem is considered. The literature for related problems is surveyed. Agraph-theoretic model for the track allocation problem is developed. Inthat model optimal track allocations correspond to conflict-free pathsin special time-expanded graphs. Furthermore, we made considerableprogress on solving track allocation problems by two main features – anovel modeling approach for the macroscopic track allocation problemand algorithmic improvements based on the utilization of the bundlemethod.More specifically, we study four types of integer programming modelformulations for the track allocation problem: two standard formulations that model resource or block conflicts in terms of packing constraints, and two novel coupling or “configuration” formulations. Inboth cases variants with either arc variables or with path variables willbe presented. The key idea of the new formulation is to use additional“configuration” variables that are approp
2 Integer Programming Models 3 Branch and Price 1 Model Comparison 2 Algorithmic Ingredients 3 Auction Experiments 4 The Simplon Corridor Figure 1: Structure of the thesis. v. Abstract This thesis is about mathematical optimization for the e cient use of railway infrastructure. We address the optimal allocation of the available railway track capacity { the track allocation problem. This track .
