Integration of Vehicle and DutyScheduling in Public Transportvorgelegt vonDipl.-Math.-oec. Steffen Weideraus BerlinVon der Fakulta¨t II – Mathematik und Naturwissenschaftender Technischen Universitat Berlin¨zur Erlangung des akademischen GradesDoktor der Naturwissenschaften– Dr. rer. nat. –genehmigte DissertationBerichter: Prof. Dr. Dr. h.c. Martin Gr¨otschelProf. Dr. Jorg Rambau¨Vorsitzender: Prof. Dr. Volker MehrmannTag der wissenschaftlichen Aussprache: 31.5.2007Berlin 2007D 83Zusammenfassung iZusammenfassungDiese Arbeit beschreibt den Algorithmus IS-OPT, welcher der erste Algo-rithmus ist, der integrierte Umlauf- und Dienstplanungsprobleme fu¨r mit-telgroße Verkehrsunternehmen lo¨st und dabei alle betrieblichen Einzelheitenberucksichtigt. Seine Losungen konnen daher direkt in den taglichen Betrieb¨ ¨ ¨ ¨u¨bernommen werden.Im ersten Kapitel werden mathematische Modelle fur verschiedenen Pro-¨bleme aus dem Planungsprozess von Nahverkehrsunternehmen beschrieben.EswerdenAnsa¨tzezurIntegrationdereinzelnenProblemeuntersucht.Indie-sem Kapitel werden außerdem das Umlauf- und das Dienstplanungsproblemeingefu¨hrt. Kapitel 2 motiviert, warum Integration von Umlauf- und Dienst-planung hilfreich ist oder in welchen Fallen sie sogar unabdingbar ist; es gibt¨¨einen Uberblick u¨ber die vorhanden Literatur zur integrierten Umlauf- undDienstplanung und umreißt unseren Algorithmus IS-OPT.
vorgelegt von Dipl.Math.oec. Steffen Weider aus Berlin
Von der Fakultät II – Mathematik und Naturwissenschaften der Technischen Universität Berlin zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften – Dr. rer. nat. –
genehmigte Dissertation
Berichter:
Vorsitzender:
Prof. Dr. Dr. h.c. Martin Grötschel Prof. Dr. Jörg Rambau Prof. Dr. Volker Mehrmann
Tag der wissenschaftlichen Aussprache: 31.5.2007
Berlin 2007 D 83
Zusammenfassung
Zusammenfassung
Diese Arbeit beschreibt den AlgorithmusISOPT, welcher der erste Algo rithmus ist, der integrierte Umlauf und Dienstplanungsprobleme für mit telgroße Verkehrsunternehmen löst und dabei alle betrieblichen Einzelheiten berücksichtigt. Seine Lösungen können daher direkt in den täglichen Betrieb übernommen werden.
Im ersten Kapitel werden mathematische Modelle für verschiedenen Pro bleme aus dem Planungsprozess von Nahverkehrsunternehmen beschrieben. Es werden Ansätze zur Integration der einzelnen Probleme untersucht. In die sem Kapitel werden außerdem das Umlauf und das Dienstplanungsproblem eingeführt. Kapitel 2 motiviert, warum Integration von Umlauf und Dienst planung hilfreich ist oder in welchen Fällen sie sogar unabdingbar ist; es gibt einenÜberblicküberdievorhandenLiteraturzurintegriertenUmlaufund Dienstplanung und umreißt unseren AlgorithmusISOPT. Die weiteren Kapitel behandeln die inISOPTverwendeten Methoden: In Kapitel 3 beschreiben wir, wie Spaltenerzeugung für lineare Programme mit LagrangeRelaxierung und SubgradientenVerfahren kombiniert werden kann. In Kapitel 4 wird unsere Variante der proximalen Bündelmethode be schrieben. Diese wird benutzt um näherungsweise primale und duale Lösun gen von lineare Programmen zu berechnen. Unsere Variante ist angepasst, um auch mit ungenauer Funktionsauswertung undǫSubgradienten arbeiten zu können. Wir zeigen die Konvergenz dieser Variante unter bestimmten An nahmen. Kapitel 5 behandelt das Erzeugen von Diensten für das Dienstpla nungsproblem. Dieses Problem ist als ein KürzesteWegeProblem mit nicht linearen Nebenbedingungen und fast linearer Zielfunktion modelliert. Wir lösen es, indem zuerst Schranken für die reduzierten Kosten von Diensten, die bestimmte Knoten benutzen, berechnet werden. Diese Schranken werden benutzt, um in einem Tiefensuchalgorithmus den Suchbaum klein zu halten. Im Kapitel 6 präsentieren wir die neu entwickelte Heuristik “Rapid Bran ching”, die eine ganzzahlige Lösung des integrierten Problems berechnet. Ra pid Branching kann als eine spezielle BranchandBoundHeuristik gesehen werden, welche die Bündelmethode benutzt. In den Knoten des Suchbaums können mehrere Variablen auf einmal fixiert werden, die mit Hilfe einer Per turbationsheuristik ausgewählt werden. In Kapitel 7 schließlich zeigen wir, daß wir mitISOPTauch große Proble minstanzen aus der Praxis lösen können und dabei bis zu 5% der Fahrzeug und Dienstkosten sparen können.
i
ii
Abstract
Abstract
This thesis describes the algorithmISOPTthat integrates scheduling of ve hicles and duties in public bus transit.ISOPTis 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 mathema tical models of the planning process of public transit companies and examines their potential for integrating them with other planning steps. It also intro duces descriptions of the vehicle and the duty scheduling problem. Chapter 2 motivates why it can be useful to integrate vehicle and duty scheduling, ex plains approaches of the literature, and gives an outline of our algorithm ISOPT.
The following chapters go into the details of the most important tech niques and methods ofISOPT: In Chapter 3 we describe how we use La grangean 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 thePBMwhich is able to utilize inexact function eval uation and the use ofǫ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 resource constraintshortestpathproblem with nonlinear side constraints and nearly linear objective function. It is solved in a twostage approach. At first we calculate lower bounds on the reduced costs of duties using certain nodes by a new inexact labelsetting algorithm. Then we use these bounds to speed up a depthfirstsearch algorithm that finds feasible duties. In Chapter 6 we present the primal heuristic ofISOPTthat solves the integrated problem to integrality. We introduce a new branchandbound 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 inISOPTis 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 ISOPT. The scheduled produced byISOPTsave up to 5% of the vehicle and duty cost of existing schedules of regional and urban public transport companies.
Preface
Preface
Public mass transit in Germany is in a phase of change. The competition between the companies is becoming more intense due to the policy of the European Union to publicly tender public transit subsidies to reduce the number of local monopolies of public transit carriers. In fact, these tenderings 1 already led to significant reductions of subsidies .
This increase in competition gives incentives to the companies to improve the efficiency of the allocation of their resources, i.e., personnel and vehicles, which together cause about 6675% of the cost of a typical German public transport bus company (see Leuthardt [1998]). In this work we propose the algorithmISOPTthat plans these resources together in a single step. We will show thatISOPTincreases the overall planning efficiency of real world planning problems in comparison to manual solutions and also in comparison to sequential optimization of vehicle and duty schedules.
The development ofISOPTwas challenging due to the large number of methods it utilizes: It combines methods from linear, convex, and combinato rial optimization, such as column generation, Lagrangean relaxation, bundle methods, shortest path algorithms, a network simplex method, and branch andbound approaches. Our contributions to these methods, in particular with the aim to accelerate them at the cost of getting only approximate so lutions, and the way how we use and combine them to solve the integrated vehicle and duty scheduling problem is the content of this work:
We will show how we replace exact LPmethods by an inexact proximal bundle method in a column generation context. To do this we had to solve the problems of obtaining a useful dual solution for the pricing problem from a Lagrangean relaxation and the handling of approximate evaluation of the Lagrangean dual with unknown approximation quality in the bundle method. We prove also the convergence of this new variant of the bundle method that is able to cope with this inexactness.
We present a new active set approach to approximate LPrelaxations of largescale setpartitioningproblems with the bundle method.
We propose a twophase algorithm to solve the pricing problem which is modeled by a resourceconstraintshortestpathproblem with addi tional constraints and a nonlinear objective function. In the first phase, 1 In the empirical study of Resch et al. [2006] three German public transit companies are mentioned whose subsidies were reduced by 32–44% in the last ten years.
iii
iv
Preface
we calculate bounds on this problem by Lagrangean relaxation and a labelingalgorithm. To calculate these bounds we develop an inexact labeling algorithm to approximate resourceconstrainedshortestpath problems. In the second phase, we use these bounds to prune the search tree of a depthfirstsearch approach.
We introduce a primal heuristic to find an integral solution of theISP. This heuristic can be seen as an inexact branchandbound algorithm that uses a branching rule which selects sets including many variables to be fixed all at once.
Another highlight of this work is the practical application of the algorithm ISOPT. The transfer from an algorithm that works for some test instances to an algorithm that is in daily use by planners was not always easy: The industrial requirements for planning tools are going beyond the requirements for typical academic software.ISOPThas to be stable using any reasonable data, it has to be flexible because no two public transit companies have the same duty rules, it has to be fast because often companies have to com pute dozens of different scenarios for different days of operation in a limited amount of time. At last, it is not easy to find out about all side constraints and rules which feasible schedules have to fulfill in practice because often some of them are only known by the planners in charge and were never set out in writing. It was common that after presenting a solution, the planners gave us additional rules and side constraints that have to be considered.
However, it is very satisfying when finally the practitioners of a planning department admit to be amazed because not only our code is able to find solutions that are usable in their daily operations without adapting them manually, but that these solutions are also significantly better than existing schedules.
Acknowledgments
Acknowledgments
Most of the research for this thesis was done in a project of the program “math 2 & industry” of the German ministry for research and education (BMBF) . It was carried out at the Zuse Institute Berlin in cooperation with two compa nies that specialize on software for public transit, namely IVU traffic tech nologies AG (IVU) and Mentz Datenverarbeitung GmbH, and a carrier for public transit, Regensburger Verkehrsbetriebe. I want to thank all project partners for providing the test data, a deep knowledge about public trans portation, and for many fruitful discussions.
After the successful completion of this research project I continued to work as one of the associates of Löbel, Borndörfer und Weider GbR closely together with IVU and DB Stadtverkehr GmbH to improve the algorithm ISOPT, such that it can be used in the daily operations of regional bus operators of DB Stadtverkehr.
I want to thank my colleagues and friends Andreas Löbel and Ralf Borndörfer for sharing their great knowledge about mathematical optimiza tion methods and implementation of largescale optimization software. I want to thank Rainer Kuschel of the Regensburger Verkehrsbetriebe because without him the BMBF project would not have been the success it was. Further, I want thank Martin Grötschel to give me the possibility to work at the Zuse Institute, which is a really great place for applied mathematics (and mathematicians). I want to thank Marc Pfetsch, Andreas Tuchscherer and Benjamin Hiller for encouraging me and giving helpful comments. At last, I thank all of my colleagues at the Zuse Institute for the good work atmosphere.