Invited Session Thu.1.H 3013

Thursday, 10:30 - 12:00 h, Room: H 3013

Cluster 2: Combinatorial optimization [...]

Combinatorial optimization in railways II


Chair: Ralf Borndörfer



Thursday, 10:30 - 10:55 h, Room: H 3013, Talk 1

Ronny Hansmann
Minimal shunting operations for freight train composition

Coauthor: Uwe Zimmermann


Planning freight train schedules in dense rail networks provides an enormous challenge. Resulting optimization models include a tremendous number of eligible train routes and departure times restricted by sparse infrastructure capacities. From our ongoing cooperation with the Deutsche Bahn (DB) within a three-year project, we outline first results focusing on the composition of rail cars in freight trains. According to requests of the customers of the DB, rail cars are routed from origin to destination throughout Germany by assigning them to a suitable sequence of previously scheduled freight trains. Additionally, the sequence of the rail cars within a freight train may be chosen. The real challenge consists in assigning rail cars to freight trains with choice of their sequence within the train minimizing the total number of time-consuming shunting operations in the visited rail yards. To our knowledge, the resulting NP-hard problem was previously not studied in the literature. We present new mixed integer programming formulations, some heuristics as well as computational experience for practical data from the DB. We conclude the talk with some remarks on future research.



Thursday, 11:00 - 11:25 h, Room: H 3013, Talk 2

Andreas Bärmann
Approximate robust optimization and applications in railway network expansion

Coauthors: Andreas Heidt, Alexander Martin, Sebastian Pokutta, Christoph Thurner


This talk is concerned with the application of robust optimization to railway network expansion planning. We introduce a methodology that linearizes the elliptic uncertainty sets describing the demand uncertainty to maintain the linearity of the problem.
Dealing with data uncertainty is of great importance in infrastructure development which can be affected by inaccuracy in demand forecast. The robust optimization framework immunizes the model against all data scenarios in a given uncertainty set. In this talk we introduce a methodology that linearizes elliptic uncertainty sets. For this purpose we apply the approach of Ben-Tal and Nemirovski for the linearization of the second order cone. In the case of a linear optimization model this allows for solving the robustified model as a linear program again. The benefits especially arise in discrete optimization, as we can maintain the warm start capabilities of the simplex method.
We present computational results for an implementation of the method in the context of a railway network expansion application in cooperation with Deutsche Bahn AG. We also outline applications in air traffic management and energy systems optimization.



Thursday, 11:30 - 11:55 h, Room: H 3013, Talk 3

Torsten Klug
An approach for solving the freight train routing problem

Coauthors: Ralf Borndörfer, Armin Fügenschuh, Thomas Schlechte


We consider the following freight train routing problem. Given is a
transportation network with fixed routes for passenger trains and a
set of freight train requests, each defined by an origin and
destination station pair. The objective is to calculate a feasible
route for each freight train such that a sum of expected delays and
running times is minimal. Previous research concentrated on
microscopic train routings for junctions or major stations. Only
recently approaches were developed to tackle larger corridors or even
networks. We investigate the routing problem from a strategic
perspective, calculating the routes in a macroscopic transportation
network. In this terms macroscopic means complex structures are
aggregated into smaller elements and the departure and arrival times
of freight trains are approximated. The problem has a strategic
character since it asks only for a rough routing through the network
without the precise timings. We propose a best insertion heuristic and
a mixed integer programming model for the freight train routing
problem, compare them, and present some computational results using
different state of the art MIP-solvers.


  There are three major facts that should be watched out for in all payday loans in the United States. Therefore, we can say that the active substances in its composition are more perfectly mixed. Vardenafil is not only present in the original Buy Levitra, but also as part of its analogs.