Public Transp (2010) 2:307–334 DOI 10.1007/s12469-010-0034-5 O R I G I N A L PA P E R

Supporting strategic crew management at passenger railways—model, method and system Ulrich Derigs · Dominik Malcherek · Simon Schäfer

Published online: 7 December 2010 © Springer-Verlag 2010

Abstract This paper reports the results of a joint project with a large railway company in Germany to build a decision support system for analyzing the consequences of timetable changes, modifications of break and working time regulations as well as changes in the cost structure on future crew needs. For that purpose we have developed a mathematical model of the underlying crew scheduling problem that respects all the organizational and technical constraints as well as labor regulations. We have implemented a Branch&Price based optimization system that is used to perform scenario analyses of future crew needs using medium-term timetable drafts as input data. Keywords Railway crew scheduling · Break and working time regulations · Branch and price · Decision support system

1 Introduction The railway planning process starts with the definition of a set of train services based on projected passenger demand. A train service is characterized by its origin station and departure time, its destination station and arrival time, and typically, it has several intermediate stops at stations with associated arrival and departure times. A timetable describes all train services to be performed within a certain time period, a week, for instance. Timetable planning typically starts several years before the timetable U. Derigs () · D. Malcherek · S. Schäfer Department of Information Systems and Operations Research (WINFORS), University of Cologne, Pohligstr. 1, 50969 Köln, Germany e-mail: [email protected] D. Malcherek e-mail: [email protected] S. Schäfer e-mail: [email protected]

308

U. Derigs et al.

goes into operation and it undergoes many changes. Depending on market scenarios, planners can add or drop services, modify the frequencies, times and capacities of train services and so forth. Once in operation, a timetable is normally valid for about six months. After the timetable has been designed, sequences of train services, referred to as rotations, are constructed which must be performed by the same train. Operational timetables may differ over the days of a week and also be dependent on seasonal influences. In strategic planning, medium-term timetable drafts are designed that neglect this variation and specify the services of a so-called standard day. A timetable defines the need for trains (named rolling stock) as well as for the personnel, i.e. the train drivers, conductors and stewards. The planning of train drivers usually constitutes a separate planning problem, while conductors and stewards are planned in combined crews. Unlike train drivers, these crews can generate additional revenue which gives their planning problem an additional economic dimension. Crews typically consist of three to four members: conductors who sell and check tickets and provide information about connections etc., and stewards who are responsible for operating the on board restaurant and are serving beverages, snacks and meals to passengers. Crews are assigned to crew bases which are located at stations where many train services pass. The purpose of crew planning is to assign work schedules to crews so that all train services are covered and labor rules are satisfied. Typically, crew planning is divided into two problems that are solved sequentially. First, in crew scheduling anonymous work schedules are constructed. Here in a complex optimization process appropriate segments from different train services are combined to operational sequences which are called pairings. Then, in crew rostering these pairings are assigned to individual crew members by generating rosters, i.e. individual work schedules. Here, specific employee characteristics are taken into account, such as language qualifications, vacations and experience and the goal is to achieve a balanced workload among all employees. Since the focus of our study is on the strategic level, we are solely concerned with crew scheduling. The goal of crew management is to establish a long-term match between the required and the available capacities of the crew bases (see Huisman et al. 2005). To achieve this, crew bases have to be selected from a set of possible stations and their respective crew needs have to be forecasted several years before a timetable goes into operation. Timetable changes may require the moving, hiring (with appropriate specialized training) or dismissal of staff. This is a consequential and costly process that involves the cooperation with unions and other partners. The time and effort required for changing the number and location of crew bases and the re-/allocation of personnel should not be underestimated. If the available staff does not match the actual need when the timetable goes into operation, crew shortages may occur and/or inefficient pairings have to be implemented. Our research was motivated by the requirements of a railway company for a user friendly and highly responsive tool for analyzing tactical and strategic options for the planning of conductors and stewards on the company’s long-distance network as for instance the optimal allocation and size of crew bases, the specification of different service levels on connections, changing working time conditions for crews etc. Such strategic crew management problems had only been approached before using

Supporting strategic crew management at passenger railways

309

personal and informal spreadsheet models representing the expertise of the respective decision maker, past experience and rules of thumb and thus the consequences of changes in the timetable and changes in contractual working rules could only be estimated with an insufficient degree of precision and granularity. The operational crew scheduling system used by the railway company was too inflexible and its high solution times would not allow to approach ad-hoc scenario analysis and simulation. The objective of our project was to give a proof of concept and show the computational feasibility for a computer-based analytical system using state-of-the-art algorithms and mathematical models covering all the complex measures and constraints which are essential for the operability and evaluation of a schedule. For that purpose we have developed a fully functional decision support system called “on.Track” and tested it on several real timetables for the long-distance network which contains approximately 800 daily train services with stops at roughly 160 stations with crews being stationed at 27 crew bases throughout the railway network. on.Track allows the specification and analysis of scenarios and thus offers the necessary decision support for the planners at this strategic level. While airline crew scheduling problems have been widely studied in Operations Research (OR), see for instance Gopalakrishnan and Johnson (2005) for a recent survey paper, research on railway crew scheduling problems has received attention only recently and relatively few publications exist. For survey articles on OR models and techniques for planning problems in passenger railway transportation, we refer to Assad (1980), Cordeau et al. (1998), and the recent articles by Huisman et al. (2005) and Caprara et al. (2007). Also, there are a few publications reporting specific applications in railway crew scheduling. Caprara et al. (1997) describe models and solution approaches for crew scheduling and crew rostering discussing a realworld application at the Italian railway company Ferrovie dello Stato SpA. Abbink et al. (2005) apply OR models to support the development of a set of scheduling rules for the drivers and conductors at the Dutch railway operator NS Reizigers. Freling et al. (2004) describe models and methods implemented in a decision support system that has been employed to schedule the catering personnel on Thalys trains, the high-speed trains between major cities in Western Europe. Vaidyanathan et al. (2007) present their solution to a crew scheduling problem at a North American cargo railroad. Bengtsson et al. (2007) describe a commercial crew planning system developed by Carmen Systems that is widely used for operational planning. Hartog et al. (2009) describe a method for solving the problem of cyclically ordering a set of duties for a number of crew members, such that several complex constraints are satisfied. Recently, Albers (2009) has developed a method and system for operational scheduling for the cargo train drivers at DB Schenker Rail Deutschland AG. His method is similar to ours, yet, the basic problem shows some significant differences. The structure and quantity of constraints is less complex, and, due to the relatively small number of stations that qualify for driver changes the resulting instance is much smaller. Bunte and Kliewer (2009) discuss models for a related problem in vehicle scheduling where buses have to cover a given set of timetabled trips under practical requirements. In 2006, Netherlands Railways introduced a completely new timetabling approach designed to facilitate the growth of passengers and freight transport on a highly utilized railway network, and to improve the robustness of the timetable in order to reduce the

310

U. Derigs et al.

