90C10 Integer programming
Refine
Year of publication
Document Type
- ZIB-Report (26) (remove)
Has Fulltext
- yes (26)
Is part of the Bibliography
- no (26) (remove)
Keywords
- combinatorial optimization (5)
- integer programming (5)
- line planning (4)
- Integer Programming (3)
- transfers (3)
- Kombinatorische Optimierung (2)
- Operations Research (2)
- Optimierung (2)
- column generation (2)
- direct connection (2)
- duty scheduling (2)
- integrated scheduling (2)
- metric inequalities (2)
- rapid branching (2)
- vehicle positioning (2)
- Airline Crew Scheduling (1)
- Benders' decomposition (1)
- Branch and Generate (1)
- Cellular Radio Telephone Systems (1)
- Column Generation (1)
- Dienstplanung (1)
- Duty Rostering (1)
- Flugzeugumlaufplanung (1)
- Frequency Assignment Problem (1)
- Ganzzahlige Programmierung (1)
- Integrierte Umlauf- und Dienstplanung (1)
- Kürzeste Wege (1)
- Linienplanung (1)
- Minimum-Cost Flow Problems (1)
- Nahverkehr (1)
- Optimization (1)
- Passenger routing (1)
- Periodic timetabling (1)
- Public Transit (1)
- Public transport (1)
- Regionalverkehr (1)
- Robust Optimization (1)
- Spaltenerzeugung (1)
- Tail Assignment (1)
- Ticket prices (1)
- Umlaufplanung (1)
- Umsteigen (1)
- Vehicle Routing Problem (1)
- bundle method (1)
- combinatorial packing (1)
- cost allocation game (1)
- crew scheduling (1)
- duty rostering (1)
- duty templates (1)
- facet (1)
- hyperassignments (1)
- hypergraph (1)
- hypergraphs (1)
- ideal matrices (1)
- inequality (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
We consider a novel partitioning of the set of non-dominated points for general multi-objective integer programs with $k$ objectives. The set of non-dominated points is partitioned into a set of non-dominated points whose efficient solutions are also efficient for some restricted subproblem with one less objective; the second partition comprises the non-dominated points whose efficient solutions are
inefficient for any of the restricted subproblems. We show that the first partition has the nice property that it yields finite rectangular boxes in which the points of the second partition are
located.
The task of timetabling is to schedule the trips in a public transport system by determining periodic arrival and departure times at every station. The goal is to provide a service that is both attractive for passengers and can be operated economically. To date, timetable optimization is generally done with respect to fixed passenger routes, i.e., it is assumed that passengers do not respond to changes in the timetable. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We propose several models that differ in the allowed passenger paths and the objectives. We compare these models theoretically and report on computations on real-world instances for the city of Wuppertal.
We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We derive a feasibility condition for path capacities supporting such direct connection flows similar to the feasibility condition for arc capacities in ordinary multi-commodity flows.
The concept allows to solve large-scale real-world line planning problems in public transport including a novel passenger routing model that favors direct connections over connections with transfers.
The set packing problem, sometimes also called the stable set problem, is a well-known NP-hard problem in combinatorial optimization with a wide range of applications and an interesting polyhedral structure, that has been the subject of intensive study. We contribute to this field by showing how, employing cliques, odd set inequalities for the matching problem can be generalized to valid inequalities for the set packing polytope with a clear combinatorial meaning.
We consider multi-commodity flow problems in which capacities are installed on paths. In this setting, it is often important to distinguish between flows on direct connection routes, using single paths, and flows that include path switching. We show that the concept of metric inequalities to characterize capacities that
support a multi-commodity flow can be generalized to deal with direct connections.
We propose a novel extended formulation for the line planning problem in public transport. It is based on a new concept of frequency configurations that account for all possible options to provide a required transportation capacity on an infrastructure edge. We show that this model yields a strong LP relaxation. It implies, in particular, general classes of facet defining inequalities for the standard model.
The treatment of transfers is a major challenge in line planning. Existing models either route passengers and lines sequentially, and hence disregard essential degrees of freedom, or they are of
extremely large scale, and seem to be computationally intractable. We propose a novel direct connection approach that allows an integrated optimization of line and passenger routing, including accurate estimates of the number of direct travelers, for large-scale real-world instances.
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.
This paper provides a generic formulation for rolling stock planning
problems in the context of intercity passenger traffic. The main contributions
are a graph theoretical model and a Mixed-Integer-Programming
formulation that integrate all main requirements of the considered
Vehicle-Rotation-Planning problem (VRPP). We show that it is
possible to solve this model for real-world instances provided by our
industrial partner DB Fernverkehr AG using modern algorithms and
computers.