Optimal Lines in Public Rail Transport

This thesis deals with the line planning problem for public transportation networks based on periodic schedules. The models and algorithms represented in this thesis take care of peculiarities of public rail transport. A line consists of a route in the network and a cycle time. The line planning problem consists of choosing a set of operating lines that complies with the passenger demand and optimizes a given objective. An important frame work for line planning is based on a hierarchical decomposition of this complex problem. The most challenging task is the line optimization problem. Algorithms for the line optimization problem described in the literature focus on heuristics with one major drawback: the lack of a performance guarantee for generated solutions. The models for the line planning problem considered in this monograph are integer linear programs. These programs provide a convenient way of modeling variants of the line optimization problem as well as a general solution technique. The objectives for the line optimization problem discussed in this thesis present service- and cost evaluations of line plans. The service quality of a line plan is determined by the number of direct travelers. The model improvements, which lead to fast solution times even for large scale real world problem instances, are based on techniques of polyhedral optimization.