Aggregation Methods for Railway Network Design Based on Lifted Benders Cuts

Beitrag in einem Sammelwerk


Details zur Publikation

Autor(en): Bärmann A, Liers F
Herausgeber: Borndörfer R, Klug T, Lamorgese L, Mannino C, Reuther M, Schlechte T
Titel Sammelwerk: Handbook of Optimization in the Railway Industry
Verlag: Springer International Publishing
Verlagsort: Cham
Jahr der Veröffentlichung: 2018
Seitenbereich: 47--72
ISBN: 978-3-319-72153-8


Abstract

Rail freight traffic in Germany has experienced significant growth rates over the last decade, and recent forecasts expect this tendency to continue over the next 20 years due to the increases in national and international trade. Internal predictions of Deutsche Bahn AG, the most important German railway enterprise, assume a mean increase of 2{%} per year for rail freight traffic until 2030. At this pace, the German railway network in its current state would reach its capacity limit way before this date. As investments into the network infrastructure bear a very high price tag, it is crucial to use the available budget in the most efficient manner. Furthermore, the large size of the networks under consideration warrants the development of efficient algorithms to handle the complex network design problems arising for real-world data. This led us to the development of network aggregation procedures which allow for much shorter solution times by compressing the network information. More exactly, our framework works by clustering the nodes of the underlying graph to components and solving the network design problem over this aggregated graph. This kind of aggregation may either be used as a quick heuristic, or it can be extended to an exact method, e.g. by iterative refinement of the clustering, The latter results in a cutting plane algorithm, which also introduces new variables with each refinement. This idea developed in Bärmann et al. (Math Program Comput 7(2):189--217, 2015) is extended in this chapter such that it is able to incorporate the costs for routing flow through the network via lifted Benders optimality cuts. Altogether, our algorithm can be seen as a novel kind of Benders decomposition which allows to shift variables from the subproblem to the master problem in the process. Computations on several benchmark sets demonstrate the effectiveness of the approach.


FAU-Autoren / FAU-Herausgeber

Bärmann, Andreas Dr.
Lehrstuhl für Wirtschaftsmathematik
Liers-Bergmann, Frauke Prof. Dr.
Professur für Diskrete Optimierung in den Ingenieurwissenschaften


Zitierweisen

APA:
Bärmann, A., & Liers, F. (2018). Aggregation Methods for Railway Network Design Based on Lifted Benders Cuts. In Borndörfer R, Klug T, Lamorgese L, Mannino C, Reuther M, Schlechte T (Eds.), Handbook of Optimization in the Railway Industry. (pp. 47--72). Cham: Springer International Publishing.

MLA:
Bärmann, Andreas, and Frauke Liers. "Aggregation Methods for Railway Network Design Based on Lifted Benders Cuts." Handbook of Optimization in the Railway Industry. Ed. Borndörfer R, Klug T, Lamorgese L, Mannino C, Reuther M, Schlechte T, Cham: Springer International Publishing, 2018. 47--72.

BibTeX: 

Zuletzt aktualisiert 2019-01-01 um 11:10