论文标题
参数城市中对称线计划的价格
The Price of Symmetric Line Plans in the Parametric City
论文作者
论文摘要
我们考虑参数城市公共交通中的线条规划问题，这是一个理想化的模型，可通过（小）参数捕获典型场景。参数城市是旋转对称的，但最佳的线计划并不总是对称的。这提出了一个问题，以量化最佳对称性和总体最佳解决方案之间的对称差距。为了进行分析，我们将线计划问题作为混合整数线性程序提出，如果溶液被迫为对称，则可以在多项式时间内解决。当固定特定的参数城市参数时，对称差距很小，在这种情况下，我们在参数城市中给出了线条规划的近似算法。虽然对称差距一般可以任意较大，但我们表明对称线计划在大多数实际情况下都是一个不错的选择。
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.
