TY - GEN A1 - Borndörfer, Ralf A1 - Liebchen, Christian T1 - When Periodic Timetables are Suboptimal N2 - 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'. T3 - ZIB-Report - 07-29 KW - Taktfahrplan KW - Fahrplan KW - Nahverkehr KW - periodic timetable KW - trip timetable KW - public transport Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9151 SN - 1438-0064 ER - TY - THES A1 - Borndörfer, Ralf T1 - Mathematical Optimization and Public Transportation N2 - 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. KW - set packing KW - set partitioning KW - set covering KW - polyhedral combinatorics KW - public transport KW - railways Y1 - 2010 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-13613 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System (Extended Abstract) N2 - 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. T3 - ZIB-Report - 08-53 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-11076 SN - 1438-0064 ER - TY - GEN A1 - Torres, Luis Miguel A1 - Torres, Ramiro A1 - Borndörfer, Ralf A1 - Pfetsch, Marc T1 - Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System N2 - 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. T3 - ZIB-Report - 08-35 KW - line planning KW - computational complexity KW - public transport KW - integer programming Y1 - 2008 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10869 SN - 1438-0064 ER -