@misc{BorndoerferEisenblaetterGroetscheletal., author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {The Orientation Model for Frequency Assignment Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-5627}, number = {TR-98-01}, abstract = {Mobile telecommunication systems establish a large number of communication links with a limited number of available frequencies; reuse of the same or adjacent frequencies on neighboring links causes interference. The task to find an assignment of frequencies to channels with minimal interference is the frequency assignment problem. The frequency assignment problem is usually treated as a graph coloring problem where the number of colors is minimized, but this approach does not model interference minimization correctly. We give in this paper a new integer programming formulation of the frequency assignment problem, the orientation model, and develop a heuristic two-stage method to solve it. The algorithm iteratively solves an outer and an inner optimization problem. The outer problem decides for each pair of communication links which link gets the higher frequency and leads to an acyclic subdigraph problem with additional longest path restrictions. The inner problem to find an optimal assignment respecting an orientation leads to a min-cost flow problem.}, language = {en} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {Integrierte Umlauf- und Dienstplanung im {\"O}ffentlichen Nahverkehr}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6773}, number = {02-10}, abstract = {Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im {\"o}ffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken f{\"u}r den Einsatz in den Planungssystemen MICROBUS II und DIVA.}, language = {de} } @misc{BorndoerferScheltenSchlechteetal., author = {Bornd{\"o}rfer, Ralf and Schelten, Uwe and Schlechte, Thomas and Weider, Steffen}, title = {A Column Generation Approach to Airline Crew Scheduling}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8713}, number = {05-37}, abstract = {The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.}, language = {en} } @misc{BorndoerferGroetschelLukacetal.2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Lukac, Sascha and Mitusch, Kay and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {An Auctioning Approach to Railway Slot Allocation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8786}, number = {05-45}, year = {2005}, abstract = {We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.}, language = {en} } @misc{BorndoerferGroetschelPfetsch, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {A Column-Generation Approach to Line Planning in Public Transport}, doi = {/10.1287/trsc.1060.0161}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8522}, number = {05-18}, abstract = {The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Fare Planning for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8541}, number = {05-20}, abstract = {In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.}, language = {en} } @misc{BorndoerferGroetschelPfetsch, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Public Transport to the fORe!}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8562}, number = {05-22}, abstract = {Can OR methods help the public transport industry to break even? The article gives evidence that there exist significant potentials in this direction, which can be harnessed by a combination of modern mathematical methods and local planning knowledge. Many of the planning steps in public transport are classical combinatorial problems, which can be solved in unprecedented size and quality due the rapid progress in large-scale optimization. Three examples on vehicle scheduling, duty scheduling, and integrated vehicle and duty scheduling illustrate the level that has been reached and the improvements that can be achieved today. Extensions of such methods to further questions of strategic, online, and market-oriented planning are currently investigated. In this way, OR can make a significant contribution to answer the basic but extremely difficult question ``What is a good public transport network?.}, language = {en} } @misc{Borndoerfer, author = {Bornd{\"o}rfer, Ralf}, title = {Combinatorial Packing Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7255}, number = {03-03}, abstract = {This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.}, language = {en} } @misc{BorndoerferGroetschelPfetsch, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Pfetsch, Marc}, title = {Models for Line Planning in Public Transport}, doi = {10.1007/978-3-540-73312-6_18}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7854}, number = {04-10}, abstract = {The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.}, language = {en} } @misc{BorndoerferLoebelWeider, author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Weider, Steffen}, title = {A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7898}, number = {04-14}, abstract = {This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Steiner Connectivity Problem}, issn = {1438-0064}, doi = {10.1007/s10107-012-0564-5}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11171}, number = {09-07}, abstract = {The Steiner connectivity problem is a generalization of the Steiner tree problem. It consists in finding a minimum cost set of simple paths to connect a subset of nodes in an undirected graph. We show that polyhedral and algorithmic results on the Steiner tree problem carry over to the Steiner connectivity problem, namely, the Steiner cut and the Steiner partition inequalities, as well as the associated polynomial time separation algorithms, can be generalized. Similar to the Steiner tree case, a directed formulation, which is stronger than the natural undirected one, plays a central role.}, language = {en} } @misc{Borndoerfer, author = {Bornd{\"o}rfer, Ralf}, title = {Discrete Optimization in Public Transportation}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11207}, number = {08-56}, abstract = {The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.}, language = {en} } @misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Set Partitioning Approach to Shunting}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11326}, number = {09-18}, abstract = {The Vehicle Positioning Problem (VPP) is a classical combinatorial optimization problem in public transport planning. A number of models and approaches have been suggested in the literature, which work for small problems, but not for large ones. We propose in this article a novel set partitioning model and an associated column generation solution approach for the VPP. The model provides a tight linear description of the problem. The pricing problem, and hence the LP relaxation itself, can be solved in polynomial resp. pseudo-polynomial time for some versions of the problems.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10555}, number = {08-04}, abstract = {Die Angebotsplanung im {\"o}ffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen f{\"u}r die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenh{\"a}nge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abh{\"a}ngigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.}, language = {de} } @misc{BorndoerferCardonha, author = {Bornd{\"o}rfer, Ralf and Cardonha, Carlos}, title = {A Binary Quadratic Programming Approach to the Vehicle Positioning Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11242}, number = {09-12}, abstract = {The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view.}, language = {en} } @misc{BorndoerferGroetschelJaeger, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planning Problems in Public Transit}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11252}, number = {09-13}, abstract = {Every day, millions of people are transported by buses, trains, and airplanes in Germany. Public transit (PT) is of major importance for the quality of life of individuals as well as the productivity of entire regions. Quality and efficiency of PT systems depend on the political framework (state-run, market oriented) and the suitability of the infrastructure (railway tracks, airport locations), the existing level of service (timetable, flight schedule), the use of adequate technologies (information, control, and booking systems), and the best possible deployment of equipment and resources (energy, vehicles, crews). The decision, planning, and optimization problems arising in this context are often gigantic and "scream" for mathematical support because of their complexity. This article sketches the state and the relevance of mathematics in planning and operating public transit, describes today's challenges, and suggests a number of innovative actions. The current contribution of mathematics to public transit is — depending on the transportation mode — of varying depth. Air traffic is already well supported by mathematics. Bus traffic made significant advances in recent years, while rail traffic still bears significant opportunities for improvements. In all areas of public transit, the existing potentials are far from being exhausted. For some PT problems, such as vehicle and crew scheduling in bus and air traffic, excellent mathematical tools are not only available, but used in many places. In other areas, such as rolling stock rostering in rail traffic, the performance of the existing mathematical algorithms is not yet sufficient. Some topics are essentially untouched from a mathematical point of view; e.g., there are (except for air traffic) no network design or fare planning models of practical relevance. PT infrastructure construction is essentially devoid of mathematics, even though enormous capital investments are made in this area. These problems lead to questions that can only be tackled by engineers, economists, politicians, and mathematicians in a joint effort. Among other things, the authors propose to investigate two specific topics, which can be addressed at short notice, are of fundamental importance not only for the area of traffic planning, should lead to a significant improvement in the collaboration of all involved parties, and, if successful, will be of real value for companies and customers: • discrete optimal control: real-time re-planning of traffic systems in case of disruptions, • model integration: service design in bus and rail traffic. Work on these topics in interdisciplinary research projects could be funded by the German ministry of research and education (BMBF), the German ministry of economics (BMWi), or the German science foundation (DFG).}, language = {en} } @misc{BorndoerferHoang, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair Ticket Prices in Public Transport}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10999}, number = {08-46}, abstract = {Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.}, language = {en} } @misc{BorndoerferGroetschelJaeger, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planung von {\"o}ffentlichem Personenverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10744}, number = {08-20}, abstract = {Millionen von Menschen werden allein in Deutschland t{\"a}glich von Bussen, Bahnen und Flugzeugen transportiert. Der {\"o}ffentliche Personenverkehr ({\"O}V) ist von großer Bedeutung f{\"u}r die Lebensqualit{\"a}t einzelner aber auch f{\"u}r die Leistungsf{\"a}higkeit ganzer Regionen. Qualit{\"a}t und Effizienz von {\"O}V-Systemen h{\"a}ngen ab von politischen Rahmenbedingungen (staatlich geplant, wettbewerblich organisiert) und der Eignung der Infrastruktur (Schienensysteme, Flughafenstandorte), vom vorhandenen Verkehrsangebot (Fahr- und Flugplan), von der Verwendung angemessener Technologien (Informations-, Kontroll- und Buchungssysteme) und dem bestm{\"o}glichen Einsatz der Betriebsmittel (Energie, Fahrzeuge und Personal). Die hierbei auftretenden Entscheidungs-, Planungs- und Optimierungsprobleme sind z.T. gigantisch und "schreien" aufgrund ihrer hohen Komplexit{\"a}t nach Unterst{\"u}tzung durch Mathematik. Dieser Artikel skizziert den Stand und die Bedeutung des Einsatzes von Mathematik bei der Planung und Durchf{\"u}hrung von {\"o}ffentlichem Personenverkehr, beschreibt die bestehenden Herausforderungen und regt zukunftsweisende Maßnahmen an.}, language = {de} } @misc{SchlechteBorndoerfer, author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf}, title = {Balancing Efficiency and Robustness - A Bi-criteria Optimization Approach to Railway Track Allocation}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10763}, number = {08-22}, abstract = {Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional \$\epsilon\$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10820}, number = {08-31}, abstract = {This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.}, language = {en} }