A Comprehensive Approach for Railway Crew Scheduling Problem (Case Study: Iranian Railway Network)

Document Type : Research Paper

Authors

1 MSc. Student, Department of Transportation Engineering, Isfahan University of Technology, Isfahan, Iran

2 Assistant Professor, Department of Transportation Engineering, Isfahan University of Technology, Isfahan, Iran

3 Assistant Professor, Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, Iran

Abstract

The aim of this study is to propose a comprehensive approach for handling the crew scheduling problem in the railway systems. In this approach, the information of different railway trips are considered as input and the problem is divided to three separated phases. In phase I, we generate all feasible sequences of the trips, which are named as the pairings. A depth-first search algorithm is developed to implement this phase. In phase II, the pairings constituting the optimal solution are to be obtained. Both mentioned phases are handled in a centralized decision-making system for the entire railway network. Phase III aims to locally assign the crew groups to the optimal pairings. To solve the problem in phase III, a new mathematical model is developed in this paper. The model can determine the minimum required crew groups, and optimally assign the crew groups to the selected pairings of each home depot. In order to evaluate the developed algorithm and model, the Iranian railway network is evaluated by consideration of all passenger trips of the network. The results show that the proposed approach is capable of efficiently generating the optimal schedules for the railway crew groups in a reasonable computation time.

Keywords


-Caprara, A., Fischetti, M., Guida, P.L., Toth, P. and Vigo D. (1999) “Solution of large-scale railway crew planning problems: The Italian experience”, Computer-aided transit scheduling, Vol. 471, pp. 1-18.
-Caprara, A., Toth, P., Vigo, D. and Fischetti, M. (1998) “Modeling and solving the crew rostering problem”, Operations research, Vol. 46, No. 6, pp. 820-830.
-Ernst, A.T., Jiang, H., Krishnamoorthy, M., Nott, H. and Sier, D. (2001) “An integrated optimization model for train crew management”, Annals of Operations Research, Vol. 108, pp. 211-224.
-Ernst, A.T., Jiang, H., Krishnamoorthy M. and Sier, D. (2004) “Staff scheduling and rostering: A review of applications, methods and models”, European Journal of Operational Research, Vol. 153, No. 1, pp. 3-27.
-Farhadfar, S. and Dolati A. (2015) “Modelling and solving the crew dispatching problem in Iranian railways”, In 4th International Conference on Recent Advances in Railway Engineering, Tehran, Iran (In Persian).
-Freling, R., Lentink, R.M. and Odijk, M. A. (2001) “Scheduling train crews: A case study for the Dutch railways”, Computer-Aided Scheduling of Public Transport,  Vol. 505 of the series Lecture Notes in Economics and Mathematical Systems, pp. 153-165.
-Guillermo, C.G. and José, M.R.L. (2009) “Hybrid algorithm of tabu search and integer programming for the railway crew scheduling problem”, PACIIA 2nd Asia-Pacific Conference on Computational Intelligence and Industrial Applications, Vol. 2, pp. 413-416.
-Hanafi, R., and Kozan, E. (2014) “A hybrid constructive heuristic and simulated annealing for railway crew scheduling”, Computers and Industrial Engineering, Vol.70, pp. 11-19.
-Jütte, S. and Thonemann, U. W. (2012) “Divide-and-price: A decomposition algorithm for solving large railway crew scheduling problems”, European Journal of Operational Research, Vol. 219, No. 2, pp. 214-223.
-Kroon, L.G., Huisman, D., Abbink E., Fioole P., Fischetti M., Maroti G., Schrijver A., Steenbeek A. and Ybema, R. (2008) “The new Dutch timetable: The OR revolution”, Report / Econometric Institute, Erasmus University Rotterdam, Vol. 1, pp. 1-18.
-Nishi, T., Muroi, Y. and Inuiguchi, M. (2011) “Column generation with dual inequalities for railway crew scheduling problems”, Public Transport, Vol. 3, No. 1, pp. 25-42.
-Pourseyedaghaiee, M. and Salehi, P. (2006) “Railway crew (conductors) programming using roundtrip and roster algorithms”, Journal of Transportation Research, Vol. 3, No. 2, pp. 163-173.
-Sepehri M. M. and Hajfathaliha, A. (2001) “A mathematical model for railway crew scheduling based on the network”, 1st Conference of Industrial Engineering, Tehran, Iran (In Persian).
-Sepehri,  M. M., Najmi, M. and Khoshalhan, F. (2004) “Solving railway crew scheduling problem using ant colony method: FBMMAS algorithm”, Conference of Industrial Engineering, Tehran, Iran (In Persian).
-Shijun C. and Yindong S. (2013) “An improved column generation algorithm for crew scheduling problems”, Journal of Information and Computational Science, Vol. 10, No. 1, pp. 175-183.
-Shijun, C., Yindong, S., Xuan S. and Heming, C. (2013) “A crew scheduling with Chinese meal break rules”, Journal of Transportation Systems Engineering and Information Technology, Vol. 13, N0. 2, pp. 90-95.
-Yaghini, M. and Ghannadpour, S. F. (2009) “Railway crew scheduling using heuristic model”. Journal of Transportation Research, Vol. 6, pp.381–395 (In Persian).
-Yaghini, M. and Fathipour, F. (2009) “Modelling and solving multi-objective crew scheduling problem by column-generation approach”, 2nd International Conference on Recent Advances in Railway Engineering, Tehran, Iran (In Persian).
-Yaghini, M., Mazinan, G. and Rostamabadi, A (2009) “Determination of optimal pairings by using minimum-cost flow algorithm for crew planning problem”, 2nd International Conference On Recent Advances In Railway Engineering, Tehran, Iran (In Persian).