Content area
For real life bus and train driver scheduling instances, the number of columns in terms of the set covering/partitioning ILP model could run into billions making the problem very difficult. Column generation approaches have the drawback that the sub-problems for generating the columns would be computationally expensive in such situations. This paper proposes a hybrid solution method, called PowerSolver, of using an iterative heuristic to derive a series of small refined sub-problem instances fed into an existing efficient set covering ILP based solver. In each iteration, the minimum set of relief opportunities that guarantees a solution no worse than the current best is retained. Controlled by a user-defined strategy, a small number of the banned relief opportunities would be reactivated and some soft constraints may be relaxed before the new sub-problem instance is solved. PowerSolver is proving successful by many transport operators who are now routinely using it. Test results from some large scale real-life exercises will be reported. [PUBLICATION ABSTRACT]
Ann Oper Res (2007) 155: 417435 DOI 10.1007/s10479-007-0203-3
Raymond S. K. Kwan Ann Kwan
Published online: 10 July 2007 Springer Science+Business Media, LLC 2007
Abstract For real life bus and train driver scheduling instances, the number of columns in terms of the set covering/partitioning ILP model could run into billions making the problem very difcult. Column generation approaches have the drawback that the sub-problems for generating the columns would be computationally expensive in such situations. This paper proposes a hybrid solution method, called PowerSolver, of using an iterative heuristic to derive a series of small rened sub-problem instances fed into an existing efcient set covering ILP based solver. In each iteration, the minimum set of relief opportunities that guarantees a solution no worse than the current best is retained. Controlled by a user-dened strategy, a small number of the banned relief opportunities would be reactivated and some soft constraints may be relaxed before the new sub-problem instance is solved. PowerSolver is proving successful by many transport operators who are now routinely using it. Test results from some large scale real-life exercises will be reported.
Keywords Driver scheduling Public transport Set covering Heuristics
Drivers are the main personnel to be scheduled in public road transport operations, which include bus, tram and train. In UK, driver costs amount to at least 50% in bus and 20% in rail operations. It is important to ensure that driver schedules are as efcient as possible, and therefore it would be desirable to schedule networks of considerable sizes and complexity in whole. However, real-life large and/or complex problem instances often need special approaches to overcome the computational difculties in solving them.
Driver scheduling is a type of crew scheduling problem well-known to be NP-hard. It has attracted much research interest since the 1960s, which has been reported in a series of international conferences since 1975 (Chicago Workshop 1975;Wren 1981a; Rousseau 1985;
R.S.K. Kwan ( )
School of Computing, University of Leeds, Leeds, UK e-mail: [email protected]
A. Kwan
TRACSiS Limited, Leeds, UK
Effective search space control for large and/or complex driver scheduling problems
418 Ann Oper Res (2007) 155: 417435
Daduna and Wren 1988; Desrochers and Rousseau 1992; Daduna et al. 1995; Wilson 1999; Voss and Daduna 2001). There are several types of crew scheduling problem. Although they may have some common characteristics, they also have major differences. The bus and train driver scheduling problem (Wren 1981b; Wren and Rousseau 1995; Kwan 2004; Desrochers and Soumis 1989; Caprara et al. 1997) concerns the compilation of driver shifts for one operational day. There is a subsequent rostering process of forming weekly packages consisting of work shifts and rest days before assignment to actual drivers. The airline crew scheduling problem (Barnhart et al. 1998; Hoffman and Padberg 1993) considers rotations consisting of ight legs and rests for each crew member over a multi-day period (close to a rostering problem). In the U.K., since 1980s, bus conductors had been gradually phased out and the personnel on the bus is the driver. In the train situation, there are other personnel than drivers to be scheduled, e.g. conductors, guards and on-board catering staff. These other types of crew have different work rules from those for drivers. In this paper, the proposed method and test results will be presented mainly in the context of driver scheduling.
Crew scheduling problems are usually modelled as a set covering or partitioning ILP (Smith and Wren 1988; Desrochers and Soumis 1989; Barnhart et al. 1998; Hoffman and Padberg 1993). Hoffman and Padberg comment in the case of airline crew scheduling that for problem instances with 1000 rows (number of work pieces), the number of columns (potential crew shifts) would be in billions, the number of columns has to be limited in practice therefore true optimality of the real problem may not be achievable. In the UK, it is usual to schedule a network of bus or train services together, rather than to schedule each route separately, to try to maximize overall efciency. Driver scheduling problem instances with over a thousand work pieces are common. Hoffman and Padberg have demonstrated that with the advances in mathematical solution techniques, large set covering/partitioning problems with millions of columns can be solved to optimality. But the set covering/partitioning problems of such sizes would only correspond to small (un-simplied/un-reduced) crew scheduling problemsthe largest set partitioning problem tested in Hoffman and Padberg (1993) has over one million columns but it represents only a small crew scheduling problem with no more than 145 work pieces.
Column generation approaches (Desrochers and Soumis 1989; Desrochers et al. 1992) have theoretically eliminated the number of columns from being the limiting factor for the set covering/partitioning model. However, the sub-problems to be solved for dynamically generating new columns would be computationally expensive and impractical for large and/or complex bus and train driver scheduling problems. Desrochers et al. use a restricted shortest path sub-problem formulation for their column generation algorithm; they explicitly state that their method is meant for small scheduling problems with only one or very few routes. The size of the shortest path sub-problem grows exponentially with the size of the scheduling problem (in terms of the number of work pieces). Some constraints are modelled using a resource concept that checks the feasibility of a cumulative property corresponding to the constraint at each stage of a path. Such cumulative properties may not be formulated easily for some constraints. And some less straightforward constraints have to be modelled using multiple shortest path networks, further increasing the computational effort required (Fores et al. 2002 give more discussion). Real life driver scheduling problems often have many non-trivial constraints. For example, a UK train operator has six rules governing the legality of meal breaks. One of the rules is: If the shift is between 6 and 9 hours long, it must have at least 2 meal breaks, the minimum lengths of the breaks are 20 and 15 minutes respectively, the total length of the 2 meal breaks must be at least 40 minutes, and the meal breaks must occur after 1hr50 and before 7hr10 from the start of the shift.
This paper investigates a new method for further utilizing the power of an existing set covering ILP based driver scheduling algorithm, so that near optimal schedules could be
Ann Oper Res (2007) 155: 417435 419
achieved for large and/or complex instances. Although tackling large and/or complex driver scheduling problems has always been important, previous attempts were generally not very successful. Work in this area has not been well reported because the attempts were largely based on ad-hoc heuristics. For example, in the 1980s a scheme of decomposing a large problem into several small sub-problems intelligently was developed at Leeds. The subproblems were solved sequentially with less efcient shifts being removed and their work carried over to the next sub-problem. The results were generally not very satisfactory because it was not easy to derive a good general algorithm for the problem sub-division task. Kwan and Wren (1996) used a simple genetic algorithm to remove a large proportion of relief opportunities thereby reducing the problem. Since the working solutions may result in rather abnormal patterns of relief opportunities, they are very difcult to be evaluated accurately. Layeld et al. (1999) extracted some combinatorial properties in the relief opportunities pattern and applied constraint programming to reduce the number of relief opportunities. Very limited results had been obtained.
In Sect. 1, we shall introduce the driver scheduling problem including a discussion of its solution and search spaces. Also, the TRACS system (Fores et al. 2002; Kwan et al. 1996; Wren et al. 2003) will be briey described because the work to be discussed later is closely related to it. Section 2 discusses the categorisation of large and/or complex instances, and the PowerSolver scheme for tackling them. Some real test cases will be presented. Finally, conclusions and further work will be discussed in Sect. 3.
1 The driver scheduling problem
Vehicles are rst allocated to journeys as dened in a vehicle schedule which is xed in advance, and will remain unchanged for several months. Notional drivers are then assigned to work on a transport operators daily schedule. Once a driver schedule is compiled, rosters will be constructed to include all drivers work over a period of weeks. Bus operations usually involve a relatively small geographical area and a single crew depot. Train operations cover a much larger geographical area and involve a number of crew depots within the network.
A days work for a driver is called a shift which obeys a set of labour rules. Drivers can only be relieved when a vehicle stops at or passes one of a number of designated relief points; the times at which vehicles pass these points are called relief opportunities.A piece of work refers to the work between two relief opportunities. Vehicle work here includes work that will be normally performed by a driver and it includes both driving and non-driving work, such as preparing or disposing the vehicle as in train operation. One or more consecutive pieces of work on a vehicle form a spell of work. A shift may contain several spells separated by one or more breaks as required by the union agreement. Breaks can be long enough for a mealbreak or a short break for the driver to change from one vehicle to another. In the latter case, the break is called a join-up.
In train operations, when constructing a shift, route and traction knowledge have to be taken into account. Since not all the drivers know all the routes or all types of traction, a shift must contain spells of work that are compatible and known to the driver of a particular crew depot. For example, only depot A driver can take an empty coach from a train platform to depot As sidings and such work can be as small as 7 minutes long. Each shift must be legal according to a set of rules in the labour agreement, e.g. no driver will work more than 5 hr 30 mins continuously; mealbreaks (also known as Personal Needs Breaks (PNB) in UK) must be at least 30 minutes and may be governed by complex rules (see 2.3.2); no shift will
420 Ann Oper Res (2007) 155: 417435
Fig. 1 A simple driver schedule
be longer than 12 hours. In train operations, drivers may have to travel as a passenger on the same or other trains after signing on, in between different trains, during breaks or before signing off. In general, train driver scheduling is more complex than bus driver scheduling.
An example of a simple driver scheduling problem with a solution of four shifts is illustrated in Fig. 1. The days work of three vehicles, 59, 60 and 365 is represented by a vehicle graph shown as horizontal lines imposed upon by relief opportunities marked by a letter code to represent the relief point. Above the point code is the corresponding relief time. Underneath the horizontal lines are the shifts assigned to the vehicle work. A spell of work is shown by a block with pointed ends to indicate the starting and ending times, and the number in each spell refers to the shift number assigned to it. Spells on different vehicles bearing the same number belong to the same shift with one or more breaks. For example, shift 1 rst works on vehicle 59 and then on vehicle 365 after a mealbreak at 1302. In this example schedule, all the shifts consist of two spells only. In many real life problems, shifts often have more than two spells, although having many breaks in a shift may not be desirable.
Driver scheduling is the process of compiling a set of shifts, the driver schedule, which together cover all the vehicle work such that:
Every piece of work is assigned to a shift; The shifts must comply with all the operational constraints and labour rules; The total number of shifts is minimised; The total cost (payable work in minutes) is minimised.
The Generate and Select (GaS) approach (Kwan 2004) is one of the most widely adopted.
GaS rst generates a very large number of legal candidate driver shifts, from which a very small subset is selected to form the schedule. The set covering ILP model naturally ts well for the Selection process with GaS, examples of successful systems derived are (Smith and Wren 1988; Fores et al. 2002). Some metaheuristic methods for the Selection process are also emerging in recent years (e.g. Kwan et al. 2001;Liand Kwan 2003).
Ann Oper Res (2007) 155: 417435 421
Using the GaS approach, the generation of candidate shifts is controlled by a set of parameters representing the labour rules, various time allowances and any route and traction knowledge. Not all legal candidate shifts will be formed as this can run into billions for large problem instances. Soft parameters are used to limit the generation of shifts. Some of these soft parameters are built-in in the system, e.g. limiting the maximum number of spells in a shift to four. Some are designed to allow schedulers to express criteria of shifts deemed to be undesirable (and therefore the system will not generate them), e.g. shifts which contain much less work than average (minimum work content); spells which are too short (minimum spell length) etc.
The Selection process naturally ts the set covering model, which can be represented by the following ILP.
Minimize
n
j
=1
[summationdisplay]aij xj 1, i I ={1, 2,...,m}, (2)
xj = 0or1, j J ={1, 2,...,n}, (3)
where n is the number of candidate shifts m is the number of work pieces
xj is a shift variable, xj = [braceleftBig]
1 if shift j is selected, 0 otherwise cj is the cost of shift j
aij = [braceleftBig]
1 if work piece i is covered by shift j,0 otherwise.
The ILP solver (Wren et al. 2003) used here is based upon the above model with cj being determined by one of three objective functions selected by the users. They are: to minimise the number of shifts; to minimise shift cost, or to minimise a combination of both. cj may include penalty weights associated with certain features of a shift. Positive penalty weights are used for features that are not preferred albeit legal, e.g. shifts with three or more spells are unpopular and may be given a positive penalty weight. In the converse, negative penalty weights, also called preferences, could be given to some favourable shift features. Furthermore, the user may add side constraints to (2) to achieve certain characteristic in the schedule as a whole, e.g. setting bounds on the number of shifts of a certain depot (depot capping), the number of a particular type of shift, the total number of shifts, the schedule cost etc.
1.1 Solution and search spaces
Regardless of the method used, the solution space includes any schedule that covers all the vehicle work without violating the hard constraints. That is, it includes any schedule that is legal and can be put into operation. It is most unlikely that any practical driver scheduling method would be able to yield, even implicitly, all such possible schedules, in which case the search space would be as large as the solution space (assuming that infeasible solutions are not considered). Since driver scheduling is a hard combinatorial problem, there is a need to cut down on the search space. This is usually achieved either by some built-in restrictions or by some adjustable features (represented by parameters) in the scheduling model. The
n
[summationdisplay]
j
=1
cj xj (1)
Subject to:
422 Ann Oper Res (2007) 155: 417435
principle is to rule out driver shifts that have undesirable properties. In this section, we shall introduce three main ways of controlling the search space:
Adjustment of soft constraint parameters Selection/de-selection of relief opportunities Problem instance decomposition
It will be apparent later that by means of an efcient systematic framework for automating the controlled suppression of some relief opportunities and adjustments of scheduling parameters, large and complex problem instances can be satisfactorily tackled.
One reasonable restriction is to limit the number of work spells in a shift. A driver shift consists of an alternation of work spells and breaks. Work spells in a shift are usually on different vehicles and the breaks generally incur inefciency. Although theoretically a shift may consist of any number of spells, it would be undesirable to have too many. The exception could be when there are a lot of small detached pieces of driving work, such as shunting and re-platforming of trains, in the problem. However, such work can often be grouped together and be considered as one larger piece so that the breaks in between can be ignored. It is also often necessary to exclude such work from the main scheduling run because they may be bound by some special scheduling conditions and constraints. Generally, 2-spell shifts with one mealbreak are the most favoured by operators and drivers. From practical experience, it is extremely unlikely that any better schedules would be missed by limiting the number of spells in a shift to a maximum of four. While the maximum may be xed, the scheduler may tighten the limit down to three or two spells thereby reducing the search space further.
Maximum number of shift spells is one of many soft scheduling constraints designed to exclude those shifts that are unlikely to be operated in practice, which are often parameterized so that the scheduler can adjust them to control the size of the search space. For some soft constraints, their corresponding parameters might be so adjusted that they would be totally relaxed, i.e. effectively removed. However, like the maximum number of shift spells, the constraint parameters might only be allowed to be adjusted within some bounds.
As the soft constraint parameters are tightened up, the risk of missing some efcient schedules increases and therefore it can only be done to a certain extent. Another approach for reducing the search space is to abandon some relief opportunities. Although a problem instance may have, say, 1500 relief opportunities, the number of them actually used in a schedule could be just around 300. The search space obviously grows exponentially with the number of relief opportunities. Ideally, we would like to predict accurately which relief opportunities could be thrown away without losing optimality in the resulting schedules. There have been some attempts to derive algorithms to do that. For example, a crude method would be to retain only those relief opportunities that would divide the vehicle work into efcient portions. The work of a vehicle is parsed from the beginning and the latest relief opportunity before the driver must be given a break is retained, any other relief opportunities in between will be abandoned. The process is then repeated from the last relief opportunity retained until the end of the working day. A reverse parse starting from the end of the vehicle work adds a few more relief opportunities. This procedure could be enhanced with consideration of peak periods and multi-depots etc., but the assumption that blocks of work close to the maximum allowed without a break are good does not always hold. Sometimes, a short spell of work might be the key to yielding an overall optimal schedule.
Often, the scheduler would have a good idea as to which relief opportunities should be avoided. For example, a common rule is not to relief drivers during peak operations. However, even the most experienced scheduler could not be entirely certain about the goodness
Ann Oper Res (2007) 155: 417435 423
of individual relief opportunities. The scheduler could rst narrow down the search space by some approximate selection of relief opportunities, and then some trial and error would be needed to ne tune the selection. This may be tedious and time consuming.
Another strategy for controlling the search space is to decompose a problem instance into several small sub-problem instances and schedule them separately. The decomposition may be based on depots and geographical areas of operation. Since perfectly sub-dividing a problem instance would be very difcult to achieve, loss of optimality is virtually inevitable. There have been some attempts in deriving schemes of re-combining the solved sub-problems to be re-optimised, but so far there was not much success.
There is a trade-off between reduction of the search space and potential loss of optimality, but these methods are necessary when the problem instance is large and/or complex. To achieve the best schedules, these methods would have to be applied on a trial-and-error basis and applied in different combinations, and this is facilitated efciently by the PowerSolver scheme to be described in Sect. 2.
1.2 TRACS
The PowerSolver scheme has been developed based on the TRACS system (Fores et al. 2002; Kwan et al. 1996; Wren et al. 2003). TRACS is currently installed in 25 bus companies of First (serving most parts of UK with a eet of about 10,000 buses), several other bus companies and some train operating companies in UK. It uses the GaS approach briey described in Sect. 1. The candidate shift generation stage is driven by parameters which represent the driver work rules and various time allowances. The shift selection stage involves using an ILP solver to select a subset from the candidate shifts to form the solution schedule. The second phase is relatively domain independent. Before the start of the ILP, there is a facility for the user to weight-adjust the shift costs according to specic shift features. The users may also specify side constraints in various combinations of crew depot, shift type, the total number of shifts or the schedule cost.
A kind of column generation technique is used with the GaS approach. The Generation Phase is unchanged producing a very large pool of candidate shifts. However, the LP solver for the Selection Phase initially only considers a small portion of the pool of candidate shifts, and then brings into consideration a few more shifts (columns) from the pool using the pricing information after each iteration. A very large number of candidate shifts therefore can be accommodated as input. However, the specic column generation implementation still has some practical limitations especially at the branch-and-bound stage searching for all-integer solutions. Furthermore, the search space for the generation phase may still be too big for large and/or complex problem instances. Completely dynamic column generation would require a very different model from GaS for the mathematical solver to work, e.g. Desrochers et al. (1992) employ a constrained shortest path sub-problem replacing the Generation Phase, which as explained in Sect. 1 has its own disadvantages. For moderate size instances, e.g. up to about 700 relief opportunities, TRACS can handle them very comfortably.
2 Solving large and/or complex problems
From practical experience, a public transport driver scheduling problem may be considered large if the vehicle work to be covered exceeds 500 hours, or if the number of relief opportunities exceeds about 800 even though the vehicle work may be considerably less than 500
424 Ann Oper Res (2007) 155: 417435
hours. The size of a problem instance is generally determined by the number and density of relief opportunities (i.e. data points) in the vehicle work. Complexity on the other hand refers to the scheduling scenario and the objectives being pursued. For example, driver depots covering rural and urban services respectively may have different not entirely compatible labour agreements. The problem may become complex if rural and urban driving work are to be mixed, which is desirable to some extent in order to achieve maximum efciency. Complex problems exist in many transport companies, though to not quite the same extent as large problems. Large and complex problems have appeared as a result of smaller operators being taken over by their larger neighbours and by the need to seek economies of scale which this provides. Still more complexity may be present as transport schedulers seek to achieve savings in the total wage cost yet endeavour to produce shifts which are legal, workable and acceptable by the driving staff.
2.1 Problem size and complexity
2.1.1 Large problems
Large problems dened by high density of relief opportunities and a great many vehicle hours are theoretically solvable as they are using TRACSif there were no limit on computing resources. Intensive urban services can have a great many relief opportunities and often give rise to problem instances of this type.
Transport operators producing driver schedules manually have overcome these difcul-ties in a number of ways:
The vehicle work to be covered has been broken down into a number of smaller problems based on some common criteria such as route.
The area covered by the network has been broken into a number of smaller but geographically cohesive sub-areas within which drivers operate for the whole of their shifts with only a few shifts overlapping into neighbouring sub-areas.
This may still produce a problem whose size is such that solution by computer is not feasible. Additional criteria need to be applied such as
Analysing the vehicle work according to its distribution during the day and devising a scheme which divides the work into smaller, but logically connected sub-groups.
Examining the vehicle work and dividing it according to which depot it is most likely to be assigned.
Dening time bands for each vehicle which embrace relief opportunities most likely to provide the shifts necessary for a good schedule.
Using tight parameters which control the number of shifts generated so that the mathematical processes can be effective.
Schedules following all of these strategies have been produced in the past with varying degrees of success.
2.1.2 Complex problems
Complex problems are those which, setting aside the consideration of size in the previous section, have some characteristics that make it difcult to produce a good schedule in a straightforward manner. Complexity may be due to:
Many depots serving the operating area.
Ann Oper Res (2007) 155: 417435 425
Individual operating conditions at each depot. A certain mix of shifts overall as well as per depot in the nal schedule. Sometimes there are constraints on the type of shift with different combinations of depots.
Inability to subdivide the problem due to interlinking within the operating area. Labour agreements which are ill-dened; i.e. rules with a lot of exceptions. Whilst a competent manual scheduler will know his area well and have intimate knowledge of how he can t portions of work together in order to produce acceptable shifts this will not always produce the most efcient and cost effective answer. If the labour rules change or a cost cutting exercise is required it would often be very time consuming to produce a new schedule.
2.1.3 Large and complex problems
Given the above difculties, solving whole problems that are both large and complex is computationally difcult. However, the ability to do this would achieve the economies of scale. Working closely with a large operator of bus services in the UK, there are several situations when the need to produce automated schedules for large and complex problems is the only way to proceed. No other practical method will produce the type of schedule required.
Another application area is in rail operation where the network to be addressed covers a huge geographical area. Whilst some drivers are conned to their local area for commuting style work, other drivers may be involved in intercity work for which the ability to cover a larger area is a necessity in order to achieve efcient working practices.
2.2 PowerSolver
The search for a practical solution to large and complex problems gathered pace when we rst started working closely with a large bus group who adopted the TRACS system for its subsidiary companies. Together with the users, we developed a new algorithm called PowerSolver which makes use of the capability of TRACS to solve smaller problems to obtain a near optimal solution. It is based on the idea that once we have an initial solution, regardless of how poor it is, we can improve upon it by rst reducing the problem size considerably and then extending the reduced problem in a controlled manner. The new solution, based on a known best solution, must be no worse and should often be better than the last solution. The algorithm is described as follows:
1. Generate a set of potential shifts using either very tight parameters or restricting the number of possible combinations.
2. Add penalties to each shift if applicable. Use ILP solver to obtain a solution with all the necessary side constraints (these are hard constraints on the schedule as a whole, e.g. total number of shifts for a remote depot may have to be capped). If it is not the rst schedule obtained and there is no more improvement to the schedule, STOP the process.
3. Copy the original problem instance to a new instance and then select the relief opportunities used only by the shifts in the best schedule produced so far.
4. Extend the search space by re-instating some relief opportunities according to one of the dened criteria. The soft parameters on the labour agreement should be relaxed to allow for more possible shifts to be generated.
5. Generate a set of potential shifts on the new problem instance set up in 3 and 4. Go back to 2.
426 Ann Oper Res (2007) 155: 417435
The rst schedule obtained in step 2 can be very crude and may contain much overlapping work. The nature of the set covering model allows for overlapping work. However, excessive overlapping work in a schedule is obviously inefcient. If there is work not possible to be covered in step 1, the system would temporarily exclude such work for the ILP solver in step 2. In subsequent runs we will ensure that all the vehicle work is covered by at least one potential shift in step 5, otherwise, the process will terminate. Since each step deals with a new problem instance, all the solutions (including the best) from previous runs are kept and can be referred to later. In step 3, the original problem is cloned and then reduced in size by using the relief opportunities present in the best solution with an option to re-instate more opportunities by one of the following criteria:
All relief opportunities within a certain time band, e.g. between 0900 to 1000. All the relief opportunities on a number of vehicle workings. A list of relief points to which the relief opportunities belong. All the relief opportunities used in the solutions from a number of previous runs. Random selection by the system one of the relief opportunities lying between the start and end of a spell.
The user can set up a number of steps with any combinations of the above criteria in a control le. If necessary, the process can be re-iterated from the beginning and the number of times it can loop back is specied as a parameter by the user. There are two situations when PowerSolver will terminate: one is when all the loops have been performed; the other case is when PowerSolver has detected that there has been no improvement in total costs and shift numbers to the solutions in the last N consecutive runs where N is set as six currently.
Any side constraints and criteria of applying penalties are specied at the initial stage and before the PowerSolver loop starts. The same constraints and penalties criteria will be used in all the steps within PowerSolver. This is to ensure that solutions obtained in subsequent steps contain the right clusters of relief opportunities to be used.
PowerSolver will change the objective functions in the ILP depending on what has been specied in the side constraints. If the user chooses to minimise the number of shifts and then to minimise the total cost (as the default in the system), PowerSolver will maintain this objective and the solutions obtained in each step should have the same or fewer number of shifts but the total costs may go up and down. The total costs here are the shift costs plus penalties. Alternatively, if the user chooses to minimise cost with a target number of shifts in the solution, PowerSolver will change the objective function to minimise shift costs only subject to the target number of shifts. Before the ILP process in each iteration, PowerSolver adds an extra side constraint on the total costs such that the total costs must be less than the best solution obtained so far. This will ensure that the ILP will look for a solution with a cheaper cost. The best solution obtained and the results from each iteration are displayed in a summary report which shows the gradual reduction in shift numbers, total wage costs, amount of work overlapped and the penalties.
Currently, the criteria in the control le are set up manually by the user. In future, the system should be able to analyse the problem and automatically set up a control le based on our experience. The user will still be able to override the settings. The analysis of the data will look at the pattern of the morning and afternoon peaks and the density of relief opportunities in different time zones. One example of choosing relief opportunities is to reinstate those after lunch and before the start of the afternoon peak, or after the morning peak, or around midday. This will allow work pieces to be broken up into reasonable lengths and form better shifts.
Depending on the type of problems and the number of steps and loops, the process can take from under an hour to many hours for big problems. The time taken to run each step
Ann Oper Res (2007) 155: 417435 427
can be very quick from a few minutes on relatively simpler problems to around 30 minutes for larger problems. The following section describes our experience in using PowerSolver on several real life problem instances that are very large and complex. The results were obtained using a Pentium IV 2.56 GHz PC.
2.3 Test cases and results
2.3.1 Large problem
The case to be discussed in this section involves a very intensive bus service in a city in the north of Scotland. There are relief opportunities on average every twenty minutes after the morning peak. There are 2061 relief opportunities on 146 vehicles giving rise to 1823 work piece constraints. The total vehicle hours is 1738:35. There are two types of shift: ordinary with maximum length 8 hours 6 minutes and split shifts which are longer shifts with a long mealbreak for covering morning and afternoon peak work. The maximum length for split shifts is 11 hours 29 minutes. The maximum number of spells for all shifts is limited to three with a maximum of one mealbreak and one joinup. The minimum mealbreak for split shifts is two hours and split shifts can also contain three spells with a joinup. Maximum length of each spell is 4 hours 42 minutes. Each ordinary shift is paid its total length from signing on to signing off. Split shifts are paid throughout except the long break. However, there is a staged extra payment attached to shifts longer than 9 hours and up to 11 hours 29 minutes.
The objective is to minimise the number of shifts and then the total cost. There is a preference for the driver to drive on the same route as much as possible in a shift. This preference can be modelled as a negative penalty for each shift. A penalty cost may be constant for a certain type of shift feature but proportional to a measure of the feature for some other types. The problem is not complex as it has only one depot, eight relief points, two types of route and a labour agreement which is well-dened. The soft parameter on the minimum length of each spell is set as two hours and the system creates several millions of potential shifts in the Generate phase.
A crude initial solution was rst obtained by a standard TRACS run using a very tight labour agreement and restricting the Generate process to create two-spell shifts only. Several hundred thousands of potential shifts were created and the ILP solution contained 255 shifts with 2 uncovered pieces of work. The control le, constructed by the user, included criteria for re-instating relief opportunities that:
Falls within some time ranges, e.g. after the morning peak; before the start of the afternoon peak; around midday and after the evening peak. Two time ranges of three hours are used on each step.
Are on certain vehicles which work on the same route service. Are at some specic relief points. Are used in the schedules obtained from the previous few runs. There were 16 criteria for re-instating relief opportunities and PowerSolver was run ve
cycles through these criteria, and hence there were 80 steps altogether.
In Table 1, Amount of overlapping is the amount of work to which more than one driver is assigned to it. This is because the set covering model allows overlapping. In train operations, overlapping of driving work may be necessary to indicate that one driver is a passenger to get from one point to another. The negative Penalties refers to the preference to keep the driver on the same route throughout the shift. The small uctuation in the costs of solutions with the same number of shifts is because the cost falls within a built-in tolerance
428 Ann Oper Res (2007) 155: 417435
Table 1 Results of some steps performed by PowerSolver
Step Number of shifts Total cost Total wage Amount of Penalties(hr:min) cost (hr:min) overlapping work (mins)
Initial 255 + 2 uncovered pieces 2015:44 2012:14 122 0 solution uncovered pieces1 254 1922:50 2001:10 0 4700 2 252 1931:10 1999:17 191 4660 3 249 1908:31 1986:51 0 4700 4 249 1904:35 1983:35 0 4740 10 248 1900:55 1977:35 0 4600 11 248 1896:40 1974:00 0 4640 56 248 1888:45 1968:45 0 4800 80 248 1889:03 1969:03 0 4800
which checks how close the integer solution cost to the optimal cost obtained in the relaxed LP solution. If the cost is within this tolerance, the branch-and-bound process will terminate, otherwise, the search will go on for a cheaper solution. Table 1 shows a steady decrease rst in shift number then in total cost. The lowest cost solution was obtained in step 56 and there are 10 solutions after step 56 that have the same cost and penalties, which were interspersed by solutions with slightly higher costs. The whole process took twelve hours to run as an overnight job.
Note that in Table 1, Total Cost is a result of the addition of penalties to the Total Wage Cost and the cost of overlapping work which is weighted by a factor of 3. It is the Total Cost which the ILP minimises as its cost criteria.
The scheduler also used PowerSolver on a very similar but slightly different problem and has been able to produce results that suit their unusual rostering requirements without any manual alterations and provides savings in wage costs.
Another similar problem was tackled by an experienced scheduler using PowerSolver to improve on an existing schedule. The existing schedule had 102 shifts plus ve pieces of overtime work and total wage cost 836:56. In this situation, we normally regard one overtime piece being equivalent to half a shift, thus there were effectively 104.5 shifts in the existing schedule. After running PowerSolver for about two hours, the best solution had 103 shifts with no overtime pieces and the cost was 833:55.
2.3.2 Complex problem
A recent exercise involved the application of PowerSolver to a railway network in a large city in Scotland. The network is part of a busy commuting operation. Although the number of vehicle hours is quite modest by rail standards at 479:02 hours, there is an opportunity for a relief almost every minute on average at some relief points during the period of the working day. The network spreads across the city centre in a predominantly east to west direction and is served by four depots situated at the terminals of the main routes. A new terminal depot is to be built to serve an enhancement to the current network and it is required to investigate what impact this would have on the current driver schedules. Currently served by 73 drivers, there is a desire not to increase this level and to keep costs in the region
Ann Oper Res (2007) 155: 417435 429
Fig. 2 Network diagram
of 580 hours. There is also a desire, especially at signing on and off, to keep the amount of passenger travel between depot and relief point and vice versa to a minimum. This is modelled as a negative penalty associated with a shift whose signing on and off point are the same.
Shift types are classied according to when they sign on: early shifts signing on between 0500 and 0700; day shifts signing on between 7000 and 2200; part shifts signing on at any time and two types of night shift (which are not required in this problem as their sign on ranges are too early). Day and early shifts can be up to ten hours in length whilst night shifts are limited to nine hours; part shifts can be up to 5hours long. Each shift may have up to three paid meal breaks of differing lengths depending on its spreadover. The break must start within a certain time band within the shift. The meal break rules are as follows:
1 break of 10 minutes for shifts with a spreadover up to 6 hours 1 break of 30 minutes for shifts with a spreadover between 6 and 9 hours, to start between the 3rd and 6th hour of the shift
2 breaks of 20 minutes for shifts with a spreadover between 6 and 9 hours, to start between the 2nd and 7th hour of the shift
1 break of 40 minutes for shifts with a spreadover between 9 and 10 hours, to start between the 4th and 7th hour of the shift
2 breaks of 25 minutes for shifts with a spreadover between 9 and 10 hours, to start between the 3rd and 8th hour of the shift
3 breaks of at least 5 minutes each but totalling at least 60 minutes for shifts with a spreadover between 9 and 10 hours, to start between the 2nd and 9th hour of the shift
All shifts are paid through from start to nish. The maximum spell is ve hours and the maximum time that each driver is allowed to drive is nine hours. There were no constraints on the distributions of drivers between depots.
The presence of ve depots with their associated route and traction knowledge gives this problem the added attribute of being complex.
Using conventional settings for the soft parameters in the Labour Agreement was going to produce many millions of potential shifts: tightening strategic ones caused some work not being able to be covered by any legal shifts. Reverting to the original settings and using a simplied version of the shift generator, which may skip over a large number of possible shifts that normally might be required to ensure the production of a good quality set of candidate shifts, all the vehicle work was covered with under 100,000 shifts generated and a schedule was obtained.
Using the relief opportunities employed in the solution schedule the problem was run through PowerSolver. Relief opportunities were selectively included in 30 minute time
430 Ann Oper Res (2007) 155: 417435
Table 2a Some PowerSolver steps for a complex problem (without preferences)
Step No. of Total cost Total wage Overlapping Penalties shifts (hr:min) cost (hr:min) work (mins)
Initial 74 595:41 595.41 0 0 solution1 72 588:05 588:05 0 0 3 72 587:51 587:51 0 0 4 72 586:42 586:42 0 0 5 72 584:52 584:52 0 0 10 72 582:20 582:20 0 0 11 72 580:59 580:59 0 0 31 72 576:44 576:44 0 0 45 72 576:44 576:44 0 0
Table 2b Some PowerSolver steps for a complex problem (with preferences)
Step Number of shifts Total cost Total wage Amount of Penalties(hr:min) cost (hr:min) overlapping work (mins)
Initial 74 595:41 595.41 0 0 solution1 72 492:35 595:55 0 6200 2 72 493:18 594:58 0 6100 9 72 482:17 588:57 0 6400 11 72 476:15 584:35 0 6500 18 72 475:55 584:15 0 6500 27 72 474:14 582:34 0 6500 31 72 474:29 582:22 9 6500 36 72 474:14 582:34 0 6500
bands throughout the day and the pattern of selection was set to run for three cycles of 15 steps. Strategic parameters in the Labour Agreement were slackened to a state which would enable the desired mix of shifts to be generated and ensured that a resulting schedule would use the fewest drivers possible.
From an initial solution with 74 shifts an immediate reduction to 72 shifts was achieved (Table 2a). No further decrease in shift numbers was possible, but the wage cost showed a steady reduction. In the run in which preferences were applied (Table 2b), the best solution showed a slight increase in wage cost of 12 minutes over the lowest cost achieved. Whilst the penalty level remained the same this cheaper solution had nine minutes of overlapping work which rendered it less attractive. The negative penalties represented the preference to keep the drivers based at their home depots to reduce the amount of cross travel incurred. The runs took around 4hours on a Pentium IV 2.56 GHz PC.
In an additional run, preferences were added to encourage shifts to sign on and off at their home depot. This succeeded in reducing the amount of unproductive passenger travel from
Ann Oper Res (2007) 155: 417435 431
twenty three instances to seven. The cost of doing this added just over ve hours (about 1%) to the total paid hours. This improved schedule was very acceptable to the end user.
2.3.3 Large and complex problem
The case to be reported in this section is from a train operating company in the north western part of England. We were commissioned by the company to produce train driver schedules for their summer and winter schedules of 2002. The company provides intensive commuting service around a large city; regular inter-urban service between this large city and another city; and rural services throughout the North of England. This is one of the most difcult problems tackled so far.
There are 11 crew depots but some of the depots are divided into different links indicating slightly different driver route and traction knowledge. Altogether, the crew depots and their links are treated as 31 separate crew bases in addition to 45 relief points. The route knowledge is very complex and there are 63 routes in total. Some portions of route cover only 7 minutes of driving work and are for a driver to take a train to and from a station to the nearest carriage sidings. There are nine different types of traction. The total vehicle hours is 1790:19 with 2304 relief opportunities giving rise to 2073 work piece constraints. One of the big depots also operates an electric service which is excluded in this exercise. There are three types of shifts: day, night and part shifts. Day shifts start at or after 0430; night shifts are those which sign on after midnight and part shifts can start anytime of the day. Day shifts can be up to 11 hours long whereas night shifts are limited to 8 hours. Part shifts have a maximum length of 5 hours with a maximum of 10 minutes break. The length of break for day and night shifts must be at least one of 20 minutes for those less than 8 hours long; otherwise, there must be two breaks of at least 30 and 10 minutes. Shifts are paid from sign on to sign off. Parameters in the labour agreement have to be relaxed so that some crucial but less efcient shifts are created. For example, the minimum spell is set to 7 minutes because there are several small portions of work on a specic route.
In 2002, the whole problem was divided into six non-overlapping sub-problems because it was not possible to solve it as one problem at that time. The rural and semi-rural areas formed three separate sub-problems; the express service from one of the stations of the large city is another sub-problem; the other two sub-problems are services provided by two other big stations of two cities. Sometimes work which was difcult to t in was transferred to another more suitable sub-problem. The problem was further complicated by tacit knowledge we were unaware of initially, hence a number of runs were needed before all the specic operating conditions were correctly implemented. For example, some stations had to be closed after midnight and re-opened at 0400 in the morning. Also, there were operating constraints such as the number of shifts at several rural crew depots had to be above a set target to sustain local employment, whereas the number of shifts in crew depots located at the big cities should be kept to a minimum because of the shortage in train drivers there. Hence penalties are used to discourage work assigned to large city crew depots. Penalties are also used to minimise drivers from changing trains at some locations and prevent cross travelling.
Table 3 shows the current and the target number set by the train operating company. Table 4 lists the results obtained by solving individual sub-problems C, S, X, V, M andW. Depots A, B, G, H, I and K are divided into sub-depots so that slightly different route knowledge can be modelled. All the sub-problems are solved by TRACS. The combined total number of shifts for the six sub-problems is 292 shifts which is lower than the current number but higher than the target total of 271 set by the train company. We later combined sub-problems M and V because there was a lot of interworking between these two sets and
432 Ann Oper Res (2007) 155: 417435
Table 3 Current and the target number of shifts for each crew depot
Depot Aa Ba L D E F Ga Ha Ia J Ka Total
Current 34 18 7 39 12 14 33 48 85 8 33 331 Target 28 16 6 31 9 11 30 37 69 7 27 271 Expected saving 6 2 1 8 3 3 3 11 16 1 6 60
aDepots consisting of several sub-depots
Table 4 Summary of individual sub-problems and their solutions
Sub-problem C S X V M W Total M + V New total (M + V)
Relief opportunities 135 254 319 378 741 486 1119No. of shifts 19 40 28 55 84 66 292 133 286 Total cost 140:24 320:20 246:11 490:11 761:10 568:19 2526:35 1205:00 2463:49
Table 5 Results and comparisons
Depot Aa Ba L D E F Ga Ha Ia J Ka Total Total cost
Target number 28 16 6 31 9 11 30 37 69 7 27 271 Best known solution 29 19 7 25 11 12 23 36 75 7 22 266 2457:44 (from TRACS)PowerSolver 28 19 6 24 11 13 22 36 72 7 22 260 2383:59
savings could be achieved if they were solved as one. The combined M and V problem was large and hence we reduced the problem size by selecting only the relief opportunities used in the two solutions. This saved 6 shifts giving a new total of 286 shifts.
Similar to the merging the M and V sets, we then combined all the sub-problems into one and reduced the problem size by selecting only the relief opportunities used by the solutions of all the sub-problems and produced a much better solution as shown in Table 5. The total number of shifts was reduced to 266 which was well below the target of 271.
We visited this problem instance again to test the capability of PowerSolver on improving the solution. PowerSolver enabled us to tackle the problem as a whole rather than previously resorting to sub-dividing the problem. We started with the initial solutions produced by TRACS. Owing to the large number of relief opportunities which occur during the day time, we had to use time ranges of half an hour after the morning peak and before the afternoon peak for re-instating relief opportunities during the day. The time ranges were extended to hourly in the evening and several hours at night.
Since there was a preference to reduce the number of shifts at big crew depots such as D, G, H, I and K, we used a penalty to discourage shifts from these depots from being selected and the system should transfer the work from these depots to the rural ones such as B and F. The control le contained 21 steps with two iterations. The process stopped at 42 steps after running for 15 hours. The numbers of potential shifts created in the Generate phase were between 400000 to 750000 shifts. The run for each step on average took about 20 minutes. In future, the data and the soft parameters can be tuned such that tighter values can be used to
Ann Oper Res (2007) 155: 417435 433
Table 6 PowerSolver benchmarked against TRACS on its own
Problem No. of ROs No. of Without With work pieces PowerSolver PowerSolver rows No. of shift Lower bound on No. of shifts variables no. of shifts (cost) (cost) columns
2.3.1 2061 1823 758721 255 (1933:13) 248 (1969:03)2.3.2 1009 769 1288518 74 (497:39) 72 (474:14)2.3.3 2304 2073 857902 261 (2406:35) 260 (2383:59)
reduce the total run time. The results are shown in Table 5 onthelastrow.Itshowsasaving of 6 shifts and 73:45 hours compared with the best known solution produced by TRACS.
There is a desirable increase in the number of shifts assigned to the rural depot B, E and F compared with the targets for these depots. Despite there is an increase of three shifts in I compared with the target, the numbers of shifts for D, G, H and K have been reduced substantially.
2.3.4 Tests using TRACS on its own
The problem instances above were real cases in which the experienced human schedulers applied PowerSolver to obtain the best schedules. We carried out further tests using single runs of TRACS without PowerSolver. The numbers of shift variables in these runs were controlled to be as large as possible but such that TRACS can at least be run through to the stage of obtaining a continuous solution for the relaxed LP. Penalties are added to shift variables in the same way in problems 2.3.1 and 2.3.2. From experience, the sum of the shift variables in the relaxed LP solution is usually a good lower bound on the number of shifts in the nal integer solution. The results of PowerSolver are compared with these lower bounds.
Table 6 shows that PowerSolver obtained signicant savings in all three cases. The test runs were continued to the branch-and-bound phase to nd all integer solutions. In the cases of problems 2.3.2 and 2.3.3, the branch-and-bound process could not nd any integer solution within reasonable time. In problem 2.3.1, the integer solution found was 264 with total shift costs 2098:54.
3 Summary and conclusions
We have presented the driver scheduling problem and described a method based on the GaS approach with an ILP solver, which has been successfully applied by many transport operators in UK. However, large and/or complex problems still present the greatest challenge to this approach. These problems, often occurring in an urban network, usually require shifts with at least three or more spells in order to achieve efciency. The number of possible combinations therefore increases exponentially with the number of relief opportunities. PowerSolver extends the GaS approach iteratively deriving new sub-problem instances of manageable sizes and complexity for the ILP solver and guarantees that any new solutions found would be at least as good as and often better than the current best.
We have presented our experience of using PowerSolver to tackle three large and/or complex real life public transport problems in the U.K. and demonstrated how PowerSolver can
434 Ann Oper Res (2007) 155: 417435
solve these types of problem very well. It also gives schedulers some control over the solution search. PowerSolver now is being used by schedulers extensively for solving problem instances with more than 100 shifts in areas such as Kidderminster, Redditch, Hereford, Worcester, Northampton, Leicester, Aberdeen, Glasgow, Manchester, Rotherham, Bristol area and Norwich. Some users have also used PowerSolver on relatively small instances effectively slackening the soft parameters to the extreme in search of possibly cheaper solutions. There is on average 1% saving on the total costs in bus and about 3% or more saving in train compared with the best known solutions. It is anticipated that PowerSolver can potentially save a great many drivers hours for many public transport companies.
Further improvements in PowerSolver include using multiple sets of labour agreements and automatically creating an initial control le. Also, PowerSolver can be invoked automatically once a driver schedule has been obtained to further improve the quality of the solution.
References
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. (1998). Branch-and-price: column generation for solving huge integer programs. Operations Research, 46, 316329.
Caprara, A., Fischetti, M., Toth, P., Vigo, D., & Luigi Guida, P. (1997). Algorithms for railway crew management. Mathematical Programming, 79, 125141.
Chicago Workshop. (1975). Preprints of the international workshop on automated techniques for scheduling of vehicle operators for urban public transportation services.
Daduna, J. R., & Wren, A. (Eds.). (1988). Computer-aided transit scheduling. Proceedings of the fourth international workshop on computer-aided scheduling of public transport. Berlin: Springer.
Daduna, J. R., Branco, I., & Paixo, J. M. P. (Eds.). (1995). Computer-aided transit scheduling. Proceedings of the sixth international workshop on computer-aided scheduling of public transport. Berlin: Springer.
Desrochers, M., & Rousseau, J.-M. (Eds.). (1992). Computer-aided transit scheduling. Proceedings of the fth international workshop on computer-aided scheduling of public transport. Berlin: Springer.
Desrochers, M., & Soumis, F. (1989). A column generation approach to the urban transit crew scheduling problem. Transportation Science, 23, 113.
Desrochers, M., Gilbert, J., Sauve, M., & Soumis, F. (1992). CREW-OPT: subproblem modelling in a column generation approach to urban crew scheduling. In M. Desrochers et al. (Eds.), Computer-aided transit scheduling (pp. 395406). Berlin: Springer.
Fores, S., Proll, L., & Wren, A. (2002). TRACS II: a hybrid IP/heuristic driver scheduling system for public transport. Journal of the Operational Research Society, 53, 10931100.
Hoffman, K. L., & Padberg, M. (1993). Solving airline crew scheduling problems by branch-and-cut. Management Science, 39(6), 657682.
Kwan, A. S. K., Kwan, R. S. K., Parker, M. E., & Wren, A. (1996). Producing train driver shifts by computer, In J. Allan et al. (Eds.), Computer in railways V, Volume 1: Railway systems and management (pp. 421435). Computational Mechanics Publications.
Kwan, R. S. K. (2004). Bus and train driver scheduling. In J.Y.-T. Leung (Ed.), Handbook of scheduling: algorithms, models, and performance analysis (Chapter 51, pp. 120). CRC Press.
Kwan, R. S. K., & Wren, A. (1996). Hybrid genetic algorithms for bus driver scheduling. In L. Bianco & P.Toth (Eds.), Advanced methods in transportation analysis (pp. 609619). Berlin: Springer.
Kwan, R. S. K., Kwan, A. S. K., & Wren, A. (2001). Evolutionary driver scheduling with relief chains.Evolutionary Computation, 9, 445460.
Layeld, C. J., Smith, B. M., & Wren, A. (1999). Bus relief opportunity selection using constraint programming. In Proceedings of rst international conference on the practical applications of constraint technologies and logic programming (pp. 537552). Blackpool: The Practical Application Company. Li, J., & Kwan, R. S. K. (2003). A fuzzy genetic algorithm for driver scheduling. European Journal of
Operational Research, 147, 334344.
Rousseau, J.-M. (Ed.). (1985). Computer scheduling of public transport 2. Proceedings of the third international workshop on computer-aided scheduling of public transport. Amsterdam: North-Holland. Smith, B. M., & Wren, A. (1988). A bus crew scheduling system using a set covering formulation. Transportation Research, 22A, 97108.
Ann Oper Res (2007) 155: 417435 435
Voss, S., & Daduna, J. R. (Eds.). (2001). Computer-aided scheduling of public transport. Proceedings of the eighth international conference on computer-aided scheduling of public transport (CASPT 2000). Berlin: Springer.
Wilson, N. H. M. (Ed.). (1999). Computer-aided transit scheduling. Proceedings of the seventh international workshop on computer-aided scheduling of public transport. Berlin: Springer.
Wren, A. (Ed.). (1981a). Computer scheduling of public transport. Proceedings of the second international workshop on computer-aided scheduling of public transport. Amsterdam: North-Holland.
Wren, A. (1981b). General review of the use of computers in scheduling buses and their crews. In A. Wren(Ed.), Computer scheduling of public transport (pp. 316). Amsterdam: North-Holland.
Wren, A., & Rousseau, J.-M. (1995). Bus driver schedulingan overview. In J. R. Daduna, I. Branco &J. M. P. Paixao (Eds.), Computer-aided transit scheduling (pp. 173187). Berlin: Springer.
Wren, A., Fores, S., Kwan, A. S. K., Kwan, R. S. K., Parker, M. E., & Proll, L. (2003). A exible system for scheduling drivers. Journal of Scheduling, 6, 437455.
Springer Science+Business Media, LLC 2007