Applying Constraint Programming and Integer Programming to Solve the Crew Scheduling Problem for Railroad Systems: Model Formulation and a Case Study

Abstract

Crew scheduling is one of the crucial processes in railroad operation planning. Based on current regulations and working and break time requirements, as well as the operational rules, this process aims to find a duty arrangement with minimal cost that covers all trips. Most past studies considered this subject for railroad systems as an optimization problem and solved it with mathematical programming-based methods or heuristic algorithms, despite numerous logical constraints embedded in this problem. Few studies have applied constraint programming (CP) approaches to tackle the railroad crew scheduling problem. This paper proposes a hybrid approach to solve the problem with a CP model for duty generation, and an integer programming model for duty optimization. These models have been applied to the Kaohsiung depot of Taiwan Railways Administration, the largest railroad operator in Taiwan. The encouraging results show that the proposed approach is more efficient than the manual process and can achieve 30% savings of driver cost. Moreover, the approach is robust and provides flexibility to easily accommodate related operational concerns such as minimizing the number of overnight duties. Thus, this hybrid two-phase approach seems to have the potential for applications to the railroad crew scheduling problems outside Taiwan.

Keywords

rail railroad operating technologies scheduling

Crew management is an important issue for public transportation systems. It is concerned with building the schedules and rosters of crews needed to cover a planned timetable while satisfying operational and regulation rules. In practice, this complex and challenging problem is decomposed into two subjects: crew scheduling and crew rostering ( 1 ). Crew scheduling aims to find a set of duties (or called “pairings”) with a minimal cost to cover all trips (or called “tasks or legs”) defined by a given timetable without violating any scheduling rules. At this level, the duties are not assigned to individual crews. Crew rostering then assigns the duties resulting from crew scheduling to construct a roster that spans a given period of time according to rostering rules. Crew scheduling thus plays a critical role in assisting a transportation agency or company in minimizing its labor costs ( 2 ).

Crew scheduling is a well-known problem in operations research (OR) and has been applied to different transportation fields including airlines, bus transit, and the railroad industry ( 1 , 3 , 4 ). This paper addresses the crew scheduling problem for railroad systems. Railroad crew scheduling has been discussed in the literature since the 1990s ( 1 , 5 ). Most current solution approaches rely on column generation with set covering problem (SCP) or set partitioning problem (SPP) formulations (6 –9). The solution procedure comprises duty generation and duty optimization. For duty generation, it starts from an initial setup and subsequently generates new duties to get a set of feasible (or partially feasible) duties—that is, columns—and to set up the master problem in SCP or SPP form. For duty optimization, it implements a dynamic column generation algorithm to search the optimal combination of duties. The algorithm repeats itself to solve the restricted master problem with linear programming relaxation, check if the dual values yield negative reduced costs, generate new columns, add them to the restricted master problem, and then resolve it for improvement until the optimum is found.

For real-world applications, it may be found that regulations and operational rules are too complicated to be fully covered in the duty generation phase for solving the problem. In such a case, it can be helpful to properly treat some rules as additional constraints and add them to the master problem in the duty optimization phase ( 8 , 9 ). Based on this modified column-generation procedure and a variable fixing technique, crew scheduling software and decision support tools have been developed and implemented at DB Schenker in Germany ( 8 ).

Other than column generation, network flow-based approaches are applied to solve the railroad crew scheduling problem as well. The problem is formulated as a minimum-cost flow problem with a space-time network, which is constructed in such a way that all regulations and rules are enforced. This formulated integer programming (IP) problem is then solved with decomposition and relaxation techniques. This approach has been applied to solve the crew scheduling problem in the context of North American railroads with encouraging results ( 10 , 11 ). A similar approach has been applied to the Turkish State Railways ( 12 ). Moreover, because of the NP-hard property of the problem, heuristics and meta-heuristics are also adopted in the applications to some light rail and mass rapid transit (MRT) systems. For example, tabu search is applied to solve the problem for the Lisbon Underground as well as the Singapore MRT, and also is the evolutionary algorithm for the Santiago Metro (13 –15).

As described above, current studies on the crew scheduling problem for railroad systems mainly consider the problem solely as an optimization problem and solve it with mathematical programming (MP)-based methods or heuristic algorithms. Instead of these conventional approaches, this paper proposes a hybrid approach using both constraint programming (CP) and IP to solve the problem. The roots of CP can be traced back to the work in the field of artificial intelligence on solving constraint satisfaction problems (CSPs) in the 1970s ( 16 ). In fact, the duty generation part of the problem is a CSP itself, and can be tackled by CP more appropriately than by MP. The underlying theory of CP and applications of CSP are discussed by Apt and Brailsford et al., respectively ( 17 , 18 ). Although CP is different from MP, it provides a complementary technology to MP for solving many combinatorial problems including the crew scheduling problem ( 19 ). Schemes of how to incorporate OR to CP are discussed by Hooker ( 20 ).

To the best of the authors’ knowledge, the hybrid CP/IP approach has not been applied to the railroad crew scheduling problem for real-world applications. Nevertheless, this hybrid approach has been proved to be successful in the applications in some related fields, for example, bus driver scheduling, MRT crew scheduling, and maintenance crew scheduling (21 –23). Therefore, this paper reports the first application of using CP and IP to solve the railroad crew scheduling problem with a case from the Kaohsiung depot of the Taiwan Railways Administration (TRA). Although passenger trains are taken for the case study, the proposed approach is also applicable to the crew scheduling problems for scheduled freight-train services.

