Weider, Steffen
Refine
Year of publication
Document Type
- ZIB-Report (15)
- In Proceedings (8)
- Article (7)
- Doctoral Thesis (1)
- Other (1)
Is part of the Bibliography
- no (32)
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)
Institute
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.
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.