In the evolving landscape of public transportation, achieving efficiency, sustainability, and cost-effectiveness is paramount. With over 8 billion passengers annually, Germany’s public transport system faces unique challenges. The strategic application of advanced mathematical methodologies has emerged as a pivotal tool in redefining the operational capabilities of buses, trains, and even airplanes. Together with our industrial partners, we optimize vehicle scheduling, manage fleet operations, and pioneer sustainable solutions. Our innovative mathematical methods not only address the challenges of urban expansion and environmental concerns but also highlight the transformative impact of research in shaping a smarter transportation future [4].
As cities grow and evolve, their transportation systems must also adapt to meet new demands. In collaboration with Berlin’s public transport operator BVG, we took on the task of enhancing public transport efficiency through advanced vehicle scheduling optimization. Imagine the city’s network of roads and stops as a colorful map, where each color represents different travel times between various destinations, illustrating not just the physical distance but also the efficiency of routes from one point to an-other. We developed a so-called Lagrangean pricing method that can optimize this map, finding the quickest routes while considering passenger flows and costs [7]. Based on this map, our method finds optimal schedules for all involved vehicles and can tackle massive problem sizes with hundreds of millions of possible connections and dozens of vehicle types. The result of this partnership is a high-performance scheduling system, which is today used by half of Germany’s public transport providers, saving time, money, and reducing emissions.
Expanding beyond urban transportation networks, efficiently scheduling long-distance trains involves not only finding optimal schedules but also dealing with the challenge of forming specific train compositions, as individual units can vary in type and orientation. In close collaboration with Deutsche Bahn (DB), the Research Campus MODAL and the MATH+ Cluster of Excellence, we have pioneered a groundbreaking approach dubbed the “hyperflow model,” which is revolutionizing train scheduling [6]. Similar to a skilled conductor leading a symphony of trains, the hyperflow model orchestrates the movement of travelers and goods throughout the train network, ensuring minimal delays. This results in gigantic optimization problems with several hundred million variables, which our newly developed coarse-to-fine optimizer, tailored for this specific problem class, efficiently solves. This new method can dynamically adjust the level of detail during computation to achieve the best combination of efficiency and accuracy [5]. As a result, our new approach allows the entire German ICE fleet for a standard week to be scheduled on a modest computing cluster. Moreover, our technology seamlessly integrates into scheduling systems such as DB’s, contributing to annual savings exceeding 70 million euros and reductions of 34,000 tons of CO2 emissions [3].
In collaboration with Lufthansa Systems, MODAL and MATH+, we have ventured into the skies, optimizing flight trajectories with a free flight model that has realized fuel savings of up to 2.5% [1, 2]. This project not only highlights the versatility of our mathematical methodologies but also underscores our commitment to environmental stewardship across all modes of transportation.
ZIB is developing sophisticated algorithms capable of optimizing transportation across various modes, including buses, trams, trains, and airplanes. This initiative exemplifies our dedication to advancing modern mobility and highlights our innovative strategies to directly address the complexities of current transportation systems while prioritizing sustainability.
References:
[1] M. Blanco, R. Borndörfer, N.-D. Hoang, A. Kaier, A. Schienle, T. Schlechte, and S. Schlobach. Solving time dependent shortest path problems on airway networks using super-optimal wind. In: 16th Workshop on Al-gorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2016). Ed. by G. Marc. Vol. 54. 2016. DOI: 10.4230/OASIcs.ATMOS. 2016.12.
[2] R. Borndörfer, F. Danecker, and M. Weiser. New-ton’s method for global free flight trajectory optimization. Operations Research Forum 4 (2023). DOI: 10.1007/s43069-023-00238-z.
[3] R. Borndörfer, T. Eßer, P. Frankenberger, A. Huck, C. Jobmann, B. Krostitz, K. Kuchenbecker, K. Moorhagen, P. Nagl, M. Peterson, M. Reuther, T. Schang, M. Schoch, H. Schülldorf, P. Schütz, T. Therolf, K. Waas, and S. Weider. Deutsche bahn schedules train rotations using hypergraph optimization. Informs Journal on Applied Analytics 51.1 (2021), 42–62. DOI: 10.1287/inte.2020.1069.
[4] R. Borndörfer, M. Grötschel, and U. Jäger. Planning problems in public transit. In: Jan. 2010, 95–121. DOI: 10.1007/978-3-642-11248-5_6.
[5] R. Borndörfer, M. Reuther, and T. Schlechte. A coarse-to-fine approach to the railway rolling stock rotation problem. In: 14th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Vol. 42. 2014, 79–91. DOI: 10.4230/OASIcs.ATMOS. 2014.79.
[6] R. Borndörfer, M. Reuther, T. Schlechte, and S. Wei-der. A Hypergraph Model for Railway Vehicle Rotation Planning. In: 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Ed. by A. Caprara and S. Kontogiannis. Vol. 20. Open Access Series in Informatics (OASIcs). Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2011, 146–155. DOI: 10.4230/OASIcs.ATMOS.2011.146. URL: https: //drops-dev.dagstuhl.de/entities/document/ 10.4230/OASIcs.ATMOS.2011.146.
[7] A. Löbel. Vehicle scheduling in public transit and lagrangean pricing. Management Science 44.12 (1998), 1637–1649. DOI: https://doi.org/10.1287/mnsc. 44.12.1637.
