Regardless of the mode, transportation – as an industry – faces numerous planning challenges, beyond these seen in other industries. They frequently entail thousands of interdependent decisions, with an element of uncertainty. This is why for many years, optimization techniques have found extensive use in that branch of economy. In this post, I would like to present some of the most prominent applications of optimization techniques in transportation, with a particular focus on rail freight transportation. I will also mention some works relating to each of the applications discussed. This choice is due to my own research focusing on that mode of transport.
Let us start from the broad perspective of the railway network of a country. With a history starting in the 19th century, these were frequently built by numerous companies, serving their own interests. Over time, they grew bigger and bigger, and gradually found themselves under the control of one entity, usually a state-owned company which maintains them and sells the access slots (just like at an airport). Now, as the transportation needs change, some of the lines are shut down while others are refurbished. On some occasions, completely new lines are built.
To assist decision-making while considering an extension to a railway network, policy-makers can use tools like those described in Andreas Bärmann’s [1]. Andreas uses forecasts of the demand for access to the railway network at different points in Germany and comes up with a model which highlights the sections of the network which will experience the greatest increase in demand. To make the problem solve efficiently, he inter alia develops a decomposition technique, made to the measure of the studied multi-period network design problem.
Going further, the network manager needs to distribute the access rights to the network. This is required in order to – in the most general terms – maintain safety in the network and assure that as many trains as possible can access the railway line. In particular, a certain distance – called headway – needs to be kept between two consecutive trains. Further, especially on the electrified sections of the network, an appropriate train schedule can help save energy thanks to recuperation.
One of the most prominent papers dealing with the described problem was written by Alberto Caprara, Matteo Fischetti and Paolo Toth [2]. They develop a graph theoretic formulation for the problem of scheduling trains on a single, one-way track linking two major stations, with a number of intermediate stations in between using a directed multigraph. They then use Lagrangian relaxation to arrive at an efficient heuristic solution algorithm, and demonstrate the results on instances supplied by two Italian railway network managers. More recently, my colleagues from the chair, Prof. Alexander Martin, Dr. Andreas Bärmann (who are the supervisors of my thesis) and others [3] together with VAG (transportation authority of Nuremberg metropolitan area) developed an approach to optimal timetabling aiming at minimizing the energy consumption of the trains through more energy-efficient driving as well as by increasing the usability of recuperated energy from braking. This solution could soon be used by VAG in their timetabling process. This work is part of a project on energy-saving via real-time driver assistant systems for interconnected trains in the ADA-Lovelace-Center in Nuremberg, Germany [4]. It is a research centre for artificial itelligence (AI) founded jointly by the Fraunhofer Institute for Integrated Circuits (IIS), the Friedrich-Alexander University Erlangen-Nürnberg (FAU) and the Ludwig-Maximilian University München (LMU) [5]. Its mission is to push methodological advancements in AI and to act as a platform for AI collaboration between research and industry.
Another important application of mathematical optimization pertains to the decisions relating to the production resources of a railway carrier, most important of which are locomotives and drivers. On one hand, one needs to ensure that both an appropriate locomotive (e.g. suitable to the line, powerful enough) and an appropriate driver (e.g. licensed to drive the mentioned locomotive on the train’s route) is attributed to the train, on the other hand, each driver has a number of working time constraints, and locos require maintenance. Other assets considered frequently include wagons and passenger train personnel.
A prominent paper pertaining to locomotive scheduling is the one by Ahuja et al. [6]. They study a problem of assigning locomotive consists to pre-planned trains, aiming at supplying each train with appropriate power. Another one, by Jütte et al. [7], uses column-generation techniques to develop and implement a crew-scheduling system at DB Schenker, the largest European rail freight carrier. My own research focuses on combining both problems (posed differently) into one, and solving them “from one hand”.
All of the abovementioned applications are just the “tip of the iceberg”. In this post, I only covered three macro-stages of planning in the railway industry, and showed how can mathematical optimization be of help there. Other applications could include e.g. train control, locomotive maintenance scheduling, shunting, train dispatch and delay management. Vast majority of those, as well as others, were all described in [8], which should serve as an reference point to the interested reader.
[1] ] Bärmann, A., 2015. Solving Network Design Problems via Decomposition, Aggregation and Approximation. Springer Spektrum. https://doi.org/10.1007/978-3-658-13913-1
[2] Caprara, A., Fischetti, M., Toth, P., 2002. Modeling and Solving the Train Timetabling Problem. Operations Research 50, 851–861. https://doi.org/10.1287/opre.50.5.851.362
[3] Bärmann, A., Gemander, P., Martin, A., Merkert, M., Nöth, F., 2019. Energy-Efficient Timetabling in a German Underground System. Preprint. http://www.optimization-online.org/DB_FILE/2020/04/7728.pdf
[4] https://www.scs.fraunhofer.de/en/focus-projects/ada-center/ai-transport-mobility.html
[5] https://www.scs.fraunhofer.de/en/focus-projects/ada-center.html
[6] Ahuja, R.K., Liu, J., Orlin, J.B., Sharma, D., Shughart, L.A., 2005. Solving Real-Life Locomotive-Scheduling Problems. Transportation Science 39, 503–517. https://doi.org/10.1287/trsc.1050.0115
[7] Jütte, S., Albers, M., Thonemann, U.W., Haase, K., 2011. Optimizing Railway Crew Scheduling at DB Schenker. Interfaces 41, 109–122. https://doi.org/10.1287/inte.1100.0549
[8] Borndörfer, R., Klug, T., Lamorgese, L., Mannino, C., Reuther, M., Schlechte, T. (Eds.), 2018. Handbook of Optimization in the Railway Industry, International Series in Operations Research & Management Science. Springer International Publishing, Cham. https://doi.org/10.1007/978-3-319-72153-8
About the author:
Jonasz Staszek is an early-stage researcher (ESR7) within ROMSOC. He is working with Friedrich-Alexander-Universität Erlangen-Nürnberg in collaboration with DB Cargo Polska on mixed-integer optimization models for an optimal resource allocation and investment for border-crossing transport services in rail traffic.