11.1 Introduction

Netherlands Railways (NS) currently (2015) operates about 4700 commercial passenger trains on each working day. Here a train is not a physical object, but a timetabled train service with a unique train number. This terminology is used in the remainder of this chapter. Each train needs at least a train driver and a number of conductors. The latter number depends on the length and the type of the corresponding rolling stock composition.

To that end, NS employs about 3300 drivers and 3500 conductors, some of which are employed part-time. In order to be able to carry out their work, these crew members possess certain qualifications. For drivers these include route knowledge and rolling stock knowledge. Having route knowledge means that a driver is familiar with the routes on which heFootnote 1 has to operate trains. He knows where to expect signals and where to adjust the speed of the trains to specific circumstances in the railway infrastructure. Rolling stock knowledge relates to the specifics of the different types of rolling stock. The conductors are also supposed to have a certain rolling stock knowledge, but this is less detailed than the drivers’.

Carrying out the work on the trains in the most efficient way with the available crew members is the result of an extensive planning and rescheduling process. This chapter discusses several aspects of this process, its organization, and the tools that are used within it. We focus on practical aspects that have not been described so much in literature yet.

The remainder of this chapter is structured as follows. In Sect. 11.2 we describe the main concepts in the crew management process in more detail. In Sects. 11.3 and 11.4 strategic and operational planning processes are presented. Section 11.5 describes the real-time rescheduling process. In Sect. 11.6 we describe two extended versions of the well-known set covering model that are used as the kernel of the planning support systems for the crew (re)scheduling processes at NS. Section 11.7 presents an overview of the developments that lead to the currently available planning support tools within NS. This chapter is finished with Sect. 11.8 where we sketch some further developments that are relevant for crew management.

11.2 Main Concepts in Crew Management

In this section, we describe the main concepts in crew management in more detail. First, we describe the demand side of crew management: the tasks that need to be scheduled to operate the trains. Then we describe the concept of a duty, a sequence of tasks to be carried out by a single crew member. Finally, we describe the depots with their crew members (the supply side of crew management) and rosters, which allocate the duties to the crew members.

11.2.1 Tasks

Each trip of a train from one station to the next defines a number of tasks: one task for a driver and one or more tasks for conductors. A task means that a crew member of the right type and with the right qualifications must be present at the corresponding train, and either drive the train or provide service to the passengers. Each task is defined by a start station and start time, and an end station and end time, as specified by the timetable. Another characteristic of a task is the type of the involved rolling stock.

Note that stations where the crew of a train cannot be changed are not really relevant in the context of crew management. Therefore one can aggregate consecutive tasks of the same type (driver or conductor) on the same train that start or end in a station where the crew of a train cannot be changed. As a consequence, one may assume that each aggregated task starts and ends in a station where a train starts or ends, or where the crew of a train can be changed. In the following, we will use the term “task” for “aggregated task”.

Apart from the trains in the commercial operation, also a number of trains are operated for repositioning rolling stock units. These trains are often also timetabled, and must also be supplied with a driver. Usually these trains do not need a conductor, although sometimes such trains are also used for repositioning crew members.

The distribution of the total workload over the weekdays is about 15% per workday, and 13% and 12% on Saturdays and Sundays, respectively. On a normal workday, the total numbers of tasks for drivers and conductors are approximately equal to 10,000 and 12,000, respectively. The workload of the conductors shows two peaks on workdays due to the higher passenger demand during peak hours, resulting in more trains and in trains with more capacity (longer, double-deck).

11.2.2 Duties

In the planning process, the tasks to be carried out are organized into a number of duties. Here each duty is a sequence of consecutive tasks to be carried out by a single crew member and in most cases on a single day. Within each duty, two consecutive tasks end and start at the same station, and the second task starts later than the first task has ended. The fact that duties are supposed to be carried out on a single day is the result of the fact that NS operates only a small number of night trains. Moreover, one of the rules used in the crew scheduling process of NS is that each duty ends at the same location as where it started. This is in contrast with the situation in larger countries, like, e.g., Germany, where an outbound duty may be followed by an inbound duty with an overnight outside rest in between.

On a normal workday, the number of duties for drivers and conductors are approximately equal to 1000 and 1100, respectively.

Example

Figure 11.1 shows nine duties for drivers. The horizontal direction represents time. The green horizontal lines represent the tasks to be carried out. The numbers above the tasks denote the corresponding train numbers. The brown horizontal lines below the tasks indicate that two consecutive tasks are carried out on the same rolling stock composition. If this is not the case, then there must be a transfer time of at least 20 min between two tasks.

Fig. 11.1
figure 1

Nine duties for train drivers as shown in the CREWS system

Full size image

For example, the first duty is a duty for depot Amsterdam (Asd), where the duty starts around 6:00. Then it proceeds along The Hague (Gvc), Utrecht (Ut), Eindhoven (Ehv), Sittard (Std), Maastricht (Mt), and Heerlen (Hrl), to return around 15:30 in Amsterdam. This duty transfers four times from one rolling stock composition to another, as is shown by the brown horizontal lines. The * (star) in the middle of the duty indicates the meal break.

The yellow horizontal lines in the fifth, seventh, and ninth duty represent crew repositioning tasks, also called passenger tasks, indicated by a “P”. These tasks are not used for driving a train from one station to another but for repositioning a driver from one station to another. In the other duties (not shown in the figure) there are other tasks for drivers on the involved trains, which are used for actually driving these trains.

