A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems

Tao Feng; Richard M. Lusby; Yongxiang Zhang; Siyu Tao; Bojian Zhang; Qiyuan Peng

doi:10.1016/j.trb.2024.102941

journal article May 01, 2024

A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems

Tao Feng

Richard M. Lusby Yongxiang Zhang

Siyu Tao

Bojian Zhang

Qiyuan Peng

Transportation Research Part B: Methodological Vol. 183 pp. 102941 · Elsevier BV

View at Publisher Save 10.1016/j.trb.2024.102941

Topics

No keywords indexed for this article. Browse by subject →

References

58

[1]

Abbink "Solving large scale crew scheduling problems in practice" Public Transp. (2011) 10.1007/s12469-011-0045-x

[2]

Reinventing Crew Scheduling at Netherlands Railways

Erwin Abbink, Matteo Fischetti, Leo Kroon et al.

Interfaces 2005 10.1287/inte.1050.0158

[3]

Abbink "07. Solving large scale crew scheduling problems by using iterative partitioning" (2007)

[4]

Adulyasak "Formulations and branch-and-cut algorithms for multivehicle production and inventory routing problems" INFORMS J. Comput. (2014) 10.1287/ijoc.2013.0550

[5]

Amaya "A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy" Top (2018) 10.1007/s11750-018-0479-2

[6]

Balakrishnan "Real-Time decision support for crew assignment in double-ended districts for US freight railways" Transp. Sci. (2016) 10.1287/trsc.2016.0707

[7]

Barnhart "Airline schedule planning: Accomplishments and opportunities" Manuf. Serv. Oper. Manag. (2004) 10.1287/msom.1030.0018

[8]

Barnhart "Branch-and-price: Column generation for solving huge integer programs" Oper. Res. (1998) 10.1287/opre.46.3.316

[9]

Matheuristics: using mathematics for heuristic design

Marco Antonio Boschetti, Vittorio Maniezzo

4OR 2022 10.1007/s10288-022-00510-8

[10]

Caprara "Timetabling and assignment problems in railway planning and integer multicommodity flow" Networks (2015) 10.1002/net.21611

[11]

Ceder "Applied analysis for improving rail-network operations" J. Rail Transp. Plan. Manag. (2015)

[12]

Cheikhrouhou "A comprehensive survey on the Multiple Traveling Salesman Problem: Applications, approaches and taxonomy" Comp. Sci. Rev. (2021)

[13]

Chen "An improved column generation algorithm for crew scheduling problems" J. Inf. Comput. Sci. (2013)

[14]

Tactical crew planning in railways

Güvenç Şahin, Birol Yüceoğlu

Transportation Research Part E: Logistics and Tran... 2011 10.1016/j.tre.2011.05.013

[15]

Dauzère-Pérès "A Lagrangian heuristic framework for a real-life integrated planning problem of railway transportation resources" Transp. Res. B (2015) 10.1016/j.trb.2015.01.008

[16]

Desaulniers "Public transit" (2007) 10.1016/s0927-0507(06)14002-5

[17]

Staff scheduling and rostering: A review of applications, methods and models

A.T Ernst, H Jiang, M Krishnamoorthy et al.

European Journal of Operational Research 2004 10.1016/s0377-2217(03)00095-x

[18]

Feng "Integrating train service route design with passenger flow allocation for an urban rail transit line" European J. Oper. Res. (2024) 10.1016/j.ejor.2023.07.031

[19]

An ADMM-based dual decomposition mechanism for integrating crew scheduling and rostering in an urban rail transit line

Tao Feng, Richard M. Lusby, Yongxiang Zhang et al.

Transportation Research Part C: Emerging Technolog... 2023 10.1016/j.trc.2023.104081

[20]

Fores "TRACS II: a hybrid IP/heuristic driver scheduling system for public transport" J. Oper. Res. Soc. (2002) 10.1057/palgrave.jors.2601271

[21]

Fuentes "A new approach to crew scheduling in rapid transit networks" Transp. Res. Procedia (2015) 10.1016/j.trpro.2015.09.009

[22]

A hybrid model for crew scheduling in rail rapid transit networks

Manuel Fuentes, Luis Cadarso, Ángel Marín

Transportation Research Part B: Methodological 2019 10.1016/j.trb.2019.05.007

[23]

Geoffrion "Lagrangean relaxation for integer programming" (1974)

[24]

Hartog "Decision support for crew rostering at NS" Public Transp. (2009) 10.1007/s12469-009-0009-6

[25]

Railway crew scheduling: Models, methods and applications

Julia Heil, Kirsten Hoffmann, Udo Buscher

