Communications - Scientific Letters of the University of Zilina 2016, 18(11):21-27 | DOI: 10.26552/com.C.2016.1A.21-27

The Column Generatiion and Traiin Crew Scheduliing

Jaroslav Janacek1, Peter Marton1, Matyas Koniorczyk2
1 Department of Mathematical Methods and Operations Research, Faculty of Management Science and Informatics, University of Zilina, Slovakia
2 Department of Applied Mathematics, Faculty of Natural Sciences, University of Pecs, Hungary

Better productivity and efficiency is more and more required in the railway operation. The train crew management is one of the several problems that could be solved using mathematical methods. Crew management is a problem that is well-known in Operations Research. We compare two approaches for solving the train crew scheduling problem. The first approach consists of solving the original problem by single model. The second approach corresponds to the step-by-step column generation. This technique was originally based on Dantzig-Wolfe decomposition. The benchmarks used for comparison of both approaches originate in real problems from railway systems in Slovakia and Hungary.

Keywords: train crew scheduling; Dantzig-Wolfe decomposition; column generation

Published: March 31, 2016  Show citation

ACS AIP APA ASA Harvard Chicago Chicago Notes IEEE ISO690 MLA NLM Turabian Vancouver
Janacek, J., Marton, P., & Koniorczyk, M. (2016). The Column Generatiion and Traiin Crew Scheduliing. Communications - Scientific Letters of the University of Zilina, 18(1A), 21-27. doi: 10.26552/com.C.2016.1A.21-27
Share...
Download citation
  • BibTeX (.bib)
  • Bookends (.ris)
  • EasyBib (.ris)
  • EndNote (.enw)
  • EndNote 8 (.xml)
  • ISI WoS (.isi)
  • Medlars (.medlars)
  • Mendeley (.ris)
  • MODS (.xml)
  • Papers (.ris)
  • RefWorks (.txt)
  • RefManager (.ris)
  • RIS (.ris)
  • MS Word (.xml)
  • Zotero (.ris)
    • Open full article

    References

    1. BARNHART, C., JOHNSON, E. L., NEMHAUSER,G. L., SAVELSBERGH, M. W. P., VANCE, P. H.: Branch-and-Price: Column generation for Solving Huge Integer programs. J. R. Birge and K. G. Murty (eds.), Mathematical Programming: State of the Art 1994, University of Michigan, 186-207, 1994.
    2. DESROSIERS, J., DUMAS, Y., SOLOMON, M. M., SOUMIS, F.: Time Constrained Routing and Scheduling. M. O. Ballet al. (eds.), Handbooks in OR&MS, vol. 8, Elsevier Science Publishers, 35-139, 1995. Go to original source...
    3. HOFFMANN, K. L., PADBERG, M. W.: Solving Airline Crew Scheduling Problems by Branch-and-cut. Management Science, 39:657-682, 1993. Go to original source...
    4. RIOS, J., ROSS, K.: Massively Parallel Dantzig-Wolfe Decomposition Applied to Traffic Flow Scheduling. Proc. of the AIAA Guidance, Navigation and Control Conference, 10-13 August, Chicago Illinois, pp.1-14, 2009. Go to original source...
    5. CAPRARA, A., FISCHETTI, M., TOTH, P., VIGO, D., GUIDA,P. L.: Algorithms for Railway Crew Management. Mathematical Programming, 79:125-141, 1997. Go to original source...
    6. KOHL, N.: Solving the World's Largest Crews Scheduling Problem. ORbit Extra, Danish Operations Research Society, August 2003.
    7. KROON, L. G., FISCHETTI, M.: Scheduling Drivers and Guards: The Dutch Noord-Oostcase. Proc. of 34th HICSS conference, Hawaii, 2000.
    8. WILSON, N. H. M. (ed.): Computer Aided Transit Scheduling, Springer-Verlag, 1999. Go to original source...
    9. ABBINK, E., FISCHETTI, M., KROON, L., TIMMER, G., VROMANS, M.: Reinventing Crew Scheduling at Netherlands Railways. Interfaces, 35.5:393-401, 2005. Go to original source...
    10. GASS, S. I.: Linear Programming-Methods and Applications, McGraw-Hill Book Co.: New York, 1969, Slovak translation Alfa Bratislava, 1972, p. 397.
    11. BORNDORFER, R., GROTSCHEL, M., PFETSCH, M. E.: A Column-generation Approach to Line Planning in Public Transport. Transportation Science, 41(1), pp. 123-132, 2007. Go to original source...
    12. JANACEK, J., SIRC, J.: The Column Generation Technique for Public Transport Line Planning by IP-solver. Communications-Scientific Letters of the University of Zilina, 12(3A), pp.60-64, 2010. Go to original source...
    13. KONIORCZIK, M., TALAS, B., GEDEON, F.: Preconditioning in the Backtracking Duty Generation of Passenger Rail Crew Scheduling: A Case Study, Communications - Scientific Letters of the University of Zilina, 17(2), pp. 23-29, 2015. Go to original source...
    14. WEDELIN, D.: Analgorithm for Largescale 0-1 Integer Programming with Application to Airline Crew Scheduling. Annals of Operations Research, 57:283-301, 1995. Go to original source...

    This is an open access article distributed under the terms of the Creative Commons Attribution 4.0 International License (CC BY 4.0), which permits use, distribution, and reproduction in any medium, provided the original publication is properly cited. No use, distribution or reproduction is permitted which does not comply with these terms.


    Return to the content