The remainder of this paper is organized as follows. First, the crew scheduling problem for railroad systems is defined. Then, a hybrid approach with a CP model is proposed for duty generation, and an IP model is proposed for duty optimization to tackle the problem. The formulations of the two models are described in detail. A real crew scheduling problem of TRA Kaohsiung Depot is then solved by the proposed models to test their efficiency and effectiveness. Finally, conclusions and recommendations for future studies are presented.

Problem Definition and Solution Framework

Given a timetable, railroad crew scheduling generates a minimum set of duties to cover all trips while satisfying all restrictions imposed by governmental regulation and company policies. In general, a train journey derived from a published timetable can be divided into a sequence of trips. Each scheduled trip is characterized by a train, a departure time, an arrival time, an origin station, and a destination station. These origin and destination stations are called relief points (RPs), where train drivers could hand over duties, rest, and even stay overnight. Train drivers check in and check out their duties at the same home depot (HD), which is also one of the RPs. Moreover, “deadhead” trips are those inevitable trips resulting from regulatory rules in which train drivers are transported as passengers to another RP station. The sequence of activities to be carried out by one train driver is called a duty, and it may last to the next day. Figure 1 depicts an example of a duty performed from 08:00 to 17:00 which starts and ends at the HD. It consists of three trips, three breaks, and one deadhead trip. As shown in the figure, the changeover between two adjacent trips is required to be at a same RP. For each trip in the duty, there are some pre-trip and post-trip works for preparing and facilitating the associated trips, which are called auxiliary works.

Figure 1.

An example of a duty performed from 08:00 to 17:00 which starts and ends at the home depot (HD).

The objective of railroad crew scheduling is to minimize the overall driver costs which are typically quantified by the number of train drivers. Theoretically, if railroad operators could assign a train driver to each trip, it would be the simplest way to arrange duties without any violation of regulations. However, the human resource is precious and limited. Thus, operators must determine the optimal arrangement of duties to save labor costs.

This paper proposes a hybrid CP/IP approach for solving the railroad crew scheduling problem. Figure 2 presents the solution framework, which consists of two phases: duty generation and duty optimization. In the first phase, the problem of identifying feasible duties that satisfy all the regulations for scheduling is actually a CSP rather than an optimization problem. Thus, based on the input data, a CP model is formulated to solve the CSP for generating all the feasible duties. In the second phase, the duty optimization problem is formulated as a SPP to determine the minimal number of duties that cover all scheduled trips. A successful application of this solution framework to the TRA is described next.

Figure 2.

A hybrid constraint programming/integer programming (CP/IP) solution framework for railroad crew scheduling problem.

Case Background and Operational Requirements

TRA is the largest railroad operator in Taiwan. Its network encircles Taiwan and is approximately 1,065 km in length. The average daily ridership was over 630,000 passenger trips in 2020 ( 24 ). The Rolling Stock Department of TRA is responsible for the arrangement of driver duties for every depot depending on the operational and regulatory requirements. Because of the geographic environment of Taiwan and the service characteristic of TRA, a long-distance train journey is divided into several segments according to the locations of associated crew-base HDs. Each segment is viewed as a unique trip and assigned to a proper depot for scheduling. Based on the current practices of TRA, the crew schedule is managed on a depot-by-depot basis such that each train driver is assigned to a specific HD. The crew schedules for all depots must comply with the common regulations set by the TRA. For example, there is a restriction on the maximum length of continuous driving time (CDT) as well as the maximum length of a duty for safety reasons. In addition, each HD may have its specific scheduling rules to meet its own needs because of different classes of trains dispatched. In some situations, a train driver may need to stay overnight at an RP for performing some next-day trips before returning to the HD. Consequently, a duty scheduled on a specific day (late at night) may cover some trips on the next day (in early morning). This cross-day coverage makes the railroad crew scheduling problem more complicated than that confronted in bus transit and MRT systems.

This case study addresses the crew scheduling problem for the Kaohsiung depot, the major depot in southern Taiwan. Figure 3 shows the service region covered by the Kaohsiung depot in TRA’s network. It covers 319 km in length with 71 stations, including nine RP stations. The total driving time and mileages for all trips are 10,539 min and 11,313 km respectively per day.

Figure 3.

Service region of the Kaohsiung depot in Taiwan Railways Administration (TRA)’s network.

Figure 4 illustrates the traffic load in the number of simultaneous trips—that is, the number of train drivers—required for a daily operation at the Kaohsiung depot. The requirements considered in the TRA-Kaohsiung crew scheduling case problem are summarized in Table 1.

Figure 4.

The trip load for a daily operation at Kaohsiung depot of Taiwan Railways Administration (TRA).

Table 1.

Requirements Considered in the Taiwan Railways Administration(TRA) Kaohsiung Case Problem

Area	Regulatory and operational requirements
Work time	• Maximum length of a duty
	• Maximum total working time —the total working time includes the time for driving work and auxiliary work during a duty
	• Additional limit for the total working time when the rest for a train driver is insufficient
