Refine
Document Type
- ZIB-Report (7)
- Article (2)
- In Proceedings (1)
Is part of the Bibliography
- no (10)
Keywords
- Kombinatorische Optimierung (1)
- Kürzeste Wege (1)
- Operations Research (1)
- Optimierung (1)
- column generation (1)
- line planning (1)
- öffentlicher Verkehr (1)
Institute
- Mathematics of Transportation and Logistics (10) (remove)
The \emph{line planning problem} is one of the fundamental problems in strategic planning of public and rail transport. It consists of finding lines and corresponding frequencies in a public transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize its operating cost; the passengers request short travel times. We propose two new multi-commodity flow models for line planning. Their main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically.
Der Schnellste Weg zum Ziel
(1999)
"`Telebus"' ist der soziale Behindertenfahrdienst im Land Berlin. Das Telebus-Forschungsprojekt des Konrad-Zuse-Zentrums für Informationstechnik (ZIB) hat das Ziel, den Fahrdienst (insbesondere die Disposition der Telebusse) zu verbessern, d.h. kundenfreundlicher zu gestalten und gleichzeitig billiger zu machen. In diesem Bericht werden die bisherigen Ergebnisse dargestellt und weitere Möglichkeiten zur Verbesserung des Service und zur Reduzierung der Kosten skizziert. \originalTeX
In diesem Artikel geben wir einen Überblick über das Telebus-Projekt am Konrad-Zuse-Zentrum, Berlin, durch das der Behindertenfahrdienst in Berlin reorganisiert und optimiert wurde. Wir berichten kurz über die mathematischen Probleme und, etwas ausführlicher, über die nicht-mathematischen Schwierigkeiten, die bei der Durchführung dieses Projektes auftraten.
{\em Telebus\/} is Berlin's dial-a-ride system for handicapped people that cannot use the public transportation system. The service is provided by a fleet of about 100 mini-busses and includes aid to get in and out of the vehicle. Telebus has between 1,000 and 1,500 transportation requests per day. The problem arises to schedule these requests into the vehicles such that punctual service is provided while operation costs should be minimum. Additional constraints include pre-rented vehicles, fixed bus driver shift lengths, obligatory breaks, and different vehicle capacities. We use a {\em set partitioning\/} approach for the solution of the bus scheduling problem that consists of two steps. The first {\em clustering\/} step identifies segments of possible bus tours (``orders'') such that more than one person is transported at a time; the aim in this step is to reduce the size of the problem and to make use of larger vehicle capacities. The problem to select a set of orders such that the traveling distance of the vehicles within the orders is minimal is a set partitioning problem that we can solve to optimality. In the second step the selected orders are {\em chained\/} to yield possible bus tours respecting all side constraints. The problem to select a set of such bus tours such that each order is serviced once and the total traveling distance of the vehicles is minimum is again a set partitioning problem that we solve approximately. We have developed a computer system for the solution of the bus scheduling problem that includes a branch-and-cut algorithm for the solution of the set partitioning problems. A version of this system is in operation at Telebus since July 1995. Its use made it possible that Telebus can service today about 30\% more requests per day for the same amount of money than before.
Steigendes Mobilitätsbedürfnis der Behinderten bei angespannter Haushaltslage --- diese Situation ergab vor drei Jahren beim Berliner Behindertenfahrdienst {\em Telebus\/} Handlungsbedarf. Gleichzeitig stie\ss{} die verwendete manuelle (Fahrzeug-)Tourenplanung mit damals etwa 1.000 Fahrtwünschen pro Tag an ihre Grenzen. Zur Lösung dieser Probleme war der effiziente Einsatz von Computern und von {\em mathematischen Optimierungsverfahren\/} erforderlich. Ergebnis des daraufhin gestarteten {\em Telebus-Projektes\/} ist die Entwicklung eines neuen, alle Arbeitsabläufe unterstützenden Computersystems, das seit über einem Jahr im Einsatz ist. Herzstück dieses Systems ist ein auf mathematischen Methoden der ganzzahligen Optimierung basierendes Verfahren zur Tourenplanung. Ziel dieses Artikels ist die Beschreibung dieses Verfahrens und seiner Verwendung bei der Behindertenbeförderung. Das Beispiel Telebus zeigt, da\ss{} der Einsatz mathematischer Optimierungstechniken neue Möglichkeiten für Kosteneinsparungen bei gleichzeitiger Serviceverbesserung auch in anderen Bereichen des ÖPNV eröffnet.
Mathematik im Verkehr
(2014)
Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein.