Nonlinear Variation Constraints in Railway Crew Scheduling

Crew scheduling at railway companies is challenging, since multiple conditions need to be taken into account. The crew scheduling algorithm currently in use at the Netherlands Railways facilitates this task. However, it is difficult to incorporate nonlinear restrictions on variation in routes of crew members. This thesis describes a study to incorporate such nonlinear restrictions. The aim of this study is twofold. First, it is investigated how the formulation of the crew scheduling problem can be extended to include nonlinear variation constraints. Second, the solution method is adjusted. Two different formulations for the given problem are proposed. In the first formulation, the nonlinear variation measure is linearized exactly. Since this formulation was expected to be difficult to solve, another formulation is presented in which the variation measure is approximated. Both formulations were used to extend the current crew scheduling algorithm. Since violations of the variation restrictions are penalized in all algorithms, we were able to compare both developed methods to the current algorithm that does not take into account variation. Two types of test instances were used to evaluate the performance of the methods. First, artificial instances of different sizes were used. Next, we used single- and multi-day instances based on real life data. On the artificial instances, the first method, in which the variation measure is linearized exactly, is able to generate schedules with more variation than those obtained using the algorithm that does not include variation restrictions, with limited additional duties. Running times and objective values, consisting of duty costs and penalty costs, are comparable to the algorithm without incorporating variation restrictions. The second method yields good solutions on artificial instances, although with slightly higher costs than the first method. On the single-day real life instance, the performance of the first method is similar to that on the artificial instances. When applying this method instead of the one that does not incorporate variation, penalty costs can be decreased by 15 to 100 percent. Since up to 5 percent more duties are selected, duty costs also increase with up to 5 percent. As a consequence, objective values are similar to those of the algorithm that does not incorporate variation. Furthermore, required running time for this method was lower than for the method that does not consider variation. Running time of the second method turned out to be too large for this method to be of practical value on the real life instance. Finally, we used a multi-day real life instance, containing tasks for multiple weekdays. On this instance, the method based on exact linearization of the variation restrictions clearly outperformed the basic model that does not incorporate variation. Where the solution of the basic algorithm only contained slightly more variation than for the single-day instance, the first method was able to increase variation by nearly 80 percent. In addition, running time was lower when we incorporated the variation restriction in comparison to when we did not. In conclusion, both methods are able to solve problems with variation restrictions, but running time of the second method becomes a limiting factor. Since the exact linearization method can increase variation in the schedule with a limited effect on running time or costs, this provides an interesting opportunity to directly include nonlinear variation restrictions in the crew scheduling algorithm at the Netherlands Railways.