Refine
Document Type
- ZIB-Report (4)
- Habilitation (1)
Language
- English (5)
Is part of the Bibliography
- no (5)
Keywords
- public transport (5) (remove)
Institute
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.
The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.
This cumulative thesis collects the following six papers for obtaining the
habilitation at the Technische Universität Berlin, Fakultät II – Mathematik
und Naturwissenschaften:
(1) Set packing relaxations of some integer programs.
(2) Combinatorial packing problems.
(3) Decomposing matrices into blocks.
(4) A bundle method for integrated multi-depot vehicle and duty scheduling
in public transit.
(5) Models for railway track allocation.
(6) A column-generation approach to line planning in public transport.
Some changes were made to the papers compared to the published versions.
These pertain to layout unifications, i.e., common numbering, figure, table,
and chapter head layout. There were no changes with respect to notation or
symbols, but some typos have been eliminated, references updated, and some
links and an index was added. The mathematical content is identical.
The papers are about the optimization of public transportation systems,
i.e.,
bus networks, railways, and airlines, and its mathematical foundations,
i.e.,
the theory of packing problems. The papers discuss mathematical models,
theoretical analyses, algorithmic approaches, and computational aspects of
and to problems in this area.
Papers 1, 2, and 3 are theoretical. They aim at establishing a theory of
packing problems as a general framework that can be used to study traffic
optimization problems. Indeed, traffic optimization problems can often be
modelled as path packing, partitioning, or covering problems, which lead
directly to set packing, partitioning, and covering models. Such models are
used in papers 4, 5, and 6 to study a variety of problems concerning the
planning
of line systems, buses, trains, and crews. The common aim is always
to exploit as many degrees of freedom as possible, both at the level of the
individual problems by using large-scale integer programming techniques, as
well as on a higher level by integrating hitherto separate steps in the
planning
process.
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.