Refine
Year of publication
Document Type
- ZIB-Report (139)
- In Proceedings (84)
- Article (63)
- Book chapter (5)
- In Collection (3)
- Other (3)
- Doctoral Thesis (2)
- Book (1)
- Habilitation (1)
- Master's Thesis (1)
Keywords
- line planning (13)
- Optimierung (9)
- integer programming (9)
- column generation (7)
- combinatorial optimization (6)
- Periodic timetabling (5)
- public transport (5)
- Column Generation (4)
- Integer Programming (4)
- Linienplanung (4)
- Mixed Integer Programming (4)
- Public transport (4)
- duty scheduling (4)
- Nahverkehr (3)
- Operations Research (3)
- Optimization (3)
- Passenger routing (3)
- computational complexity (3)
- discrete optimization (3)
- flight planning (3)
- free flight (3)
- optimal control (3)
- polyhedral combinatorics (3)
- shortest path (3)
- transfers (3)
- Dienstplanung (2)
- Fallstudie (2)
- Game Theory (2)
- Ganzzahlige Programmierung (2)
- Hilbert's projective metric (2)
- Kombinatorische Optimierung (2)
- Linienplan (2)
- Netzwerkaggregation (2)
- Periodic Event Scheduling Problem (2)
- Periodic Timetabling (2)
- Predictive Maintenance (2)
- Preisplanung (2)
- Railway Slot Allocation (2)
- Railway Track Allocation (2)
- Rolling Stock Rotation Planning (2)
- Stackelberg Equilibrium (2)
- Vehicle Routing Problem (2)
- case study (2)
- demand function (2)
- direct connection (2)
- discrete choice model (2)
- discrete-continuous algorithm (2)
- duty templates (2)
- fare planning (2)
- integrated scheduling (2)
- lognormal duration (2)
- metric inequalities (2)
- mixed integer programming (2)
- network aggregation (2)
- public transit (2)
- railway track allocation (2)
- rapid branching (2)
- robust optimization (2)
- set packing (2)
- set partitioning (2)
- vehicle positioning (2)
- vehicle scheduling (2)
- öffentlicher Verkehr (2)
- Airline Applications (1)
- Airline Crew Scheduling (1)
- Benders decomposition (1)
- Benders' decomposition (1)
- Bicriteria Optimization (1)
- Bipartite matching (1)
- Branch and Generate (1)
- Bundle Method (1)
- Cellular Radio Telephone Systems (1)
- Change-cycle inequality (1)
- Combinatorial Auctions (1)
- Combinatorial Optimization (1)
- Connectivity (1)
- Constraint Shortest Paths Problem (1)
- Controls in transportation networks (1)
- Crew Planning (1)
- Cycle inequality (1)
- Degree Property (1)
- Discrete Mathematics (1)
- Diskrete Optimierung (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Duty Scheduling (1)
- Electric Vehicle Scheduling (1)
- Fahrplan (1)
- Fahrplanung (1)
- Flight Planning Problem (1)
- Flugzeugumlaufplanung (1)
- Frequency Assignment Problem (1)
- Generalization (1)
- Hall condition (1)
- Heuristic (1)
- Hypergraph (1)
- Integer Linear Programming (1)
- Integrated Passenger Routing (1)
- Integrierte Umlauf- und Dienstplanung (1)
- Kürzeste Wege (1)
- Linear and Integer Programming (1)
- Logistics (1)
- Lower Bound (1)
- Management Science and Operations Research (1)
- Matchings in hypergraphs (1)
- Minimum-Cost Flow Problems (1)
- Mixed-Integer Nonlinear Programming (1)
- Modeling and Simulation (1)
- Moving Block (1)
- Multi-Criteria Optimisation (1)
- Multiobjective Approximation Algorithms (1)
- Multiobjective Shortest Path Problem (1)
- Multiobjective Shortest Paths (1)
- Nachfragefunktion (1)
- Network Optimization (1)
- Newton's method (1)
- Non-Linear Charging (1)
- Normal hypergraphs (1)
- Output-Sensitive Multiobjective Combinatorial Problems (1)
- Packing problems (1)
- Partition Inequalities (1)
- Paths (1)
- Polymatrix game (1)
- Price of Anarchy (1)
- Primal-Dual Approximation (1)
- Produktionsfaktor Mathematik (1)
- Proximale Bündelmethode (1)
- Public Transit (1)
- Railway Optimization (1)
- Railway Timetabling (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (1)
- Regionalverkehr (1)
- Robust Optimization (1)
- Rolling Stock Planning, Hypergraph Modeling, Integer Programming, Column Generation, Rapid Branching (1)
- Rolling Stock Rostering (1)
- Security Games (1)
- Shortest Routes in Public Transport (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Spaltenerzeugung (1)
- Stackelberg game (1)
- Steiner Connectivity Problem (1)
- Steiner Tree (1)
- Steiner Tree Generalization (1)
- Steiner connectivity (1)
- Steiner tree (1)
- Steiner tree packing (1)
- Sustainability Indicator (1)
- System Dynamics (1)
- Tail Assignment (1)
- Taktfahrplan (1)
- Test Library (1)
- Ticket prices (1)
- Time Dependent Shortest Paths (1)
- Toll Enforcement (1)
- Track Allocation Problem (1)
- Train Dispatching (1)
- Train Routing (1)
- Train Timetabling (1)
- Train Timetabling Problem (1)
- Transportation (1)
- Transportation Systems (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Umlaufplanung (1)
- Umsteigen (1)
- Value Creation Process (1)
- Variable-Depth Neighborhood Search (1)
- Vehicle scheduling (1)
- Vickrey Auction (1)
- Vickrey Auktion (1)
- Zielorientierte Planung (1)
- activity network (1)
- assignment (1)
- bicriteria optimization (1)
- bundle method (1)
- capacity optimization (1)
- coarse-to-fine approach (1)
- combinatorial packing (1)
- cost allocation game (1)
- crew rostering (1)
- crew scheduling (1)
- cycle embedding problem (1)
- directed hypergraphs (1)
- diskrete Optimierung (1)
- driver satisfaction (1)
- duty rostering (1)
- facet (1)
- facet classification (1)
- freight train routing (1)
- ganzzahlige Programmierung (1)
- global optimization (1)
- graph segmentation (1)
- hyperassignment (1)
- hyperassignments (1)
- hypergraph (1)
- hypergraphs (1)
- ideal matrices (1)
- inequality (1)
- large scale optimization (1)
- lognormal distribution (1)
- macroscopic railway modeling (1)
- makroskopische Bahnmodellierung (1)
- matching (1)
- mixed-integer prgramming (1)
- mixed-integer-programming (1)
- multi-commodity flow problem (1)
- multi-commodity flows (1)
- multi-layer approach (1)
- network interdiction (1)
- nonlinear programming (1)
- operations research (1)
- parametric city modeling (1)
- passenger routing (1)
- pattern detection (1)
- periodic timetable (1)
- periodic timetabling, modulo network simplex, passenger routing (1)
- polyhedral structure (1)
- public transport optimization (1)
- quadratic programming (1)
- railway models, railway capacity, track allocation framework (1)
- railway operations (1)
- railway planning (1)
- railway rolling stock optimization (1)
- railway timetables (1)
- railway vehicle rotation scheduling (1)
- railways (1)
- re-optimization (1)
- robust optimization, rolling stock planning (1)
- robuste Optimierung (1)
- rolling stock rotation problem (1)
- rolling-stock-planning (1)
- rostering (1)
- scheduling (1)
- sequential coarse-first-fine-second planning approach (1)
- set covering (1)
- shortest paths (1)
- symmetry (1)
- timetabling (1)
- toll billing (1)
- trip timetable (1)
- unimodal demand (1)
- vehicle rotation planning (1)
- vehicle routing (1)
- visualization (1)
- ÖPNV (1)
- Öffentlicher Personenverkehr (1)
- Öffentlicher Verkehr (1)
Institute
- Mathematical Optimization (240)
- Mathematics of Transportation and Logistics (106)
- Network Optimization (48)
- ZIB Allgemein (15)
- Modeling and Simulation of Complex Processes (8)
- AI in Society, Science, and Technology (4)
- Mathematics of Health Care (3)
- Computational Medicine (2)
- Mathematical Algorithmic Intelligence (2)
- Mathematics for Life and Materials Science (2)
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.
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.
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.
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.
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.
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.
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?.
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.
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.