number of train delays in the operation. In 2008 this work received the prestigious Edelman Award for outstanding practice in OR (see Kroon et al. 2009). In November 2008 Transportation Science, the flagship journal of the Institute for Management Science and Operations Research, published a focused issue on rail transportation (cf. Vol. 42(4), 2008) with articles covering the broad range of problems in this area. These two instances document the rising importance and recognition of OR in this area. From a conceptual point of view, the scheduling of railway crews and of airline crews form very similar problem types. Both are commonly modeled as set covering or partitioning problems and solved with Branch&Price approaches. Thus, algorithmic advancements can be shared in principle. Railways operate a predominantly national transportation system. Therefore, the specific logic of a railway problem is highly dependent on local factors, such as the structure of the railway network as well as specific labor laws and union agreements. Reported research on railway problems thus tends to be rather specialized which makes it in turn more difficult to generalize results to a wider set of problem instances. Generally, railway crew scheduling problems have a higher complexity than the corresponding airline problems, due to the larger size of the instances to be solved as well as the number and type of operational constraints. A dense railway network as it exists in Germany increases the number of possible combinations for pairings dramatically. Additionally, the relatively high number of crew bases contributes to an increase in combinatorial complexity compared to airlines which often operate from a single crew hub only. Cordeau et al. (1998) have attributed the scarce research on railway crew scheduling problems to the large dimension and the high complexity of the problems and a lack of computing capabilities needed to solve models with realistic sizes. The remainder of the paper is organized as follows: In Sect. 2 we introduce all relevant concepts and describe the problem precisely, while in Sect. 3 we develop the mathematical programming model. In Sect. 4, we describe our solution approach for solving the model in detail. Finally, in Sect. 5, we shortly present the main applications of our decision support system and we conclude with some final remarks in Sect. 6.

2 Problem description In this section, we describe the crew scheduling problem and we introduce in detail all concepts which are relevant for designing a mathematical program. Starting point is the timetable for a standard day consisting of the set T of all train services which start on that day. All train services have been cut into small segments, the legs, at stations which qualify for crew changes. Let L be the set of legs of the timetable. The basic planning entities are crew teams, consisting of a head conductor and a number of supportive crew members, typically two to three. Every crew is assigned to a home crew base. Let B be the set of crew bases. We have to design anonymous work schedules referred to as pairings, which denote sequences of activities which have to be fulfilled by the same crew team and which are starting and ending at the same base.

Supporting strategic crew management at passenger railways

311

To be consistent with operational planning, we mimic the modeling approach which has been implemented in the operational system. Especially, we use the same leg segmentation, pairing structure, system of break regulations, and cost structure. Also, we follow the required planning paradigm, i.e., we assume that every day a fixed pattern of pairings is performed sequentially during the validity of the timetable. 2.1 From train services to pairings: legs, activities and connections Every leg l ∈ L is characterized by its origin stop origl and departure time depl , and by its destination stop destl and arrival time arrl . In our planning problem, every train service T ∈ T is represented as a sequence of legs, i.e. T = (l1T , . . . , lnTT ) where destl T = origl T for k = 1, . . . , nT −1 . Note that we measure time on a minute scale, k k+1 i.e. 0 ≤ depl ≤ 1440 and due to the specific duration of train services in the timetable arrl ≤ 2880 for all l ∈ L. In rolling stock scheduling rotations have been constructed which are served sequentially by the same train. Thus, we can associate with every train service T and therefore with every leg l a rotation number rotT and rotl , respectively. Legs have a specific crew need, depending e.g. on the catering service offered and the expected number of passengers. Several team categories with differing crew sizes are predefined and with every leg l we associate its category teaml . Legs can be assigned to pairings in two different roles: When the crew works on a leg l, it performs a service activity sl , and if it uses a leg for repositioning (in which case the crew is off-duty), it performs a deadhead activity dl . Deadhead activities are not assigned to a team category since crews are off-duty here. When we refer to service and deadhead activities in the sequel but do not have to differentiate between the two roles, we use the term leg activity, denote it by al and we set A := {al | l ∈ L}. Figure 1 depicts the orthogonal relationship between train services and pairings. Each pairing begins at a crew base b ∈ B with a leavebase connection from b to the first leg activity of the pairing. This connection contains the preparation of the crew at the base followed by a walk to the platform where the first leg activity starts. Then follows a sequence of service activities and deadhead activities. Each pairing ends with a back2base connection from the last leg activity to the crew base where the pairing started. This connection contains a walk from the platform back to the base and a closing at base activity. Service activities and deadhead activities are always preceded and/or succeeded by several mandatory activities. Before the first leg and after the last leg of a train service, the crew which is servicing this leg has to perform a preparation on train (pont) activity and closing on train (cont) activity, respectively. Their duration depends on the train type, i.e., it takes longer to shut down a train with an on board restaurant than one with a bistro. For service and security reasons, crews have to be present during all train stops. Therefore, before every leg of a train service (except the first leg), the crew servicing the leg performs a mandatory stay on train (sont) activity. When a crew uses two consecutive legs of a train for deadheading, they perform a dh stay on train (dhsont) activity during the train stop.

Fig. 1 Relationship between train services and pairings

312 U. Derigs et al.

Supporting strategic crew management at passenger railways

313

Let pontT and contT be the durations of the pont and the cont activity, respectively, of a train service T . Now we define for all leg activities a ∈ A two attributes which define when a crew ⎧ begins and ends the activity: if a = dl ⎪ ⎨ depl , T , if a = s and l = l T dep − pont l begina := l 1 ⎪ ⎩ arr  , if a = sl and l = ljT , j = 1, and l  = ljT−1 l ⎧ ⎨ arrl , enda := arrl + contT , ⎩ arrl ,

if a = dl if a = sl and l = lnTT otherwise.

Also, let dura = enda − begina be the duration of a leg activity a ∈ A. Note that regulations allow the duration of a pairing to be up to 36 hours and thus a pairing starting with a leg activity on day 1 may end with a leg activity on day 3. To be able to model such pairings spanning over more than one day we conceptually extend the planning period and introduce two copies of the standard day, i.e., for every l1 ∈ L1 := L we introduce two legs l2 and l3 , respectively, with deplk = depl1 + (k − 1) · 1440 arrlk = arrl1 + (k − 1) · 1440 for k = 2, 3 which constitute the sets L2 and L3 , respectively. We extend all definitions and concepts to these sets. Yet, we allow leavebase connections to activities al with l ∈ L1 only, and, for every l ∈ L a pairing must not contain more than one service activity from the associated set {sl1 , sl2 , sl3 } in which case we say that the pairing covers l. Obviously, in any pairing a leg activity al  ∈ A can only follow immediately after a leg activity al ∈ A, i.e., the crew assigned to al can connect to al  , if at least the conditions destl = origl  and dural ,al  := beginal  − endal ≥ 0 are satisfied. Moreover, since all service activities in a pairing must have the same team category, teaml = teaml  must hold if al = sl and al  = sl  . Such pairs of leg activities are called compatible, and we distinguish three types of feasible connections between compatible activities: (1) If rotl = rotl  and dural ,al  ≤ maxDurationNonstop then the crew can perform a nonstop connection between l and l  . (2) If rotl = rotl  and minDurationTransfer ≤ dural ,al  ≤ maxDurationTransfer then the crew can perform a transfer connection between l and l  . (3) Otherwise, if minDurationLayover ≤ dural ,al  ≤ maxDurationLayover, the crew can perform a layover connection between l and l  which means that there is an overnight rest at destl by which the pairing is separated into duties. Here maxDurationNonstop, minDurationTransfer, maxDurationTransfer, minDurationLayover and maxDurationLayover are prespecified parameters which may be subject to change if labor regulations are altered. Transfers can be used for breaks and it is the necessity to allocate the mandatory breaks within these transfers which contributes to the high complexity of the problem. The fractions of the transfer durations which are not used for breaks determine the idle activities. Figure 2 gives an example of a typical pairing.

Fig. 2 Structure of a pairing

314 U. Derigs et al.

Supporting strategic crew management at passenger railways

315

