TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - The Price of Symmetric Line Plans in the Parametric City N2 - We consider the line planning problem in public transport in the Parametric City, an idealized model that captures typical scenarios by a (small) number of parameters. The Parametric City is rotation symmetric, but optimal line plans are not always symmetric. This raises the question to quantify the symmetry gap between the best symmetric and the overall best solution. For our analysis, we formulate the line planning problem as a mixed integer linear program, that can be solved in polynomial time if the solutions are forced to be symmetric. The symmetry gap is provably small when a specific Parametric City parameter is fixed, and we give an approximation algorithm for line planning in the Parametric City in this case. While the symmetry gap can be arbitrarily large in general, we show that symmetric line plans are a good choice in most practical situations. T3 - ZIB-Report - 22-01 KW - line planning KW - mixed integer programming KW - parametric city modeling Y1 - 2022 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-85648 SN - 1438-0064 ER - TY - GEN A1 - Masing, Berenike A1 - Lindner, Niels A1 - Borndörfer, Ralf T1 - Optimal Line Plans in the Parametric City and the Impact of In-Motion Costs N2 - Line planning in public transport involves determining vehicle routes and assigning frequencies of service such that travel demands are satisfied. We evaluate how line plans, which are optimal with respect to in-motion costs (IMC), the objective function depending purely on arc-lengths for both user and operator costs, performs with respect to the value of resources consumed (VRC). The latter is an elaborate, socio-economic cost function which includes discomfort caused by delay, boarding and alighting times, and transfers. Even though discomfort is a large contributing factor to VRC and is entirely disregarded in IMC, we observe that the two cost functions are qualitatively comparable. T3 - ZIB-Report - 21-27 KW - line planning KW - public transport KW - mixed-integer prgramming Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-84195 SN - 1438-0064 ER - TY - GEN A1 - Masing, Berenike T1 - Optimal Line Planning in the Parametric City N2 - We formulate the line planning problem in public transport as a mixed integer linear program (MILP), which selects both passenger and vehicle routes, such that travel demands are met with respect to minimized travel times for both operators and users. We apply MILP to the Parametric City, a generic city model developed by Fielbaum et al. While the infrastructure graph and demand are entirely rotation symmetric, asymmetric optimal line plans can occur. Using group theory, we analyze the properties of symmetric solutions and introduce a symmetry gap to measure their deviation of the optimum. We also develop a 1+(1+\sqrt{2})/g-approximation algorithm, depending only on the cost related parameter g. Supported by computational experiments, we conclude that in practice symmetric line plans provide good solutions for the line planning problem in the Parametric City. T3 - ZIB-Report - 21-26 KW - line planning KW - city modelling KW - symmetry KW - mixed integer programming KW - approximation algorithm Y1 - 2021 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-83238 SN - 1438-0064 ER -