@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{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{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{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{BorndoerferLoebelStrubbeetal., author = {Bornd{\"o}rfer, Ralf and L{\"o}bel, Andreas and Strubbe, Uwe and V{\"o}lker, Manfred}, title = {Zielorientierte Dienstplanoptimierung}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3847}, number = {SC-98-41}, abstract = {Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im {\"O}PNV. Der Ansatz zielt auf die vollst{\"a}ndige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Ber{\"u}cksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenw{\"a}rtig in einem vom Bundesministerium f{\"u}r Bildung und Forschung ({\tt bmb+f}) gef{\"o}rderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum f{\"u}r Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben {\"u}ber eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten {\"u}ber den Stand der Entwicklung.}, language = {de} } @misc{PfetschBorndoerfer, author = {Pfetsch, Marc and Bornd{\"o}rfer, Ralf}, title = {Routing in Line Planning for Public Transportation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8706}, number = {05-36}, 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 network such that a giv en demand can be satisfied. There are two objectives. Passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.}, language = {en} } @misc{BorndoerferFerreiraMartin, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Matrix Decomposition by Branch-and-Cut}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2839}, number = {SC-97-14}, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix \$A\$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the \%LP- and MIP-libraries \Netlib{} and MIPLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem.}, language = {en} } @misc{BorndoerferFerreiraMartin, author = {Bornd{\"o}rfer, Ralf and Ferreira, Carlos E. and Martin, Alexander}, title = {Decomposing Matrices into Blocks}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2849}, number = {SC-97-15}, abstract = {In this paper we investigate whether matrices arising from linear or integer programming problems can be decomposed into so-called {\em bordered block diagonal form}. More precisely, given some matrix \$A\$, we try to assign as many rows as possible to some number of blocks of limited size such that no two rows assigned to different blocks intersect in a common column. Bordered block diagonal form is desirable because it can guide and speed up the solution process for linear and integer programming problems. We show that various matrices from the LP- and MIP-libraries NETLIB and MITLIB can indeed be decomposed into this form by computing optimal decompositions or decompositions with proven quality. These computations are done with a branch-and-cut algorithm based on polyhedral investigations of the matrix decomposition problem. In practice, however, one would use heuristics to find a good decomposition. We present several heuristic ideas and test their performance. Finally, we investigate the usefulness of optimal matrix decompositions into bordered block diagonal form for integer programming by using such decompositions to guide the branching process in a branch-and-cut code for general mixed integer programs.}, language = {en} } @misc{BorndoerferEisenblaetterGroetscheletal., author = {Bornd{\"o}rfer, Ralf and Eisenbl{\"a}tter, Andreas and Gr{\"o}tschel, Martin and Martin, Alexander}, title = {Frequency Assignment in Cellular Phone Networks}, doi = {10.1023/A:1018908907763}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3044}, number = {SC-97-35}, abstract = {We present a graph-theoretic model for the \emph{frequency assignment problem} in Cellular Phone Networks: Obeying several technical and legal restrictions, frequencies have to be assigned to transceivers so that interference is as small as possible. This optimization problem is NP-hard. Good approximation cannot be guaranteed, unless P = NP. We describe several assignment heuristics. These heuristics are simple and not too hard to implement. We give an assessment of the heuristics' efficiency and practical usefulness. For this purpose, typical instances of frequency assignment problems with up to 4240 transceivers and 75 frequencies of a German cellular phone network operator are used. The results are satisfying from a practitioner's point of view. The best performing heuristics were integrated into a network planning system used in practice.}, language = {en} } @misc{AbdelHamidBorndoerfer, author = {Abdel-Hamid, Atef Abdel-Aziz and Bornd{\"o}rfer, Ralf}, title = {On the Complexity of Storage Assignment Problems.}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-1430}, number = {SC-94-14}, abstract = {{\def\NP{\hbox{\$\cal N\kern-.1667em\cal P\$}} The {\sl storage assignment problem} asks for the cost minimal assignment of containers with different sizes to storage locations with different capacities. Such problems arise, for instance, in the optimal control of automatic storage devices in flexible manufacturing systems. This problem is known to be \$\NP\$-hard in the strong sense. We show that the storage assignment problem is \$\NP\$-hard for {\sl bounded sizes and capacities}, even if the sizes have values \$1\$ and~\$2\$ and the capacities value~\$2\$ only, a case we encountered in practice. Moreover, we prove that no polynomial time \$\epsilon\$-approximation algorithm exists. This means that almost all storage assignment problems arising in practice are indeed hard.}}, language = {en} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Optimization of Transportation Systems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-3529}, number = {SC-98-09}, abstract = {The world has experienced two hundred years of unprecedented advances in vehicle technology, transport system development, and traffic network extension. Technical progress continues but seems to have reached some limits. Congestion, pollution, and increasing costs have created, in some parts of the world, a climate of hostility against transportation technology. Mobility, however, is still increasing. What can be done? There is no panacea. Interdisciplinary cooperation is necessary, and we are going to argue in this paper that {\em Mathematics\/} can contribute significantly to the solution of some of the problems. We propose to employ methods developed in the {\em Theory of Optimization\/} to make better use of resources and existing technology. One way of optimization is better planning. We will point out that {\em Discrete Mathematics\/} provides a suitable framework for planning decisions within transportation systems. The mathematical approach leads to a better understanding of problems. Precise and quantitative models, and advanced mathematical tools allow for provable and reproducible conclusions. Modern computing equipment is suited to put such methods into practice. At present, mathematical methods contribute, in particular, to the solution of various problems of {\em operational planning}. We report about encouraging {\em results\/} achieved so far.}, language = {en} } @misc{BorndoerferGroetschelHerzogetal., author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Herzog, Werner and Klostermeier, Fridolin and Konsek, Wilhelm and K{\"u}ttner, Christian}, title = {K{\"u}rzen muß nicht Kahlschlag heißen - das Beispiel Telebus-Behindertenfahrdienst Berlin}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-2510}, number = {SC-96-41}, abstract = {M{\"u}ssen Etatk{\"u}rzungen bei staatlichen Dienstleistungseinrichtungen notwendig zu Leistungseinschr{\"a}nkungen oder Geb{\"u}hrenerh{\"o}hungen f{\"u}hren? Wir zeigen am Beispiel des Berliner Behindertenfahrdienstes {\em Telebus}, da\ss{} Sparzwang auch als Chance zur Verbesserung der eigenen Verwaltungs- und Arbeitsabl{\"a}ufe genutzt werden kann. Durch st{\"a}rkere Dienstleistungsorientierung, Vereinfachung der Arbeitsabl{\"a}ufe und durch den Einsatz von moderner EDV und von mathematischen Optimierungsmethoden zur Fahrzeugeinsatzplanung werden bei Telebus heute staatliche Leistungen trotz geringeren Etats besser erbracht als vorher.}, language = {de} } @misc{BorndoerferGroetschelLoebel, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and L{\"o}bel, Andreas}, title = {Duty Scheduling in Public Transit}, doi = {10.1007/978-3-642-55753-8_50}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6286}, number = {01-02}, abstract = {This article is about \emph{adaptive column generation techniques} for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.}, language = {en} }