2.2 Feasibility and evaluation of duties and pairings Pairings have to fulfill several feasibility constraints. As already mentioned, only feasible connections are allowed and all service activities in a pairing must be assigned to the same team category. Also, labor regulations allow (at most) one layover per pairing, i.e., a pairing can be separated into at most two duties. Additionally, several constraints with respect to working time have to be fulfilled. Before we describe them, we introduce six time measures which are important for checking the feasibility and for evaluating the cost of a pairing p: 1. The Time Away From Base (TAFBp ) gives the total time a crew is absent from its base, i.e. it is the duration of all activities and connections in p including layovers. 2. the Duty Time (DT d ) states the duration for each duty d separately, 3. the Regulated Working Time (RWT d ) states for each duty the part of the duration that is subject to legal regulations, 4. the Accountable Working Time (AWT d ) states for each duty the part of the duration that accounts for the contractual annual working time of an employee, 5. the Deadheading Time (DHT p ) aggregates the (unproductive) time that a crew spends during pairing p on deadhead activities, and, finally, 6. the Idle Time (IT p ) aggregates all other unproductive working time of p. Activities and connections contribute to these time measures with their duration. Table 1 states the purpose of the time measures and illustrates which activity/connection contributes to which time measures. Now, labor regulations state that for every pairing TAFBp is limited to maxTAFB hours. Also, for each duty in the pairing, DT d and RWT d are limited to maxDT and maxRWT, respectively. As can be seen from the table, non-productive activities such as deadheads and transfer connections are not subject to working time regulations and thus do not count as RWT d . When constructing a pairing the fulfillment of all Table 1 Time measures Activities/connections Service activity sl Deadhead activity dl Leavebase connection (b, al ) Back2base connection (al , b) Nonstop connection (al , sl  ) to service Nonstop connection (sl , dl  ) from service to deadhead Nonstop connection (dl , dl  ) between deadheads Transfer connection (al , al  ) Layover connection (al , al  ) Purpose 1 Depending on break allocations

TAFBp

DTd

RWTd

AWTd

√

√

√

√

√

√

√

√

√

√

√

√

√

√

√

DHTp

ITp

√

n/a since dural ,sl  = 0 √

√

√

√

√

√

√

√

√1

√ √

√ Feasibility checking

Evaluation

√1

316

U. Derigs et al.

constraints mentioned so far is easy to control, since these measures are dynamic and additive in the sense that for a feasible pairing all partial pairings, i.e. subsequences of activities, fulfill the constraints and the time measures increase by summation over all activities/connections. More complicating constraints stem from the German break regulations which have to be fulfilled, i.e., every duty must allow the crew to take the mandatory duration of breaks which depends on RWT d . To reduce the complexity of the exposition in this paper, we introduce only the most important rules which are representative for the entire set. Note that in our system we have obviously implemented the complete set of rules. 1. If RWT d is less than 6 hours, no break within the duty is necessary, 2. if RWT d is between 6 and 9 hours, then 30 minutes of break time are required, and, 3. if RWT d of d is larger than 9 hours, then 45 minutes of break time are mandatory. Note that in any case, the required break time may be split into breaks of 15 minutes duration, and the first break must always occur within the first 6 hours of RWT d . For the evaluation of a pairing p, we calculate DHT p and IT p as well as AWT p , the total accountable working time of p, by adding the AWT d of all duties in p. Then, these values are multiplied with predefined cost parameters CDHT , CIT , and CAW T , respectively, and we add fixed costs CDU T Y per duty and CLO per layover. Defining βp = 1 if p contains a layover, 0 otherwise, cp is defined as follows: cp = AWT p · CAWT + DHT p · CDHT + IT p · CIT + CDU T Y + βp · (CLO + CDU T Y ).

(2.2.1)

Note that independent of the actual AWT d , at least AWT min minutes are paid and accounted for per duty. 2.3 Feasibility and evaluation of crew schedules A complete crew schedule consists of a set of feasible pairings which covers all legs of all train services in a timetable, and which fulfills additional constraints. These constraints are specific for the strategic level of our problem, e.g. lower and/or upper limits for crew base capacities have to be fulfilled. Here, simulations with different lower and upper limits can be used to analyze the efficiency of the locations and the capacities for crew bases with respect to different timetables. Also, the percentage of pairings in the schedule which contain a layover is subject to (negotiable) labor agreements and is thus controlled by parametrized constraints. The problem of finding a set of pairings covering all legs at minimal costs can be modeled as a classical set-partitioning problem (SPP). In addition to the typical constraints of a SPP, the model has to be extended with constraints securing that the lower and upper bounds for crew base capacities and upper bounds for the frequency of layovers are fulfilled. These constraints are based on the following parameters, whose values are subject to the specific simulation:

Supporting strategic crew management at passenger railways

317

MaxAWT b = maximum amount of AWT available at crew base b, b ∈ B MinAWT b = minimum amount of AWT that has to be used from crew base b, b ∈ B MaxLOb = maximum allowable ratio between AWT of layover pairings at b and AWT of pairings without layover at b, b ∈ B MaxLO = maximum allowable ratio between AWT of all layover pairings and AWT of all pairings without layover After introducing all relevant concepts we are now able to state the analytical model/mathematical program for the strategic crew scheduling problem in detail.

3 Modeling the strategic crew scheduling problem 3.1 The analytical crew scheduling model Assume that we are given the set P of all feasible pairings. We define for every p ∈ P the following indicators:  αpb =  βp =  γpl

=

1, if pairing p ∈ P is assigned to crewbase b ∈ B 0, otherwise 1, if pairing p ∈ P contains a layover 0, otherwise 1, if pairing p ∈ P covers leg l 0, otherwise.

And we introduce the decision variables:  xp =

1, if pairing p ∈ P is part of the solution 0, otherwise.

Now, the strategic crew scheduling problem (SCSP) is modeled as follows: SCSP-Model min



(3.1.1)

cp xp

p∈P

s.t.



γpl xp = 1 ∀l ∈ L

p∈P

MinAWT b ≤  p∈P



(3.1.2)

AWT p αpb xp ≤ MaxAWT b

p∈P

AWT p αpb βp xp ≤ MaxLOb

 p∈P

∀b ∈ B

AWT p αpb (1 − βp )xp

(3.1.3) ∀b ∈ B (3.1.4)

318

U. Derigs et al.



AWT p βp xp ≤ MaxLO

p∈P



AWT p (1 − βp )xp

(3.1.5)

p∈P

xp ∈ {0, 1}

∀p ∈ P

(3.1.6)

The objective (3.1.1) of the crew scheduling problem is to minimize overall costs. Constraints (3.1.2) ensure that every leg is covered exactly once while constraints (3.1.3) set lower and upper bounds for the AWT assigned to a crew base. Constraints (3.1.4) set crew base specific limits for the frequency of layovers at each crew base. If, for instance, MaxLOb is set to 1.5, the AWT of all pairings at b with a layover may have up to 1.5 times the AWT of pairings at b without a layover. Constraint (3.1.5) sets an overall limit to the frequency of layovers, and constraints (3.1.6) define the binary decision variables. 3.2 The computational model Note that the problem of finding a feasible integer solution for the SCSP is already NP-complete. In order to obtain a computationally tractable mathematical program, we modify the model in several ways. First, we transform the set partitioning constraints (3.1.2) into set covering constraints (3.2.2). A set covering solution needs not be feasible for the original set partitioning version since it may lead to multiple coverings (overcovers) of a leg. In reality, overcovers can be transformed into deadheads. Let AWT l be the AWT of a leg l ∈ L. Hence, in (3.2.3), we count zoc , the number of overcover working time minutes, and penalize each minute with nonnegative overcovering cost coc in the objective function. Secondly, we soften the b b , b constraints (3.1.3)–(3.1.5) by introducing artificial variables zawtmin , zawtmax , zlo and zlo which measure the infeasibility and we penalize these infeasibilities with b b , and c . If all penalty costs are set b non-negative penalty costs cawtmin , cawtmax , clo lo to appropriate positive numbers, then a feasible solution to the SCSP model is obtained, if such a feasible solution exists. Thus, we obtain the following relaxed model which we refer to as SCSP’: SCSP’-Model min



cp xp + coc zoc + clo zlo

p∈P