European Journal of Operational Research 2020 10.1016/j.ejor.2019.06.016

[26]

Huisman "Combining column generation and Lagrangian relaxation" (2005)

[27]

Ibarra-Rojas "Planning, operation, and control of bus transport systems: A literature review" Transp. Res. B (2015) 10.1016/j.trb.2015.03.002

[28]

Irnich "Shortest path problems with resource constraints" (2005)

[29]

Irnich "Path-reduced costs for eliminating arcs in routing and scheduling" INFORMS J. Comput. (2010) 10.1287/ijoc.1090.0341

[30]

Kroon "Scheduling train drivers and guards: the Dutch“ Noord-Oost” case" (2000)

[31]

Kroon "Crew scheduling for Netherlands railways “destination: customer”" (2001)

[32]

Kuo "Public transport for smart cities: Recent innovations and future challenges" European J. Oper. Res. (2023) 10.1016/j.ejor.2022.06.057

[33]

Lu "Rich arc routing problem in city logistics: Models and solution algorithms using a fluid queue-based time-dependent travel time representation" Transp. Res. B (2022) 10.1016/j.trb.2022.10.011

[34]

Lusby "A column generation-based heuristic for rostering with work patterns" J. Oper. Res. Soc. (2012) 10.1057/jors.2011.27

[35]

Lusby "A branch-and-price algorithm for railway rolling stock rescheduling" Transp. Res. B (2017) 10.1016/j.trb.2017.03.003

[36]

Lusby "A benders decomposition-based matheuristic for the cardinality constrained shift design problem" European J. Oper. Res. (2016) 10.1016/j.ejor.2016.04.014

[37]

Montalva "Assignment of work shifts to public transit drivers based on stated preferences" Public Transp. (2010) 10.1007/s12469-010-0031-8

[38]

An efficient column generation approach for practical railway crew scheduling with attendance rates

Janis S. Neufeld, Martin Scheffler, Felix Tamke et al.

European Journal of Operational Research 2021 10.1016/j.ejor.2020.12.058

[39]

Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey

Alena Otto, Niels Agatz, James Campbell et al.

Networks 2018 10.1002/net.21818

[40]

Pan "Demand-oriented integration optimization of train timetabling and rolling stock circulation planning with flexible train compositions: A column-generation-based approach" European J. Oper. Res. (2023) 10.1016/j.ejor.2022.05.039

[41]

Papadakos "Integrated airline scheduling" Comput. Oper. Res. (2009) 10.1016/j.cor.2007.08.002

[42]

Quesnel "A branch-and-price heuristic for the crew pairing problem with language constraints" European J. Oper. Res. (2020) 10.1016/j.ejor.2019.11.043

[43]

Ropke "Branch and cut and price for the pickup and delivery problem with time windows" Transp. Sci. (2009) 10.1287/trsc.1090.0272

[44]

Ryan "An integer programming approach to scheduling" (1981)

[45]

Shen "Evolutionary crew scheduling with adaptive chromosomes" Transp. Res. B (2013) 10.1016/j.trb.2013.08.003

[46]

Shenzhen Metro (2021)

[47]

Tapkan "A constraint programming based column generation approach for crew scheduling: A case study for the Kayseri railway" J. Oper. Res. Soc. (2022)

[48]

Trigui "An analytical hierarchy process-based approach to solve the multi-objective multiple traveling salesman problem" Intell. Serv. Robot. (2018) 10.1007/s11370-018-0259-8

[49]

Wang "A branch-price-and-cut algorithm for the local container drayage problem with controllable vehicle interference" Transp. Res. B (2023) 10.1016/j.trb.2023.102835

[50]

Yao "ADMM-based problem decomposition scheme for vehicle routing problem with time windows" Transp. Res. B (2019) 10.1016/j.trb.2019.09.009

Showing 50 of 58 references

Metrics

23

Citations

58

References

Details

Published: May 01, 2024
Vol/Issue: 183
Pages: 102941
License: View

Authors

Funding

National Natural Science Foundation of China Award: 72201218

Fundamental Research Funds for the Central Universities Award: 2682022CX028

Sichuan Province Science and Technology Support Program Award: 2023NSFSC0901

China Scholarship Council Award: 202107000041

National Key Research and Development Program of China Award: 2022YFB4300502

Science and Technology Department of Sichuan Province Award: 22RKX0382

Cite This Article

Tao Feng, Richard M. Lusby, Yongxiang Zhang, et al. (2024). A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems. Transportation Research Part B: Methodological, 183, 102941. https://doi.org/10.1016/j.trb.2024.102941

A branch-and-price algorithm for integrating urban rail crew scheduling and rostering problems

You May Also Like