Reducing a given street network to a public transport network is essential for bundling passenger demand and reducing the environmental impact of mobility. Here, both the operators’ budget and the passengers’ routing costs have to be considered. We introduce a new integer programming model for designing routing-cost-minimal public transport networks in circular cities leveraging their symmetry. In an extensive computational study, we compare generic and symmetric sub-networks structurally, show that the newly introduced model can be solved orders of magnitude faster than generic models and determine that the routing-cost gap between symmetric and generic sub-networks can be disregarded for most budgets.

International audience

Line planning, i.e. choosing routes which are to be serviced by vehicles in order to satisfy network demands, is an important aspect of public transport planning. While there exist heuristic procedures for generating lines from scratch, most theoretical investigations consider the problem of choosing lines only from a predefined line pool. We consider the line planning problem when all simple paths can be used as lines and present an algorithm which is fixed-parameter tractable, i.e. it is efficient on instances with small parameter. As a parameter we consider the treewidth of the public transport network, along with its maximum degree as well as the maximum allowed frequency.

Bus Rapid Transit (BRT) systems can provide a fast and reliable service to passengers at lower costs compared to tram, metro and train systems. Therefore, they can be of great value to attract more passengers to use public transport, which is vital in reaching the Paris Agreement Targets. However, the main advantage of BRT systems, namely their flexible implementation, also leads to the risk that the system is only implemented partially to save costs. This paper focuses therefore on the Edge Investment Problem: Which edges (segments) of a bus line should be upgraded to full-level BRT? Motivated by the construction of a new BRT line around Copenhagen, we consider a setting in which multiple parties are responsible for different segments of the line. Each party has a limited budget and can adjust its investments according to the benefits provided to its passengers. We suggest two ways to determine the number of newly attracted passengers, prove that the corresponding problems are NP-hard and identify special cases that can be solved in polynomial time. In addition, problem relaxations are presented that yield dual bounds. Moreover, we perform an extensive numerical comparison in which we evaluate the extent to which these two ways of modeling demand impact the computational performance and the choice of edges to be upgraded.

We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.

When evaluating the operational costs of a public transport system, the most important factor is the number of vehicles needed for operation. In contrast to the canonical sequential approach of first fixing a timetable and then adding a vehicle schedule, we consider a sequential approach where a vehicle schedule is determined for a given line plan and only afterwards a timetable is fixed. We compare this new sequential approach to a model that integrates both steps. To represent various operational requirements, we consider multiple possibilities to restrict the vehicle circulations to be short, as this can provide operational benefits. The sequential approach can efficiently determine public transport plans with a low number of vehicles. This is evaluated theoretically and empirically demonstrated for two close-to real-world instances.

In this paper we deal with three consecutive planning stages in public transportation: Line planning (including line pool generation), timetabling, and vehicle scheduling. These three steps are traditionally performed one after another in a sequential way often leading to high costs in the (last) vehicle scheduling stage. In this paper we propose three different ways to "look ahead", i.e., to include aspects of vehicle scheduling already earlier in the sequential process: an adapted line pool generation algorithm, a new cost structure for line planning, and a reordering of the sequential planning stages. We analyze these enhancements experimentally and show that they can be used to decrease the costs significantly.

The periodic event scheduling problem (PESP) is a well studied problem known as intrinsically hard. Its main application is for designing periodic timetables in public transportation. To this end, the passengers' paths are required as input data. This is a drawback since the final paths which are used by the passengers depend on the timetable to be designed. Including the passengers' routing in the PESP hence improves the quality of the resulting timetables. However, this makes PESP even harder. Formulating the PESP as satisfiability problem and using SAT solvers for its solution has been shown to be a highly promising approach. The goal of this paper is to exploit if SAT solvers can also be used for the problem of integrated timetabling and passenger routing. In our model of the integrated problem we distribute origin-destination (OD) pairs temporally through the network by using time-slices in order to make the resulting model more realistic. We present a formulation of this integrated problem as integer program which we are able to transform to a satisfiability problem. We tested the latter formulation within numerical experiments, which are performed on Germany's long-distance passenger railway network. The computation's analysis in which we compare the integrated approach with the traditional one with fixed passengers' weights, show promising results for future scientific investigations.