Refine
Year of publication
Document Type
- ZIB-Report (19)
- Article (9)
- In Proceedings (9)
- Book chapter (1)
- Doctoral Thesis (1)
Is part of the Bibliography
- no (39)
Keywords
- Periodic timetabling (5)
- Passenger routing (3)
- Public transport (3)
- combinatorial optimization (3)
- line planning (3)
- Linienplan (2)
- Optimierung (2)
- direct connection (2)
- integer programming (2)
- metric inequalities (2)
Institute
Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.
Steiner trees are constructed to connect a set of terminal nodes in a graph. This basic version of the Steiner tree problem is idealized, but it can effectively guide the search for successful approaches to many relevant variants, from both a theoretical and a computational point of view. This article illustrates the theoretical and algorithmic progress on Steiner tree type problems on two examples, the Steiner connectivity and the Steiner tree packing problem.
Umsteigen ohne Warten
(2017)
Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.
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.
Umsteigen ohne Warten
(2017)
Wir stellen einen mathematischen Optimierungsansatz zur Berechnung von periodischen Taktfahrplänen vor, bei dem die Umsteigezeiten unter
Berücksichtigung des Passagierverhaltens minimiert werden. Wir untersuchen damit den Einfluss wichtiger Systemparameter und Verhaltensmuster auf die Beförderungsqualität.
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.
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 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.