11.2.3 Depots

The drivers and conductors of NS currently operate from 28 depots: each crew member belongs to one crew depot, where each of his duties starts and ends. The depots are typically located at the main stations in the network (like Amsterdam, Rotterdam, Utrecht, and Eindhoven), but also at the stations closer to the borders of the country, either the natural borders of the country (like Den Helder and Vlissingen) or the borders with the neighbouring countries (like Groningen, Enschede, and Maastricht). The former depots are usually large, since they are visited by many trains, and, as a consequence, they can easily cover a large number of tasks. The latter depots are usually smaller. A main reason for the existence of these depots is that their crew members can cover the tasks in the early morning from these stations as well as the tasks in the late evening towards these stations.

11.2.4 Rosters

The rosters describe the allocation of the duties to the crew members. Within NS, the crew members of each crew depot have been allocated to a number of roster groups. The crew members within each roster group have more or less the same qualifications.

The duties of each depot are allocated to the different roster groups: each roster group has its own duties. In this allocation the contents of the duties and the qualifications of the members of the roster groups are taken into account. The allocation of the duties to the crew members of the roster groups is based on a periodic roster. As a consequence, if the roster is carried out completely as planned, then the crew members already know a long time in advance on which days they will be on or off duty. However, in practice there are usually deviations from the periodic roster, due to vacations or illness of crew members.

Currently in many companies the allocation of duties to crew members is handled by an individual rostering system. Here crew members can specify their preferences for days and times on which they want to be on or off duty. This provides much more flexibility than a periodic roster. Although some experiments with such an individual rostering system have been carried out, NS has not implemented such a system yet.

11.3 Strategic Planning

With respect to the capacity and the organization of the workforce, decisions have to be made to make sure that the capacity of the workforce matches as well as possible with the work to be carried out, both quantitatively and qualitatively. The latter refers to the required qualifications of the crew members.

Strategic decisions have to be taken with respect to the number, the locations and the capacities of the depots, both on the relatively short term and on the longer term. Changing the number or the locations of the depots is not usual. It is more common to change the capacities of the depots by hiring new crew members. Firing crew members is very uncommon, but of course in the long run crew members quit, since they retire or change jobs. Furthermore, transferring or delegating crew members from one depot to another is incidentally possible.

It takes one (for conductors) to three (for drivers) years to fully train a new crew member. This includes both theoretical training and practical on-the-job training. As a consequence, the long term capacity management process has to anticipate on long term changes in the workload. These are mainly determined by long term changes in the line system, the timetable, the rolling stock capacity, and the labor rules. Conversely, the decisions taken within the capacity management process, e.g. with respect to hiring new crew members, have long lasting effects on the capacity of the workforce.

A problem that is often faced in practice is that the capacity of the workforce as a whole is sufficient to cover the total workload, but that part of the capacity of the workforce is available at the wrong locations. This may have a negative influence on the efficiency of the crew scheduling process, since in such situations more repositioning tasks will have to be scheduled in order to move the crew members to the locations of the tasks to be carried out. According to the collective labour agreements, such repositioning tasks are also considered as part of the work to be carried out, and are paid as such.

Despite the strategic impact and relevance of the long term capacity management process, models and tools for supporting this process are hardly available. The studies usually do not go beyond “what-if” analyses based on a forecasted timetable and rolling stock circulation. As a consequence, in the remainder of this chapter we focus on the operational and real-time crew management processes, given the number, locations, and capacities of the crew depots.

11.4 Operational Planning

The operational crew planning process can be split in several steps, as depicted in Fig. 11.2.

Fig. 11.2
figure 2

Planning phases

Full size image

The major part of the operational planning process is carried out within the NS headquarters in Utrecht. However, the process of planning the rosters for the crew depots, based on the planned crew duties, is carried out in the depots themselves.

In each stage of the operational planning process as well as in the real-time rescheduling process, the crew (re)scheduling process follows the timetabling and rolling stock (re)scheduling process. This is caused by the fact that the timetable and the rolling stock circulation determine the tasks to be carried out by the crew, as explained before.

The tasks are input for scheduling the duties. During the duty scheduling process, the duties are anonymous. That means that the duties have not yet been allocated to individual crew members. Thus the qualifications of the individual crew members can not be taken into account in this stage of the planning process.

The finalized duties are used for creating the rosters. About six times a year, the generic tasks, duties and rosters are modified. Each week, the schedules are adapted to the specific exceptions on a calendar day.

When we expect severe weather conditions, we can adapt the schedules and reduce the number of trains to be operated in advance. We call this Ultra-short rescheduling, on the day before operation. We will discuss the most important steps, the planning of generic duties, basic rosters, calendar duties and the Ultra-short term rescheduling, in the following sections.

11.4.1 Planning for Generic Duties

In principle, the timetable that is operated by NS is a periodic timetable with a period of 1 h. Most of the lines in the system are even operated twice per hour with an interval of exactly 30 min. However, there are slight differences between peak hours and off-peak hours and weekends. Usually during peak hours a few additional trains are scheduled in order to cope with the increased passenger demand.

