90B20 Traffic problems
Refine
Year of publication
Document Type
- ZIB-Report (15)
- Doctoral Thesis (2)
Language
- English (17) (remove)
Is part of the Bibliography
- no (17)
Keywords
- integer programming (4)
- Nahverkehr (3)
- combinatorial optimization (3)
- line planning (3)
- transfers (3)
- vehicle scheduling (3)
- Netzwerkaggregation (2)
- Optimierung (2)
- demand function (2)
- discrete choice model (2)
Institute
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.
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 present the problem of planning mobile tours of inspectors on German motorways to enforce the payment of the toll for heavy good trucks. This is a special type of vehicle routing problem with the objective to conduct as good inspections as possible on the complete network. In addition, the crews of the tours have to be scheduled. Thus, we developed a personalized crew rostering model. The planning of daily tours and the rostering are combined in a novel integrated approach and formulated as a complex and large scale Integer Program. The paper focuses first on different requirements for the rostering and how they can be modeled in detail. The second focus is on a bicriterion analysis of the planning problem to find the balance between the control quality and the roster acceptance. On the one hand the tour planning is a profit maximization problem and on the other hand the rostering should be made in a employee friendly way. Finally, computational results on real-world instances show the practicability of our method.
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 study the influence of technology, traffic properties and price trends on optimized
design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node,
we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical
(packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in
traffic volume,
demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints,
we assess the relative roles of the two distinct equipment groups, IP routers and optical
cross-connects, with respect to resulting changes in cost-sensitive network architectures.
This paper presents a case study on a railway timetable optimization for the very dense Simplon corridor, a major railway connection in the Alps between Switzerland and Italy. Starting from a detailed microscopic network as it is used in railway simulation, the data is transformed by an automatic procedure to a less detailed macroscopic network, that is sufficient for the purpose of capacity planning and amenable to state-of-the-art integer programming optimization methods. In this way, the macroscopic railway network is saturated with trains. Finally, the corresponding timetable is re-transformed to the microscopic level in such a way that it can be operated without any conflicts among the slots. Using this integer programming based micro-macro aggregation-disaggregation approach, it becomes for the first time possible to generate a profit maximal and conflict free timetable for the complete Simplon corridor over an entire day by a simultaneous optimization of all trains requests. This also allows to to undertake a sensitivity analysis of various problem parameters.
In this paper a bottom-up approach of automatic simplification of a railway network is presented. Starting from a very detailed, microscopic level, as it is used in railway simulation, the network is transformed by an algorithm to a less detailed level (macroscopic network), that is sufficient for long-term planning and optimization. In addition running and headway times are rounded to a pre-chosen time discretization by a special cumulative method, which we will present and analyse in this paper. After the transformation we fill the network with given train requests to compute an optimal slot allocation. Then the optimized schedule is re-transformed into the microscopic level and can be simulated without any conflicts occuring between the slots. The algorithm is used to transform the network of the very dense Simplon corridor between Swiss and Italy. With our aggregation it is possible for the first time to generate a profit maximal and conflict free timetable for the corridor across a day by a simultaneously optimization run.
We propose a novel integer programming approach to transfer minimization for line planning problems in public transit. The idea is to incorporate penalties for transfers that are induced by “connection capacities” into the construction of the passenger paths. We show that such penalties can be dealt with by a combination of shortest and constrained shortest path algorithms such that the pricing problem for passenger paths can be solved efficiently. Connection capacity penalties (under)estimate the true transfer times. This error is, however, not a problem in practice. We show in a computational comparison with two standard models on a real-world scenario that our approach can be used to minimize passenger travel and transfer times for large-scale line planning problems with accurate results.
The mathematical treatment of planning problems in public transit has made significant advances in the last decade. Among others, the classical problems of vehicle and crew scheduling can nowadays be solved on a routine basis using combinatorial optimization methods. This is not yet the case for problems that pertain to the design of public transit networks, and for the problems of operations control that address the implementation of a schedule in the presence of disturbances. The article gives a sketch of the state and important developments in these areas, and it addresses important challenges. The vision is that mathematical tools of computer aided scheduling (CAS) will soon play a similar role in the design and operation of public transport systems as CAD systems in manufacturing.