Refine
Year of publication
Document Type
- ZIB-Report (139)
- In Proceedings (83)
- Article (63)
- Book chapter (5)
- In Collection (3)
- Other (3)
- Doctoral Thesis (2)
- Book (1)
- Habilitation (1)
- Master's Thesis (1)
Keywords
- line planning (13)
- Optimierung (9)
- integer programming (9)
- column generation (7)
- combinatorial optimization (6)
- Periodic timetabling (5)
- public transport (5)
- Column Generation (4)
- Integer Programming (4)
- Linienplanung (4)
Institute
- Mathematical Optimization (240)
- Mathematics of Transportation and Logistics (106)
- Network Optimization (47)
- ZIB Allgemein (15)
- Modeling and Simulation of Complex Processes (8)
- AI in Society, Science, and Technology (4)
- Mathematics of Health Care (3)
- Computational Medicine (2)
- Mathematical Algorithmic Intelligence (2)
- Mathematics for Life and Materials Science (2)
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'.
We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.
The covering of a graph with (possibly disjoint) connected subgraphs is a fundamental problem in graph theory. In this paper, we study a version to cover a graph's vertices by connected subgraphs subject to lower and upper weight bounds, and propose a column generation approach to dynamically generate feasible and promising subgraphs. Our focus is on the solution of the pricing problem which turns out to be a variant of the NP-hard Maximum Weight Connected Subgraph Problem. We compare different formulations to handle connectivity, and find that a single-commodity flow formulation performs best. This is notable since the respective literature seems to have dismissed this formulation. We improve it to a new coarse-to-fine flow formulation that is theoretically and computationally superior, especially for large instances with many vertices of degree 2 like highway networks, where it provides a speed-up factor of 10 over the non-flow-based formulations. We also propose a preprocessing method that exploits a median property of weight constrained subgraphs, a primal heuristic, and a local search heuristic. In an extensive computational study we evaluate the presented connectivity formulations on different classes of instances, and demonstrate the effectiveness of the proposed enhancements. Their speed-ups essentially multiply to an overall factor of 20. Overall, our approach allows the reliabe solution of instances with several hundreds of nodes in a few minutes. These findings are further corroborated in a comparison to existing districting models on a set of test instances from the literature.
The covering of a graph with (possibly disjoint) connected subgraphs is a funda-mental problem in graph theory. In this paper, we study a version to cover a graph’svertices by connected subgraphs subject to lower and upper weight bounds, and pro-pose a column generation approach to dynamically generate feasible and promisingsubgraphs. Our focus is on the solution of the pricing problem which turns out to bea variant of the NP-hard Maximum Weight Connected Subgraph Problem. We com-pare different formulations to handle connectivity, and find that a single-commodityflow formulation performs best. This is notable since the respective literature seemsto have widely dismissed this formulation. We improve it to a new coarse-to-fine flowformulation that is theoretically and computationally superior, especially for largeinstances with many vertices of degree 2 like highway networks, where it provides aspeed-up factor of 5 over the non-flow-based formulations. We also propose a pre-processing method that exploits a median property of weight-constrained subgraphs,a primal heuristic, and a local search heuristic. In an extensive computational studywe evaluate the presented connectivity formulations on different classes of instances,and demonstrate the effectiveness of the proposed enhancements. Their speed-upsessentially multiply to an overall factor of well over 10. Overall, our approach allowsthe reliable solution of instances with several hundreds of vertices in a few min-utes. These findings are further corroborated in a comparison to existing districtingmodels on a set of test instances from the literature
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.
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.