Each year a new timetable, often based on a modified timetable, is introduced in December. That is, a detailed plan for each generic day of the week is produced. It is a plan for 7 × 24 generic hours. This plan is based on the one hour periodic timetable, but takes into account also the deviations from the periodic timetable in more detail: the start and end of the day, the peak hours, and the weekends. The rolling stock circulation is already such that the rolling stock that is needed in each station for the start-up of the timetable on a certain day has arrived on that station in the preceding night.

After creating the timetable and rolling stock circulation, detailed duties for the crew members are created, thereby taking into account the available capacities of the depots. If a certain depot does not have sufficient capacity for carrying out all its tasks, then additional capacity is provided by scheduling repositioning tasks from other depots. In each depot also a number of stand-by duties is scheduled. Crew scheduling is the process of creating the total set of crew duties from scratch.

The generic set of duties for the complete week is used as input for the crew rosters in the depots. The generic plan is modified only a few times per year. When modifying the generic plan, the existing crew rosters in the depots are taken into account. The crew duties are modified such that they fit as well as possible within the existing crew rosters.

11.4.2 Crew Rostering

As it was mentioned in Sect. 11.2.4, NS currently uses a periodic crew rostering system for allocating the anonymous duties to the crew members. Within NS this process is carried out completely manually, although some experiments with automated rostering support have been carried out, see Hartog et al. [7] and Abbink [1].

As described in Sect. 11.2.4, each crew member belongs to exactly one roster group in a crew depot.

The rostering process is carried out once per year in the crew depots, usually in the autumn when the duties for the generic days in the next yearly timetable have been completed and communicated with the crew depots.

Usually, a first step in the creation of a detailed roster for a roster group is the creation of a pattern roster, describing the pattern of early, late, night and rest duties. Herein also some additional duties must be scheduled, such as stand-by duties and compensation duties. A compensation duty is an extra day off due to a certain amount of irregular working times. Given the many aspects to be taken into account, creating a new pattern roster by hand is extremely difficult. Therefore, the previous roster is often used as a basis for the new one, with only minor adjustments.

The second step in the rostering process is the allocation of the duties to the different roster groups. This is accomplished by a negotiation process between the representatives of the roster groups. In this process the characteristics of the duties and the qualifications of the crew members of the roster groups are taken into account. Also a fair allocation of the attractive and less attractive duties among the roster groups is aimed at. See also Sect. 11.6.2 for a further description of this aspect.

Finally, the duties that have been allocated to a roster group are attached to its pattern roster. If at some point in this rostering process some roster groups cannot find a feasible roster, then the allocation of the duties to the roster groups must be revised or the pattern roster must be adjusted.

Examples of constraints that have to be considered in the rostering process are the following: the rest time between two duties is at least 12 h, except when the first duty finished after 2:00 a.m., then it is at least 14 h. The minimum rest time between two duties is 14 h, if the first duty finishes after 2:00 a.m., the day following the day this first duty starts. The maximum working time per week is 45 h, and over a period of 13 consecutive weeks the average working time per week is at most 40 h. At least once every 3 weeks there is a Red Weekend: a rest period of at least 60 h, starting not later than Saturday 0:00 a.m. and ending not earlier than Monday 4:00 a.m.

From the crew members perspective, the quality of a roster is determined by the sequencing of the roster days and the variety in the duties. Some examples: a series of duties with the same type directly after each other is preferred over sequences of different types of work. Here the type of a duty is either an early, late or night duty. Two or more adjacent days off are preferred. Similar duties should be spread over the roster. A lot of variety in the work is preferred (routes, rolling stock).

For more details and for optimization models that can be used in the rostering process, we refer to [7] and [1]. Here the constraints to be satisfied are modeled in an explicit way. Caprara et al. [6] describe models for crew rostering based on set covering models that are very similar to the standard models for solving crew scheduling problems, where the constraints to be satisfied are modeled more implicitly.

11.4.3 Planning for Calendar Duties

In the following stage, a detailed plan for the calendar days is generated. Usually, each calendar day requires a modified timetable. The latter may be due to the fact that certain trains have to be cancelled because of maintenance or extension of the railway infrastructure, or due to the fact that extra trains have been scheduled for a special event, such as an exposition or a sports event. Especially during the weekends often a lot of maintenance of the infrastructure is carried out.

The planning process for the calendar days is an ongoing process that is carried out on a week-by-week basis. Thus this planning process covers 52 × 7 × 24 calendar hours. Again the crew duties are modified such that they fit as well as possible within the existing rosters in the depots. As far as possible, the same constraints are taken into account as in the duties for the generic days.

The planning process for the calendar days is a rescheduling process , in which one of the aims is to leave as many as possible of the duties the same as they are in the plan for the generic days. However, sometimes it is inevitable to modify a large number of duties.

11.4.4 Ultra-Short Term Rescheduling

In order to be able to better cope with snow during winters and other extreme weather conditions, NS decided to develop an ultra-short term rescheduling process. The aim of this ultra-short term rescheduling process is to reduce the number of trains in case of expected snow or other extreme weather conditions. The reduced number of trains is realized by decreasing the frequencies of the trains, in particular on the main corridors. Due to the reduced number of trains, the remaining trains can be controlled better by traffic control, and thus the probability of a snow-ball effect of delays and cancellations is reduced. Therefore, the predictability of the railway system remains higher than without these measures.