+

 b b b b b b cawtmin zawtmin + cawtmax zawtmax + clo zlo

(3.2.1)

b∈B

s.t.



γpl xp ≥ 1 ∀l ∈ L

(3.2.2)

p∈P



γpl xp − zoc ≤ |L|

p∈P l∈L

MinAWT b ≤

 p∈P

b AWT p αpb xp + zawtmin

(3.2.3) ∀b ∈ B

(3.2.4)

Supporting strategic crew management at passenger railways

319

Table 2 Variables of the dual of SCSP’LP Constraints

Dual variable

Set-covering (3.2.2)

πl

Overcovering (3.2.3)

πoc

MinAWT at crewbase (3.2.4)

b πawtmin

∀b ∈ B

MaxAWT at crewbase (3.2.5)

b πawtmax

∀b ∈ B

MaxLO ratio per crewbase (3.2.6)

b πlo

∀b ∈ B

Overall MaxLO ratio (3.2.7)

πlo



b AWT p αpb xp − zawtmax ≤ MaxAWT b

p∈P



b AWT p αpb βp xp − zlo ≤ MaxLOb

p∈P





∀l ∈ L

∀b ∈ B AWT p αpb (1 − βp )xp

(3.2.5) ∀b ∈ B

p∈P

AWT p βp xp − zlo ≤ MaxLO

p∈P



(3.2.6) AWT p (1 − βp )xp

(3.2.7)

p∈P

xp ∈ {0, 1}

∀p ∈ P

b b b zawtmin , zawtmax , zlo ≥0

(3.2.8) ∀b ∈ B

zoc , zlo ≥ 0

(3.2.9) (3.2.10)

Our solution approach is based on solving the LP-relaxation SCSP’LP of SCSP’. This LP-relaxation is obtained by relaxing the binary condition for the decision variables (3.2.8) to non-negativity conditions, i.e. xp ≥ 0 ∀p ∈ P

(3.2.11)

For this LP we obtain the dual variables listed in Table 2 and the reduced cost of a pairing p with respect to a dual solution is given by c¯p = cp − πp with    b b πp = γpl (πl + πoc ) + AWT p αpb πawtmin + πawtmax l∈L

+



b∈B

 b AWT p αpb βp − MaxLOb · AWT p αpb 1 − βp πlo

b∈B

  + AWT p βp − MaxLO · AWT p (1 − βp ) πlo .

(3.2.12)

320

U. Derigs et al.

4 Solution approach Our approach for solving SCSP’ is based on the Branch&Price (B&P) method. B&P is a variant of the classical Branch&Bound (B&B) method with the specialty that for the given Mixed-Integer (Master-)Program (MP), the linear program relaxation (MLP) is solved via column generation. B&P is a very effective method particularly for solving set partitioning/covering problems. Column generation (CG) is appropriate for solving Linear Programs (LP) that contain a huge number of variables. In such problems most of the columns will have their associated variable equal to zero in an optimal solution. Thus, in CG a subset of variables/columns of the given MLP is selected and reduced LP (RMLP) is defined and solved by conventional LPtechniques/solvers. In a subsequent outpricing step the optimal dual prices are used to check whether introducing variables/columns of the LP not yet considered in the RMLP would contribute to an improvement. In a minimization problem, all columns with negative reduced costs are candidates for such an improvement. In that case the RMLP is extended by adding (some of) these columns and resolved. We denote by RMP the reduced Mixed-Integer (Master-)Program which is associated with RMLP. An overview on the state-of-the-art in CG, the underlying concepts as well as applications to integer programming can be found in Desaulniers et al. (2005). One of the main advantages of the CG approach is the property that not all columns need to be stored or even be known from the beginning or during the procedure. In delayed column generation columns of improving variables are identified and constructed on the fly in the outpricing step. Also, even more essential, it is possible to incorporate specific feasibility constraints into the outpricing step. Consequently, the computation of columns with negative reduced costs may become a complex (combinatorial) optimization problem. In our case, columns correspond to feasible pairings and thus a pairing generator that considers all constraints has to be implemented. In conventional B&B the (LP-)relaxation of the Integer Program is solved to optimality and if the optimal solution is not integer, then a general or problem-specific branching strategy is applied. Usually variables are simply fixed or bounded, which results in a decomposition of the solution space and to a set of open (sub-)problems to be solved in the sequel which are represented as nodes in the B&B-tree. Now, solving the LP relaxation to optimality via column generation may require a large number of outpricing and reoptimization steps without significant improvements, an effect known as tailing off. Thus, there is a tradeoff between the computational effort associated with computing stronger bounds and handling bigger B&B-trees (cf. Lübbecke and Desrosiers 2005), and computational experience indicates that it may be more efficient to terminate the pricing phase and to branch early, i.e. when tailing off occurs. For an introduction to the B&P-concept and its relationship to other IPtechniques we refer to Barnhart et al. (1998) who present a general methodology for Branch&Price using crew scheduling as one example for illustration. Figure 3 displays the different steps/modules and the process of our approach. First, in INIT we generate a connection graph G (see Sect. 4.1.1) and then initialize the solution process with a simple heuristic that generates a sufficiently large set of trivial pairings, such that a feasible solution to SCSP’ can be constructed. Each trivial pairing covers a single leg and uses deadheads to depart from and/or return to

Supporting strategic crew management at passenger railways

321

Fig. 3 Solution approach for SCSP’

a crew base. These trivial pairings define the columns of the initial RMLP. During the solution process sequences of RMLP instances are generated and these are solved by a standard LP-solver. In our study we have used CPLEX 11.1. Along with the optimal solution, CPLEX returns the optimal dual values which are then used in the PRICE-module to check optimality and to possibly generate improving columns. The pricing phase is terminated when no improving columns can be found or when the improvement of the objective function value falls below a pre-specified level. Then, we apply a problem-specific branching strategy in BRANCH if the (optimal) solution of the RMLP is not integer and continue with PRICE. At regular intervals, we call the SOLVE MIP-module and compute a feasible integer solution for our master problem SCSP’ using the set of columns/variables contained in the current RMLP only. For solving this integer problem we again use CPLEX. Especially in early iterations only very few columns in a RMLP solution are integral and it would be computationally too expensive to compute the optimal solution in SOLVE MIP. Thus we set a time limit and stop the MIP-solver with a suboptimal solution, but we increase this time limit during the solution process. When the quality of the solutions generated by SOLVE MIP has reached a required level, i.e., the gap between the lower bound obtained from solving RMLP and the best MIP-solution found is sufficiently small, we stop the solution process. In BRANCH, we use a specific strategy that has shown to be effective for set-covering type problems and we perform a depth-first search strategy without backtracking. The algorithmic concepts used in the PRICE-module and their implementation are introduced in Sect. 4.1, while our branching strategy is shortly described in Sect. 4.2. 4.1 Solving problem PRICE Given an optimal primal and dual solution to RMLP, the role of PRICE is to check if this solution is optimal for MLP, too, and to possibly generate columns (pairings) with negative reduced costs. This problem of generating improving pairings (columns) can be formulated and solved as a resource-constrained shortest path problem (RCSP) on a connection graph G = (V , E). Here, leg activities are represented as nodes and directed arcs between nodes are introduced if a connection between leg activities is

322

U. Derigs et al.

