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

Pınar Tapkan, Sinem Kulluk, Lale Özbakır, Fatih Bahar and Burak Gülmez

Journal of the Operational Research Society, 2023, vol. 74, issue 9, 2028-2042

Abstract: 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.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2022.2125843 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:74:y:2023:i:9:p:2028-2042

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2022.2125843

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().