Trassenbörse
Refine
Year of publication
Document Type
- In Proceedings (12)
- ZIB-Report (11)
- Article (7)
- Book (2)
- Habilitation (1)
- Proceedings (1)
Language
- English (34)
Is part of the Bibliography
- no (34)
Keywords
Institute
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
Running and optimizing transportation systems give rise to very complex and large-scale optimization problems requiring innovative solution techniques and ideas from mathematical optimization, theoretical computer science, and operations research. Since 2000, the series of Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS) workshops brings together researchers and practitioners who are interested in all aspects of algorithmic methods and models for transportation optimization and provides a forum for the exchange and dissemination of new ideas and techniques. The scope of ATMOS comprises all modes of transportation.
The 18th ATMOS workshop (ATMOS’18) was held in connection with ALGO’18 and hosted by Aalto University in Helsinki, Finland, on August 23–24, 2018. Topics of interest were all optimization problems for passenger and freight transport, including, but not limited to, demand forecasting, models for user behavior, design of pricing systems, infrastructure planning, multi-modal transport optimization, mobile applications for transport, congestion modelling and reduction, line planning, timetable generation, routing and platform assignment, vehicle scheduling, route planning, crew and duty scheduling, rostering, delay management, routing in road networks, traffic guidance, and electro mobility. Of particular interest were papers applying and advancing techniques like graph and network algorithms, combinatorial optimization, mathematical programming, approximation algorithms, methods for the integration of planning stages, stochastic and robust optimization, online and real-time algorithms, algorithmic game theory, heuristics for real-world instances, and simulation tools.
There were twenty-nine submissions from eighteen countries. All of them were reviewed by at least three referees in ninety-one reviews, among them five external ones, and judged on their originality, technical quality, and relevance to the topics of the workshop. Based on the reviews, the program committee selected sixteen submissions to be presented at the workshop (acceptance rate: 55%), which are collected in this volume in the order in which they were presented. Together, they quite impressively demonstrate the range of applicability of algorithmic optimization to transportation problems in a wide sense. In addition, Dennis Huisman kindly agreed to complement the program with an invited talk on Railway Disruption Management: State-of-the-art in practice and new research directions. Based on the reviews, Ralf Borndörfer, Marika Karbstein, Christian Liebchen, and Niels Lindner won the Best Paper Award of ATMOS’18 with their paper A simple way to compute the number of vehicles that Are required to operate a periodic timetable. In addition, we awarded Tomas Lidén the Best VGI Paper Award of ATMOS’18 for his paper Reformulations for railway traffic and maintenance planning.
We would like to thank the members of the Steering Committee of ATMOS for giving us the opportunity to serve as Program Chairs of ATMOS’18, all the authors who submitted papers, Dennis Huisman for accepting our invitation to present an invited talk, the members of the Program Committee and the additional reviewers for their valuable work in selecting the papers appearing in this volume, our sponsors MODAL, TomTom, and VGIscience for their support of the prizes, and the local organizers for hosting the workshop as part of ALGO’18. We acknowledge the use of the EasyChair system for the great help in managing the submission and review processes, and Schloss Dagstuhl for publishing the proceedings of ATMOS’18 in its OASIcs series.
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.
Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.
Railway transportation and in particular train timetabling is one of the basic and source application areas of combinatorial optimization and integer programming. We will discuss two well established modeling techniques for the train timetabling problem. In this paper we focus on one major ingredient - the bounding by dual relaxations. We compare two classical dual relaxations of large scale time expanded train timetabling problems - the Lagrangean Dual and Lagrangean Decomposition. We discuss the convergence behavior and show limitations of the Lagrangean Decomposition approach for a configuration based model. We introduce a third dualization approach to overcome those limitations. Finally, we present promising preliminary computational experiments that show that our new approach indeed has superior convergence properties.
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 inconveniently by underestimating the global optimal value.
Railway Track Allocation
(2012)
Rapid Branching
(2013)
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.
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.
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.
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.
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.
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.
Railway Track Allocation
(2012)
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.
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.
This cumulative thesis collects the following six papers for obtaining the
habilitation at the Technische Universität Berlin, Fakultät II – Mathematik
und Naturwissenschaften:
(1) Set packing relaxations of some integer programs.
(2) Combinatorial packing problems.
(3) Decomposing matrices into blocks.
(4) A bundle method for integrated multi-depot vehicle and duty scheduling
in public transit.
(5) Models for railway track allocation.
(6) A column-generation approach to line planning in public transport.
Some changes were made to the papers compared to the published versions.
These pertain to layout unifications, i.e., common numbering, figure, table,
and chapter head layout. There were no changes with respect to notation or
symbols, but some typos have been eliminated, references updated, and some
links and an index was added. The mathematical content is identical.
The papers are about the optimization of public transportation systems,
i.e.,
bus networks, railways, and airlines, and its mathematical foundations,
i.e.,
the theory of packing problems. The papers discuss mathematical models,
theoretical analyses, algorithmic approaches, and computational aspects of
and to problems in this area.
Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of
packing problems as a general framework that can be used to study traffic
optimization problems. Indeed, traffic optimization problems can often be
modelled as path packing, partitioning, or covering problems, which lead
directly to set packing, partitioning, and covering models. Such models are
used in papers 4, 5, and 6 to study a variety of problems concerning the
planning
of line systems, buses, trains, and crews. The common aim is always
to exploit as many degrees of freedom as possible, both at the level of the
individual problems by using large-scale integer programming techniques, as
well as on a higher level by integrating hitherto separate steps in the
planning
process.
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.
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.
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.
Railway scheduling is based on the principle of the construction of a conflict-free timetable. This leads to a strict definition of capacity: in contrast with road transportation, it can be said in advance whether a given railway infrastructure can accommodate - at least in theory - a certain set of train requests. Consequently, auctions for railway capacity are modeled as auctions of discrete goods -- the train slots. We present estimates for the efficiency gain that may be generated by slot auctioning in comparison with list price allocation. We introduce a new class of allocation and auction problems, the feasible assignment problem, that is a proper generalization of the well-known combinatorial auction problem. The feasible assignment class was designed to cover the needs for an auction mechanism for railway slot auctions, but is of interest in its own right. As a practical instance to state and solve the railway slot allocation problem, we present an integer programming formulation, briefly the ACP, which turns out to be an instance of the feasible assignment problem and whose dual problem yields prices that can be applied to define a useful activity rule for the linearized version of the Ausubel Milgrom Proxy auction. We perform a simulation aiming to measure the impact on efficiency and convergence rate.
Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional $\epsilon$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.
This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.
We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.