Railway Crew (Conductors) Programming Using Roundtrip and Roster Algorithms

In this paper train conductor scheduling in railway network is discussed according to the periodic need of railway to these schedules as a result of periodic train scheduling. By network representation that is consisted of nodes and arcs, a graph is set up by a set of stations and rail links. This graph shows complexity of the discussed railway network. The arcs of the graph represent roundtrips, thus by establishing the roundtrips all the working trips between the stations (nodes) are covered. Roundtrips are generated by heuristic algorithms, for example heuristic algorithm of branching. This algorithm specifies definable roundtrips all over the railway network. Outputs of this algorithm are characteristics of existing roundtrips in each depot, starting and finishing time of each roundtrip as well as covered routes. Afterwards the characteristics of roundtrips are used by roster generation algorithms and clique generation. Clique is used for roundtrips that have overlap with each other and thus can not be performed by one single group of crews. Roster generation is used for evenly generating time shift tables. The rosters used, divide workloads evenly among different units of time. Workload of each roundtrip, duration of the roundtrips, etc.. In this way the roundtrips are assigned so that workload of each unit of time issimilar to others.For assigning similar work load to different periods of time, an f(z) can be used as an objective function that controls the quality of rosters. But as this objective function is non-linear and NP-hard, instead of an exact approach, a heuristic algorithm is used that generates one periodic roster for each depot. This algorithm generates rosters as dense as possible so that it can achieve some levels of optimality. Finally by roster generation algorithm rosters are turned into work shift schedules. In this stage it is important that all the roundtrips assigned to one unit of time in work shift schedules are performed by one group of crews at that unit of time.For showing how the algorithms are used and that better results have been achieved comparing to the current procedures of crew scheduling in Iranian railways, some real examples are included. The achievements in comparison with current situation are:Reducing travel time by generating optimum roundtrips for crewsReducing the number of crews for covering defined roundtrips in each depot.By roster algorithm, the working standards are considerably taken into account. The long paths by which the working time period of the service crew is more than the standard level, reaches to half. The nightly resting time is cancelled except for home depots, and as a result, the dormitory costs are cut. Priorities of this method which divides the railway network to different depots in phase 2 is that the assignments allocated to each depot will not be too large. It means that the number of missions becomes very smaller compared to the dimensions of the network and this, specifically causes reduction of solving time by the computer software.