90B06 Transportation, logistics
Refine
Keywords
- column generation (3)
- Rapid Branching (2)
- rapid branching (2)
- Bundle Method (1)
- Column Generation (1)
- Container terminal (1)
- Hypergraph Modeling (1)
- Integer Programming (1)
- Integer programming (1)
- Optimization (1)
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.
Rapid Branching
(2012)
We propose rapid branching (RB) as a general branch-and-bound heuristic for solving large scale optimization problems in traffic and transport. The key idea is to combine a special branching rule and a greedy node selection strategy in order to produce solutions of controlled quality rapidly and efficiently. We report on three successful applications of the method for integrated vehicle and crew scheduling, railway track allocation, and railway vehicle rotation planning.
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.
The track allocation problem, also known as train routing problem or train timetabling problem, is to find a conflict-free set of train routes of maximum value in a railway network. Although it can be modeled as a standard path packing problem, instances of sizes relevant for real-world railway applications could not be solved up to now. We propose a rapid branching column generation approach that integrates the solution of the LP relaxation of a path coupling formulation of the problem with a special rounding heuristic. The approach is based on and exploits special properties of the bundle method for the approximate solution of convex piecewise linear functions. Computational results for difficult instances of the benchmark library TTPLIB are reported.
We propose a model for the integrated optimization of vehicle rotations and vehicle compositions in long distance railway passenger transport. The main contribution of the paper is a hypergraph model that is able to handle the challenging technical requirements as well as very general stipulations with respect to the "regularity" of a schedule. The hypergraph model directly generalizes network flow models, replacing arcs with hyperarcs. Although NP-hard in general, the model is computationally well-behaved in practice. High quality solutions can be produced in reasonable time using high performance Integer Programming techniques, in particular, column generation and rapid branching. We show that, in this way, large-scale real world instances of our cooperation partner DB Fernverkehr can be solved.
Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially.
Im Zuge der Übernahme von 6 Linien der Havelbus Verkehrsgesellschaft mbH durch die ViP Verkehr in Potsdam GmbH ergab sich 2009 die Notwendigkeit der Entwicklung eines neuen Linien- und Taktplans für das Jahr 2010. Das Konrad-Zuse-Zentrum für Informationstechnik Berlin (ZIB) entwickelt in einem Projekt des DFG-Forschungszentrums Matheon ein Verfahren zur mathematischen Linienoptimierung. Dieses Tool wurde bei der Optimierung des ViP Linienplans 2010 in einer projektbegleitenden Studie eingesetzt, um Alternativen bei verschiedenen Planungs- und Zielvorgaben auszuloten. In dem Artikel wird eine Auswertung der Ergebnisse mit dem Verkehrsanalysesystem Visum der PTV AG beschrieben. Die Auswertungen bestätigen, dass mit Hilfe von mathematischer Optimierung eine weitere Verkürzung der Reisezeit um 1%, eine als um 6% verkürzt empfundene Reisezeit, 10% weniger Fahrzeit im Fahrzeug und eine gleichzeitige Kostenreduktion um 5% möglich sind
Die Angebotsplanung im öffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,
Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und
Preisplanung vor. Wir zeigen anhand von Berechnungen für die Verkehrsbetriebe in Potsdam
(ViP), dass sich damit komplexe Zusammenhänge quantitativ analysieren lassen. Auf diese
Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien
und die Wahl von Reisewegen der Passagiere, Abhängigkeiten zwischen Kosten und Reisezeiten
sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.
Every day, millions of people are transported by buses, trains, and airplanes
in Germany. Public transit (PT) is of major importance for the quality of
life of individuals as well as the productivity of entire regions. Quality and
efficiency of PT systems depend on the political framework (state-run, market
oriented) and the suitability of the infrastructure (railway tracks, airport
locations), the existing level of service (timetable, flight schedule), the use
of adequate technologies (information, control, and booking systems), and
the best possible deployment of equipment and resources (energy, vehicles,
crews). The decision, planning, and optimization problems arising in this
context are often gigantic and “scream” for mathematical support because of
their complexity.
This article sketches the state and the relevance of mathematics in planning
and operating public transit, describes today’s challenges, and suggests a
number of innovative actions.
The current contribution of mathematics to public transit is — depending
on the transportation mode — of varying depth. Air traffic is already well
supported by mathematics. Bus traffic made significant advances in recent
years, while rail traffic still bears significant opportunities for improvements.
In all areas of public transit, the existing potentials are far from being exhausted.
For some PT problems, such as vehicle and crew scheduling in bus and
air traffic, excellent mathematical tools are not only available, but used in
many places. In other areas, such as rolling stock rostering in rail traffic,
the performance of the existing mathematical algorithms is not yet sufficient.
Some topics are essentially untouched from a mathematical point
of view; e.g., there are (except for air traffic) no network design or fare
planning models of practical relevance. PT infrastructure construction is
essentially devoid of mathematics, even though enormous capital investments
are made in this area. These problems lead to questions that can only be
tackled by engineers, economists, politicians, and mathematicians in a joint
effort.
Among other things, the authors propose to investigate two specific topics,
which can be addressed at short notice, are of fundamental importance not
only for the area of traffic planning, should lead to a significant improvement
in the collaboration of all involved parties, and, if successful, will be of real
value for companies and customers:
• discrete optimal control: real-time re-planning of traffic systems in case
of disruptions,
• model integration: service design in bus and rail traffic.
Work on these topics in interdisciplinary research projects could be funded
by the German ministry of research and education (BMBF), the German
ministry of economics (BMWi), or the German science foundation (DFG).
The timetable is the essence of the service offered by any provider
of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the
timetable has a major impact on both operating costs and on passenger
comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two
strategies with respect to vehicle operation costs. It turns out that
for short time horizons, periodic timetabling can be suboptimal; for
sufficiently long time horizons, however, periodic timetabling can
always be done in an optimal way'.
Line planning is an important step in the strategic planning
process of a public transportation system. In this paper, we discuss an
optimization model for this problem in order to minimize operation costs
while guaranteeing a certain level of quality of service, in terms of
available transport capacity. We analyze the problem for path and tree
network topologies as well as several categories of line operation that
are important for the Quito Trolebus system. It turns out that, from a
computational complexity worst case point of view, the problem is hard in
all but the most simple variants. In practice, however, instances based
on real data from the Trolebus System in Quito can be solved quite well,
and significant optimization potentials can be demonstrated.
We introduce new elevator group control algorithms that can be implemented to be real-time compliant on embedded microcontrollers. The algorithms operate a group of elevators in a destination call system, i.e. passengers specify the destination floor instead of the travel direction only. The aim is to achieve small waiting and travel times for the passengers. We provide evidence, using simulation, that the algorithms offer good performance. One of our algorithms has been implemented by our industry partner and is used in real-world systems.
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a network such that a giv en demand can be satisfied. There are two objectives. passengers want to minimize travel times, the transport company wishes to minimize operating costs. We investigate three variants of a multi-commo dity flow model for line planning that differ with respect to passenger routings. The first model allows arbitrary routings, the second only unsplittable routings, and the third only shortest path rou tings with respect to the network. We compare these models theoretically and computationally on data for the city of Potsdam.
This paper concerns the problem of operating a landside container exchange area that is serviced by multiple semi-automated rail mounted gantry cranes (RMGs) that are moving on a single bi-directional traveling lane. Such a facility is being built by Patrick Corporation at the Port Botany terminal in Sydney. The gantry cranes are a scarce resource and handle the bulk of container
movements. Thus, they require a sophisticated analysis to achieve near optimal utilization. We present a three stage algorithm to manage the container exchange facility, including the scheduling of cranes, the control of associated short-term container stacking, and
the allocation of delivery locations for trucks and other container transporters. The key components of our approach are a time scale decomposition, whereby an integer program controls decisions across a long time horizon to produce a balanced plan that is fed to a series of short time scale online subproblems, and a highly efficient space-time divisioning of short term storage areas.
A computational evaluation shows that our heuristic can find effective solutions for the planning problem; on real-world data it yields a solution at most 8% above a lower bound on optimal RMG utilization.