The aim of this study is to propose a comprehensive approach for optimally solving the crew scheduling problem in the railway system. In this approach, the passenger trip data of the railway network are as inputs. The problem is divided into three different phases. In the first phase, all the feasible sequence of trips (called pairings) are generated by using a depth-search algorithm. In the second phase, the optimal pairings are determined. These two phases are solved in a centralized manner for whole of the network.
To select the optimal pairings in the second phase of railway crew scheduling problem, a mathematical model based on the crew transition was proposed. In this model, a penalty cost is considered for the crew transition. The penalty is applied such that not only reducing the number of crew transition, but also maintaining the search space.
The third phase is performed, aiming to assign the crew groups to the optimal pairings and is locally solved for each of the passenger depots. In order to perform this phase, an innovative mathematical programming model is proposed, which is solved by software CPLEX 12. This model, specifies how to assign different pairings to the crew and how much the minimum required crew in each depot is. In this model, the best value for minimum and maximum depot workloads can be determined, through a sensitivity analysis on different levels of workloads. In the proposed model, the solutions for which, the crew workloads are less than their minimum allowable values, are considered as feasible solutions imposed by reasonable penalty costs.
To evaluate the proposed algorithms and the models, the Iranian railway network with all its passenger trips is investigated. These trips are considered in two main outlines, with time horizons of four and six days, based on the specific constraints of Iranian railways. The long-haul trips were divided to two or more ones, considering the depots situated near the borders of the railway areas. The total number of trips for four-day and six-day scenarios were 1068 and 1602, respectively. For each of two mentioned scenarios, different values of the maximum pairing time were tested, aimed to specify the best time horizon, appropriate for Iranian railways. A comparison of scenarios shows that the scenario with a time horizon of 6 days and 28 hours for maximum pairings time, is an appropriate option for Iranian railway conditions. According to the results of the superior scenario, 19025 feasible pairings were produced at the first phase of the problem.
In the second phase, to find the optimal pairings, the proposed transition model with different penalty coefficients was applied for all generated feasible pairings. According to the results, coefficient of 1 was selected as the best value for crew transition penalty in Iran. The results show that 727 optimal pairings were selected for the six-day planning horizon. In the third phase, the crew rostering is implemented separately for each passenger depot of the network. Since the origins and the destinations of the railway network trips are continuously changed, the proposed approach is able to prepare the optimal crew timetables in a reasonable time.