Aggregation Methods for Railway Network Design Based on Lifted Benders Cuts

Bärmann A, Liers F (2018)


Publication Type: Book chapter / Article in edited volumes

Publication year: 2018

Publisher: Springer International Publishing

Edited Volumes: Handbook of Optimization in the Railway Industry

City/Town: Cham

Pages Range: 47--72

ISBN: 978-3-319-72153-8

DOI: 10.1007/978-3-319-72153-8_3

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.

Authors with CRIS profile

How to cite

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: Download