feasible. Each constraint that defines the feasibility of a pairing is interpreted as a constraint for a resource consumption. Note that the connection graph is generated only once in INIT. In Sect. 4.1.1 we show how we construct the connection graph G, in Sect. 4.1.2 we describe our label setting algorithm for generating pairings, and in Sect. 4.1.3 we discuss strategies which are necessary for an efficient implementation. 4.1.1 Constructing the connection graph G = (V , E) contains four types of nodes: source nodes, sink nodes, service nodes and deadhead nodes. For each crew base b ∈ B, we introduce a source node qb and a sink node sb . Let Q be the set of source nodes and S the set of sink nodes. Every service activity slt , t = 1, 2, 3 is represented by a service node utl , and every deadhead activity dlt is represented by a deadhead node wlt . Let U be the set of all service nodes and W be the set of all deadhead nodes. Then, V := Q ∪ S ∪ U ∪ W . We will use the term leg node when we refer to either a service node or a deadhead node, i.e. a node v ∈ U ∪ W. E contains five types of arcs. For each source node qb ∈ Q and each leg node vl1 ∈ U ∪ W with origv 1 = b we introduce a leavebase arc (qb , vl1 ). Accordingly, for each l sink node sb ∈ S and each leg node v ∈ U ∪ W with destv = b, we create a back2base arc. For any two leg nodes v1 , v2 ∈ U ∪ W which allow a feasible connection, we create an arc (v1 , v2 ) of the same type as the underlying connection, i.e., a nonstop, transfer or layover arc. Now, every directed path in G starting from a node qb ∈ Q and ending in a node sb ∈ S represents a pairing. Based on the assignments stated in Table 1 we can associate resource consumptions R(v) for nodes v ∈ U ∪ W and R(e) for arcs e ∈ E, respectively, with R ∈ {TAFB, DT, RWT, AWT, DHT, IT}. Note that, when calculating AWT(e) for a transfer arc e, we assume that all possible breaks during the connection are taken and thus we underestimate the actual AWT of e. Also, for each arc e, we define two indicators LBe := 1, if e is a leavebase-arc (0 otherwise) and LOe := 1, if e is a layover-arc (0 otherwise). To control the generation of paths which lead to feasible pairings with respect to the break rules and to estimate path costs we calculate for each transfer arc e = (v, w) two values:   durv,w , the number of possible 15 min breaks, and, PB(e) := 15 minIT(e) := durv,w mod 15,

a lower bound for the idle time.

Note that if a transfer connection is part of a pairing then independently of the duration of the allocated breaks the crew is at least minIT(e) minutes idle. Given a dual solution of the RMLP we define πv := πoc + πl for each service node v = utl ∈ U . For all other nodes v we define πv := 0. Finally, we assign cost values cv and ce to nodes and arcs which are used to approximate path costs with: cv := AWT(v) · CAW T + DHT(v) · CDHT ce := AWT(e) · CAW T + DHT(e) · CDHT + minI T (e) · CI T + LBe · CDU T Y + LOe · (CLO + CDU T Y ).

Supporting strategic crew management at passenger railways

323

4.1.2 Generating pairings Pairings with negative reduced costs are generated by solving a resource-constrained shortest path problem (RCSP) on G using a specific implementation of the label setting algorithm (see Desrosiers et al. 1995). Starting from source nodes qb ∈ Q paths corresponding to pairings are constructed by successively extending partial paths. Such partial paths are represented by node labels. Here a label J assigned to a node v contains the following attribute values: PRED(J ) := pointer to the predecessor of J in the path BASE(J ) := starting base of the path TAFB(J ) := TAFB of the path AWTc (J ) := AWT of the completed duties of the path AWTd (J ) := AWT of the current duty d of the path AWTp (J ) := AWT of the path DT(J ) := DT of the current duty of the path RWT(J ) := RWT of the current duty of the path PB(J ) := number of possible breaks in the current duty of the path ⎧ ⎨ 1, if a break possibility exists within the first 6 hrs of RWT of the current duty of the path BW6H(J ) := ⎩ 0, otherwise  1, if the path contains a layover LO(J ) := 0, otherwise VL(J ) := set of legs associated with service leg nodes on the path (J ) := accumulated duals of legs of the path c(J ) := costs of the path The procedure is initialized by assigning a label to every source node qb ∈ Q with all numerical values set to zero, the set of visited legs defined as empty, the predecessor undefined, and BASE set to b. In the course of the procedure we select a label J at a node v and an arc e = (v, v  ), v  ∈ U ∪ W ∪ S according to a strategy which is described in the next section and we check whether the extension of the path to node v represented by label J via arc e is feasible. Let l be the leg associated with v  , then, if v  ∈ U and l ∈ VL(J ) the extension is obviously infeasible since we would cover the same leg twice on different days. Otherwise we calculate a candidate label K that will be associated with v  if additional conditions hold. In the following we describe the calculation of the candidate labels and the feasibility checks. As already mentioned, implementation issues such as selection strategies are described in Sect. 4.1.3. Label setting is different for the different types of arcs and we have to distinguish three cases.

324

U. Derigs et al.

Case 1: Path-extensions via leavebase, nonstop and transfer arcs (standard case) Here the values of label K are calculated as follows: PRED(K) = J BASE(K) = BASE(J ) TAFB(K) = TAFB(J ) + TAFB(e) + TAFB(v  ) AWTc (K) = AWTc (J ) AWTd (K) = AWTd (J ) + AWT(e) + AWT(v  ) AWTp (K) = AWTc (K) + AWTd (K) DT(K) = DT(J ) + DT(e) + DT(v  ) RWT(K) = RWT(J ) + RWT(e) + RWT(v  ) PB(K) = PB(J ) + PB(e) LO(K) = LO(J )  1, if ((BW6HJ = 1) or (RWT(J ) ≤ 5 : 45 and PB(e) ≥ 1)) BW6H(K) = 0, otherwise  VL(J ) ∪ l, if v  ∈ U VL(K) = VL(J ), otherwise (K) = (J ) + πv  c(K) = c(J ) + ce + cv  Now, we check whether label K represents a feasible partial path, i.e. a partial path which may be extended to a complete path representing a feasible pairing. Obviously, if one of the resource conditions TAFB(K) ≤ maxTAFB, DT(K) ≤ maxDT,

or

RWT(K) ≤ maxRWT does not hold, then the partial path is infeasible and we discard the extension and we do not set the label. Otherwise, we check whether the break regulations can be fulfilled within the current duty, i.e., whether the needed number NB of mandatory breaks can be allocated. In all duties the first break must be taken during the first 6 hours of RWT. Thus if either RWT k ≤ 6 (= Case a) or NB ≤ PB(K) and BW6H(K) = 1 (= Case b) then the partial path is feasible in that sense and we assign label K to v  . Otherwise, if NB > PB(K) and BW6H(K) = 1 (= Case c) the path is not feasible per se but additional break possibilities may occur for an extension making the extended path feasible. Therefore, in Case c, we should not discard the extension and we assign label K to v  as a tentatively feasible label. In all other cases the partial path represented by label K is infeasible and consequently we discard the extension and we do not set the label.

Supporting strategic crew management at passenger railways

325

Case 2: Path-extensions via layover arcs Now assume that we have selected a feasible label J at node v with LO(J ) = 0 and a layover arc (v, v  ). If we extend the partial path via (v, v  ), the current duty of the partial path ends with the activity associated with v and the next duty begins with the activity associated with v  . If label J is only tentatively feasible, this extension is infeasible. Otherwise we reset all values of duty attributes defining the label K on node v  . Also, since all unused break possibilities in the current duty have now to be counted as working time, we have to correct the working time of the current duty by AWT d+ := max{(PB(J ) − NB(J )) · 15, 0}. Finally, we have to ensure that AWT d is at least AWT min . Therefore, the calculation of the candidate label K differs from the standard case for the following attributes:   AWTc (K) = AWTc (J ) + max AWTd (J ) + AWTd+ , AW Tmin AWTd (K) = AWT(v  ) DT (K) = DT (v  ) RWT(K) = RWT(v  ) PB(K) = 0 LO(K) = 1 BW6H(K) = 0

  (K) = (J ) + πv  + max AWTd (J ) + AWTd+ , AWTmin  b b b + πawtmax + πlo + πlo × πawtmin    c(K) = c(J ) + ce + cv  + CAWT · max AWTd (J ) + AWTd+ , AWTmin − AWTdj + CI T · AWTd+

