Refine
Year of publication
Document Type
- ZIB-Report (139)
- In Proceedings (83)
- 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 (47)
- 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)
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.
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.
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.
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to feasible rosters for one month. We present computational results in a case-study on a German subnetwork which documents the practicability of our approach.
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to
feasible rosters for one month. We present computational results in a
case-study on a German subnetwork which documents the practicability of our approach.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
We propose a new coarse-to-fine approach to solve certain linear programs by column generation. The problems that we address contain layers corresponding to different levels of detail, i.e., coarse layers as well as fine layers. These layers are utilized to design
efficient pricing rules. In a nutshell, the method shifts the pricing of a fine linear program to a coarse counterpart. In this way, major decisions are taken in the coarse layer, while minor
details are tackled within the fine layer. We elucidate our methodology by an application to a complex railway rolling stock rotation problem. We provide comprehensive computational results that demonstrate the benefit of this new technique for the solution of large scale problems.
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.