The decision to adapt the timetable, the rolling stock circulation and the crew duties is based on the weather forecast on the day before the adapted schedules are to be operated. The final go/no go decision for the adaptations is taken at 15:20 and communicated at 16:00 on that day. Thus the timetable, the rolling stock circulation and the crew duties must be adapted during the upcoming evening and night, although some pre-processing can be done already in advance. In this ultra-short term crew rescheduling process, the availability of fast and automated rescheduling tools has proven to be indispensable.

A consequence of the application of the ultra-short term rescheduling process was that the railway system remained better in control during bad weather conditions. On the other hand, the reduced frequencies of the trains obviously also lead to a reduced transport capacity. Therefore, after the first applications of this process, this reduction in transport capacity was compensated by increasing the capacities of the remaining trains where possible.

11.5 Real-Time Operations

The proof of the pudding is in the eating: the duties have to be carried out during the real-time operations. On the day-of-operations, the allocation of duties to crew members is determined by the crew rosters. However, it may happen that this is not possible due to illness or vacation of crew members. In that case, first the crew members that have been allocated to a stand-by duty may be used to replace the absent crew members. If these crew members are active already, then an ad hoc solution must be found. The crew dispatchers in the dispatching centres are responsible for covering as many tasks and duties by a crew member as possible.

Given the allocation of duties to crew members, rescheduling the duties is not necessary as long as the timetable and the rolling stock circulation are carried out as planned. However, if there are delays or disruptions, the duties may have to be rescheduled. If a train has a serious delay and the driver has to transfer to another train at a next station, then the other train may get a delay as well if the duties are not rescheduled. In that case, the crew dispatchers will try to find an alternative crew member who can carry out the tasks that are delayed otherwise. Also the delayed driver will have to get an alternative continuation of his duty.

In case of a serious disruption, for example due to malfunctioning infrastructure or rolling stock or due to an accident, usually a number of trains (or parts thereof) are cancelled. In such a situation, the trains that are cancelled are selected based on a certain incident scenario for the actual disruption. As a consequence, at least the duties covering the tasks corresponding to the cancelled trains have to be rescheduled, since the involved crew members may not be able to reach the next tasks in their duties in time. However, in order to get some more flexibility in the rescheduling process, also some additional duties may be rescheduled. The crew dispatchers usually aim at minimizing the number of rescheduled duties.

Examples of aspects that have to be taken into account when rescheduling the crew duties are the following: The rescheduled duties should still as much as possible satisfy the general constraints for the crew duties. Thus there is preferably a meal break at an appropriate time and place if the duty length exceeds a certain minimum length. Furthermore, the length of the duty may not be extended too much, and the duty should end at its own depot. Due to the many constraints to be taken into account, and due to the fact that the crew duties do not follow a periodic pattern (as is more or less the case for the rolling stock), crew rescheduling is usually considered as the most difficult part of the disruption management process.

The real-time rescheduling process is carried out in five regional dispatching centers, directed by the central Operational Control Center Rail located in Utrecht. The fact that this process is carried out from five dispatching centers requires a lot of coordination between these centers, which significantly complicates the real-time crew rescheduling process.

11.6 Optimization Models

In this section, models and solution techniques for the crew scheduling (see Sect. 11.4.1) and crew rescheduling (see Sect. 11.5) are described. We start with a description of a number of relevant objectives and constraints.

11.6.1 Objectives

NS considers three important objectives in crew planning: (1) efficiency, (2) robustness, and (3) quality of work. Efficiency means that the total crew costs are as small as possible, both the planned costs and the realized costs. In principle, this means that the workload should be carried out by a minimum number of crew members, since these are the main cost drivers in this planning process. In the real-time rescheduling process additional costs should be avoided by minimally extending the original duty lengths (additional time must be paid), and by minimally using taxis for repositioning crew members, additional to the taxis already included in the planning phases.

The robustness of the crew duties, i.e. preventing propagation of delays via the crew duties, depends on several elements, including the transfer times of the crews when transferring from one rolling stock composition to another. The recoverability of the duties in case of a disruption may depend on the structure of the duties. If the rescheduling process is carried out manually, then duties with a relatively simple structure may be easier to recover than more complex duties. However, it has been demonstrated also that the availability of effective crew rescheduling tools eliminates this advantage of simply structured duties, see Vlugt [14].

The quality of work is the quality of the duties as it is perceived by the crew members. This quality of work is addressed via labor rules and company agreements, for example, on the amount of variation in the duties as specified by the so-called “Sharing-Sweet-and-Sour” rules. These rules are described in the next section.

Since several objectives have to be taken into account, a trade-off between these objectives must be made until a solution has been found that is acceptable with respect to all objectives. The availability of effective planning support tools is indispensable here.

11.6.2 Constraints

The constraints that have to be respected in the crew scheduling process are rules at the duty level and constraints at the depot level. Examples of constraints at the duty level are the following: each duty starts and ends at the home depot, the length of a duty should not exceed a certain maximum duty length, each duty longer than 5:30 h should have a meal break of sufficient length, the transfer time when transferring from one train to another should be at least 20 min, and each duty should have a certain variation. The latter is expressed by an upper bound on the “repetition in duty”, which means that a duty cannot cover any part of the railway network more than a certain number of times.

Examples of constraints at the depot level are the following: per depot the number of weekly duties should not exceed a certain number, per depot the weekly average duty length should not exceed 8 h, per depot the weekly percentage of duties longer than 9 h should not exceed a certain upper bound, and per depot the weekly percentage of night duties should not exceed another upper bound.