Now we check the partial path represented by K for feasibility and proceed as in the standard case. Case 3: Path-extensions via back2base arcs/path completion Now assume that we have selected a label J at node v and a back2base arc (v, v  ) to a sink node v  = sb ∈ S with b = BASE(J ), then the extension results in a complete path. Note that no activity is associated with v  , hence AWT v  equals zero. As in case 2, we have to correct the working time of the current duty by AWT d+ := max{(PB(K) − NB(K)) · 15, 0} and we have to ensure that the AWT of this duty is at least AWT min . Again we state only those calculations which are different from the standard case: AWTc (K) = AWTc (J ) + AWT d (K)   AWTd (K) = max AWT d (J ) + AWT(e) + AWT d+ , AWT min

326

U. Derigs et al.

 b b + AWT d (K) (K) = (J ) + πv  + AWT d (K) · πawtmin + πawtmax  b b × (1 − LOk ) · (−MaxLOb πlo − MaxLOπlo ) + LOk (πlo + πlo ) c(K) = c(J ) + ce + cv  + CAW T · (AWT d (K) − AWT d (J )) + CI T · AWT d+

Now we check the partial path represented by K for feasibility, as in the standard case. Yet, since by this extension we generate a complete path, we are not allowed to assign a tentatively feasible label and therefore we have to discard the extension if case c holds. If all constraints are fulfilled, we have found a path that represents a feasible pairing. 4.1.3 Implementation issues G is an acyclic directed graph and we assume that all non-base nodes are sorted ascendingly with respect to the begin-value of the associated activities. Then all paths representing a feasible pairing can be generated by the following simple label-setting procedure using the logic described above. First, we perform from all base-nodes qb all possible path extensions via leavebase arcs and assign the associated labels. Then we discuss all nodes sequentially by checking for all assigned labels all outgoing arcs for feasible path extensions in which case we assign the appropriate label to the successor node. After all nodes have been discussed we evaluate the labels at the sink nodes sb to identify pairings with negative reduced costs. If no such paths exist, we terminate the PRICE phase and we go to BRANCH. Due to the size of G this approach is computationally infeasible and we have to apply strategies for reducing the search space and/or reducing the search time. Here we distinguish decomposition, relaxation and column management as well as graph reduction. Overviews on the numerous CG acceleration techniques proposed in literature are given in Desaulniers et al. (2002) and Lübbecke and Desrosiers (2005), for example. Decomposition Obviously we can organize the search into subproblems PRICE(b) where only paths starting from a specific source qb are constructed. These subproblems are then solved iteratively in a round robin fashion until no negative reduced cost path can be identified for a sequence involving all source nodes in Q. Moreover we divide the first planning day into m time windows of equal length (typically m = 12) and we define and solve the subproblems PRICE(b, i) where we consider only the subset of leavebase arcs from base b for which the associated activity starts within the i-th time window. Abbink et al. (2007) have implemented a similar partitioning method to solve large-scale crew scheduling problems at Dutch Railways. Relaxation A common approach to reduce the search state space when solving RCSP problems is to apply some dominance criteria to eliminate labels. This approach cannot be implemented in our case since the (reduced) costs of partial paths are not monotonically increasing. To reduce the search space we apply a technique known as partial pricing (see Maros 2003), i.e., for each node we allow only a limited

Supporting strategic crew management at passenger railways

327

number n of labels. We maintain those labels with minimal c(K) ¯ := c(K) − (K) value. Note that when applying this relaxation, we may not be able to find a negative reduced costs path although such a path does exist. Therefore, the value for n is chosen rather small (e.g. n = 25) at the beginning of the optimization when many such paths exist and n is successively increased during the optimization until finally all labels are created. Column management Introducing many improving columns into RMLP instead of the column with most negative reduced costs is a well known strategy to accelerate CG (see Desaulniers et al. 2002). On the other hand when the number of columns in the RMLP becomes large, then the LP-solution takes too much time. Hence it is recommendable to also remove superfluous columns from the RMLP. Our experiments have shown that we achieve a good balance between solution quality and solution time by introducing into RMLP after each iteration of PRICE(b) the columns for the 5 pairings with largest negative reduced costs and by removing from RMLP all columns that have not been part of any optimal RMLP-basis for the last 100 iterations. Dynamic graph reduction—arc elimination The purpose of PRICE is to identify feasible pairings with πp ≥ cp . Now assume that we know a lower bound λ for cp . Then, if we can show that πp ≤ λ for all p ∈ P then no feasible pairing with negative reduced costs exists. Such a lower bound λ can be determined based on the problem data. Recall that AWT min , the minimal (paid) working time of a duty, is a problem parameter, while we can calculate AWT max , the maximal working time of a duty, based on the problem data. Now assume that we consider subproblem PRICE(b). Then, let (i, j ) be an arc in G and P(b,i,j ) be the set of feasible pairings starting at b which use arc (i, j ). Now, if μ := max{πp | p ∈ P(b,i,j ) } ≤ λ then we can delete arc (i, j ) before solving PRICE(b). For p ∈ P(b,i,j ) we obtain πp ≤



b b γpl (πl + πoc ) + AWT p · πawtmin + AWT p · πawtmax

l∈L b − AWT p (MaxLOb · πlo + MaxLO · πlo ), b , π ≤ 0. Hence since πlo lo

πp ≤



γpl (πl + πoc ) + δ

b b with δ = 2 · AWT max · πawtmin + 2 · AWT min · πawtmax

l∈L b − 2 · AWT max (MaxLOb · πlo + MaxLO · πlo ), b b since πawtmin ≥ 0 and πawtmax ≤ 0. Now let πi (πj ) be the longest (unconstrained) path in G from sb to i (from j to qb ) with respect to the aggregated node potentials πv . Then the following inequality holds for all p ∈ P(b,i,j ) :

γ :=

 v∈Pi

πv +

 v∈Pj

πv + δ ≥ πp .

328

U. Derigs et al.

Thus if γ ≤ λ we can eliminate arc (i, j ) when solving PRICE(b). Obviously, πi and πj can be obtained by a straightforward and fast label setting procedure. Thus before solving PRICE(b) we check all arcs for possible elimination. Note that δ can b be replaced by a smaller value depending on the known current values for πawtmin b and πawtmax , respectively. Also, for the early iterations when many paths/pairings with negative reduced cost exist, we overestimate λ to further reduce the search space. Our arc elimination technique has been motivated by a similar procedure presented in Mingozzi et al. (1999) and the dual variable based fathoming approach of Lnbbecke (2005). Analyzing the connection graph, we can observe that only 20% of the arcs represent connections between service nodes, the majority of arcs have a deadhead node as tail or head. Thus, in order to accelerate the procedure for solving PRICE(b), before each call of the dynamic arc elimination procedure, we eliminate heuristically a significant percentage of these deadhead-related arcs. In the course of the optimization, this percentage is decreased until finally all deadhead-related arcs are considered. This heuristic graph reduction has been used by Freling et al. (2001) to solve a crew scheduling problem at Dutch Railways. Despite these acceleration methods the sizes of the instances are still too large to be solved within a running time which is acceptable for analytical purposes. Therefore we have used the following preprocessing strategy to reduce the size of the connection graph. Static graph reduction—leg aggregation While legs in L have a duration of 25 minutes on average a typical pairing in practice contains longer sequences of service activities with nonstop connections of the same train service of 2–4 hours duration. Between these sequences relatively short transfer connections or layover connections are scheduled, predominantly at busy stations, i.e. stations where a large number of connections exists. In order to reduce the number of nodes in G, we have developed a preprocessing procedure that anticipates this solution characteristic by aggregating sequences of legs. We define a parameter maxAggregationDuration (which is typically set to 1 hour) and use the entire set B as the set of busy stations. Now, for each train service T = (l1T , . . . , lnTT ) ∈ T we begin aggregating the first subsequence of legs into an aggregated leg l  until arrl T − depl T ≥ maxAggregationDuration 1

