Optimization Online


Energy-Efficient Timetabling in a German Underground System

Andreas Bärmann(Andreas.Baermann***at***math.uni-erlangen.de)
Patrick Gemander(Patrick.Gemander***at***fau.de)
Alexander Martin(Alexander.Martin***at***fau.de)
Maximilian Merkert(Maximilian.Merkert***at***ovgu.de)
Frederik Nöth(Frederik.Noeth***at***vag.de)

Abstract: Timetabling of railway traffic and other modes of transport is among the most prominent applications of discrete optimization in practice. However, it has only been recently that the connection between timetabling and energy consumption has been studied more extensively. In our joint project VAG Verkehrs-Aktiengesellschaft, the transit authority and operator of underground transport in the German city of Nürnberg, we develop algorithms for optimal timetabling to minimize the energy consumption of the trains via more energy-efficient driving as well as increasing the usability of recuperated energy from braking. Together with VAG, we have worked extensively to establish a broad basis of operational data, for example characteristic power consumption profiles as well as travel time and dwell time distributions for the trains running in the network, to serve as input to our optimization methods. On the collected data sets, our approach has already shown significant potential to reduce energy consumption and, as a consequence, electricity costs and environmental impact. Furthermore, mathematical analysis of the polyhedral and graph structures involved in the optimization approach have enabled us to compute high-quality solutions within short time. This positive outlook motivated VAG to extend this project to include further operational constraints in the model and to adopt the resulting software planning tool in practice afterwards. It will assist timetable planners at VAG in using the available degrees of freedom in their timetable drafts to optimize the energy-efficiency of the underground system.

Keywords: Timetabling, Energy, Clique Problem with Multiple-Choice Constraints, Combinatorial Optimization, Perfect Graph

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Combinatorial Optimization (Graphs and Matroids )


Download: [PDF]

Entry Submitted: 04/06/2020
Entry Accepted: 04/07/2020
Entry Last Modified: 04/06/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society