1120
eng
reportzib
0
2009-02-25
2009-02-25
--
Discrete Optimization in Public Transportation
The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.
Die mathematische Behandlung von Planungsproblemen im öffentlichen Verkehr hat im letzten Jahrzehnt große Fortschritte gemacht. Klassische Probleme wie die Umlauf- und die Dienstplanung können heutzutage routinemäßig mit kombinatorischen Optimierungsmethoden gelöst werden. Die Behandlung von Problemen der Angebotsplanung und der Betriebssteuerung sind dagegen noch nicht ganz auf diesem Stand. Dieser Artikel gibt einen Überblick über den Stand der Forschung, über wichtige Entwicklungen und einige Herausforderungen in diesem Gebiet. Die Vision ist, dass mathematische Planungswerkzeuge im öffentlichen Verkehr (Computer Aided Scheduling, CAS) in Zukunft eine ähnliche Rolle spielen werden wie CAD-Systeme in der industriellen Fertigung.
08-56
1438-0064
1168
urn:nbn:de:0297-zib-11207
Ralf Borndörfer
unknown unknown
ZIB-Report
08-56
deu
uncontrolled
Öffentlicher Verkehr
deu
uncontrolled
Nahverkehr
deu
uncontrolled
Optimierung
eng
uncontrolled
Public Transit
eng
uncontrolled
Optimization
Mathematik
Traffic problems
Integer programming
Mathematical Optimization
Borndörfer, Ralf
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.pdf
https://opus4.kobv.de/opus4-zib/files/1120/ZR_08_56.ps
5027
deu
reportzib
0
--
2014-05-22
--
Integrierte Dienst- und Dienstreihenfolgeplanung zur Erhöhung der Fahrerzufriedenheit
Wir stellen einen mathematischen Optimierungsansatz zur integrierten Dienst- und Dienstreihenfolgeplanung
im öffentlichen Nahverkehr vor, mit dem sich bei konstanten Personalkosten
die Fahrerzufriedenheit deutlich steigern lässt.
1438-0064
urn:nbn:de:0297-zib-50270
Appeared in: Straßenverkehrstechnik. (2014) pp. 583-591
Ralf Borndörfer
Regine Kossick
Bastian Dittbrenner
Andreas Langenhan
Stephan Seidl
Steffen Weider
ZIB-Report
14-02
eng
uncontrolled
duty scheduling
eng
uncontrolled
duty rostering
eng
uncontrolled
integrated scheduling
eng
uncontrolled
Benders' decomposition
PHYSICAL SCIENCES AND ENGINEERING
Optimization
Traffic problems
Integer programming
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Weider, Steffen
WS-OPT
https://opus4.kobv.de/opus4-zib/files/5027/ZR-14-02.pdf
1188
eng
reportzib
Zuse Institut Berlin
0
2010-11-01
2010-11-01
--
Aggregation Methods for Railway Networks
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.
10-23
1438-0064
1251
http://www.sciencedirect.com/science/article/pii/S2210970611000047
urn:nbn:de:0297-zib-11881
A rev. vers. appeared in: Journal of Rail Transport Planning & Management 1(2011) 38-48
Ralf Borndörfer
unknown unknown
Berkan Erol
Thomas Graffagnino
Thomas Schlechte
Elmar Swarat
ZIB-Report
10-23
deu
uncontrolled
makroskopische Bahnmodellierung
deu
uncontrolled
Netzwerkaggregation
eng
uncontrolled
macroscopic railway modeling
eng
uncontrolled
network aggregation
Mathematik
Transportation, logistics
Traffic problems
Models of real-world systems
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
Swarat, Elmar
MATHEON-B22
Trassenbörse
https://opus4.kobv.de/opus4-zib/files/1188/ZR-10-23.pdf
1189
eng
reportzib
Zuse Institut Berlin
0
2010-11-01
2010-11-01
--
Optimizing the Simplon Railway Corridor
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.
10-24
1438-0064
1252
urn:nbn:de:0297-zib-11892
10.1007/s10479-012-1260-9
A rev. vers. appeared in: Annals of Operations Research, Dec. 2012
Ralf Borndörfer
unknown unknown
Berkan Erol
Thomas Graffagnino
Thomas Schlechte
Elmar Swarat
ZIB-Report
10-24
deu
uncontrolled
Trassenallokation
deu
uncontrolled
Netzwerkaggregation
deu
uncontrolled
Fallstudie
deu
uncontrolled
Simplon Korridor
eng
uncontrolled
railway track allocation
eng
uncontrolled
network aggregation
eng
uncontrolled
case study
eng
uncontrolled
Simplon corridor
Mathematik
Transportation, logistics
Traffic problems
Mixed integer programming
Combinatorial optimization
Models of real-world systems
Mathematical Optimization
Borndörfer, Ralf
Schlechte, Thomas
Swarat, Elmar
https://opus4.kobv.de/opus4-zib/files/1189/ZR-10-24.pdf
1448
deu
reportzib
0
2012-01-18
2012-01-18
--
Optimierung des Linienplans 2010 in Potsdam
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.
1438-0064
12-04
urn:nbn:de:0297-zib-14486
Erschienen in: Der Nahverkehr 30/4 (2012) 34-39
Ralf Borndörfer
Karbstein Marika
Isabel Friedow
Marika Karbstein
ZIB-Report
12-04
deu
uncontrolled
Fallstudie
deu
uncontrolled
Linienplan
deu
uncontrolled
Optimierung
Transportation, logistics
Traffic problems
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/1448/ZR-12-04.pdf
856
eng
reportzib
0
2005-03-23
2005-03-23
--
Public Transport to the fORe!
Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.
05-22
856
urn:nbn:de:0297-zib-8562
http://www.lionhrtpub.com/orms/orms-4-06/frtransport.html
Appeared in: OR/MS Today, Apr 2006, Vol 33 (2), 30-40
Ralf Borndörfer
Martin Grötschel
Marc Pfetsch
ZIB-Report
05-22
eng
uncontrolled
Public transport
eng
uncontrolled
vehicle scheduling
eng
uncontrolled
duty scheduling
Informatik, Informationswissenschaft, allgemeine Werke
Traffic problems
ZIB Allgemein
Borndörfer, Ralf
Grötschel, Martin
MATHEON-B1
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/856/ZR-05-22.pdf
https://opus4.kobv.de/opus4-zib/files/856/ZR-05-22.ps
6200
deu
reportzib
0
--
2017-02-23
--
Umsteigen ohne Warten
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.
1438-0064
urn:nbn:de:0297-zib-62006
Ralf Borndörfer
Marika Karbstein
Heide Hoppmann
Marika Karbstein
ZIB-Report
17-05
Transportation, logistics
Traffic problems
Combinatorial optimization
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
Hoppmann, Heide
ECMath-MI3
https://opus4.kobv.de/opus4-zib/files/6200/ZR_17-05.pdf
1581
eng
47
57
25
reportzib
Schloss Dagstuhl - Leibniz-Zentrum für Informatik
0
2012-09-17
2012-09-17
--
A Direct Connection Approach to Integrated Line Planning and Passenger Routing
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems
1438-0064
urn:nbn:de:0297-zib-15812
http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47
Appeared in: Proc. of the 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2012), D. Delling, L. Liberti (eds.) pp. 47-57. Open Access Series in Informatics, vol. 25
Ralf Borndörfer
Marika Karbstein
Daniel Delling
Marika Karbstein
Leo Liberti
ZIB-Report
12-29
eng
uncontrolled
combinatorial optimization
eng
uncontrolled
integer programming
eng
uncontrolled
line planning
eng
uncontrolled
transfers
Traffic problems
Integer programming
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/1581/ZR_12_29.pdf
5350
2015
eng
reportzib
0
--
2015-01-27
--
Metric Inequalities for Routings on Direct Connections with Application in Line Planning
We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.
1438-0064
10.1016/j.disopt.2015.07.004
urn:nbn:de:0297-zib-53507
Appeared in: Discrete Optimization 18 (2015) 56-75
Ralf Borndörfer
Marika Karbstein
Marika Karbstein
ZIB-Report
15-07
eng
uncontrolled
combinatorial optimization
eng
uncontrolled
integer programming
eng
uncontrolled
line planning
eng
uncontrolled
transfers
eng
uncontrolled
direct connection
eng
uncontrolled
metric inequalities
Traffic problems
Integer programming
Combinatorial optimization
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
ECMath-MI3
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/5350/ZR_15_07.pdf
5543
deu
reportzib
0
--
2015-06-22
--
Neue Planungsinstrumente nutzen: Das Verkehrsangebot verbessern und Kosten sparen
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.
1438-0064
urn:nbn:de:0297-zib-55439
Ersch. in: Verkehr und Technik 68/7 (2015) S. 239-243
Ralf Borndörfer
Marika Karbstein
Marika Karbstein
ZIB-Report
15-33
deu
uncontrolled
Linienplan
deu
uncontrolled
Optimierung
Transportation, logistics
Traffic problems
Mathematical Optimization
Mathematics of Transportation and Logistics
Borndörfer, Ralf
ECMath-MI3
MATHEON-B15
https://opus4.kobv.de/opus4-zib/files/5543/ZR-15-33.pdf