90B06 Transportation, logistics
Refine
Year of publication
Document Type
- ZIB-Report (54)
- Master's Thesis (3)
- Habilitation (1)
Has Fulltext
- yes (58)
Is part of the Bibliography
- no (58)
Keywords
- column generation (8)
- Optimierung (7)
- line planning (5)
- online optimization (5)
- real-time (5)
- ADAC (4)
- competitive analysis (4)
- soft time windows (4)
- vehicle dispatching (4)
- Column Generation (3)
- Competitive Analysis (3)
- Integer Programming (3)
- Online Optimization (3)
- Optimization (3)
- combinatorial optimization (3)
- elevator (3)
- integer programming (3)
- online (3)
- public transport (3)
- Fallstudie (2)
- Linienplan (2)
- Linienplanung (2)
- Netzwerkaggregation (2)
- Online-Optimierung (2)
- Passenger routing (2)
- Periodic timetabling (2)
- Public transport (2)
- Train Timetabling Problem (2)
- Vehicle Routing Problem (2)
- branch and bound (2)
- elevator group control (2)
- network aggregation (2)
- polyhedral combinatorics (2)
- pricing (2)
- railway track allocation (2)
- rapid branching (2)
- real world data (2)
- real-world problems (2)
- öffentlicher Verkehr (2)
- Aufzugsgruppensteuerung (1)
- Aufzugssteuerung (1)
- Aufzüge (1)
- Automatic Storage System (1)
- Bicriteria Optimization (1)
- Bundle Method (1)
- Constraint Shortest Paths Problem (1)
- Container Terminal (1)
- Data Library (1)
- Dial-a-Ride problem on trees (1)
- Dial-a-Ride-Problem (1)
- Dienstplanung (1)
- Discrete Mathematics (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Duty Scheduling (1)
- Echtzeit-Optimierung (1)
- Echzeitoptimierung (1)
- Exakte Reoptimierung (1)
- Fahrplan (1)
- Fahrplanung (1)
- Flugzeugumlaufplanung (1)
- Ganzzahlige Programmierung (1)
- Heuristics (1)
- Hochregallagerbediengeräte (1)
- Intermediate Storage Area (1)
- Kommissioniermobile (1)
- Kompetitive Analyse (1)
- Landside operation (1)
- Latency (1)
- Logistik (1)
- Nahverkehr (1)
- Online Algorithmen (1)
- Online Optimierung (1)
- Online optimization (1)
- Online-Algorithm (1)
- Online-Algorithms (1)
- Onlineoptimierung (1)
- Operations Research (1)
- Preisplanung (1)
- Problembibliothek (1)
- Proximale Bündelmethode (1)
- Railway Track Allocation (1)
- Rapid Branching (1)
- Rapid-Branching-Heuristik (1)
- Realtime Optimization (1)
- Robust Optimization (1)
- Simplon Korridor (1)
- Simplon corridor (1)
- Simulation (1)
- Spaltenerzeugung (1)
- Storage space allocation (1)
- Survey (1)
- Tail Assignment (1)
- Taktfahrplan (1)
- Toll Enforcement (1)
- Transportation Systems (1)
- Trassenallokation (1)
- Trassenallokationsproblem (1)
- Traveling Repairman (1)
- Traveling Salesman Problem (1)
- Vehicle Routing (1)
- Yard crane scheduling (1)
- Zielorientierte Planung (1)
- Zielrufsteuerung (1)
- applications of integer programming (1)
- bundle method (1)
- case study (1)
- competitiveness (1)
- computational complexity (1)
- convex relaxation (1)
- destination call system (1)
- discrete optimization (1)
- diskrete Optimierung (1)
- duty scheduling (1)
- duty templates (1)
- elevator control (1)
- exact reoptimation (1)
- ganzzahlige Programmierung (1)
- high load (1)
- hyperassignments (1)
- hypergraphs (1)
- kompetitive Analyse (1)
- large scale optimization (1)
- large scale problems (1)
- logistics (1)
- lower bounds (1)
- macroscopic railway modeling (1)
- makroskopische Bahnmodellierung (1)
- mixed-integer-programming (1)
- network models (1)
- online algorithms (1)
- optimality gap (1)
- passenger routing (1)
- periodic timetable (1)
- policy (1)
- probabilistic analysis (1)
- public transit (1)
- public transportation (1)
- railways (1)
- randomized algorithms (1)
- real time optimation (1)
- reoptimization (1)
- robuste Optimierung (1)
- rolling-stock-planning (1)
- set covering (1)
- set packing (1)
- set partitioning (1)
- simulation (1)
- simulation studies (1)
- stochastic demand (1)
- supply chain management, supply network optimization, mixed-integer linear programming, primal heuristics, numerical stability, large-scale optimization (1)
- timetabling (1)
- transportation planning (1)
- trip timetable (1)
- vehicle rotation planning (1)
- vehicle routing (1)
Institute
Dieser Artikel behandelt einen Ansatz zur zielorientierten Optimierung der Dienstplanung im ÖPNV. Der Ansatz zielt auf die vollständige Ausnutzung aller planerischen Freiheitsgrade unter korrekter Berücksichtigung von gesetzlichen, tariflichen, technischen und betrieblichen Rahmenbedingungen. Er basiert auf mathematischen Optimierungstechniken, die wir gegenwärtig in einem vom Bundesministerium für Bildung und Forschung ({\tt bmb+f}) geförderten Verbundprojekt in einer Kooperation zwischen der HanseCom GmbH, der IVU GmbH und dem Konrad-Zuse-Zentrum für Informationstechnik Berlin entwickeln. Es ist geplant, das Verfahren in die Softwareprodukte HOT II, MICROBUS II und OPUS zu integrieren. Verhandlungen mit den Berliner Verkehrsbetrieben über eine Projektbeteiligung und Integration unserer Software in BERTA sind zur Zeit im Gang. Wir beschreiben die Methodik des Ansatzes, diskutieren Aspekte seiner praktischen Verwendung, und wir berichten über den Stand der Entwicklung.
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'.
Anwendungen der Mathematik in der Verkehrs- und Transporttechnologie haben eine große und bedeutende Tradition. Natürlich wurden die ersten Fahrzeuge mit der ingenieurmäßigen Methode von Versuch, Irrtum und Verbesserung entworfen. Aber schon sehr bald kamen mathematische Berechnungen hinzu, mit denen mechanische Eigenschaften von Fahrzeugteilen ermittelt und zum Teil optimiert wurden. Die hierzu erforderliche Mathematik wurde in diesem Jahrhundert zu einem mächtigen Werkzeugkasten ausgebaut. Mit diesem kann man heute z.B. hocheffiziente Motoren mit geringem Schadstoffausstoß entwerfen, aerodynamisch günstige Fahrzeugprofile ermitteln und Flugzeugflügel berechnen, die die gewünschte Last sicher und mit geringem Treibstoffaufwand tragen. Die Mathematik unterstützt die Technologie des Verkehrs beginnend bei globalen Designfragen bis hin zur Spezifizierung von Materialeigenschaften kleinster Bauteile; sie berechnet mit hoher Präzision energieoptimale Bahnen von Raumflugkörpern oder zeitoptimale Trajektorien für Flugzeuge, steuert automatische Roboteranlagen oder innerbetriebliche Transportsysteme.
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.
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.
We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis.
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.
In the online traveling salesman problem requests for visits to cities (points in a metric space) arrive online while the salesman is traveling. The salesman moves at no more than unit speed and starts and ends his work at a designated origin. The objective is to find a routing for the salesman which finishes as early as possible. Performance of algorithms is measured through their competitive ratio, comparing the outcome of the algorithms with that of an adversary who provides the problem instance and therefore is able to achieve the optimal offline solution. Objections against such omnipotent adversaries have lead us to devise an adversary that is in a natural way, in the context of routing problems, more restricted in power. For the exposition we consider the online traveling salesman problem on the metric space given by the non-negative part of the real line. We show that a very natural strategy is~$3/2$-competitive against the conventional adversary, which matches the lower bound on competitive ratios achievable for algorithms for this problem. Against the more ``\emph{fair adversary}'', that we propose, we show that there exists an algorithm with competitive ratio $\frac{1+\sqrt{17}}{4}\approx 1.28$ and provide a matching lower bound. We also show competitiveness results for a special class of algorithms (called zealous algorithms) that do not allow waiting time for the server as long as there are requests unserved.
In this paper we consider the following online transportation problem (\textsc{Oltp}): Objects are to be transported between the vertices of a given graph. Transportation requests arrive online, specifying the objects to be transported and the corresponding source and target vertex. These requests are to be handled by a server which commences its work at a designated origin vertex and which picks up and drops objects at their starts and destinations. After the end of its service the server returns to its start. The goal of \textsc{Oltp} is to come up with a transportation schedule for the server which finishes as early as possible. We first show a lower bound of~$5/3$ for the competitive ratio of any deterministic algorithm. We then analyze two simple and natural strategies which we call \textsf{REPLAN} and \textsf{IGNORE}. \textsf{REPLAN} completely discards its schedule and recomputes a new one when a new request arrives. \textsf{IGNORE} always runs a (locally optimal) schedule for a set of known requests and ignores all new requests until this schedule is completed. We show that both strategies, \textsf{REPLAN} and \textsf{IGNORE}, are $5/2$-competitive. We also present a somewhat less natural strategy \textsf{SLEEP}, which in contrast to the other two strategies may leave the server idle from time to time although unserved requests are known. We also establish a competitive ratio of~$5/2$ for the algorithm \textsf{SLEEP}. Our results are extended to the case of ``open schedules'' where the server is not required to return to its start position at the end of its service.
In this paper, we analyze algorithms for the online dial-a-ride problem with request sets that fulfill a certain worst-case restriction: roughly speaking, a set of requests for the online dial-a-ride problem is reasonable if the requests that come up in a sufficiently large time period can be served in a time period of at most the same length. This new notion is a stability criterion implying that the system is not overloaded. The new concept is used to analyze the online dial-a-ride problem for the minimization of the maximal resp.\ average flow time. Under reasonable load it is possible to distinguish the performance of two particular algorithms for this problem, which seems to be impossible by means of classical competitive analysis.
SAP's decision support systems for optimized supply network planning rely on mixed-integer programming as the core engine to compute optimal or near-optimal solutions. The modeling flexibility and the optimality guarantees provided by mixed-integer programming greatly aid the design of a robust and future-proof decision support system for a large and diverse customer base. In this paper we describe our coordinated efforts to ensure that the performance of the underlying solution algorithms matches the complexity of the large supply chain problems and tight time limits encountered in practice.
The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.
In a large distribution center of Herlitz AG, Berlin, we invesigated the elevator subsystem of the fully automated pallet transportation system. Each elevator may carry one pallet and has to serve eight levels. The goal is to minimize the average resp.\ the maximum flow time. The variants of this elevator control problem have been subject of recent theoretical research and are known as online-dial-a-ride problems. In this paper we investigate several online algorithms for several versions of online-dial-a-ride problems by means of a simulation program, developed on the basis of the simulation library AMSEL. We draw statistics from samples of randomly generated data providing for different load situations. Moreover, we provide preliminary studies with real production data for a system of five elevators connected by a conveyor circuit, as can be found at the Herlitz plant. We show which algorithms are best under certain load situations and which lead to break downs under particular circumstances.
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.
Robust Tail Assignment
(2010)
We propose an efficient column generation method to minimize the probability of delay propagations along aircraft rotations. In this way, delay resistant schedules can be constructed. Computational results for large-scale real-world problems demonstrate substantial punctuality improvements. The method can be generalized to crew and integrated scheduling problems.
Under high load, the automated dispatching of service vehicles for the German Automobile Association (ADAC) must reoptimize a dispatch for 100--150 vehicles and 400 requests in about ten seconds to near optimality. In the presence of service contractors, this can be achieved by the column generation algorithm ZIBDIP. In metropolitan areas, however, service contractors cannot be dispatched automatically because they may decline. The problem: a model without contractors yields larger optimality gaps within ten seconds. One way-out are simplified reoptimization models. These compute a short-term dispatch containing only some of the requests: unknown future requests will influence future service anyway. The simpler the models the better the gaps, but also the larger the model error. What is more significant: reoptimization gap or reoptimization model error? We answer this question in simulations on real-world ADAC data: only the new model ZIBDIP{\footnotesize dummy} can keep up with ZIBDIP.
Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers.
Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.
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.
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.