SINCE THE GERMAN RAILWAY REFORM IN 1996, federal states and transport associations are responsible for regional rail passenger transport. Usually, transport associations determine lines and timetables as well as all requirements for running a transportation network. Based on this, they invite tenders for operating services, whereas railway companies submit bids as operators. In order to be able to make a realistic, cost-effective and thus promising offer, a detailed deployment of material and personnel is necessary. Therefore, the railway companies have to plan vehicles, local services and personnel. Each of these planning problems is very complex and difficult to solve, so that it is hardly possible to generate efficient schedules without appropriate decision support systems.
Since personnel costs make up a substantial part of the overall operating costs of a local transport network, the preparation of shift schedules for train drivers and conductors is of particular importance. First of all, anonymous shifts are created, i.e. sequences of tasks which must meet the requirements of labour laws and collective agreements but are not yet assigned to a specific person. In addition to staffing trains, the shifts also include preparation and closing services, breaks, guest journeys and necessary foot journeys, for example for a change of trains. In a later planning step, these shifts are then assigned to specific employees (personnel rostering).
CHALLENGES
As a conductor is able to change trains at many stations, the number of possible shifts increases exponentially with the size of the planned network and can easily amount to several hundred million per day (!) for a medium-sized network. With this, of course, finding a (near) optimal schedule represents a major challenge, especially as the usual planning horizon for tactical planning is at least one (standardized) week. This week can then be rolled out for a longer planning period. At the same time, the creation of efficient shifts can have a considerable influence on the employees’ productivity and thus on the resulting costs.
Another major complexity driver is the high number of requirements that have to be met with the generated schedule. These derive from the German Working Hours Act, collective agreements and operational demands. Among these are regulations on breaks, working hours and shift length. In addition, preparatory train services, such as times for viewing the working documents at the beginning of the shift, final services at the end of a covered trip, or times for accounting for ticket sales have to be considered. Transitions between two subsequent trips must be organised in such a way that a changeover is possible. Furthermore, requirements that take the entire schedule into account, especially lead to a significant increase in complexity of the crew scheduling. For example, these can be a limited personnel capacity of crew bases (the only places where shifts can start or end), a given percentage of full-time and part-time employees or bounds for the average paid working time.
While each train must always be assigned to a train driver, recently the shift planning for conductors often has a specific characteristic, the so-called attendance rates. These are often required in the tender documents by the transport association to reduce costs and imply that only a specified percentage of train kilometres must be attended by a conductor. In order to avoid penalisation by the transport association, it is necessary for the operating railway company to fulfil these specified rates. Attendance rates can vary, for example, depending on the type of train, the line, the time of day (e.g. from 7 p.m. more personnel required to ensure safety) or even within a train (e.g. change of rate at the border of a federal state). Frequently, several attendance rates have to be considered in a regional transport network.
However, attendance rates are usually not integrated in conventional IT systems for railway planning. Therefore, especially more complex rates (e.g. depending on the time of day) can quickly lead to a high manual effort over several days for planning a transport network. This task often has to be repeated several times throughout the year, e.g. due to construction sites or changes of the timetable. Because of the complexity of the problem, in practice shift plans from previous periods are often used as a basis and adapted manually by the planner. However, the lack of IT support leads to a time-consuming ongoing check of compliance with the attendance rates and the efficiency of the generated schedules is often questionable.
One way of dealing with this planning problem without IT support is to create separate shifts for trips with different rates. In this case, with the support of conventional systems, all trips can first be assigned to shifts (i.e. with a rate of 100%). Afterwards, depending on the respective attendance rate, only a part of the generated shifts is included in the final shift plan (e.g. with a rate of 25%, only a quarter of the generated shifts is actually used). However, this procedure is difficult to implement for some regulations (for example, in the case of attendance rates that are dependent on the time of day). In addition, synergy effects from joint planning of trips with different rates cannot be realised. Since there are no available approaches in research or practice to tackle this task automatically, the research project Sina was established by the German railway company DB Regio AG and the university TU Dresden. A new algorithm had to be developed that makes use of several Operational Research methods. Finally, it was integrated in a new software-based decision support system.
SOLUTION METHOD
In order to solve complex planning problems, the use of Operational Research is often essential. In the past, railway crew scheduling problems could already be solved successfully, but only without taking attendance rates into account. Therefore, it was necessary to extend and adapt existing approaches.
For the railway crew scheduling problem, a solution is created in two phases. In a first step, a large number of feasible shifts are generated, which must meet the requirements mentioned above. Theoretically, all possible shifts could be generated. However, due to the high number of possible changes in regional transport networks, even for smaller practical problems the number of shifts exceeds the capacity of a planner. It is, therefore, important to limit the number of shifts without restricting the solution space and wasting optimization potential. Column generation is a modern mathematical solution method of Operational Research and has already been successfully used to solve highly complex problems. By only generating promising shifts it is able to keep the number of considered shifts low and speed up the solution process significantly.
In the second phase, a set of shifts is selected from all generated shifts. This schedule has to cover all trips that have to be attended, meet attendance rates and, at the same time, should minimize the number of necessary conductors (i.e. costs). This second step can be modelled mathematically as a so-called Set Covering Problem and be solved with the help of a mathematical solver (e.g. IBM ILOG CPLEX or Gurobi).
APPLICATION
The column generation algorithm has been implemented in a new software solution, Sina, to provide decision support. It is designed as client-server architecture so that necessary input data can be prepared locally by the individual planner, while a powerful calculation server solves the underlying mathematical problem. The results can then be downloaded and be further processed by each planner. shows the user interface with a schematic shift schedule generated by Sina.
FIGURE 1 USER INTERFACE OF SINA AND A GENERATED SHIFT SCHEDULE
The results for three real regional transportation networks show exemplarily the applicability and performance of the solution algorithm. shows some properties and the results for these examples. It should be noted that the number of train stations per network contains only train stations where a change of trains is possible. A trip is defined as each part of a train journey that runs between two of these stations. Due to their size and structure, the presented networks can be regarded as typical networks for a regional rail passenger transport. In the generated schedules all essential requirements are met, such as attendance rates, labour regulations or technical requirements. In order to assess the solution quality of Sina, its shift schedules were compared to the approach where trips with different attendance rates are planned separately and are subsequently aggregated to form a feasible schedule. This approach corresponds to planning with conventional planning systems (as presented above), that cannot take attendance rates into account directly.
TABLE 1 RESULTS FOR THREE REAL REGIONAL TRANSPORTATION NETWORKS
the improvements of the objective function ranged between 2% and 38%
The objective function values are composed of fixed costs per shift and a cost rate per working minute of each conductor. Therefore, they represent the actual personnel costs very well. It is evident that considerable reductions of personnel costs can be achieved by using the integrated planning approach of Sina. For the networks presented, the improvement lies between 23.5% and over 50%. It should be noted, however, that in practice the shift schedules of the conventional approach could possibly be improved by manual post-processing by an experienced planner. Nevertheless, it is clear that the high complexity of the planning problem cannot be adequately overseen by a human planner. Taking into account all the shift schedules of DB Regio AG that have been considered during the project, the improvements of the objective function ranged between 2% and 38% as a result of Sina.
Depending on network size and structure, the computation times of Sina are between 15 minutes (Network I) and 35 minutes (Network III). Since the railway crew scheduling is performed on a tactical level, these times are totally acceptable and enable automated shift planning even for larger local transport networks in practice. This is especially the case as the required computation time is nearly exclusively necessary on the calculation server. Furthermore, it is possible to test several variants of shift schedules in parallel to check the influence of changes in the conditions by sensitivity analyses. This includes, for example, strategic issues such as the opening of new crew bases or considerations as to whether tickets should be sold by ticket vending machines or an increased number of personnel in the trains. The results show the potential for improvement that can be achieved through algorithm-based, integrated planning using modern methods of Operational Research.
The developed algorithm resulted in significant cost reductions and enabled a considerable simplification of the planning process
CONCLUSION
The Sina project showed that the integration of attendance rates in regional passenger transport requires new solution methods for an efficient deployment of conductors. The developed algorithm proved to be suitable for use in practice. It resulted in significant cost reductions and enabled a considerable simplification of the planning process. This is another example for the necessity as well as the potential of modern methods of Operational Research. Summing up, the project manager at DB Regio, Volker Jacobsen, stated: ‘The powerful algorithms and, in particular, the consideration of the numerous requirements that are essential for practical application, enable high-quality decision support. This leads to a considerable reduction of our planning effort and considerable cost reductions. Sina is a great benefit for our planning processes.’
Additional information
Notes on contributors
Janis S. Neufeld
Janis S. Neufeld is leader of the research group Operations Management at Technische Universität Dresden, where he received his PhD in 2016. He has worked on several Operational Research projects with partners from industry.