A constraint programming based column generation approach for crew scheduling: A case study for the Kayseri railway

Tapkan P., KULLUK S., ÖZBAKIR L., Bahar F., GÜLMEZ B.

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, cilt.74, sa.9, ss.2028-2042, 2023 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 74 Sayı: 9
  • Basım Tarihi: 2023
  • Doi Numarası: 10.1080/01605682.2022.2125843
  • Dergi Adı: JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Social Sciences Citation Index (SSCI), Scopus, IBZ Online, International Bibliography of Social Sciences, Periodicals Index Online, ABI/INFORM, Applied Science & Technology Source, Business Source Elite, Business Source Premier, Compendex, Computer & Applied Sciences, INSPEC, zbMATH
  • Sayfa Sayıları: ss.2028-2042
  • Anahtar Kelimeler: Crew scheduling problem, column generation, constraint programming, INEQUALITIES, FRAMEWORK
  • Erciyes Üniversitesi Adresli: Evet

Özet

Although railway systems have been widely used in public transportation for several years, crew scheduling research focuses on airline operations. Since the crew costs constitute the critical part of the operational costs in railway public transportation, the crew scheduling problem gains more importance. Crew scheduling aims to assign all trips to duty packages in a timeline while satisfying several labour working rules, company requirements, and operational restrictions. Because of the complexity of real-world conditions, crew scheduling problems are NP-complete. In this study, the crew scheduling problem was addressed, and a constraint programming based column generation algorithm was proposed as a solution approach. A column generation algorithm was employed to solve problems having a considerable number of variables. In this study, the master problem was designed as a set partitioning problem that aimed to assign all trips to duty while minimizing the cost. In the subproblem, new column(s) satisfying all constraints were generated and added to the master problem to reduce the cost. To analyse the performance of the proposed approach, an integer programming model of the problem was developed. An extensive computational study is presented to compare the results of these two modelling approaches via different real-life problem instances.