90C10 Integer programming
Refine
Year of publication
Document Type
- ZIB-Report (23) (remove)
Language
- English (23) (remove)
Has Fulltext
- yes (23)
Is part of the Bibliography
- no (23)
Keywords
- combinatorial optimization (5)
- integer programming (5)
- line planning (4)
- Integer Programming (3)
- transfers (3)
- column generation (2)
- direct connection (2)
- metric inequalities (2)
- rapid branching (2)
- vehicle positioning (2)
- Airline Crew Scheduling (1)
- Branch and Generate (1)
- Cellular Radio Telephone Systems (1)
- Column Generation (1)
- Duty Rostering (1)
- Flugzeugumlaufplanung (1)
- Frequency Assignment Problem (1)
- Ganzzahlige Programmierung (1)
- Kombinatorische Optimierung (1)
- Linienplanung (1)
- Minimum-Cost Flow Problems (1)
- Nahverkehr (1)
- Operations Research (1)
- Optimierung (1)
- Optimization (1)
- Passenger routing (1)
- Periodic timetabling (1)
- Public Transit (1)
- Public transport (1)
- Robust Optimization (1)
- Spaltenerzeugung (1)
- Tail Assignment (1)
- Ticket prices (1)
- Umsteigen (1)
- Vehicle Routing Problem (1)
- bundle method (1)
- combinatorial packing (1)
- cost allocation game (1)
- crew scheduling (1)
- duty scheduling (1)
- duty templates (1)
- facet (1)
- hyperassignments (1)
- hypergraph (1)
- hypergraphs (1)
- ideal matrices (1)
- inequality (1)
- integrated scheduling (1)
- large scale optimization (1)
- matching (1)
- mixed-integer-programming (1)
- multi-commodity flow problem (1)
- nonlinear programming (1)
- operations research (1)
- polyhedral combinatorics (1)
- public transit (1)
- quadratic programming (1)
- robuste Optimierung (1)
- rolling-stock-planning (1)
- set packing (1)
- set partitioning (1)
- shortest paths (1)
- vehicle rotation planning (1)
- vehicle scheduling (1)
- Öffentlicher Verkehr (1)
Institute
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.
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.
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.