90B06 Transportation, logistics
Refine
Year of publication
Document Type
- ZIB-Report (24)
- Habilitation (1)
Has Fulltext
- yes (25)
Is part of the Bibliography
- no (25) (remove)
Keywords
- Optimierung (5)
- column generation (3)
- public transport (3)
- Column Generation (2)
- Fallstudie (2)
- Integer Programming (2)
- Linienplan (2)
- Linienplanung (2)
- Netzwerkaggregation (2)
- Passenger routing (2)
Institute
- Mathematical Optimization (25) (remove)
Umsteigen ohne Warten
(2017)
Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter
Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.
The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems.
Wir illustrieren anhand des Liniennetzes der Stadt Potsdam das Potenzial mathematischer Methoden der Angebotsplanung. Wir zeigen,
dass das "bestmögliche" Verkehrsangebot stark von planerischen Vorgaben beeinflusst wird, mit denen man die Erreichung unterschiedlicher und teilweise gegenläufiger Ziele steuern kann. Die Komplexität des Systems führt zum Auftreten von Rückkoppelungseffekten, die man nicht mit Hilfe von Daumenregeln beherrschen kann. Vielmehr ist der Einsatz moderner Planungsverfahren in einer interdisziplinären Zusammenarbeit von politischen Entscheidungsträgern, Verkehrsingenieuren und Mathematikern notwendig, um die aktuellen Herausforderungen in der Verkehrsplanung zu meistern. Der Artikel dokumentiert einen Beitrag zum 7. ÖPNV Innovationskongress des Ministeriums für Verkehr und Infrastruktur des Landes Baden-Württemberg, der vom 9.-11. März 2015 in Freiburg stattfand.
The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.
Mathematik im Verkehr
(2014)
Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.
We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to
feasible rosters for one month. We present computational results in a
case-study on a German subnetwork which documents the practicability of our approach.
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.
Rapid Branching
(2012)
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.
Duty Scheduling Templates
(2012)
We propose duty templates as a novel concept to produce similar duty
schedules for similar days of operation in public transit. Duty templates
can conveniently handle various types of similarity requirements, and
they can be implemented with ease using standard algorithmic techniques.
They have produced good results in practice.
Vehicle rotation planning is a fundamental problem in
rail transport. It decides how the railcars, locomotives, and
carriages are operated in order to implement the trips of the
timetable. One important planning requirement is operational
regularity, i.e., using the rolling stock in the same way on every
day of operation. We propose to take regularity into account by
modeling the vehicle rotation planning problem as a minimum cost
hyperassignment problem (HAP). Hyperassignments are generalizations
of assignments from directed graphs to directed hypergraphs.
Finding a minimum cost hyperassignment is
NP-hard.
Most instances arising from regular vehicle rotation planning, however, can
be solved well in practice. We show that, in particular, clique
inequalities strengthen the canonical LP relaxation substantially.
Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft
mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der
Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010.
Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB)
entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in
einer projektbegleitenden Studie eingesetzt, um Alternativen bei
verschiedenen Planungs- und Zielvorgaben auszuloten.
In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verkürzung der Reisezeit um 1%, eine
als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im
Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind.
This paper proposes the first model for toll enforcement optimization
on German motorways. The enforcement is done by mobile control teams and our
goal is to produce a schedule achieving network-wide control, proportional to
spatial and time-dependent traffic distributions. Our model consists of two
parts. The first plans
control tours using a vehicle routing approach with profits and some side
constraints. The second plans feasible rosters for the control teams. Both
problems can be modeled as Multi-Commodity Flow Problems. Adding additional
coupling constraints produces a large-scale integrated integer programming
formulation. We show that this model can be solved to optimality for real
world instances associated with a control area in East Germany.
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.
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.
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.
Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berücksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 für Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es möglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen.
Robust Tail Assignment
(2010)
We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.
Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and “scream” for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today’s challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
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.
Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.
The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.
The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.