Refine
Year of publication
Document Type
- ZIB-Report (110)
- In Proceedings (70)
- Article (46)
- Book chapter (4)
- Other (3)
- Doctoral Thesis (2)
- In Collection (2)
- Book (1)
- Habilitation (1)
- Master's Thesis (1)
Keywords
- integer programming (9)
- line planning (8)
- Optimierung (7)
- combinatorial optimization (6)
- Periodic timetabling (5)
- Linienplanung (4)
- Mixed Integer Programming (4)
- column generation (4)
- public transport (4)
- Column Generation (3)
- Nahverkehr (3)
- Operations Research (3)
- Passenger routing (3)
- Public transport (3)
- computational complexity (3)
- duty scheduling (3)
- polyhedral combinatorics (3)
- transfers (3)
- Fallstudie (2)
- Game Theory (2)
- Ganzzahlige Programmierung (2)
- Hilbert's projective metric (2)
- Integer Programming (2)
- Kombinatorische Optimierung (2)
- Linienplan (2)
- Netzwerkaggregation (2)
- Optimization (2)
- Periodic Event Scheduling Problem (2)
- Periodic Timetabling (2)
- Preisplanung (2)
- Railway Slot Allocation (2)
- Stackelberg Equilibrium (2)
- Vehicle Routing Problem (2)
- case study (2)
- demand function (2)
- direct connection (2)
- discrete choice model (2)
- discrete optimization (2)
- duty templates (2)
- fare planning (2)
- lognormal duration (2)
- metric inequalities (2)
- network aggregation (2)
- railway track allocation (2)
- rapid branching (2)
- robust optimization (2)
- set packing (2)
- set partitioning (2)
- vehicle positioning (2)
- öffentlicher Verkehr (2)
- Benders decomposition (1)
- Benders' decomposition (1)
- Bicriteria Optimization (1)
- Bipartite matching (1)
- Bundle Method (1)
- Change-cycle inequality (1)
- Combinatorial Auctions (1)
- Combinatorial Optimization (1)
- Connectivity (1)
- Controls in transportation networks (1)
- Crew Planning (1)
- Cycle inequality (1)
- Degree Property (1)
- Diskrete Optimierung (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Fahrplan (1)
- Fahrplanung (1)
- Flugzeugumlaufplanung (1)
- Generalization (1)
- Hall condition (1)
- Hypergraph (1)
- Integrated Passenger Routing (1)
- Kürzeste Wege (1)
- Linear and Integer Programming (1)
- Matchings in hypergraphs (1)
- Mixed-Integer Nonlinear Programming (1)
- Multi-Criteria Optimisation (1)
- Multiobjective Shortest Path Problem (1)
- Nachfragefunktion (1)
- Network Optimization (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 Track Allocation (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (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)
- Ticket prices (1)
- Toll Enforcement (1)
- Track Allocation Problem (1)
- Train Dispatching (1)
- Train Timetabling (1)
- Train Timetabling Problem (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Umsteigen (1)
- Value Creation Process (1)
- Variable-Depth Neighborhood Search (1)
- Vehicle scheduling (1)
- Vickrey Auction (1)
- Vickrey Auktion (1)
- activity network (1)
- assignment (1)
- bicriteria optimization (1)
- capacity optimization (1)
- coarse-to-fine approach (1)
- combinatorial packing (1)
- cost allocation game (1)
- crew rostering (1)
- cycle embedding problem (1)
- directed hypergraphs (1)
- discrete-continuous algorithm (1)
- diskrete Optimierung (1)
- driver satisfaction (1)
- duty rostering (1)
- facet (1)
- facet classification (1)
- flight planning (1)
- free flight (1)
- freight train routing (1)
- ganzzahlige Programmierung (1)
- graph segmentation (1)
- hyperassignment (1)
- hyperassignments (1)
- hypergraph (1)
- hypergraphs (1)
- ideal matrices (1)
- inequality (1)
- integrated scheduling (1)
- large scale optimization (1)
- lognormal distribution (1)
- macroscopic railway modeling (1)
- makroskopische Bahnmodellierung (1)
- matching (1)
- mixed integer programming (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)
- optimal control (1)
- pattern detection (1)
- periodic timetable (1)
- periodic timetabling, modulo network simplex, passenger routing (1)
- polyhedral structure (1)
- public transit (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 path (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) (remove)
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.
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.
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.
We introduce a concurrent solver for the periodic event scheduling problem (PESP). It combines mixed integer programming techniques, the modulo network simplex method, satisfiability approaches, and a new heuristic based on maximum cuts. Running these components in parallel speeds up the overall solution process. This enables us to significantly improve the current upper and lower bounds for all benchmark instances of the library PESPlib.