Also the so-called “Sharing-Sweet-and-Sour” rules are to a large extent constraints at the depot level. These rules aim to quantify the fair allocation of the “sweet” and “sour” workloads among the 28 crew depots. “Sweet” mainly represents the variety in routes and lines as well as the work on intercity trains. “Sour” mainly represents the work on lines with a lot of anticipated passenger aggression and the work on relatively old rolling stock. For example, for each depot at least 35% of the work should be on intercity trains. Furthermore, there is also an upper bound on the standard deviation of these percentages over the 28 depots in order to guarantee a fair allocation of the different types of work, see Abbink et al. [2].

11.6.3 Crew Scheduling: Model

The crew scheduling problem for generic days, as described in Sect. 11.4.1, is the problem of most efficiently covering a number of tasks by a number of feasible duties from scratch. As is well-known, the crew scheduling problem can be described by an extended set covering model, see Caprara et al. [5]. Modelling the complex constraints directly usually leads to models that are hard to solve.

To that end, let T be the set of tasks to be covered and let D be the set of potential duties. The subset D t ⊂ D consists of the set of potential duties covering task t ∈ T. Every duty d has costs c d . Furthermore, let S be the set of additional constraints at the depot level, and let l s and u s be the corresponding lower and upper bound for constraint s ∈ S. Finally, let w s, d be the coefficient of duty d ∈ D for constraint s ∈ S.

Next, the binary decision variable X d indicates whether potential duty d ∈ D is included in the solution or not. Then the extended set-covering model, with additional constraints at the depot level, can be formulated as follows:

$$\displaystyle\begin{array}{rcl} & & \min \sum _{d\in D}c_{d}X_{d} \\ & & \text{subject to}{}\end{array}$$
(11.1)
$$\displaystyle\begin{array}{rcl} \sum _{d\in D_{t}}X_{d} \geq 1\qquad \text{ for all }t \in T& &{}\end{array}$$
(11.2)
$$\displaystyle\begin{array}{rcl} l_{s} \leq \sum _{d\in D}w_{s,d}X_{d} \leq u_{s}\qquad \text{ for all }s \in S& &{}\end{array}$$
(11.3)
$$\displaystyle\begin{array}{rcl} X_{d} \in \{ 0,1\}\qquad \text{ for all }d \in D& &{}\end{array}$$
(11.4)

Here (11.1) is the objective function, which states that the sum of the duty costs is to be minimized. Constraints (11.2) guarantee that for each task t ∈ T at least one duty covering this task is selected. It may sometimes be better to cover a task more than once. If, for example, on a certain day the number of tasks going out of a crew depot differs from the number of tasks going into that crew depot, then over-covering is necessary. Moreover, even if over-covering is not necessary, it may sometimes be more efficient to allow over-covering. By allowing over-covering, other tasks may be covered more easily, resulting in a larger decrease in costs than the additional costs for the over-covered tasks.

Besides the regular tasks that must be covered, the formulation also allows to include a number of additional tasks in the model. These are tasks outside the set T, so that they need not be covered according to (11.2). For example, one can add possible taxi trips to reposition crew members from one location to another. These taxi trips have certain costs, but may make the duties feasible and/or more efficient. Tasks related to shunting activities at stations are examples of other additional tasks. They can be included in the duties, but they can also be performed by dedicated shunting crew members locally at the stations, when the crew duties become inefficient by including these additional shunting tasks.

The additional constraints (11.3) are related to the constraints at the depot level, such as the number of duties per crew depot, or the average length of the duties per crew depot. In these constraints, u s can be considered as the availability of a certain resource, and w s, d as a parameter describing the amount of this resource used by duty d. For example, let K be the set of depots, and let k d and l d denote the crew depot and the length of duty d, respectively. Furthermore, let C k denote the maximum number of duties for depot k (given the capacity of depot k), and let L denote the maximum average length of the duties of each crew depot. Then the following constraints (11.5) and (11.6) guarantee that the maximum number of duties and the average duty length for each crew depot k ∈ K are not exceeded, respectively. These constraints have the general structure described by constraints (11.3).

$$\displaystyle\begin{array}{rcl} & \sum _{d\in D:\ k_{d}=k}X_{d} \leq C_{k}\qquad \text{ for all }k \in K&{}\end{array}$$
(11.5)
$$\displaystyle\begin{array}{rcl} & \sum _{d\in D:\ k_{d}=k}(l_{d} - L)X_{d} \leq 0\qquad \text{ for all }k \in K&{}\end{array}$$
(11.6)

11.6.4 Crew Scheduling: Solution Technique

The solution process for solving the extended set covering model usually consists of a duty-generation module and a duty-selection module. The algorithm first generates a large set of potential feasible duties. A duty is feasible if it satisfies all constraints at the duty level. That is, it takes into account, for example, the maximum duty length, and the location and duration of the meal break. Then the above described extended set covering model is used to select the subset of feasible duties that covers all tasks in the most efficient ways.

However, since the set of feasible duties can be extremely large, enumerating all possible feasible duties a priori is usually not a practical approach. Therefore a standard approach is to use dynamic column generation . This technique does not generate all duties a priori, but it generates them on-the-fly during the solution process. Within the solution process, dual information from the current solution is used to determine whether it is useful to extend the number of duties. An appropriate way to determine this dual information is based on Lagrangian Relaxation instead of Linear Programming. This dual information is used in the duty-generation module, which checks for the existence of additional duties that may be useful to improve the solution. The duty-generation problem can be solved as a resource constrained shortest path problem in a network representing the crew tasks, see Caprara et al. [5].