j

or destl T ∈ B. Then, we proceed this procedure from ljT+1 etc. For each aggrej

gated leg l  = (liT , . . . , ljT ), we set depl  = depl T , origl  = origl T , arrl  = arrl T and i

i

j

destl  = destl T . By this preprocessing we construct a smaller set L of (aggregated) j legs which now must be covered by a set of pairings and which is used to generate service activities and the corresponding leg nodes in G. Note that the duration of the unproductive but necessary deadhead activities to reposition crews should be as short as possible. Therefore we do not aggregate these legs and generate a deadhead activity for each leg in L. Obviously, when replacing set L by L we will in general not be able to identify the optimal SCSP’ solution. However, for a typical instance, the associated connection network is much smaller, which reduces the solution time significantly. Our computational comparisons have shown that the deterioration of the solution quality is acceptable for strategic purposes.

Supporting strategic crew management at passenger railways

329

4.2 Branching strategy Instead of branching by fixing non-integer variables of the optimal RMLP solution to zero or one, we branch by forcing or forbidding pairs of legs to be covered by the same pairing. This strategy was introduced by Ryan and Foster (1981). Consider two legs l1 , l2 ∈ L and two pairings with fractional values in a RMLP solution with the property that one pairing covers l1 and l2 , while the other pairing covers either l1 or l2 . Then, in the force branch we require that l1 and l2 must be covered together by the same pairing and in the forbid branch we require that l1 and l2 must not be covered by the same pairing. By this branching we obtain two new master problems. If we construct the associated RMLP problems, then the current LP solution is infeasible for both. This branching strategy can be implemented as follows: for both branches, the pairings which violate the respective condition are deleted from the RMLP. Then, for the force branch, we delete from G all outgoing arcs from service nodes associated with l1 and all incoming arcs at service nodes associated with l2 , except for the arcs representing a connection between l1 and l2 . For the forbid branch, we delete all arcs from G representing a connection between the service nodes associated with l1 and l2 . In our implementation, we apply the problem-specific strategy to only consider pairs (l1 , l2 ) of legs which are consecutive legs on a train service and which have the property described above. Experiments have shown that this strategy performs well. We select the pair whose associated pairing has the highest fractional value in the RMLP solution and for which a feasible RMLP solution can be generated after deleting all pairings that violate the respective branching condition. Note that we only perform the corresponding force branch. We never explore the complementary forbid branch, but perform a depth-first search on the force branch without backtracking. Thus, our approach follows a schema denoted as Fix & Price. This does not guarantee optimality, but this strategy allows a fast generation of good integer solutions, as empirical studies on similar problems reported in literature (see Desaulniers et al. 2002) and our own experience shows.

5 Applications and computational experience Based on the models and algorithms presented in Sects. 3 and 4, we have implemented the decision support system on.Track which allows the specification and analysis of different planning scenarios in an interactive manner. Here, the typical process of an analysis is as follows. As a first step on.Track requires to import the (medium-term) timetable draft to be analyzed. This input is then checked automatically for correctness and completeness. Possible errors, such as incomplete information on train services or inconsistencies between the course of train services and the corresponding rotations, are indicated in order to enable (manual) correction. In scenarios, planners specify crew bases and their capacities, set relevant planning and cost parameters, assign team categories to legs based on demand information etc. on.Track allows the individual specification of lower or upper crew capacities

330

U. Derigs et al.

b b (πawtmin , πawtmax ) for each crew base, such that contractual obligations concerning staffing levels and/or realistic assessments for capacity expansions can be respected. b b By setting πawtmin = πawtmax , capacities can be fixed, which is useful for scenarios where it is impossible or unwanted in practice to change the capacities at a specific crew base. With this information, on.Track generates solutions to the SCSP. In order to demonstrate the effectiveness of our algorithmic approach and DSS we now present some computational results obtained on data provided from our industry partner, i.e., an actual medium-term timetable draft containing the complete set of daily long-distance passenger train services which has been analyzed. Note that our approach and DSS have been designed to support the ad-hoc analysis and design of various strategic options on crew size, crew structure and crew base distribution etc. For a specific and individual timetable it is not possible to generate a set of instances which could serve the role of a representative benchmark as it is possible when repetitive operational problems are solved on time-varying data by just saving the input data. Instead we show the results on six different realistic planning scenarios obtained from one given timetable. We first configure a “base” scenario with realistic crew base capacities and team categories. Then, we configure six alternative scenarios to address the following strategic questions:

1. What are the consequences of categorizing legs into one, two or even four different team categories while specifying realistic upper crew base capacities? 2. What are the consequences if crew base capacities are assumed to be unlimited? The alternative scenarios are named T1lim , T1∞ , T2lim , T2∞ , T4lim , and T4∞ , where 1–4 indicate the number of different team categories in the scenario and the suffixes lim and ∞ specify whether the crew base capacities are limited or unlimited. Table 3 lists the major characteristics for each of the alternative scenarios: the number of service and deadhead activities for the different team categories, the number of crew bases and the available AWT at the crew bases in total. Note that in scenarios T1lim Table 3 Characteristics of the evaluated scenarios and associated connection networks Scenario Legs

T1lim

T1∞

T2lim

T2∞

T4lim

T4∞

8,149

8,149

8,149

8,149

8,149

8,149

thereof in team category 1

8,149

8,149

4,323

4,323

3,661

3,661

thereof in team category 2

./.

./.

3,826

3,826

2,038

2,038

thereof in team category 3

./.

./.

./.

./.

662

662

thereof in team category 4

./.

./.

./.

./.

1,788

1,788

Crew bases

27

27

27

27

27

27

Total available AWT

972

∞

972

∞

972

∞

Associated connection networks Source nodes

27

27

27

27

27

27

Leg nodes

26,588

26,588

26,588

26,588

26,588

26,588

Arcs

987,759

987,759

850,771

850,771

789,878

789,878

Generation time

00:00:07

00:00:07

00:00:06

00:00:06

00:00:06

00:00:06

Supporting strategic crew management at passenger railways

331

Table 4 Computational results for the scenarios Scenario

T1lim

T1∞

T2lim

T2∞

T4lim

T4∞

Computation time RMLP/RMP

05:50 h

06:12 h

04:43 h

03:02 h

04:33 h

02:47 h

Computation time SP

35:53 h

29:15 h

28:54 h

29:36 h

29:07 h

18:36 h

Total computation time

41:44 h

35:28 h

33:37 h

32:38 h

33:41 h

21:23 h

Branches

2,022

1,996

1,842

1,739

1,814

1,735

Gap(RMLPBest /RMPBest )

2.51%

1.27%

3.75%

0.52%

3.59%

0.58%

B&P

Key performance indicators of generated solutions Pairings

361

360

383

378

401

388

Duties

553

553

582

569

599

567

Average AWT per duty

9:42 h

9:45 h

9:40 h

9:44 h

9:25 h

9:43 h

Layovers per crew and week

1.46

1.39

1.45

1.41

1.44

1.33

Average productivity

74.60%

75.81%

72.68%

73.84%

71.28%

72.67%

Change of required crews

−56.05

−38.44

−11.04

−24.80

−8.19

−20.88

Required crew moves

0.09%

21.10%

0.40%

20.59%

1.18%

17.44%

