Skip to main content
SpringerLink
Log in

Duty Scheduling in Public Transit

  • Chapter
Mathematics — Key Technology for the Future

Abstract

This article is about adaptive column generation techniques for the solution of duty scheduling problems in public transit. The current optimization status is exploited in an adaptive approach to guide the subroutines for duty generation, LP resolution, and schedule construction toward relevant parts of a large problem. Computational results for three European scenarios are reported.

This research has been supported with funds of the German Ministry for Research and Education, Grant No. 03-GR7ZI1. Responsibility for the contents of this article is with the authors.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ahuja R.K., Magnanti T.L., Orlin J.B. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice-Hall, Englewood Cliffs, New Jersey

    MATH  Google Scholar 

  2. Andersson E., Housos E., Kohl N., Wedelin D. (1998) Crew Pairing Optimization. In [57], Chap. 8

    Google Scholar 

  3. Applegate D., Bixby R.E., Chvátal V., Cook W. (1995) Finding Cuts in the TSP. Technical Report 95-05, DIMACS, Rutgers University, New Jersey

    Google Scholar 

  4. Ascheuer N., Fischetti M., Grötschel M. (1997) A Polyhedral Study of the Asymmetric Travelling Salesman Problem with Time Windows. Preprint SC 97-11, Konrad-Zuse-Zentrum, Berlin (available at http://www.zib.de/ZIBbib/Publications/)

    Google Scholar 

  5. Balas E., Ho A. (1980) Set Covering Algorithms Using Cutting Planes, Heuristics, and Subgradient Optimization: A Computational Study. Math. Prog. 12:37–60

    MathSciNet  MATH  Google Scholar 

  6. Ball M.O., Magnanti T.L., Monma C.L., Nemhauser G.L. (Eds.) (1995) Network Routing, Vol. 8 of Handbooks in Operations Research and Management Science. Elsevier, Amsterdam

    Google Scholar 

  7. Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P.H. (1994) Branch-and-Price: Column Generation for Solving Huge Integer Programs. In [11], pp. 186–207

    Google Scholar 

  8. Beasley J. (1987) An Algorithm for Set Covering Problem. Europ. J. on OR 31:85–93

    Article  MathSciNet  MATH  Google Scholar 

  9. Beasley J., Christofides N. (1989) An Algorithm for the Resource Constrained Shortest Path Problem. Networks 19:379–394

    Article  MathSciNet  MATH  Google Scholar 

  10. Bertsekas D.P. (1995) Nonlinear Programming. Athena, Belmont, Massachusetts

    Google Scholar 

  11. Birge J.R., Murty K.G. (Eds.) (1994) Mathematical Programming: State of the Art 1994. University of Michigan.

    Google Scholar 

  12. Bixby R.E., Gregory J.W., Lustig I.J., Marsten R.E., Shanno D.F. (1992) Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods. Op. Res. 40:885–897

    Article  MathSciNet  MATH  Google Scholar 

  13. Borndörfer R. (1998) Aspects of Set Packing, Partitioning, and Covering. Ph.D. Thesis, Technical University Berlin (available at http://www.zib.de/ZIBbib/Publications/). Shaker, Aachen.

    Google Scholar 

  14. Borndörfer R., Löbel A., Strubbe U., Völker M. (1999) Zielorientierte Dienstplanoptimierung. In Heureka ′99: Optimierung in Verkehr und Transport. Forschungsgesellschaft für Straßen-und Verkehrswesen, Köln, pp. 171–194 (available as Preprint SC 98-41 at URL http://www.zib.de/ZIBbib/Publications/)

    Google Scholar 

  15. Caprara A., Fischetti M., Toth P. (1996) A Heuristic Algorithm for the Set Covering Problem. In Cunningham W.H., McCormick S.T., Queyranne M. (Eds.) Integer Programming and Combinatorial Optimization, Proc. of the 5th Int. IPCO Conf., Vancouver, British Columbia, Canada, pp. 72–84

    Google Scholar 

  16. Ceria S., Nobili P., Sassano A. (1995) A Lagrangian-Based Heuristic for Large-Scale Set Covering Problems. Working Paper, University of Roma La Sapienza

    Google Scholar 

  17. Crainic T.G., Laporte G. (Eds.) (1998) Fleet Management and Logistics. Kluwer, Dordrecht

    MATH  Google Scholar 

  18. Daduna J.R., Branco I., Paixão J.M.P. (Eds.) (1995) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, Springer, Berlin

    Google Scholar 

  19. Daduna J.R., Wren A. (Eds.) (1988) Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin

    Google Scholar 

  20. DeH’Amico M., Maffioli F., Martello S. (Eds.) (1997) Annotated Bibliographies in Combinatorial Optimization. Wiley, Chichester

    Google Scholar 

  21. Desaulniers G., Desrosiers J., Ioachim I., Solomon M.M., Soumis F., Villeneuve D. (1998) A Unified Framework for Deterministic Time Constrained Vehicle Routing and Crew Scheduling Problems. In [17], Chap. 3, pp 57–93

    Google Scholar 

  22. Desaulniers G., Desrosiers J., Lasry A. (1999) Crew Pairing for a Regional Carrier. In [56], pp. 19–42

    Google Scholar 

  23. Desaulniers G., Desrosiers J., Solomon M.M. (1999) Accelerating Strategies in Column Generation Methods for Vehicle Routing and Crew Scheduling Problems. Technical Report G-99-36, Les Cahiers du GERAD, Montreal

    Google Scholar 

  24. Desrochers M. (1986) A New Algorithm for the Shortest Path Problem with Resource Constraints. Technical Report 421A, Centre de Recherche sur les Transports, University of Montréal

    Google Scholar 

  25. Desrochers M., Gilbert J., Sauvé M., Soumis F. (1992) Crew-Opt: Subproblem Modelling in a Column Generation Approach to Urban Crew Scheduling. In [26], pp. 395–406

    Google Scholar 

  26. Desrochers M., Rousseau J.-M. (Eds.) (1992) Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin

    Google Scholar 

  27. Desrochers M., Soumis F.C. (1988a) A Generalized Permanent Labelling Algorithm for the Shortest Path Problem with Time Windows. Infor 26:191–212

    MATH  Google Scholar 

  28. Desrochers M., Soumis F.C. (1988b) A Reoptimization Algorithm for the Shortest Path Problem with Time Windows. Europ. J. on OR 35:242–254

    Article  MathSciNet  MATH  Google Scholar 

  29. Desrochers M., Soumis F.C. (1989) A Column Generation Approach to the Urban Transit Crew Scheduling Problem. Transp. Sci. 23:1–13

    Article  MATH  Google Scholar 

  30. Desrosiers J., Dumas Y., Solomon M.M., Soumis F. (1995) Time Constrained Routing and Scheduling. In [6], Chap. 2, pp. 35–139

    Google Scholar 

  31. Desrosiers J., Rousseau J.-M. (1995) Results Obtained with Crew-Opt: A Column Generation Method for Transit Crew Scheduling. In [18], pp. 349–358

    Google Scholar 

  32. Desrosiers J., Soumis F., Desrochers M. (1984) Routing with Time Windows by Column Generation. Networks 14:545–565

    Article  MATH  Google Scholar 

  33. du Merle O., Villeneuve D., Desrosiers J., Hansen P. (1999) Stabilized Column Generation. Disc. Math. 194:229–237

    Article  MATH  Google Scholar 

  34. Fischetti M., Kroon L. (1999) Scheduling Train Drivers and Guards: The Dutch “Noord-Oost” Case. Manuscript

    Google Scholar 

  35. Fisher M.L. (1981) The Lagrangian Relaxation Method for Solving Integer Programming Problems. Mgmt. Sci. 27:1–18

    Article  MATH  Google Scholar 

  36. Fisher M.L., Kedia P. (1990) Optimal Solution of Set Covering/Partitioning Problems Using Dual Heuristics. Mgmt. Sci. 39:674–688

    Article  MathSciNet  Google Scholar 

  37. Garey M.R., Johnson D.S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York

    MATH  Google Scholar 

  38. Grötschel M., Lovász L., Schrijver A. (1988) Geometric Algorithms and Combinatorial Optimization. Springer, Berlin

    Book  MATH  Google Scholar 

  39. Handler G.Y., Zang I. (1980) A Dual Algorithm for the Constrained Shortest Path Problem. Networks 10:293–310

    Article  MathSciNet  Google Scholar 

  40. Kammler M. (2000) Optimierungsverfahren für Dienstpläne im ÖV. Nahverkehrspraxis 7/8:22

    Google Scholar 

  41. Leuthardt H. (1998) Kostenstrukturen von Stadt-, Überland-und Reisebussen. Der Nahverkehr 6:19–23

    Google Scholar 

  42. Leuthardt H. (2000) Betriebskosten von Stadtbahnen. Der Nahverkehr 10:14–17

    Google Scholar 

  43. Löbel A. (1997) Experiments with a Dantzig-Wolfe Decomposition for Multiple-Depot Vehicle Scheduling Problems. Preprint SC 97-16, Konrad-Zuse-Zentrum, Berlin (available at URL http://www.zib.de/ZIBbib/Publications/)

    Google Scholar 

  44. Marsten R.E., Hogan W., Blankenship J. (1975) The Boxstep Method for Large-Scale Optimization. Op. Res. 23:389–405

    Article  MathSciNet  MATH  Google Scholar 

  45. Marsten R.E., Shepardson F. (1981) Exact Solution of Crew Scheduling Problems Using the Set Partitioning Model: Recent Successful Applications. Networks 11:165–177

    Article  Google Scholar 

  46. Mehlhorn K., Ziegelmann M. (2000) Resource constrained shortest paths. In Proc. 8th European Symposium on Algorithms (ESA2000), Lecture Notes in Computer Science, Springer, Berlin, pp. 326–337

    Google Scholar 

  47. Nemhauser G., Savelsbergh M., Sigismondi G. (1994) MINTO, a Mixed INTe-ger Optimizer. Op. Res. Letters 15:47–58

    Article  MathSciNet  MATH  Google Scholar 

  48. Ribeiro C.C., Minoux M. (1985) A Heuristic Approach to Hard Constrained Shortest Path Problems. Disc. Applied Math. 10:125–137

    Article  MathSciNet  MATH  Google Scholar 

  49. Ribeiro C.C., Minoux M. (1986) Solving Hard Constrained Shortest Path Problems by Lagrangean Relaxation and Branch-and-Bound Algorithms. Math. of OR 53:303–316

    MathSciNet  MATH  Google Scholar 

  50. Rousseau J.-M., Wren A. (1995) Bus Driver Scheduling — an Overview. In [18], pp. 173–187

    Google Scholar 

  51. Sanders P., Takkula T., Wedelin D. (1999) High Performance Integer Optimization for Crew Scheduling. In Proc. of the HPCS ′99, Amsterdam, Lecture Notes in Cmputer Science, Springer, Berlin

    Google Scholar 

  52. Soumis F. (1997) Decomposition and Column Generation. In [20], Chap. 8, pp. 115–126

    Google Scholar 

  53. Warburton A. (1987) Approximation of Pareto Optima in Multiple-Objective Shortest Path Problems. Op. Res. 35:70–79

    Article  MathSciNet  MATH  Google Scholar 

  54. Wedelin D. (1995a) An Algorithm for Large Scale 0-1 Integer Programming with Application to Airline Crew Scheduling. Annals of OR 57:283–301

    Article  MathSciNet  MATH  Google Scholar 

  55. Wedelin D. (1995b) The Design of a 0-1 Integer Optimizer and its Application in the Carmen System. Europ. J. on OR 87:722–730

    Article  MATH  Google Scholar 

  56. Wilson N. (Ed.) (1999) Computer-Aided Transit Scheduling, Lecture Notes in Economics and Mathematical Systems, Springer, Berlin

    Google Scholar 

  57. Yu G. (1998) Operations Research in the Airline Industry. Int. Series in OR and Mgmt. Sci., Kluwer, Dordrecht

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Konrad-Zuse-Zentrum Berlin, Takustr. 7, 14195, Berlin, Germany

    Martin Grötschel, Ralf Borndörfer & Andreas Löbel

Authors
  1. Martin Grötschel
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ralf Borndörfer
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Andreas Löbel
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Universität Heidelberg IWR, Im Neuenheimer Feld 368, 69120, Heidelberg, Germany

    Willi Jäger

  2. Forschungszentrum Jülich GmbH PTJ, 52425, Jülich, Germany

    Hans-Joachim Krebs

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Grötschel, M., Borndörfer, R., Löbel, A. (2003). Duty Scheduling in Public Transit. In: Jäger, W., Krebs, HJ. (eds) Mathematics — Key Technology for the Future. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-55753-8_50

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-55753-8_50

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-62914-3

  • Online ISBN: 978-3-642-55753-8

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation