90C10 Integer programming
Refine
Document Type
- ZIB-Report (13)
- Doctoral Thesis (2)
Is part of the Bibliography
- no (15) (remove)
Keywords
- combinatorial optimization (4)
- line planning (4)
- integer programming (3)
- transfers (3)
- Kombinatorische Optimierung (2)
- direct connection (2)
- hypergraph (2)
- metric inequalities (2)
- Benders' decomposition (1)
- Ganzzahlige Programmierung (1)
- Kürzeste Wege (1)
- Linienplanung (1)
- Operations Research (1)
- Passenger routing (1)
- Periodic timetabling (1)
- Public transport (1)
- Umsteigen (1)
- assignment (1)
- bipartite (1)
- duty rostering (1)
- duty scheduling (1)
- facet (1)
- hyperassignment (1)
- hyperassignments (1)
- ideal matrices (1)
- inequality (1)
- integrated scheduling (1)
- line planning, transfers,Steiner connectivity problem (1)
- matching (1)
- multi-commodity flow problem (1)
- polyhedral combinatorics (1)
- set packing (1)
- set partitioning (1)
- vehicle rotation planning (1)
Institute
- Mathematics of Transportation and Logistics (15) (remove)
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 integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity.
In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem.
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.
This thesis deals with the hypergraph assignment problem (HAP), a set partitioning problem in a special type of hypergraph. The HAP generalizes the assignment problem from bipartite graphs to what we call bipartite hypergraphs, and is motivated by applications in railway vehicle rotation planning. The main contributions of this thesis concern complexity, polyhedral results, analyses of random instances, and primal methods for the HAP. We prove that the HAP is NP-hard and APX-hard even for small hyperedge sizes and hypergraphs with a special partitioned structure. We also study the complexity of the set packing and covering relaxations of the HAP, and present for certain cases polynomial exact or approximation algorithms. A complete linear description is known for the assignment problem. We therefore also study the HAP polytope. There, we have a huge number of facet-defining inequalities already for a very small problem size. We describe a method for dividing the inequalities into equivalence classes without resorting to a normal form. Within each class, facets are related by certain symmetries and it is sufficient to list one representative of each class to give a complete picture of the structural properties of the polytope. We propose the algorithm "HUHFA" for the classification that is applicable not only to the HAP but combinatorial optimization problems involving symmetries in general. In the largest possible HAP instance for which we could calculate the complete linear description, we have 14049 facets, which can be divided into 30 symmetry classes. We can combinatorially interpret 16 of these classes. This is possible by employing cliques to generalize the odd set inequalities for the matching problem. The resulting inequalities are valid for the polytope associated with the set packing problem in arbitrary hypergraphs and have a clear combinatorial meaning. An analysis of random instances provides a better insight into the structure of hyperassignments. Previous work has extensively analyzed random instances for the assignment problem theoretically and practically. As a generalization of these results for the HAP, we prove bounds on the expected value of a minimum cost hyperassignment that uses half of the maximum possible number of hyperedges that are not edges. In a certain complete partitioned hypergraph G2,2n with i. i. d. exponential random variables with mean 1 as hyperedge costs it lies between 0.3718 and 1.8310 if the vertex number tends to infinity. Finally, we develop an exact combinatorial solution algorithm for the HAP that combines three methods: A very large-scale neighborhood search, the composite columns method for the set partitioning problem, and the network simplex algorithm.
This thesis introduces the Steiner connectivity problem. It is a generalization of the well
known Steiner tree problem. Given a graph G = (V, E) and a subset T ⊆ V of the nodes,
the Steiner tree problem consists in finding a cost minimal set of edges connecting all
nodes in T . The Steiner connectivity problem chooses, instead of edges, from a given set
of paths a subset to connect all nodes in T . We show in the first part of this thesis that
main results about complexity, approximation, integer programming formulations, and
polyhedra can be generalized from the Steiner tree problem to the Steiner connectivity
problem.
An example for a straightforward generalization are the Steiner partition inequalities, a
fundamental class of facet defining inequalities for the Steiner tree problem. They can be
defined for the Steiner connectivity problem in an analogous way as for the Steiner tree
problem. An example for a generalization that needs more effort is the definition of a
directed cut formulation and the proof that this dominates the canonical undirected cut
formulation enriched by all Steiner partition inequalities. For the Steiner connectivity
problem this directed cut formulation leads to extended formulations, a concept that is
not necessary for the Steiner tree problem. There are also major differences between
both problems. For instance, the case T = V for the Steiner connectivity problem is
equivalent to a set covering problem and, hence, not a polynomial solvable case as in the
Steiner tree problem.
The Steiner connectivity problem is not only an interesting generalization of the Steiner
tree problem but also the underlying connectivity problem in line planning with inte-
grated passenger routing. The integrated line planning and passenger routing problem
is an important planning problem in service design of public transport and the topic of
the second part. Given is the infrastructure network of a public transport system where
the edges correspond to streets and tracks and the nodes correspond to stations/stops
of lines. The task is to find paths in the infrastructure network for lines and passengers
such that the capacities of the lines suffice to transport all passengers. Existing models
in the literature that integrate a passenger routing in line planning either treat transfers
in a rudimentary way and, hence, neglect an important aspect for the choice of the pas-
senger routes, or they treat transfers in a too comprehensive way and cannot be solved
for large scale real world problems. We propose a new model that focuses on direct
connections. The attractiveness of transfer free connections is increased by introducing a transfer penalty for each non-direct connection. In this way, a passenger routing is
computed that favors direct connections.
For the computation of this model we also implemented algorithms influenced by the
results for the Steiner connectivity problem. We can compute with our model good
solutions that minimize a weighted sum of line operating costs and passengers travel
times. These solutions improve the solutions of an existing approach, that does not
consider direct connections, by up to 17%. In contrast to a comprehensive approach,
that considers every transfer and for which we could not even solve the root LP within
10 hours for large instances, the solutions of the new model, computed in the same time,
are close to optimality (<1%) or even optimal for real world instances. In a project with
the Verkehr in Potsdam GmbH to compute the line plan for 2010 we showed that our
approach is applicable in practice and can be used to solve real world problems.
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.