TY - GEN A1 - Borndörfer, Ralf A1 - Schelten, Uwe A1 - Schlechte, Thomas A1 - Weider, Steffen T1 - A Column Generation Approach to Airline Crew Scheduling N2 - 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. T3 - ZIB-Report - 05-37 KW - Integer Programming KW - Airline Crew Scheduling KW - Branch and Generate Y1 - 2005 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-8713 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit N2 - 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. T3 - ZIB-Report - 04-14 KW - vehicle scheduling KW - crew scheduling KW - integrated scheduling KW - public transit KW - bundle method Y1 - 2004 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7898 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Löbel, Andreas A1 - Weider, Steffen T1 - Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr N2 - Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im ö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ür den Einsatz in den Planungssystemen MICROBUS II und DIVA. T3 - ZIB-Report - 02-10 KW - Integrierte Umlauf- und Dienstplanung KW - Umlaufplanung KW - Dienstplanung KW - Optimierung KW - Regionalverkehr Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6773 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Eisenblätter, Andreas A1 - Grötschel, Martin A1 - Martin, Alexander T1 - The Orientation Model for Frequency Assignment Problems N2 - 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. T3 - ZIB-Report - TR-98-01 KW - Minimum-Cost Flow Problems KW - Cellular Radio Telephone Systems KW - Frequency Assignment Problem KW - Integer Programming Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5627 ER -