The First Optimized Railway Timetable in Practice

References

• Berger F., Gritzmann P., de Vries S. Minimum cycle bases for network graphs. Algorithmica (2004) 40(1):51–62Crossref, Google Scholar
• Bollobás B.Modern Graph Theory, Graduate Texts in Mathematics (2002) 184(Springer, New York) . 2nd printingGoogle Scholar
• Borndörfer R., Grötschel M., Pfetsch M. E. A column-generation approach to line planning in public transport. Transportation Sci. (2007) 41:123–132Link, Google Scholar
• Borndörfer R., Grötschel M., Lukac S., Mitusch K., Schlechte T., Schultz S., Tanner A. An auctioning approach to railway slot allocation. Competition Regulation Network Industries (2006) 1:163–196Crossref, Google Scholar
• Bussieck M. Solving difficult MIP problems using GAMS and CONDOR. Presentation Oper. Res. Conf. (2006) Karlsruhe, GermanyGoogle Scholar
• Bussieck M., Winter T., Zimmermann U. Discrete optimization in public rail transport. Math. Programming B (1997) 79:415–444Crossref, Google Scholar
• Caprara A., Fischetti M., Toth P. Modeling and solving the train timetabling problem. Oper. Res. (2002) 50(5):851–861Link, Google Scholar
• Daduna J. R., Voß S., Daduna J. R., Branco I., Paixao J. M. P. Practical experiences in schedule synchronization. CASPT (1995) 430(Springer, Berlin) 39–55Lecture Notes in Economics and Mathematical SystemsCrossref, Google Scholar
• Deo N., Krishnamoorthy M. S., Prabhu G. M. Algorithms for generating fundamental cycles in a graph. ACM Trans. Math. Software (1982) 8(1):26–42Crossref, Google Scholar
• Grötschel M., Löbel A., Völker M., Hoffmann K. H., Jäger W., Lohmann T., Schunck H. Optimierung des Fahrzeugumlaufs im öffentlichen Nahverkehr. Mathematik—Schlüsseltechnologie Für die Zukunft (1997) (Springer, Berlin) 609–624Crossref, Google Scholar
• Hariharan R., Kavitha T., Mehlhorn K., Bugliesi M., Preneel B., Sassone V., Wegener I. A faster deterministic algorithm for minimum cycle bases in directed graphs. Automata, Languages and Programming: 33rd International Colloquium, ICALP 2006 (2006) 4051(Springer, Berlin) 250–261Lecture Notes in Computer ScienceCrossref, Google Scholar
• Horton J. D. A polynomial-time algorithm to find the shortest cycle basis of a graph. SIAM J. Comput. (1987) 16(2):358–366Crossref, Google Scholar
• Huschke R. Schneller umsteigen. Berliner Zeitung (2005) 61(262, November 9):12Google Scholar
• Kavitha T., Mehlhorn K., Michail D., Paluch K. E., Diaz J., Karhumäki J., Lepistö A., Sanella D. A faster algorithm for minimum cycle basis of graphs. Automata, Languages and Programming: 31st International Colloquium, ICALP 2004 (2004) 3142(Springer, Berlin) 846–857Lecture Notes in Computer ScienceCrossref, Google Scholar
• Kurz I. Bessere Anschlüsse von U-Bahn zu U-Bahn. BVG Profil (Employee Newsletter of Berliner Verkehrsbetriebe) (2005) 4:11Google Scholar
• Liebchen C., Di Battista G., Zwick U. Finding short integral cycle bases for cyclic timetabling. Algorithms: ESA 2003 (2003) 2832(Springer, Berlin) 715–726Lecture Notes in Computer ScienceCrossref, Google Scholar
• Liebchen C., Nikoletseas S. E. A cut-based heuristic to produce almost feasible periodic railway timetables. Experimental and Efficient Algorithms: 4th International Workshop, WEA 2005 (2005a) 3503(Springer, Berlin) 354–366Lecture Notes in Computer ScienceCrossref, Google Scholar
• Liebchen C. Der Berliner U-Bahn Fahrplan 2005—Realisierung eines mathematisch optimierten Angebotskonzeptes. HEUREKA '05: Optimierung in Transport und Verkehr, Tagungsbericht, No. 002/81 (2005b) (FGSV Verlag, Cologne, Germany) Google Scholar
• Liebchen C. Fahrplanoptimierung im Personenverkehr—Muss es immer ITF sein? Eisenbahntechnische Rundschau (2005c) 54(11):689–702Google Scholar
• Liebchen C. Periodic timetable optimization in public transport. (2006) . Dissertation, dissertation.de-Verlag im Internet GmbH, Berlin. http://www.dissertation.de/buch.php3?buch=4788Google Scholar
• Liebchen C., Möhring R. H. A case study in periodic timetabling. Electronic Notes Theoret. Comput. Sci. (2002) 66(6):18–31Crossref, Google Scholar
• Liebchen C., Möhring R. H. Information on MIPLIB's timetab-instances. (2003) . Preprint 049/2003, Mathematical Institute, Technische Universität Berlin, BerlinGoogle Scholar
• Liebchen C., Möhring R. H., Geraets F., Kroon L., Schöbel A., Wagner D., Zaroliagis C. The modeling power of the periodic event scheduling problem: Railway timetables—and beyond. ATMOS 2004 (2007) 4359(Springer, Berlin) 3–40Lecture Notes in Computer ScienceCrossref, Google Scholar
• Liebchen C., Peeters L. W. P. On cyclic timetabling and cycles in graphs. (2002) . Technical Report 761-2002, Mathematical Institute, Technische Universität Berlin, BerlinGoogle Scholar
• Liebchen C., Rizzi R. A greedy approach to compute a minimum cycle basis of a directed graph. Inf. Process. Lett. (2005) 94(3):107–112Crossref, Google Scholar
• Liebchen C., Rizzi R. Classes of cycle bases. Discrete Appl. Math. (2007) 155(3):337–355Crossref, Google Scholar
• Liebchen C., Proksch M., Wagner F. H., Hickman M., Mirchandani P., Voß S. Performance of algorithms for periodic timetable optimization. Computer-Aided Systems in Public Transport (CASPT 2004) (2008) 600(Springer, Berlin) 151–180Lecture Notes in Economics and Mathematical SystemsCrossref, Google Scholar
• Lindner T. Train schedule optimization in public rail transport. (2000) . Ph.D. thesis, Technische Universität Braunschweig, Braunschweig, GermanyGoogle Scholar
• Nachtigall K. Exact solution methods for periodic programs. (1993) . Hildesheimer Informatik-Berichte 14/93, Universität Hildesheim, Hildesheim, GermanyGoogle Scholar
• Nachtigall K. Cutting planes for a polyhedron associated with a periodic network. (1996) . Institutsbericht IB 112-96/17, Deutsche Forschungsanstalt für Luft- und Raumfahrt e.V, July, Braunschweig, GermanyGoogle Scholar
• Nachtigall K. Periodic network optimization and fixed interval timetables. (1998) . Habilitation thesis, DLR Report 113-99/02, Universität Hildesheim, Hildesheim, GermanyGoogle Scholar
• Nachtigall K., Voget S. A genetic algorithm approach to periodic railway synchronization. Comput. Oper. Res. (1996) 23(5):453–463Crossref, Google Scholar
• Odijk M. A. Construction of periodic timetables, Part 1: A cutting plane algorithm. (1994) . Technical Report 94-61, Technische Universiteit Delft, Delft, The NetherlandsGoogle Scholar
• Odijk M. A. A constraint generation algorithm for the construction of periodic railway timetables. Transportation Res. B (1996) 30(6):455–464Crossref, Google Scholar
• Papadimitriou C. H., Yannakakis M. Optimization, approximation, and complexity classes. J. Comput. System Sci. (1991) 43(3):425–440Crossref, Google Scholar
• Schrijver A., Steenbeek A. G. Dienstregelingontwikkeling voor Nederlandse Spoorwegen N.S. (1993) . Rapport Fase 1, Centrum voor Wiskunde en Informatica, Oktober, AmsterdamnGoogle Scholar
• SenStadt (Senatsverwaltung für Stadtentwicklung) Nahverkehrsplan des Landes Berlin—Fortschreibung 2000/2001 und 2004. (2001) (SenStadt, Berlin)Google Scholar
• Serafini P., Ukovich W. A mathematical model for periodic scheduling problems. SIAM J. Discrete Math. (1989) 2(4):550–581Crossref, Google Scholar
• Vitányi P. M. B. How well can a graph be n-colored? Discrete Math. (1981) 34:69–80Crossref, Google Scholar
• Wong R. C. W., Leung J. M. Y. Optimizing timetable synchronization for rail mass transit. Transportation Sci. (2008) 42(1):57–69Link, Google Scholar