and T1∞ all legs belong to an identical team category and thus the resulting connection graphs of the underlying problems contain the highest possible number of arcs. The motivation behind categorizing legs into multiple team categories is the associated specialization of crews, e.g. for specific train types, which generally improves the quality of service. In Table 4 we report the computational results on the scenarios. The upper part of the table shows technical details, such as the computation times, the number of branches, and the gap between the best RMLP and the best RMP solution. In the lower part, key performance indicators of the computed solutions are given, e.g. the total number of pairings and duties in the final solution, the number of layovers per crew and week, the average amount of AWT per duty, and the average productivity of RWT a pairing. The productivity of a pairing is defined as AWT pp for a pairing p, RWT p being the regulated working time of a pairing (which captures “on.productive” working time). The last two rows of Table 4 depict the resulting total change of the number of crews (compared to the “base” scenario) and the percentage of required crew “moves” from one base to another base. The results of the six scenarios show that our solution method is able to generate high-quality solutions in running times which are acceptable in a strategic, i.e., non-operational, setting. We can observe that increasing the number of team categories has a negative effect on the average productivity of pairings as well as the number of required crews. Comparing the results of the lim and ∞ scenarios, we see that slightly better solutions can be obtained if crew base capacities are unlimited. This result shows that for the timetable the present distribution of the crew capacities which is specified in the base scenario does not fit the anticipated demand; moreover, the required crew moves from one base to another are considerable and may thus be hard to realize in practice. Notice that we performed additional tests of our system

Fig. 4 The reporting dashboard in on.Track

332 U. Derigs et al.

Supporting strategic crew management at passenger railways

333

based on different realistic timetable drafts and parameter settings. In these tests, we were able to confirm the applicability of our approach concerning solution quality and runtime. Since the focus of this paper is to give a proof of concept and show the computational feasibility for a DSS, we do not give extensive computational results here, e.g. for different input timetables. To facilitate the analysis of a solution, on.Track offers extensive reporting features. Figure 4 shows one of the reporting dashboards of on.Track, which contains among others the key performance indicators mentioned in Table 4, a chart that displays the distribution of the total AWT to activities, and a diagram illustrating the current and the optimal capacities at each crew base. Further strategic questions in crew management which can be analyzed with on.Track concern alternative layover and working time/break regulations. In general, crews do not like layovers since they are away from home. However, layovers can increase the productivity of a crew schedule and thus they are attractive from management perspective. Also, some legs which are out of way might only be covered by layover pairings in an efficient manner. By varying layover costs CLO and duty costs CDU T Y , planners can control to what extent long pairings with layovers are favored over short pairings without layovers. Moreover, the average number of layovers per employee and week (parameters which are also subject to negotiations) can be limited by adjusting MaxLOb for specific crew bases and by adjusting MaxLO for the overall crew schedule. Working time and break regulations are often subject to negotiations with unions. For management it is desirable to be able to evaluate the effects of discussed changes in regulations beforehand. Since most of the current regulations are parameterized in our model, planners can easily perform what-if analyses on parameterized regulations. 6 Concluding remarks We have demonstrated how a complex, real-world crew scheduling problem can be modeled and how the model can be implemented in an optimization system to allow the analysis of strategic scenarios typical for crew management. The solution approach is problem-specific and is intended to generate good, not necessarily optimal solutions for interactive analyses. Management is supported by our decision support system on.Track which has shown to be suitable for the evaluation of scenarios essential for the decision makers. Future research will focus on the application of further acceleration techniques on the one hand and on the other hand on extensions of the model to allow more flexible integration of different strategic options. References Abbink E, Fischetti M, Kroon L, Timmer G, Vromans M (2005) Reinventing crew scheduling at Netherlands railways. Interfaces 35(5):393–401 Abbink E, van ’t Wout J, Huisman D (2007) Solving large scale crew scheduling problems by using iterative partitioning. In: Liebchen C, Ravindra K, Ahuja RK, Mesa JA (eds) ATMOS 2007—7th workshop on algorithmic approaches for transportation modeling, optimization, and systems. Internationales Begegnungs- und Forschungszentrum fnr Informatik (IBFI) Schloss Dagstuhl

334

U. Derigs et al.

Albers M (2009) Freight railway crew scheduling—models, methods, and applications. Logos, Berlin Assad AA (1980) Modelling of rail networks: toward a routing/makeup model. Transportation Research 14(B):101–114 Barnhart C, Johnson EL, Nemhauser GL, Savelsbergh MWP, Vance PH (1998) Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46(3):316–329 Bengtsson L, Galia R, Gustafsson T, Hjorring C, Kohl N (2007) Algorithmic methods for railway optimization. Lecture notes in computer science, vol 4359. Springer, Berlin; Railway crew pairing optimization Bunte S, Kliewer N (2009) An overview on vehicle scheduling models. J. Public Transp. 1:299–317 Caprara A, Fischetti M, Toth P, Vigo D, Guida PL (1997) Algorithms for railway crew management. Math. Program. 79:125–141 Caprara A, Kroon L, Monaci M, Peeters M, Toth P (2007) Passenger railway optimization. In: Barnhart C, Laporte G (eds) Handbooks in operations research and management science. Elsevier, Amsterdam Cordeau J-F, Toth P, Vigo D (1998) A survey of optimization models for train routing and scheduling. Transp. Sci. 32(4):380–404 Desaulniers G, Desrosiers J, Solomon MM (2002) Essays and surveys in metaheuristics. In: Accelerating strategies in column generation methods for vehicle and crew scheduling problems. Kluwer Academic, Norwell, pp 309–324 Desaulniers G, Desrosiers J, Solomon MM (2005) Column generation. Springer, Berlin Desrosiers J, Dumas Y, Solomon MM, Soumis F (1995) In: Handbooks in operations research and management science. Network routing, vol 8. Elsevier, Amsterdam, pp 35–139; Time constrained routing and scheduling Freling R, Lentink RM, Odijk M (2001) In: Computer-aided scheduling of public transport. Lecture notes in economics and mathematical systems, vol 505. Springer, Berlin; Scheduling train crews: a case study for the Dutch railways Freling R, Lentink RM, Wagelmans AP (2004) A decision support system for crew planning in passenger transportation using a flexible branch-and-price algorithm. Ann. Oper. Res. 127:203–222 Gopalakrishnan B, Johnson EL (2005) Airline crew scheduling: state-of-the-art. Ann. Oper. Res. 140:305– 337 Hartog A, Huisman D, Abbink E, Kroon L (2009) Decision support for crew rostering at ns. J. Public Transp. 1:121–133 Huisman D, Kroon LG, Lentink RM, Vromans M (2005) Operations research in passenger railway transportation. Stat. Neerl. 59(4):467–497 Kroon L, Huisman D, Abbink E, Fioole P-J, Fischetti M, Maróti G, Schrijver A, Steenbeek A, Ybema R (2009) The new dutch timetable: the OR revolution. Interfaces 39:6–17 Lübbecke ME, Desrosiers J (2005) Selected topics in column generation. Oper. Res. 53(6):1007–1023 Lnbbecke ME (2005) Dual variable based fathoming in dynamic programs for column generation. Eur. J. Oper. Res. 162:122–125 Maros I (2003) A general pricing scheme for the simplex method. Ann. Oper. Res. 124:193–203 Mingozzi A, Boschetti MA, Ricciardelli S, Bianco L (1999) A set partitioning approach to the crew scheduling problem. Oper. Res. 47(6):873–888 Ryan DM, Foster BA (1981) An integer programming approach to scheduling. In: Wren A (ed) Scheduling of public transport urban passenger vehicle and crew scheduling. North-Holland, Amsterdam, pp 269–280 Vaidyanathan B, Jha KC, Ahuja RK (2007) Multicommodity network flow approach to the railroad crew scheduling problem. IBM J. Res. Dev. 51(3/4):325–344