If dynamic column generation is applied, then the solution process iterates between the duty-generation module (also called pricing problem) and the duty-selection module (also called the master problem). The algorithm may delete feasible duties that were generated in earlier stages and whose effectiveness turns out to be low during later stages of the process. The latter is done to keep the number of active duties manageable. Usually the duty-selection module heuristically looks for a solution for the overall model, based on the currently available set of feasible duties. After a number of iterations, the procedure may activate a fixing procedure to select some duties that appear to be particularly efficient, and to fix them as belonging to the final solution. Then the algorithm repeats this process on the tasks that have not yet been covered by the fixed duties.

Solving an instance of NS for a single day may take at least several hours to compute a feasible solution with sufficient quality. Moreover, currently also instances of NS for a complete week can be solved in up to a week of computation time, see Abbink et al. [4]. The advantage of solving instances for a complete week is that several of the constraints are expressed in weekly averages per depot, such as the constraints on the maximum weekly average duty length per depot. Therefore the resulting solution is usually more efficient than a solution that is obtained by requiring such constraints on a day-by-day basis.

11.6.5 Real-Time Crew Rescheduling: Model

The model and solution process as described in Sects. 11.6.3 and 11.6.4 focus on the planning process from scratch. As explained, it may take at least several hours to compute a feasible solution with sufficient quality for an instance involving a single day. Although this is an impressive improvement in comparison with a manual planning process, it is far too long for the real-time disruption management process, as described in Sect. 11.5. There a solution is needed within minutes, and hence a suboptimal solution is better than no solution at all.

Moreover, the real-time crew rescheduling problem is different from the crew scheduling problem (11.1), (11.2), (11.3), and (11.4) in the planning stage. First of all, the real-time crew rescheduling process has to take into account the fact that a number of duties have started already. The parts of these duties that have been carried out already cannot be changed anymore. Thus for each active duty a feasible completion must be found. Furthermore, whereas the crew scheduling problem (11.1), (11.2), (11.3), and (11.4) aims at the generation of anonymous duties, one has to deal now with duties that have been allocated to individual crew members, each with their own qualifications. When rescheduling the duties, these have to be respected.

In addition, in the crew scheduling problem (11.1), (11.2), (11.3), and (11.4) all tasks must be covered, since the timetable and rolling stock circulation are fixed. In the real-time crew rescheduling process this may not be true anymore. If it turns out that certain tasks cannot be covered by a completion of a duty, these tasks will have to be cancelled. If this is a task for a driver, then this means that the corresponding train will not be operated. This is highly undesirable in itself, but in particular since this also has consequences for the rolling stock circulation. If it seriously influences the rolling stock circulation, then another iteration of timetable rescheduling, rolling stock rescheduling and crew rescheduling will be required. Note that, if the driver agrees, then it is allowed that a train is operated without a conductor, but this is undesirable as well.

An issue that also plays a role in the real-time crew rescheduling process is the fact that the duration of the disruption is usually not known at the start of the disruption, when the initial rescheduling of the duties has to be carried out. A common approach here is to make an educated guess of the duration of the disruption, e.g. based on experiences with similar disruptions in the past. If later on it turns out that the duration of the disruption is different from the initially assumed duration, then this is considered as a second disruption. At that point in time, another iteration of timetable, rolling stock and crew rescheduling will have to be carried out.

Altogether, assuming a certain duration of the disruption, the timetable that will be operated can be determined based on the involved incident scenario. From this timetable and the rescheduled rolling stock circulation, the crew tasks to be covered can be determined.

Now the real-time crew rescheduling problem can be described as follows. As in (11.1), (11.2), (11.3), and (11.4), let T be the set of crew tasks to be covered. Furthermore, let D be the set of original duties at the moment of rescheduling. This set may be equal to the set of originally planned duties, but it may also be different from that set due to earlier disruptions on the same day.

For each original duty d ∈ D, let D d be the set of feasible completions of duty d. Then, for each original duty d and for each feasible completion d′ ∈ D d , let X d′ d be a binary decision variable, indicating whether or not feasible completion d′ ∈ D d is used to complete original duty d ∈ D. Furthermore, for each task t ∈ T, let Y t be a binary decision variable indicating whether or not task t is cancelled. Then the real-time crew rescheduling problem can be described as follows:

