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
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.
This paper proposes the first model for toll enforcement optimization
on German motorways. The enforcement is done by mobile control teams and our
goal is to produce a schedule achieving network-wide control, proportional to
spatial and time-dependent traffic distributions. Our model consists of two
parts. The first plans
control tours using a vehicle routing approach with profits and some side
constraints. The second plans feasible rosters for the control teams. Both
problems can be modeled as Multi-Commodity Flow Problems. Adding additional
coupling constraints produces a large-scale integrated integer programming
formulation. We show that this model can be solved to optimality for real
world instances associated with a control area in East Germany.
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.
In this thesis we present a novel extended formulation for the line planning problem that is based on what we call "configurations" of lines and frequencies. Configurations are combinatorial building blocks of primal solutions; they rule out the "capacity numerics" and make the problem purely combinatorial. The concept of configurations can also be adapted to other capacitated network design problems.
The configuration model is strong in the sense that it implies several facet-defining inequalities for the standard model: set cover, symmetric band, multicover, and MIR inequalities. These theoretical findings can be confirmed in computations, however, the enormous number of configurations can blow up the formulation for large instances. We propose a mixed model that enriches the standard model by a judiciously chosen subset of configurations that provide a good compromise between model strength and size. Computational results for large-scale line planning problems are presented.
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 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 transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.
In this paper we present the problem of computing optimal tours of toll inspectors on German motorways. This problem is a special type of vehicle routing problem and builds up an integrated model, consisting of a tour
planning and a duty rostering part. The tours should guarantee a network-wide control whose intensity is proportional to given spatial and time dependent traffic distributions. We model this using a space-time network
and formulate the associated optimization problem by an integer program (IP). Since sequential approaches fail, we integrated the assignment of crews to the tours in our model. In this process all duties of a crew member must fit in a feasible roster. It is modeled as a Multi-Commodity Flow Problem in a directed acyclic graph, where specific paths correspond to
feasible rosters for one month. We present computational results in a
case-study on a German subnetwork which documents the practicability of our approach.
A Case Study of Joint Online Truck Scheduling and Inventory Management for Multiple Warehouses
(2005)
For a real world problem --- transporting pallets between warehouses in order to guarantee sufficient supply for known and additional stochastic demand --- we propose a solution approach via convex relaxation of an integer programming formulation, suitable for online optimization. The essential new element linking routing and inventory management is a convex piecewise linear cost function that is based on minimizing the expected number of pallets that still need transportation. For speed, the convex relaxation is solved approximately by a bundle approach yielding an online schedule in 5 to 12 minutes for up to 3 warehouses and 40000 articles; in contrast, computation times of state of the art LP-solvers are prohibitive for online application. In extensive numerical experiments on a real world data stream, the approximate solutions exhibit negligible loss in quality; in long term simulations the proposed method reduces the average number of pallets needing transportation due to short term demand to less than half the number observed in the data stream.