Driving time	• Maximum continuous driving time (CDT)—a train driver will be required to take a break when CDT has reached a certain limit
Driving time	• Additional limit for CDT when involving late-night trips
Break time	• Acceptable duration of rest for a train driver according to different circumstances
Location	• Train driver takes a break only at a relief point (RP)
	• The changeover of two trips in a duty must be at a same RP
	• A train driver must start and end their duty at the home depot (HD)
Other	• Acceptable time gap between two adjacent trips according to different circumstances
Other	• Maximum continuous driving mileage—a train driver will be required to take a break when the continuous driving mileage has reached a certain limit

Formulation of the CP Model for Duty Generation

First, the input data and parameters used for the CP modeling in the case study are introduced. The notations associated are listed in Table 2. Most of the input data for the proposed CP model is related to trips. $T$ represents the set of all trips to be scheduled, and $T = {0, 1, \dots, N}$ , where 0 represents a dummy trip. For such a dummy trip, that is, t = 0, null values are set to its train identification number (ID), setup time, driving mileage, and origin and destination stations; also, a big number (9,999) is set to its departure and arrival times to facilitate the CP formulation.

Table 2.

Notations of Input Data Sets and Parameters in the Constraint Programming (CP) Model

Set	Description
$T$	The set of all trips, $T = {0, 1, \dots, N}$
Parameter
$m$	Maximum number of trips that can be included in a duty
$N$	Total number of trips derived from a given timetable
$Or g_{t}$	Origin relief point (RP) station of trip $t$ , $\forall t \in T$
$De s_{t}$	Destination RP station of trip $t$ , $\forall t \in T$
$Base$	Home depot for check in and check out, also serves as an RP
$Dep t_{t}$	Departure time of trip $t$ , $\forall t \in T$
$Ar r_{t}$	Arrival time of trip $t$ , $\forall t \in T$
$PreTri p_{t}$	Preparation time before trip $t$ , $\forall t \in T$
$PostTri p_{t}$	Preparation time after trip $t$ , $\forall t \in T$
$TrainI D_{t}$	Train ID of trip $t$ , $\forall t \in T$
$LateNightTri p_{t}$	A Kronecker delta value indicates whether the driving time of trip $t$ during the period from 22:00 and 06:00 the next day is greater than or equal to 2 h, $\forall t \in T$
$TripMil e_{t}$	Driving mileage of trip $t$ , $\forall t \in T$
$TripTim e_{t}$	Driving time of trip $t$ , $\forall t \in T$
$minRT$	Minimal rest time
$maxRT$	Maximal rest time
$maxCDM$	Maximal continuous driving mileage
$maxCDT$	Maximal continuous driving time (CDT)
$maxAWT$	Maximal auxiliary working time
$maxTWT$	Maximal total working time
$maxLength$	Maximal length of duty time

In the first phase of the CP/IP solution approach, a CP model for duty generation is formulated. Each solution obtained from the CP model represents a feasible duty. The definition of decision variables and the associated constraints of the CP model are described in detail as follows.

Representation of Decision Variables

A feasible duty can be defined as a sequence of trips in a general form as Equation 1:

Duty = {x_{1}, x_{2}, \dots, x_{m}}

(1)

where

$x_{i}$ represents the $i^{th}$ trip of the duty;

$\forall i = 1, 2, \dots, m$ ;

and the domain of $x_{i}$ is ${0, 1, \dots, N}$ .

The parameter $m$ represents the maximal number of trips that can be covered in a duty. For those duties which do not actually cover as many as $m$ trips, dummy trips will be assigned. Specifically, for a feasible duty with $n$ ( $n < m$ ) scheduled trips, each of the rest trips will be set to be as a dummy trip with a value of 0, that is, $x_{n + 1}, \dots, x_{m} = 0$ .

There may be a break between two adjacent trips. The variable $brea k_{(i, i + 1)}$ denotes whether the time gap between two adjacent trips (the $i^{th}$ trip and $i + 1^{th}$ trip) is greater than or equal to the minimal rest time and is defined as Equation 2. When the value of the variable $brea k_{(i, i + 1)}$ equals to 1, it implies that there is a break between these two adjacent trips and the driver may take a rest in this break time. Otherwise, these two adjacent trips are consecutive trips without breaks.

