90B06 Transportation, logistics
Refine
Year of publication
Document Type
- ZIB-Report (54)
- Master's Thesis (3)
- Habilitation (1)
Has Fulltext
- yes (58)
Is part of the Bibliography
- no (58)
Keywords
- column generation (8)
- Optimierung (7)
- line planning (5)
- online optimization (5)
- real-time (5)
- ADAC (4)
- competitive analysis (4)
- soft time windows (4)
- vehicle dispatching (4)
- Column Generation (3)
- Competitive Analysis (3)
- Integer Programming (3)
- Online Optimization (3)
- Optimization (3)
- combinatorial optimization (3)
- elevator (3)
- integer programming (3)
- online (3)
- public transport (3)
- Fallstudie (2)
- Linienplan (2)
- Linienplanung (2)
- Netzwerkaggregation (2)
- Online-Optimierung (2)
- Passenger routing (2)
- Periodic timetabling (2)
- Public transport (2)
- Train Timetabling Problem (2)
- Vehicle Routing Problem (2)
- branch and bound (2)
- elevator group control (2)
- network aggregation (2)
- polyhedral combinatorics (2)
- pricing (2)
- railway track allocation (2)
- rapid branching (2)
- real world data (2)
- real-world problems (2)
- öffentlicher Verkehr (2)
- Aufzugsgruppensteuerung (1)
- Aufzugssteuerung (1)
- Aufzüge (1)
- Automatic Storage System (1)
- Bicriteria Optimization (1)
- Bundle Method (1)
- Constraint Shortest Paths Problem (1)
- Container Terminal (1)
- Data Library (1)
- Dial-a-Ride problem on trees (1)
- Dial-a-Ride-Problem (1)
- Dienstplanung (1)
- Discrete Mathematics (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Duty Scheduling (1)
- Echtzeit-Optimierung (1)
- Echzeitoptimierung (1)
- Exakte Reoptimierung (1)
- Fahrplan (1)
- Fahrplanung (1)
- Flugzeugumlaufplanung (1)
- Ganzzahlige Programmierung (1)
- Heuristics (1)
- Hochregallagerbediengeräte (1)
- Intermediate Storage Area (1)
- Kommissioniermobile (1)
- Kompetitive Analyse (1)
- Landside operation (1)
- Latency (1)
- Logistik (1)
- Nahverkehr (1)
- Online Algorithmen (1)
- Online Optimierung (1)
- Online optimization (1)
- Online-Algorithm (1)
- Online-Algorithms (1)
- Onlineoptimierung (1)
- Operations Research (1)
- Preisplanung (1)
- Problembibliothek (1)
- Proximale Bündelmethode (1)
- Railway Track Allocation (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (1)
- Realtime Optimization (1)
- Robust Optimization (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Simulation (1)
- Spaltenerzeugung (1)
- Storage space allocation (1)
- Survey (1)
- Tail Assignment (1)
- Taktfahrplan (1)
- Toll Enforcement (1)
- Transportation Systems (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Traveling Repairman (1)
- Traveling Salesman Problem (1)
- Vehicle Routing (1)
- Yard crane scheduling (1)
- Zielorientierte Planung (1)
- Zielrufsteuerung (1)
- applications of integer programming (1)
- bundle method (1)
- case study (1)
- competitiveness (1)
- computational complexity (1)
- convex relaxation (1)
- destination call system (1)
- discrete optimization (1)
- diskrete Optimierung (1)
- duty scheduling (1)
- duty templates (1)
- elevator control (1)
- exact reoptimation (1)
- ganzzahlige Programmierung (1)
- high load (1)
- hyperassignments (1)
- hypergraphs (1)
- kompetitive Analyse (1)
- large scale optimization (1)
- large scale problems (1)
- logistics (1)
- lower bounds (1)
- macroscopic railway modeling (1)
- makroskopische Bahnmodellierung (1)
- mixed-integer-programming (1)
- network models (1)
- online algorithms (1)
- optimality gap (1)
- passenger routing (1)
- periodic timetable (1)
- policy (1)
- probabilistic analysis (1)
- public transit (1)
- public transportation (1)
- railways (1)
- randomized algorithms (1)
- real time optimation (1)
- reoptimization (1)
- robuste Optimierung (1)
- rolling-stock-planning (1)
- set covering (1)
- set packing (1)
- set partitioning (1)
- simulation (1)
- simulation studies (1)
- stochastic demand (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- timetabling (1)
- transportation planning (1)
- trip timetable (1)
- vehicle rotation planning (1)
- vehicle routing (1)
Institute
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).
This extended abstract is about algorithms for controlling elevator systems employing destination hall calls, i.e. the passenger provides his destination floor when calling an elevator. We present the first exact algorithm for controlling a group of elevators and report on simulation results indicating that destination hall call systems outperform conventional systems.
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.
We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis.
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'.
Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.