• Deutsch
Login

  • Home
  • Search
  • Browse
  • Publish
  • FAQ

Refine

Author

  • Weider, Steffen (29)
  • Borndörfer, Ralf (27)
  • Schlechte, Thomas (14)
  • Reuther, Markus (11)
  • Löbel, Andreas (9)
  • Schulz, Christof (7)
  • Langenhan, Andreas (4)
  • Seidl, Stephan (3)
  • Dittbrenner, Bastian (2)
  • Grimm, Boris (2)
+ more

Year of publication

  • 2020 (1)
  • 2019 (1)
  • 2018 (1)
  • 2016 (1)
  • 2015 (3)
  • 2014 (2)
  • 2013 (1)
  • 2012 (6)
  • 2011 (2)
  • 2010 (2)
+ more

Document Type

  • ZIB-Report (14)
  • Article (7)
  • In Proceedings (7)
  • Doctoral Thesis (1)

Language

  • English (26)
  • German (3)

Has Fulltext

  • yes (15)
  • no (14)

Is part of the Bibliography

  • no (29)

Keywords

  • duty scheduling (4)
  • Dienstplanung (2)
  • Umlaufplanung (2)
  • column generation (2)
  • duty templates (2)
  • integrated scheduling (2)
  • rapid branching (2)
  • vehicle scheduling (2)
  • Airline Crew Scheduling (1)
  • Benders decomposition (1)
+ more

Institute

  • Mathematical Optimization (25)
  • Mathematics of Transportation and Logistics (10)
  • ZIB Allgemein (4)
  • Network Optimization (1)

29 search hits

  • 1 to 10
  • BibTeX
  • CSV
  • RIS
  • XML
  • 10
  • 20
  • 50
  • 100

Sort by

  • Year
  • Year
  • Title
  • Title
  • Author
  • Author