$$\displaystyle\begin{array}{rcl} & \min \sum _{d\in D}\sum _{d'\in D_{d}}c_{d'}^{d}X_{d'}^{d} +\sum _{t\in T}\kappa _{t}Y _{t}& \\ & \text{subject to} &{}\end{array}$$
(11.7)
$$\displaystyle\begin{array}{rcl} & \sum _{d\in D}\sum _{d'\in D_{d}:\ t\in d'}X_{d'}^{d} + Y _{t} \geq 1\qquad \text{ for all }t \in T&{}\end{array}$$
(11.8)
$$\displaystyle\begin{array}{rcl} & \sum _{d'\in D_{d}}X_{d'}^{d} = 1\qquad \text{ for all }d \in D&{}\end{array}$$
(11.9)
$$\displaystyle\begin{array}{rcl} & X_{d'}^{d} \in \{ 0,1\}\qquad \text{ for all }d \in D;\ d' \in D_{d}&{}\end{array}$$
(11.10)
$$\displaystyle\begin{array}{rcl} & Y _{t} \in \{ 0,1\}\qquad \text{ for all }t \in T&{}\end{array}$$

The objective function (11.7) does not only focus on minimizing the total costs of the completions of the duties, but also the costs of canceling tasks. Here κ t represents the costs of canceling task t ∈ T. These canceling costs are very high and dominate the other cost components, since canceled tasks must be avoided as much as possible. Constraints (11.8) specify that each task t ∈ T is either covered by at least one completion of a duty, or is canceled. Constraints (11.9) require that for each original duty d ∈ D exactly one completion is selected.

Note that each original duty has the trivial completion consisting of taking a taxi back to the home depot. However, in that case no additional tasks are covered by the completion. If such trivial completions are selected for many original duties, then many trains will be cancelled due to absence of the required crew. Note that in the real-time crew rescheduling process it is hard to deal with constraints at the depot level, such as constraints (11.3).

11.6.6 Real-Time Crew Rescheduling: Solution Technique

In the real-time crew rescheduling process, short computation times are essential. If one needs a solution within minutes, but has to wait for it for hours, then this solution is useless.

In order to deal with this time constraint and with the other details of the disruption management process [12], developed a solution method to be used for real-time disruption management. Their algorithm is based on column generation techniques combined with Lagrangian heuristics. In order to handle the very large number of duties in practical instances, they first define a core problem with a limited number of duties to be rescheduled. The core problem may exist of only the duties that must be rescheduled.

If some tasks remain uncovered in the solution of the core problem, they perform a neighborhood search to improve the solution by defining a new core problem for each uncovered task. This new core problem is typically small such that a large part of the solution of the previous step is fixed. Computational experiments with real-life instances show that this method is capable of producing good solutions within a couple of minutes of computation time, in particular in case of a relatively large disruption.

As mentioned before, a complicating issue in the real-time crew rescheduling process is the fact that the duration of a disruption is usually not known at the start of the disruption. As a consequence, at the start of the disruption it is uncertain for a number of tasks whether they have to be carried out or not. In order to deal with this uncertainty [13], developed a method that is to some extent robust against the duration of the disruption. They consider a minimum and a maximum duration of the disruption. Furthermore, in their rescheduling model they focus on rescheduling the duties for the minimum duration of the disruption, but in such a way that, also in the case that the disruption lasts longer, the duties can be modified easily to cope with this. They call this approach quasi-robust, since the rescheduled duties are not feasible independently of the duration of the disruption, but the duties can be made feasible relatively easily under all possible durations of the disruption.

Abbink et al. [3] also developed a solver for supporting the real-time crew rescheduling process based on multi-agent techniques. Here crew members are represented by virtual agents. If, due to a disruption, some agents cannot carry out certain tasks within their duties, then these agents may ask their virtual colleagues to support them by taking over some of these tasks. A virtual colleague may be able to take over these tasks directly or indirectly. The latter means that he may be able to take over these tasks, but only if someone else takes over some of his own tasks. In this way a recursive negotiation process between the agents is carried out, which usually leads to a solution in the end.

Although this approach performed especially well in disturbed situations involving not too many duties and relatively small delays, it performed on average worse than the set covering based approach developed by Potthoff et al. [12]. However, recently this agent-based approach method was enhanced into a local search heuristic which can be used either as a mini-solver in itself or as a supporting tool in the neighborhood search that is part of the set covering based approach of [12].

11.7 Planning Support System CREWS

The crew scheduling process within NS was carried out traditionally by many planners in a manual way, to some extent supported by relatively simple information systems that mainly provided administrative functions. However, within NS it was recognized already in the early 1990s that crew scheduling is one of the most complex planning processes of a railway operator. Therefore, it was decided that automated planning support , also providing duty generating functions, was needed. This was the start of a long research and development process.

11.7.1 CREWS: The First Phase

At that time NS chose for the CREWS system developed by Siscog in Portugal. This system provided an extensive and user friendly system interface that was appreciated by the planners. The algorithmic support was provided by an algorithm based on the A ∗-algorithm, see Morgado and Martins [11]. Unfortunately, it turned out that this algorithm was not sufficiently powerful for finding solutions that were satisfactory for the planners. In particular, due to the structure of the A ∗-algorithm, it could take into account the constraints at the duty level, but it could hardly deal with the constraints at the depot level.

Therefore the algorithmic part of the CREWS system was enhanced by combining it with the system TURNI developed by Double-Click in Italy, see Kroon and Fischetti [9]. TURNI was complementary to CREWS in the sense that it consisted of a powerful algorithm, based on dynamic column generation, and a very simple user-interface. This combination of CREWS and TURNI was used satisfactorily for a couple of years in the early 2000s.

Amongst others it was used to analyze a large number of different constraint sets to be used in the crew scheduling process, in the end leading to the “Sharing-Sweet-and-Sour” rules, see Abbink et al. [2]. Since this combination of CREWS and TURNI was able to deal with these complex rules, which are really hard to deal with manually, it was also appreciated by the planners. The combination of CREWS and TURNI was used for generating the generic crew duties, as described in Sect. 11.4.1.

11.7.2 CREWS: Stand-Alone

A next step in the development was the implementation into CREWS of a dedicated model and solution technique for supporting the crew rescheduling process for calendar days as described in Sect. 11.4.3. This model is very similar to the model (11.7), (11.8), (11.9), and (11.10), since this process aims at rescheduling a set of existing duties, instead of on scheduling the duties from scratch. However, also constraints similar to (11.3) must be taken into account to deal with constraints at the depot level. Moreover, this process is still a planning process. Therefore solution quality is more important than computation time. The applied solution technique is very similar to the one described in Sect. 11.6.4, see Huisman [8].

In a next step, the solution technique provided by TURNI was replaced by an algorithm similar to TURNI’s, see Abbink et al. [4]. As a consequence, CREWS became powerful enough to operate on its own, and thus TURNI became redundant.

One of the main advantages of the application of CREWS in the planning process was that it allowed to carry out “what-if” analyses, by changing the parameters of the system. As a consequence, it became possible to study the trade-off between different objectives, such as efficiency and robustness. The latter is usually impossible in a manual planning process, where one is usually satisfied already after having found one feasible solution. Additional advantages of the use of the algorithmic support provided by CREWS were a more efficient planning process as well as a reduction of the throughput time of the planning process. For more details on these advantages, see Kroon et al. [10] and Abbink [1].

11.7.3 CREWS: Real-Time Dispatcher

The next step in the extension of the CREWS system aimed at providing support for the real-time crew rescheduling process. To that end [12], developed the rescheduling algorithm described in Sect. 11.6.6. This algorithm was implemented in the real-time dispatching module of CREWS, also called CREWS-RTD.

This system is based on the assumption that the real-time crew rescheduling process is carried out in a centralized way by a single solver. At the moment that the solver is started, the status quo of the duties is frozen: the duties cannot be modified manually anymore, but only by the solver. Once a feasible and satisfying solution has been obtained, it is checked against the duties in the real-world, and communicated to the relevant stake-holders.

CREWS-RTD was first used in a rescheduling process that was set up in parallel to the manual real-time crew rescheduling process. Currently this system is used regularly in disrupted situations due to delayed infrastructure maintenance or incidents lasting several days. However, implementing and applying algorithmic support in a real-time rescheduling process turns out to be even more complex than applying such support in a planning process. Therefore, some further development and implementation steps will be needed to make the use of CREWS-RTD in the real-time rescheduling process common practice. These will be described in the next section.

11.8 Further Developments

In this chapter we described the status quo in the area of railway crew management in the Netherlands. The operational crew planning process is currently to a large extent and satisfactorily supported by the crew scheduling tool CREWS. Nevertheless, there are still several developments in the crew management area that may lead to further improvements.

In particular, the implementation of the real-time crew dispatching system CREWS-RTD is not yet complete. The system has been used many times in disrupted situations, but its application in real-time rescheduling situations is certainly not yet common practice. To improve this, it may first be useful to extend the system with a tool that validates the duties in the system against what happens in reality, so that, once the solver is used, it starts with a correct initial situation.

Furthermore, the disruption management process is still to be organized in a more effective way. For example, a more centralized approach of the disruption management process would be more effective than the current decentralized approach. Also the application of objective rules describing which rescheduled duties are feasible or not will be helpful in speeding up the disruption management processes. This will enable silent digital communication between dispatchers and crew members, and eliminate time-consuming negotiations.

Another improvement would be to change the crew rescheduling rules in the disruption management process so that the crew rescheduling process becomes less dependent on the rolling stock rescheduling process, and can hence be carried out in parallel. This may save a lot of time in this time-critical process. A lower dependence can be achieved, e.g. by stating that in case of disruptions one conductor per train is sufficient.

Furthermore, there used to be not much flexibility in the crew scheduling and rostering process. In principle all duties per crew type are scheduled based on the same rules: one size fits all. For crew members it is possible to have a part-time job, but then part-time refers to a limited weekly number of full size duties. However, times are changing, and in order to remain attractive as an employer, NS may have to introduce more flexibility in the duties. For example, a category of shorter duties may be especially attractive to certain categories of employees. Note that shorter duties may also be attractive for NS. Indeed, shorter duties enable a more efficient covering of the workload during peak hours. Introducing such part-time duties will have a significant impact on the scheduling and rostering process. Recently some first steps into the direction of more flexibility in the rosters have been made.

Other developments involving the crews, in particular the drivers, are the application of driver advisory systems and energy efficiency. A driver advisory system supports the driver in his activities. The current driver advisory system of NS (called RouteLint) just informs the driver about his environment: what is the position, speed, and delay of the own train, and which trains are present in the direct neighborhood of his own train. The next generation driver advisory system will support the driver actively with speed advices: that is, where to accelerate to which speed and with which acceleration, and where to reduce the speed again? Important criteria for driver advisory systems are punctuality and energy efficiency.

At this moment (2015), automatic train operation (ATO) does not exist yet for heavy rail systems. However, several metro and light rail systems are operated already by ATO. ATO is a challenging topic that receives a lot of research attention nowadays. Although there are still many practical issues to be solved, it may not be impossible that in the far future also trains in heavy rail systems will be operated by ATO. This will simplify the railway crew management process to a process focused on the conductors. Anyway, whether ATO is applied or not, railway crew management will be a challenging topic, both from a practical and from a scientific point of view.