In this project we developed a novel theory of path connectivity that generalizes the Steiner tree problem to a hypergraph setting. Main results include a Menger companion Theorem, approximation algorithms, and a polyhedral characterization, complemented by a new method to handle transfers in public transport applications. We used this theory to optimize the 2010 line plan of Potsdam’s public transport company ViP in a project Stadt+. To our knowledge, this was the first mathematically optimized line plan in operation.
The goal of service design is to construct a public transport system which is both attractive for passengers and can be operated economically. This requires strategic decisions in network design, line planning, timetabeling, and fare planning. Each of these questions deals with difficult optimization problems with multiple objectives. We have developed first mathematical methods for line planning, timetabling, and fare planning in the projects Strategic Planning in Public Transport at ZIB and Line Planning and Periodic Timetabling in Railway Traffic at TU Berlin.
In this project we further improved our models for line planning.
Line planning is a fundamental problem in the design of a public transportation system. It consists in finding a set of lines in an infrastructure network and their frequencies of operation such that a given travel demand can be routed. There are two main objectives, namely, minimization of operation costs and minimization of travel and transfer times.
The Steiner connectivity problem is an abstract combinatorial problem that underlies line planning. This prototype model has the same significance for line planning in public transport as the Steiner tree problem has for telecommunication network design. We investigate the Steiner connectivity problem and showe that main results about complexity, approximation, integer programming formulations, and polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity problem.
The treatment of transfers is a major challenge in line planning. Previous existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of extremely large scale, and seem to be computationally
intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
Our biggest practical success was the optimization of the ViP (Verkehrsbetrieb Potsdam GmbH) line plan for 2010. In close cooperation with ViP, we fine-tuned our model and set up a data base that is suitable for the application of optimization methods. Among other things, we defined possible endpoints for new lines, added missing links, and modeled planning requirements such as a minimum cycle time for the tram, minimum frequency requirements for each station, or minimal and maximal lengths for lines with respect to travel time and distance. The final optimized solution reduces the cost by around 4% and the perceived travel time by around 6%. It further reduces the total number of transfers by around 5%; ViP also certified that this line plan was practicable and implemented the solution almost one-to-one.
A major challenge in service design optimization is the consideration of passenger behavior. The level of service decides whether passengers are attracted to this system or not. Understanding and controlling the interplay between service design and passenger behavior is therefore a main goal in service planning. We will investigate these aspects in the project Infrastructure Design & Passenger Behaviour in Public Transport.
Poster 2012 [pdf]