A Column Generation Approach to Airline Crew Scheduling (2005)
Borndörfer, Ralf ; Schelten, Uwe ; Schlechte, Thomas ; Weider, Steffen
The airline crew scheduling problem deals with the construction of crew rotations in order to cover the flights of a given schedule at minimum cost. The problem involves complex rules for the legality and costs of individual pairings and base constraints for the availability of crews at home bases. A typical instance considers a planning horizon of one month and several thousand flights. We propose a column generation approach for solving airline crew scheduling problems that is based on a set partitioning model. We discuss algorithmic aspects such as the use of bundle techniques for the fast, approximate solution of linear programs, a pairing generator that combines Lagrangean shortest path and callback techniques, and a novel rapid branching'' IP heuristic. Computational results for a number of industrial instances are reported. Our approach has been implemented within the commercial crew scheduling system NetLine/Crew of Lufthansa Systems Berlin GmbH.
An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem (2000)
Krumke, Sven ; Rambau, Jörg ; Weider, Steffen
In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation.
Integrierte Umlauf- und Dienstplanung im Öffentlichen Nahverkehr (2002)
Borndörfer, Ralf ; Löbel, Andreas ; Weider, Steffen
Wir beschreiben einen Ansatz zur integrierten Umlauf- und Dienstplanung im öffentlichen Nahverkehr. Der Ansatz zielt auf die Verbesserung des Gesamtwirkungsgrades dieser beiden Planungsschritte und auf die besondere Planungsproblematik im Regionalverkehr. Wir entwickeln dazu mathematische Optimierungstechniken für den Einsatz in den Planungssystemen MICROBUS II und DIVA.
Integration of Vehicle and Duty Scheduling in Public Transport (2007)
Weider, Steffen
This thesis describes the algorithm IS-OPT that integrates scheduling of vehicles and duties in public bus transit. IS-OPT is the first algorithm which solves integrated vehicle and duty scheduling problems arising in medium sized carriers such that its solutions can be used in daily operations without further adaptions. This thesis is structured as follows: The first chapter highlights mathematical models of the planning process of public transit companies and examines their potential for integrating them with other planning steps. It also introduces descriptions of the vehicle and the duty scheduling problem. Chapter 2 motivates why it can be useful to integrate vehicle and duty scheduling, explains approaches of the literature, and gives an outline of our algorithm IS-OPT. The following chapters go into the details of the most important techniques and methods of IS-OPT: In Chapter 3 we describe how we use Lagrangean relaxation in a column generation framework. Next, in Chapter 4, we describe a variant of the proximal bundle method (PBM) that is used to approximate linear programs occurring in the solution process. We introduce here a new variant of the PBM which is able to utilize inexact function evaluation and the use of epsilon-subgradients. We also show the convergence of this method under certain assumptions. Chapter 5 treats the generation of duties for the duty scheduling problem. This problem is modeled as a resourceconstraint- shortest-path-problem with non-linear side constraints and nearly linear objective function. It is solved in a two-stage approach. At first we calculate lower bounds on the reduced costs of duties using certain nodes by a new inexact label-setting algorithm. Then we use these bounds to speed up a depth-first-search algorithm that finds feasible duties. In Chapter 6 we present the primal heuristic of IS-OPT that solves the integrated problem to integrality. We introduce a new branch-and-bound based heuristic which we call rapid branching. Rapid branching uses the proximal bundle method to compute lower bounds, it introduces a heuristic node selection scheme, and it utilizes a new branching rule that fixes sets of many variables at once. The common approach to solve the problems occurring in IS-OPT is to trade inexactness of the solutions for speed of the algorithms. This enables, as we show in Chapter 7, to solve large real world integrated problems by IS-OPT. The scheduled produced by IS-OPT save up to 5% of the vehicle and duty cost of existing schedules of regional and urban public transport companies.
A Bundle Method for Integrated Multi-Depot Vehicle and Duty Scheduling in Public Transit (2004)
Borndörfer, Ralf ; Löbel, Andreas ; Weider, Steffen
This article proposes a Lagrangean relaxation approach to solve integrated duty and vehicle scheduling problems arising in public transport. The approach is based on the proximal bundle method for the solution of concave decomposable functions, which is adapted for the approximate evaluation of the vehicle and duty scheduling components. The primal and dual information generated by the bundle method is used to guide a branch-and-bound type algorithm. Computational results for large-scale real-world integrated vehicle and duty scheduling problems with up to 1,500 timetabled trips are reported. Compared with the results of a classical sequential approach and with reference solutions, integrated scheduling offers remarkable potentials in savings and drivers' satisfaction.
A Hypergraph Model for Railway Vehicle Rotation Planning (2011)
Borndörfer, Ralf ; Reuther, Markus ; Schlechte, Thomas ; Weider, Steffen
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.
Duty Scheduling Templates (2012)
Borndörfer, Ralf ; Langenhan, Andreas ; Löbel, Andreas ; Schulz, Christof ; Weider, Steffen
We propose duty templates as a novel concept to produce similar duty schedules for similar days of operation in public transit. Duty templates can conveniently handle various types of similarity requirements, and they can be implemented with ease using standard algorithmic techniques. They have produced good results in practice.
Rapid Branching (2012)
Borndörfer, Ralf ; Löbel, Andreas ; Reuther, Markus ; Schlechte, Thomas ; Weider, Steffen
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.
Vehicle Rotation Planning for Intercity Railways (2012)
Borndörfer, Ralf ; Reuther, Markus ; Schlechte, Thomas ; Weider, Steffen
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.
Integrated Optimization of Rolling Stock Rotations for Intercity Railways (2012)
Reuther, Markus ; Borndörfer, Ralf ; Schlechte, Thomas ; Weider, Steffen
This paper provides a highly integrated solution approach for rolling stock planning problems in the context of intercity passenger traffic. The main contributions are a generic hypergraph based mixed integer programming model and an integrated algorithm for the considered rolling stock rotation planning problem. The new developed approach is able to handle a very large set of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacity, and regularity aspects. By the integration of this large bundle of technical railway aspects, we show that our approach has the power to produce implementable rolling stock rotations for our industrial cooperation partner DB Fernverkehr. This is the first time that the rolling stock rotations at DB Fernverkehr could be optimized by an automated system utilizing advanced mathematical programming techniques.
  • 1 to 10

OPUS4 Logo

  • Contact
  • Impressum und Datenschutz
  • Sitelinks