TY - GEN A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Models for Line Planning with Transfers N2 - We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results. T3 - ZIB-Report - 10-11 KW - Linienplanung KW - Umsteigen KW - Ganzzahlige Programmierung KW - Kombinatorische Optimierung KW - line planning KW - transfers KW - integer programming KW - combinatorial optimization Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11742 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - Railway Track Allocation by Rapid Branching N2 - The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported. T3 - ZIB-Report - 10-22 KW - Trassenallokationsproblem KW - Ganzzahlige Programmierung KW - Rapid-Branching-Heuristik KW - Proximale Bündelmethode KW - Optimization KW - Railway Track Allocation KW - Bundle Method KW - Rapid Branching Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11864 SN - 1438-0064 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Schlechte, Thomas A1 - Weider, Steffen ED - Erlebach, Thomas ED - Lübbecke, Marco T1 - Railway Track Allocation by Rapid Branching T2 - Proceedings of the 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2010 UR - http://drops.dagstuhl.de/opus/volltexte/2010/2746 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2010.13 VL - 14 SP - 13 EP - 23 PB - Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik CY - Dagstuhl, Germany ER -