brea k_{(i, i + 1)} = {\begin{matrix} 1, & if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \land (x_{i + 1} \neq 0) \\ 0, & otherwise \end{matrix} \forall i = 1, 2, \dots, m - 1

(2)

To trace the duration of the break between two adjacent trips, the variable $breaktim e_{(i, i + 1)}$ is defined as shown in Equation 3, where the time required for preparing the preceding trip and its succeeding trip, that is, $PreTri p_{x_{i + 1}}$ and $PostTri p_{x_{i}}$ , is not included. Note that Equations 2 and 3 apply for $i = 1, 2, \dots, m - 1$ rather than for $i = 1, 2, \dots, m$ because no further breaks can follow the $m^{th}$ trip of a duty.

\begin{matrix} breaktim e_{(i, i + 1)} = {\begin{matrix} \begin{matrix} Dep t_{x_{i + 1}} - Ar r_{x_{i}} - PreTri p_{x_{i + 1}} \\ - PostTri p_{x_{i}} \\ 0 \end{matrix} & \begin{matrix} if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \\ \land (x_{i + 1} \neq 0) \\ otherwise \end{matrix} \end{matrix} \forall i = 1, 2, \dots, m - 1 \end{matrix}

(3)

In railroad crew scheduling, a sequence of consecutive trips without breaks makes a huge influence on driver fatigue. Driver fatigue is one of the most common hazards to railroad safety. Therefore, it is necessary to keep track of CDT and mileage for consecutive trips, which are denoted by the variables $CD T_{i}$ and $CD M_{i}$ , respectively. These cumulative variables are defined in the following Equations 4 to 7. Note that these variables only count for those trips ending with a break, or at the end the $m^{th}$ trip.

CD T_{i} = {\begin{matrix} \sum_{n = 1}^{i} TripTim e_{x_{n}} - \sum_{k = 1}^{i - 1} CD T_{k}, & if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \\ 0, & otherwise \end{matrix} \forall i = 1, 2, \dots, m - 1

(4)

CD T_{m} = \sum_{n = 1}^{m} TripTim e_{x_{n}} - \sum_{k = 1}^{m - 1} CD T_{k}

(5)

CD M_{i} = {\begin{matrix} \sum_{n = 1}^{i} TripMil e_{x_{n}} - \sum_{k = 1}^{i - 1} CD M_{k}, & if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \\ \begin{matrix} 0, \end{matrix} & \begin{matrix} otherwise \end{matrix} \end{matrix} \forall i = 1, 2, \dots, m - 1

(6)

CD M_{m} = \sum_{n = 1}^{m} TripMil e_{x_{n}} - \sum_{k = 1}^{m - 1} CD M_{k}

(7)

Working time is also viewed as a critical performance measure reflecting the efficiency of duty arrangement. The work performed by a driver is composed of driving work and auxiliary work. The auxiliary time $AuxTim e_{(i, i + 1)}$ , as defined in Equation 8, represents the sum of preparation time between two adjacent trips when the time gap between them is greater than or equal to the minimal rest time. On the other hand, when the time gap between them is less than the minimal rest time, auxiliary working time equals to the value of the time gap. The total working time variable $TWT$ , as defined in Equation 9, is the summation of the total time for driving and auxiliary works in the whole duty.

\begin{matrix} AuxTim e_{(i, i + 1)} = {\begin{matrix} PostTri p_{x_{i}} + PreTri p_{x_{i + 1}}, & if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \land (x_{i + 1} \neq 0) \\ PostTri p_{x_{i}}, & if (x_{i + 1} = 0) \\ Dep t_{x_{i + 1}} - Ar r_{x_{i}}, & if (Dep t_{x_{i + 1}} - Ar r_{x_{i}} < minRT) \land (x_{i + 1} \neq 0) \end{matrix} \forall i = 1, 2, \dots, m - 1 \end{matrix}

(8)

TWT = \sum_{n = 1}^{m} TripTim e_{x_{n}} + \sum_{n = 1}^{m - 1} AuxTim e_{(n, n + 1)} + PreTri p_{x_{1}} + PostTri p_{x_{m}}

(9)

Table 3 summarizes the variables used in the proposed CP model. A part of the regulations can be tackled by setting upper bounds in the domain of associated variables. For example, $maxCDT$ is set as the upper bound in the domain of variable $CD T_{i}$ to satisfy the related regulation. Other variables are treated similarly.

Table 3.

Definition of Variables in the Constraint Programming (CP) Model

Variable	Description	Domain
$x_{i}$	the $i^{th}$ trip of a duty, $\forall i = 1, 2, \dots, m$	${0, 1, \dots, N}$
$brea k_{(i, i + 1)}$	Indicator of the break between the $i^{th}$ trip and $i + 1^{th}$ trip, $\forall i = 1, 2, \dots, m - 1$	${0, 1}$
$breaktim e_{(i, i + 1)}$	The time length of the break between the $i^{th}$ trip and $i + 1^{th}$ trip, $\forall i = 1, 2, \dots, m - 1$	${0, 1, \dots, maxRT}$
$CD T_{i}$	The continuous driving time (CDT) at the end of the $i^{th}$ trip, $\forall i = 1, 2, \dots, m$	${0, 1, \dots, maxCDT}$
$CD M_{i}$	The continuous driving mileage (CDM) at the end of the $i^{th}$ trip, $\forall i = 1, 2, \dots, m$	${0, 1, \dots, maxCDM}$
$AuxTim e_{(i, i + 1)}$	The sum of preparation time between the $i^{th}$ trip and $i + 1^{th}$ trip, $\forall i = 1, 2, \dots, m - 1$	${0, 1, \dots, maxAWT}$
$TWT$	The time for driving work and auxiliary work during a duty	${0, 1, \dots, maxTWT}$

Representation of Constraints

Feasible duties must satisfy all the regulatory and operational rules. All these rules are formulated as logical constraints in the CP model as described below.

Equations 10 and 11 are used to ensure the appropriate order of the trips. In general, the time between two adjacent trips is greater than 70 min under the regulation as shown in Equation 10. However, the requirement can be exempted in the case that it is the same train in operation, as shown in Equation 11.

(TrainI D_{x_{i + 1}} \neq TrainI D_{x_{i}}) \land (x_{i + 1} \neq 0) \to Dep t_{x_{i + 1}} \geq Ar r_{x_{i}} + 70 \forall i = 1, 2, \dots, m - 1

(10)

(TrainI D_{x_{i + 1}} = TrainI D_{x_{i}}) \land (x_{i + 1} \neq 0) \to Dep t_{x_{i + 1}} > Ar r_{x_{i}} \forall i = 1, 2, \dots, m - 1

(11)

In a feasible duty, each succeeding trip must start from the same RP station where the preceding trip ended. This location-fit rule is formulated as Equation 12. In addition, drivers must both start and end their duties at the HD, as shown in Equations 13 to 15.

(x_{i + 1} \neq 0) \to (ArrSt n_{x_{i}} = DeptSt n_{x_{i + 1}}) \forall i = 1, 2, \dots, m - 1

(12)

(x_{i} \neq 0) \land (x_{i + 1} = 0) \to (ArrSt n_{x_{i}} = DeptSt n_{x_{1}}) \forall i = 1, 2, \dots, m - 1

(13)

(x_{m} \neq 0) \to (ArrSt n_{x_{m}} = DeptSt n_{x_{1}})

(14)

DeptSt n_{x_{1}} = Base

(15)

Taking overnight stays for train drivers into account, the regulation allows a longer break time for such drivers to have an enough rest. For two adjacent trips with a break, if the arrival time of the preceding trip is between 20:00 and 01:00 the next day, the driver is allowed to perform the succeeding trip at most 10 h after the end of the preceding trip. This rule is as defined by Equation 16. For other cases, the time gap between two adjacent trips is limited to 6 h as described in Equations 17 and 18.

\begin{matrix} (1500 \geq Ar r_{x_{i}} \geq 1200) \land (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \land \\ (x_{i + 1} \neq 0) \to (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \leq 600) \\ \forall i = 1, 2, \dots, m - 1 \end{matrix}

(16)

\begin{matrix} (1200 \geq Ar r_{x_{i}} \geq 60) \land (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \land \\ (x_{i + 1} \neq 0) \to (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \leq 360) \\ \forall i = 1, 2, \dots, m - 1 \end{matrix}

(17)

\begin{matrix} (1200 + 1440 \geq Ar r_{x_{i}} \geq 60 + 1440) \land \\ (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \geq minRT) \land (x_{i + 1} \neq 0) \\ \to (Dep t_{x_{i + 1}} - Ar r_{x_{i}} \leq 360) \\ \forall i = 1, 2, \dots, m - 1 \end{matrix}

(18)

In this study, the upper bound of CDT for train drivers is 6 h. However, for late-night trips, the TRA has a more restricted limit, that is, 5 h, for safety considerations. A late-night trip is defined as a trip of which the driving time during the period from 22:00 to 06:00 the next day is longer than or equal to 2 h. For such late-night trips, there is a specific regulation to restrict CDT to 5 h for safety reasons. The illustration of the regulation of CDT related to late-night trips is shown in Figure 5. The duty as show in Figure 5a covers no late-night trips, so its CDT is limited to 6 h. On the other hand, the two duties as shown in Figure 5, b and c, cover two and one late-night trips, respectively, so that, for both of them, CDT is restricted to at most 5 h. For the case shown in Figure 5b, where the continuous driving breaks at a late-night trip, its CDT restriction is defined in Equation 19. On the other hand, for the case shown in Figure 5c, where the last one of the consecutive trips is not a late-night trip, CDT is defined in Equation 20.

Figure 5.

Illustration of three duties related to late-night trips.

(LateNightTri p_{x_{i}} = 1) \to (CD T_{i} \leq 300) \forall i = 1, 2, \dots, m

(19)

\begin{matrix} (LateNightTri p_{x_{i}} = 1) \land (CD T_{i} = 0) \land (CD T_{i + k} > 0) \to \\ (CD T_{i + k} \leq 300) \\ \forall i = 1, 2, \dots, m and k = 1, 2, \dots, m - i \end{matrix}

(20)

In general, the total working time is limited to at most 14 h, which is defined as the upper-bound value of its domain. However, when the duration of any break occurring in a duty does not exceed 4 h, it must be limited within 12 h, as defined in Equation 21. Moreover, the length of duty time, that is, the sum of total working time and the total break time, has a maximal value of $maxLength$ , which is 22.5 h as described later. This rule is defined in Equation 22.

\sum_{i = 1}^{m} ((breaktim e_{i} \leq 240) = m) \to (TWT \leq 720)

(21)

TWT + \sum_{n = 1}^{m} breaktim e_{n} \leq maxLength

(22)

Formulation of the SPP Model for Duty Optimization

Given all the feasible duties generated from the CP model in the first phase, the next phase of the solution framework is to determine the minimum number of duties that satisfy all TRA scheduling rules. This duty optimization problem is formulated as a SPP in the IP model. The advantage of the SPP formulation is that, unlike the SCP formulation, it will not yield optimal duties with repeated trips.

The input data for the SPP model include the following: the set of trips, T , which is as given in the CP model; the set of all feasible duties, D , obtained from the CP model; the cost of duty $d$ , $C_{d}$ ; and the Kronecker delta of $A_{td}$ which indicates whether trip $t$ is covered by duty $d$ . The SPP model for duty optimization is defined as follows.

Min

\sum_{d \in D} C_{d} y_{d}

(23)

Subject to

\sum_{d \in D} A_{td} y_{d} = 1 \forall t \in T

(24)

y_{d} \in {0, 1} \forall d \in D

(25)

As shown in Equation 23, the model minimizes the total cost of duties. The cost for each duty (i.e., $C_{d}$ ) in Equation 23 may include the penalty cost for overnight stays. Equation 24 requires that each trip $t$ be covered only once by one of the feasible duties selected. Equation 25 defines the binary variable $y_{d}$ in the model.

Case Study

The current study employs C# programing language compiled on the .Net framework. A desktop PC (Intel Core i7-6700K CPU, 3.40 GHz with 16GB RAM) is used to execute the proposed solution approach in a Windows 10 environment. An open-source solver, Google OR-Tools, is utilized to formulate the proposed CP and SPP models for solving the crew scheduling problem confronted by the Kaohsiung depot of TRA ( 25 ).

As mentioned earlier in the case background, it is inevitable to assign cross-day duties with overnight stays to some train drivers. It is because there are not enough midnight trips to take all the train drivers back to the HD in time without violating work-time constraints. This situation implies that a daily schedule at the TRA Kaohsiung depot would include both single-day duties, which start and end on a same day, and cross-day duties, which start on one day but end on the next day. To incorporate this cross-day coverage into a single-day crew schedule problem, this study has developed a novel scheme to carry out the proposed CP/IP solution methods. This scheme proceeds as the following: 1) to use an extended input with next-day trips for duty generation in the CP model; 2) to modify the cross-day duties generated from the CP model; and 3) to apply the modified duties to the SPP model for duty optimization in day one.

Suppose that the scheduling problem for a particular day, say day one, is being dealt with. First, an extended (cross-day) input that includes all day-one trips and some day-two trips is used for duty generation. All these trips are derived from the timetable published by TRA. The time distribution of these trips over time is illustrated in Figure 6, where a black bar and a gray bar represent a day-one trip and a day-two trip, respectively. Note that it is not necessary to consider all day-two trips for the duty generation in day one. Instead, it is only necessary to consider those day-two trips within a time span, which is called “cross-day range.” In the base case, as shown in the figure, the cross-day range is 21 h, which extends from 24:00 to 45:00, that is, from the end of day one to the 21:00 of day two. It is because the last trip scheduled on day one is at 23:00, the pre-trip preparation requires 30 min so that the last trip actually starts from 22:30. Moreover, the TRA rules demands that the maximum length of a duty be limited to 22.5 h. Accordingly, the maximal time range of day-two trips that can be covered by day-one duties is 21 h.

Figure 6.

Time distribution of cross-day input with day-one and day-two trips.

As explained above, the extended cross-day input of the case study includes 130 day-one trips and 98 day-two trips. The related parameter values used in the CP model are summarized in Table 4. The computation time and the resulting number of feasible duties of the CP model for duty generation are summarized in the left side of Table 5.

Table 4.

Parameter Values in the Taiwan Railways Administration(TRA) Kaohsiung Case Study

Parameter	Value
$m$	8
$N$	228
$minRT$	100 min
$maxRT$	10 h
$maxCDM$	250 km
$maxCDT$	6 h
$maxAWT$	100 min
$maxTWT$	14 h
$maxLength$	22.5 h

Table 5.

Results of the Base Case

The first phase		The second phase
Elapsed time for duty generation	# Feasible duties	Elapsed time for duty optimization	# Optimal duties
2,888 s	349,540	46 s	26

As mentioned earlier, the second key step of the implementation scheme is the modification of the feasible duties generated from the CP model. Specifically, those repeated trips at the same time on both days are relabelled with a same trip identification number for all generated feasible duties. The final step is to apply this modified set of feasible duties to the SPP model for duty optimization in day one, in which the same unity cost (i.e., $C_{d}$ = 1) for all feasible duties is assumed. In other words, the aim is to minimize the number of drivers in the base case.

Table 5 summarizes the results of the base case application. In TRA, the crew schedule is generated manually by an experienced employee. The manual results provided by the Kaohsiung depot of TRA required 37 duties for a daily operation. This approach generated a solution of 26 duties, which represents approximately 30% savings in labor costs in relation to the number of drivers. It is found that the optimal solution obtained from the proposed model has a higher average duty length and a smaller standard deviation when compared with the manual solution. In the base case, the average duty length increases from around 12 h (in the manual result) to about 17.5 h (in the optimal solution), while the standard deviation of duty length decreases from 276 min to 217 min. It implies that the optimal duties are arranged more efficiently and evenly without violating scheduling rules.

The computer implementation of this solution is very efficient. The manual process usually takes several weeks, whereas this approach takes only 49 min to get the optimal solution. As railroad crew scheduling is an offline planning process, the computational efficiency of the proposed models should be adequate for real-world applications.

Figure 7 depicts the detailed composition for each of the 26 optimal duties in relation to trips, auxiliary works, breaks, and overnight stays. Specifically, these 26 optimal duties include 7 single-day duties and 19 cross-day duties, of which 13 are with overnight stays.

Figure 7.

Composition of the optimal duties in the base case.

Impact of Overnight-Stay Cost

Extra costs are incurred from the arrangement of overnight stays for train drivers in their cross-day duties. Such costs include not only providing dormitories for drivers, but also the allowances paid for the duties overtime, the extra administration cost, and other risk management cost for overnight stays. To take these costs into account, a weighted cost in the objective function of the SPP model with a penalty cost factor α is adopted. Specifically, the cost of duty $d$ is now considered as $C_{d} (1 + α)$ . The penalty cost means the extra cost incurred, and the factor α is defined as a multiplier of the unit cost of a duty without an overnight stay. Thus, when α = 0, it means that there is no extra cost incurred as in the base case. Similarly, when α = 1, the cost of an overnight-stay duty is twice as much as that of a duty without an overnight stay. Several different values of α are tested to explore the impact of the overnight-stay cost. The results are illustrated in Figure 8.

Figure 8.

Impact of the overnight-stay cost.

As shown in the figure, the number of overnight-stay duties decreases quickly and significantly from 13 to 9 as α goes from 0 to 0.5. For α > 0.5, further increase of the overnight-stay cost seems to have no impact on the resulting number of overnight-stay duties. Meanwhile, the total number of duties required for a daily operation seems insensitive to the overnight-stay cost; it remains the same as 26 for all values of α tested from 0 to 10. Note that, for α ≥ 0.5, the overnight-stay ratio of all train drivers drops from 50% to 35%, that is, from 13/26 to 9/26. This indicates a significant improvement in both the operation cost for the TRA, and the overnight-stay workload assigned to train drivers. A detailed composition of the 26 optimal duties with 9 overnight-stay duties for α = 1 is shown in Figure 9.

Figure 9.

Composition of the optimal duties for α = 1.

Solution Efficiency Enhancement

In railroad crew scheduling, the problem size increases considerably with the increase in the number of trips included, which significantly affects the solution quality and efficiency. As described earlier, in the base case scenario where the cross-day range is 21 h, there are 98 next-day trips on top of 130 same-day trips in the CP model. The idea here is trying to improve the solution efficiency by properly reducing the number of next-day trips. Thus, testing the base-case instance is repeated with different values of the cross-day range between 12 h and 21 h. The results are shown in Table 6.

Table 6.

Sensitivity Analysis for the Cross-Day Range

Range (hour)	# Next-day trips	# Feasible duties	Elapsed time for duty generation (s)	# Optimal duties
21	98	349,540	2,888	26
20	97	346,788	2,720	26
19	87	343,005	2,610	26
18	84	335,191	2,535	26
17	75	309,923	2,285	26
16	71	308,535	2,203	26
15	62	294,558	2,033	26
14	53	273,985	1,949	26
13	49	254,769	1,808	27
12	41	254,489	1,710	27

Note that the elapsed time of the computer implementation for duty generation declines as the cross-day range decreases. Specifically, the CP model implementation took 2,888 s to generate all 349,540 feasible duties when the range is 21 h. As the range decreases to 14 h, it only took 1,949 s to generate all 273,985 feasible duties. The elapsed time reduces significantly from 2,888 s to as low as 1,949 s, while the optimal duties keep the same at 26. The computational efficiency for duty generation is improved by 33%. However, when the cross-day range is less than 14 h, the number of required duties increases to 27. In this case, the cross-day range is too small to generate enough numbers of feasible duties to yield the optimal solution. On the whole, the results imply that railroad operators can enhance the solution efficiency with properly designed input of the CP model without sacrificing the solution quality.

Conclusions

This paper proposes a hybrid CP/IP approach to solve the crew scheduling problem for railroad operators. Existing studies on this topic consider the process as primarily an optimization problem and solve it with heuristic or meta-heuristic methods. Because of the complexity of the problem, they usually involve approximations and adjustments, and even ignoring or relaxing features that are difficult to formulate. This paper seems to be one of the first that applies CP techniques to railroad crew scheduling applications while considering the condition of overnight stays for train drivers.

The hybrid approach was applied to tackle the crew scheduling problem for the Kaohsiung depot of TRA and encouraging results were obtained. As compared with the manual results generated by TRA, the proposed models can significantly reduce the number of the required duties from 37 to 26 for a daily operation, which represents 30% savings in labor costs. Moreover, the issues for reducing overnight duties, as well as enhancing solution quality and efficiency, are also discussed. With the same minimum cost of 26 required duties, the ratio of duties with overnight stays further reduces from 50% to 35% in this study. Besides, the computer elapsed time can be reduced by 33% with properly condensing the solution space for the proposed CP model.

Facing the revision of regulations on crew scheduling regularly, TRA must take lots of effort in duty arrangement to satisfy the operational and contractual requirements. The proposed solution approach can easily deal with any adjustment of requirements with the CP model. The results of this paper demonstrate that the proposed hybrid approach is promising and has the potential for applications to crew scheduling problems of railroad systems in countries other than Taiwan, as well as scheduled freight-train services.

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: G. Chen, J. Jong, A. Han; data collection: G. Chen; analysis and interpretation of results: G. Chen, J. Jong, A. Han; draft manuscript preparation: G. Chen, J. Jong, and A. Han. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

ORCID iDs

Jyh-Cherng Jong

Anthony Fu-Wha Han

References

Caprara

Fischetti

Toth

Vigo

Guida

P. L.

Algorithms for Railway Crew Management. Mathematical Programming, Vol. 79, 1997, pp. 125–141.

Ernst

A. T.

Jiang

Krishnamoorthy

Nott

Sier

An Integrated Optimization Model for Train Crew Management. Annals of Operations Research, Vol. 108, 2001, pp. 211–224.

Barnhart

Cohn

A. M.

Johnson

E. L.

Klabjan

Nemhauser

G. L.

Vance

P. H.

Airline Crew Scheduling. Handbook of Transportation Science, Vol. 56, 2003, pp. 517–560.

Wren

Rousseau

J. M.

Bus Driver Scheduling – An Overview. In Computer-Aided Transit Scheduling ( Daduna

J. R.

Branco

Paixao

J. M. P.

, eds.), Lecture Notes in Economics and Mathematical Systems. Springer, Berlin, Vol. 430, 1995, pp. 173–187.

Ernst

A. T.

Krishnamoorthy

Dowling

Train Crew Rostering using Simulated Annealing. Proc., International Conference on Optimization Techniques and Applications, Perth, Western Australia, 1998.

Freling

Lentink

R. M.

Odijk

M. A.

Scheduling Train Crews: A Case Study for the Dutch Railways. Computer-Aided Scheduling of Public Transport, Vol. 505, 2001, pp. 153–165.

Janacek

Marton

Koniorczyk

The Column Generation and Train Crew Scheduling. Communications-Scientific letters of the University of Zilina, Vol. 18, 2016, pp. 21–27.

Jutte

Albers

Thonemann

U. W.

Haase

Optimizing Railway Crew Scheduling at DB Schenker. INFORMS Journal on Applied Analytics, Vol. 41, No. 2, 2011, pp. 109–122.

Jutte

Thonemann

U. W.

Divide-and-Price: A Decomposition Algorithm for Solving Large Railway Crew Scheduling Problems. European Journal of Operational Research, Vol. 219, No. 2, 2011, pp. 214–223.

10.

Ahuja

R. K.

Cunha

C. B.

Sahin

Network Models in Railroad Planning and Scheduling. Tutorials in Operations Research, Vol. 1, 2005, pp. 54–101.

11.

Vaidyanathan

Jha

K. C.

Ahuja

R. K.

Multi-Commodity Network Flow Based Approaches for the Railroad Crew Scheduling Problem. IBM Journal of Research and Development, Vol. 51, 2007, pp. 325–344.

12.

Sahin

Yuceoglu

Tactical crew planning in railways. Transportation Research Part E: Logistics and Transportation Review, Vol. 47, No. 6, 2011, pp. 1221–1243.

13.

Cavique

Rego

Themido

Subgraph Ejection Chains and Tabu Search for the Crew Scheduling Problem. Journal of the Operational Research Society, Vol. 50, No. 6, 1999, pp. 608–616.

14.

Chew

K. L.

Pang

Liu

Teo

C. P.

An Optimization Based Approach to the Train Operator Scheduling Problem at Singapore MRT. Annals of Operations Research, Vol. 108, 2001, pp. 111–122.

15.

Elizondo

Parada

Pardenas

Artigues

An Evolutionary and Constructive Approach to a Crew Scheduling Problem in Underground Passenger Transport. Journal of Heuristics, Vol. 16, No. 4, 2010, pp. 575–591.

16.

Lauriere

J. L.

A Langrage and a Program for Stating and Solving Combinatorial Problems. Artificial Intelligence, Vol. 10, No. 1, 1978, pp. 29–127.

17.

Apt

K. R.

Principles of Constraint Programming. Cambridge University Press, Cambridge, 2009.

18.

Brailsford

S. C.

Potts

C. N.

Smith

B. M.

Constraint Satisfaction Problem: Algorithms and Applications. European Journal of Operational Research, Vol. 119, No. 3, 1999, pp. 557–581.

19.

Lustig

I. J.

Puget

J. F.

Program Does Not Equal Program: Constraint Programming and Its Relationship to Mathematical Programming. Interfaces, Vol. 31, No. 6, 2001, pp. 29–53.

20.

Hooker

J. N.

Operations Research Methods in Constraint Programming. Handbook of Constraint Programming, Vol. 2, 2006, pp. 527–570.

21.

Silva

A. D.

Combining Constraint Programming and Linear Programming on an Example of Bus Driver Scheduling. Annals of Operations Research, Vol. 108, 2001, pp. 277–291.

22.

Han

A. F.

E. C.

A Constraint Programming-based Approach to the Crew Scheduling Problem of the Taipei Mass Rapid Transit System. Annals of Operations Research, Vol. 223, No. 1, 2014, pp. 173–193.

23.

Pour

S. M.

Drake

J. H.

Ejlertsen

L. S.

Rasmussen

K. M.

Burke

E. K.

A Hybrid Constraint Programming/Mixed Integer Programming Framework for the Preventive Signaling Maintenance Crew Scheduling Problem. European Journal of Operational Research, Vol. 269, No. 1, 2018, pp. 341–352.

24.

Taiwan Railways Administration Website. https://tip.railway.gov.tw/tra-tip-web/tip?lang=EN_US. Accessed July 7, 2020.

25.

Perron

Furnon

Google’s OR-Tools 6.9. http://developers.google.com/optimization. Accessed July 7, 2020.