Content area
This paper addresses the problem of determining the best scheduling for Bus Drivers, a N P-hard problem consisting of finding the minimum number of drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and regulations that must be enforced such as spreadover and working time. This problem is known in literature as Crew Scheduling Problem and, in particular in public transportation, it is designated as Bus Driver Scheduling Problem. We propose a new mathematical formulation of a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. Unfortunately, this model can only be usefully applied to small or medium size problem instances. For large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results are reported for a set of real-word problems and comparison is made with an exact method. Moreover, we report a comparison of the computational results obtained with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci. 39(4):491-502, 2005). [PUBLICATION ABSTRACT]
J Heuristics (2011) 17:441466
DOI 10.1007/s10732-010-9141-3
Received: 18 May 2005 / Revised: 29 March 2010 / Accepted: 8 July 2010 / Published online: 22 July 2010 Springer Science+Business Media, LLC 2010
Abstract This paper addresses the problem of determining the best scheduling for
Bus Drivers, a N P-hard problem consisting of nding the minimum number of
drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and regulations that must be enforced such as spreadover and working time. This problem is known in literature as Crew Scheduling Problem and, in particular in public transportation, it is designated as Bus Driver Scheduling Problem. We propose a new mathematical formulation of a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. Unfortunately, this model can only be usefully applied to small or medium size problem instances. For large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results are reported for a set of real-word problems and comparison is made with an exact method. Moreover, we report a comparison of the computational results obtained with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci. 39(4):491502, 2005).
Keywords Crew and Bus Driver Scheduling Problem Transportation
Meta-heuristics GRASP
R. De Leone E. Marchitto
School of Science and Technology, University of Camerino, Via Madonna delle Carceri, 9, 62032 Camerino, MC, Italy
R. De Leonee-mail: [email protected]
E. Marchittoe-mail: [email protected]
P. Festa ( )
Department of Mathematics and Applications, University of Napoli Federico II, Naples, Italy e-mail: mailto:[email protected]
Web End [email protected]
A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution
Renato De Leone Paola Festa Emilia Marchitto
442 R. De Leone et al.
Introduction
The Bus Driver Scheduling Problem (BDSP) is an extremely complex part of the Transportation Planning System (e.g., Wren 2004; Desaulniers and Hickman 2003; Mesquita et al. 2009; Portugal et al. 2009; Moz et al. 2009). Its combinatorial nature and the need to solve large size real-world problems has led to the development of several heuristics. Wren and Rousseau (1995) give an outline of the BDSP and propose various approaches for solving it. Many of these techniques have been reported in the proceedings of international conferences on Computer-Aided-Scheduling of Public Transport (e.g., Wren 1981; Rousseau 1985; Daduna and Wren 1988; Desrochers and Rousseau 1992; Daduna et al. 1995; Wilson 1999; Vo and Daduna 2001).
In general, the Transportation Planning System is divided in different subproblems due to its complexity: Timetabling, Vehicle Scheduling, Crew Scheduling (Bus and Driver Scheduling), and Crew Rostering (see Fig. 1 for the relationship between these subproblems).
The transportation service is composed of a set of lines that corresponds to a bus travelling between two locations of the same city or between two cities. For each line, the frequency is determined by the demand. Then, a timetable is constructed, resulting in journeys characterized by a start and end point, and a start and end time. The Vehicle Scheduling Problem consists in nding a schedule for the buses, each schedule being dened as a bus journey starting at the depot and returning to the same depot.
The objective is to minimize the total cost given by the cost of buses used for the service and running costs. Running costs can be minimized avoiding unnecessary deadheads, i.e., trips carrying no passengers. The daily schedule of each single bus is known as a running board (or vehicle block).
Bus schedules are composed of several running boards and their lengths are determined by the total time the bus is operating away from the depot.
Fig. 1 Transportation Planning
System
A Bus Driver Scheduling Problem: a new mathematical model 443
The Bus Driver Scheduling is the second phase of the general operational planning of a public transportation company. This problem is important from an economic point of view and it is related to the costs of the drivers. The BDSP consists of determining the shifts (i.e., full days of work) for the drivers at a certain depot to cover all the running boards.
Since a driver exchange can occur at various points along a running board, the entire running board is divided in units (Pieces-Of-Work) that start and nish at relief points, i.e., designed locations and times where and when a change of driver may occur. Different types of shift can be taken into account, which are composed of Pieces-Of-Work whose length is variable and whose beginning occurs at possibly distinct starting times. For example, a shift can contain a single Piece-Of-Work, two Pieces-Of-Work or more Pieces-Of-Work.
A set of Pieces-Of-Work that satises all the constraints is a feasible shift. A break (a time slot of no work) can also be inserted between two different Pieces-Of-Work or in a single Piece-Of-Work (i.e., when the vehicle is stopped for a period of time at a location where there is not a relief point). There are two different types of break: rest and idle time. Rest is unpaid, while idle time is paid (in Italy, for example, its rate is 12 percent of ordinary wage).
The feasibility of a shift not only depends on the breaks and the duration of the Pieces-Of-Work, but also on the total working time and on the spreadover. The total working time is the sum of the duration of the Pieces-Of-Work (excluding idle time) while the spreadover is the total time between the start and the end of the shift.
A feasible solution for the BDSP is a set of feasible shifts for the drivers. A different cost to each shift can be associated. The aim is to minimize not only the total cost but also the total number of shifts.
In Fig. 2 an example of a vehicle schedule is represented. It may typically be depicted by several horizontal lines, each representing a running board. Along these lines the relief points are identied by a time/location pair, at which drivers can be relieved. For example, the pair (A, 08:10) is designed as relief point, where A is the relief location and 08:10 is the relief time. An example of Piece-Of-Work is the interval between the pairs (B, 15:40) and (A, 16:10) that, in general, must be covered
Fig. 2 Representation of vehicle schedule and of a possible shift
444 R. De Leone et al.
by a single driver. Figure 2 shows a part of the schedule of Vehicle 1 that leaves the depot at 06:50 and passes relief point A at various times, relief point B at 11:30, and so on. Moreover, an example of a possible shift is also shown including the rst part of Vehicle 1, a break, and the second part of Vehicle 2 (dashed line connecting the timetable line for Vehicle 1 to the timetable line for Vehicle 2).
The BDSP which is a N P-hard problem even when there are only spreadover
and working time constraints (for a proof see Fischetti et al. 1987, 1989), can be formulated as a Set Partitioning Problem or a Set Covering Problem. By solving the Set Covering Problem we often produce a solution that contains very little or no over-covering at all. Moreover, the over-covering can be eliminated a posteriori using, for example, a heuristic procedure.
Given the Set Covering Problem, different heuristic approaches such as column generation, Lagrangian and Linear programming relaxation are used to solve the BDSP.
Several heuristic approaches have been proposed in the literature; for a survey see Wren and Rousseau (1995) and Wren (2004); Mesquita et al. (2009); Portugal et al. (2009); Moz et al. (2009).
Curtis et al. (1999) solved the restricted Set Partitioning model by means of a hybrid constraint programming/linear programming heuristic method, where the linear programming solutions are adopted to guide variable and value ordering in the constraint programming algorithm. One interesting aspect of this method is that the constraint programming component is able to deal with nonlinear constraints which can derive from specic work rules.
Recently, Fores et al. (2002) combined a column generation strategy with the set covering model. The approach consists of generating new columns as needed from a subsets of a priori enumerated valid shifts. This strategy is applied only to the root node of the Branch & Bound search tree. The solution is signicantly improved with a slight increase in the solution time.
Column generation techniques for the BDSP were introduced by Desrochers and Soumis (1989) and they have been successfully tested on real-world problems (e.g., Rousseau and Desrosiers 1993). The problem is decomposed into two subproblems: a Set Covering and a Shortest Path Problem. By solving the Set Covering subproblem, a schedule from already known feasible shifts is determined. Starting from this newly found schedule, a Shortest Path Problem is solved to nd a new and better feasible set of shifts.
Carraresi et al. (1993) propose a decomposition approach based on Lagrangian relaxation that can also be applied to the Airline Crew Scheduling Problem.
Dias et al. (2001) proposed a hybrid relaxation of the Set Partitioning model and a Genetic Algorithm; recently, in Dias et al. (2005), they proposed a new multi-objective Genetic Algorithm based on a Pareto approach. Furthermore, they have depicted a set of novel operations: a tness assignment procedure based on the dominance sharing notion, a coding scheme and several new operators. The approach has been tested on a set of real-world problems from three mass transportation companies.
Finally, various papers describe commercial software packages used by public transport companies: the HASTUS system, which has been on the market for more
A Bus Driver Scheduling Problem: a new mathematical model 445
than 20 years (for more details see Rousseau and Blais 1985), GIST (see Cunha and Sousa 2002), TRACS II (see Fores et al. 2001), TURNI (see Kroon and Fischetti 2001) and DOPT (Duty Optimization for Public Transport, see Huisman 2004).
Further solution approaches can be found in Wren (2004), Daduna and Wren (1988), Fores (1996) and Shen (2001); for a description of the terminology used in Bus and Driver Scheduling, the reader is referred to the glossary of Hartley (1981).
The remaining of the paper is organized as follows. In Sect. 1 a new mathematical model is provided for a BDSP under special constraints imposed by Italian transportation rules. Section 2 describes the general GRASP framework for solving combinatorial optimization problems and Sect. 3 contains a brief literature review on GRASP for transportation problems and states how it is applied to the special variant of the Bus Driver Scheduling Problem we studied here. In Sect. 4, we report computational results; in particular, in Sect. 4.2 we compare the GRASP procedure and the approach of Huisman et al. (2005), using the same random instances. Finally, in Sect. 5 we close the article with suggestions for future work.
1 Problem description and mathematical formulation
In this section, a new mathematical model is provided for a BDSP under special constraints originated by our collaboration with PluService Srl, a leading Italian group in software for transportation companies. The goal has been to model specic collective agreements and labour rules stated by the Italian government but also to generalize the state-of-the-art problem including constraints for a variety of trade-union rules and regulations for transportation companies.
Obviously, given the large number of different types of constraints, we have modelled only the most important of them such as working time, spreadover, idle time and constraints on depots (i.e., drivers must terminate the shifts at the same depot of departure). To the best of our knowledge, this is the rst attempt of this kind to model such trade-union rules and regulations. The approaches utilized in literature are based on knapsack or multi-knapsack problems with additional constraints or on Set Partitioning formulations.
As mentioned before, Crew Scheduling Problems are among the most important problems that public transport companies must solve. It consists of assigning the Pieces-Of-Work (i.e., a sequence of trips, deadheads, and breaks between two relief points on a running board) to shifts in such a way that:
1. each Piece-Of-Work is performed by only one driver;2. the shifts are feasible (that depends on a given set of working rules);3. total operational costs of the shifts or the total number of shifts are minimized or both.
To determine the Pieces-Of-Work, it is necessary to solve a Vehicle Scheduling Problem. Let J be a set of Pieces-Of-Work, L be a set of positions (i.e., the sequence position of Pieces-Of-Work covered within a shift), and K be a set of shifts. The following binary variables are dened:
446 R. De Leone et al.
for each j J , k K, and l L,
xjkl = [braceleftbigg]
1 if the Piece-Of-Work j is in shift k at position l, 0 otherwise;
for each k K and l = 1, . . . , L 1,
ykl = [braceleftBigg]
1 if there is some idle time in shift k immediately after position l,
0 otherwise;
for each i, j J ,
vij = [braceleftbigg]
1 if the Piece-Of-Work j follows the Piece-Of-Work i in a shift, 0 otherwise;
for each i and j J ,
uij = [braceleftBigg]
1 if the Pieces-Of-Work i and j are respectively the rst and the last Piece-Of-Work in the same shift,
0 otherwise.
Moreover, we dene the following nonnegative variables: for each k K,
TSk = starting time of shift k, TEk = ending time of shift k,
for each k K and l = 1, . . . , L 1,
rkl = the difference between the starting time of the next Piece-Of-Work and the ending time of the Piece-Of-Work at position l in shift k.
Dene now the following constant parameters:
C1: maximum spreadover allowed (duration between the start and the end of a
shift);
C2: if between two consecutive Pieces-of-Work in a shift there is a delay larger
than C2, then an idle time occurs;
C3: maximum number of occurrences of idle time in a shift; C4: maximum total working time allowed; and for each j J ,
tsj and tej denote, respectively, the start and end time of Piece-Of-Work j; Rj is equal to 1 if there is idle time in Piece-Of-Work j, 0 otherwise; dj is the working time of Piece-Of-Work j; depj is equal to 1 if Piece-Of-Work j starts from the depot, 0 otherwise; and for each i J and j J ,
A Bus Driver Scheduling Problem: a new mathematical model 447
sij is equal to 2 if Piece-Of-Work j can follow Piece-Of-Work i, 1 otherwise; tij is equal to 2 if Piece-Of-Work i starts from the depot and Piece-Of-Work j ends
in the same depot, 1 otherwise.
Furthermore, for each pair of Pieces-Of-Work (i, j), let wij 0 be the associated
cost to carry out Piece-Of-Work j directly after Piece-Of-Work i, where wij = +
if the pair (i, j) is not compatible or if i = j. Similarly, for each pair of Pieces-Of-
Work (i, j) that starts and ends in the same depot, let Wij be the nonnegative cost incurred when a driver starts his shift with Piece-of-Work i and terminates the shift with Piece-of-Work j. Moreover, let cj 0 be the associated costs to carry out a
shift.
Depending on the choice of the cost coefcient, different objectives can be modelled. The number of shifts is minimized if cj = 1 for each Piece-Of-Work j that
starts from a depot, and wij = 0 and Wij = 0 for each compatible pair (i, j). In
stead, if cj = 0 for each Piece-Of-Work j and quantities Wij and wij are propor
tional to the operational costs, including penalties for idle times, then the objective function minimizes overall operational costs. Moreover, any combination of the previous two objective functions can be modelled using specic choices of the values cj , Wij and wij .
The Bus Driver Scheduling Problem can be formulated as follows:
min
K
[summationdisplay]
k=1
J
[summationdisplay]
j=1
cjxjk1 +
J
[summationdisplay]
i=1
J
[summationdisplay]
j=1
wij vij +
J
[summationdisplay]
i=1
J
[summationdisplay]
j=1
Wijuij
subject toJ
j=1xjkl 1, k = 1, . . . , K, l = 1, . . . , L, (1)
J
[summationdisplay]
j=1
xjkl+1
J
j=1
xjkl, k = 1, . . . , K, l = 1, . . . , L 1, (2)
J
[summationdisplay]
j=1
xjkl+1[parenrightBigg],
k = 1, . . . , K, l = 1, . . . , L 1, (3)
TEk
J
[summationdisplay]
j=1
tej xjkl
J
[summationdisplay]
j=1
[summationdisplay] tsj xjkl+1 + MQ[parenleftBigg]1
J
[summationdisplay]
j=1
tej xjkl, k = 1, . . . , K, l = 1, . . . , L, (4)
TSk =
J
[summationdisplay]
j=1
tsj xjk1, k = 1, . . . , K, (5)
TEk TSk C1, k = 1, . . . , K, (6)
448 R. De Leone et al.
J
[summationdisplay]
j=1
tsj xjkl+1
tej xjkl C2 + Mykl,
k = 1, . . . , K, l = 1, . . . , L 1, (7)
J
[summationdisplay]
j=1
J
[summationdisplay]
j=1
L
[summationdisplay]
l=1
Rj xjkl +
L1
[summationdisplay]
l=1
ykl C3, k = 1, . . . , K, (8)
L
[summationdisplay]
l=1
J
[summationdisplay]
j=1
dj xjkl +
L1
[summationdisplay]
l=1
rkl C4, k = 1, . . . , K, (9)
rkl MQ[parenleftBigg]
J
[summationdisplay]
j=1
xjkl+1[parenrightBigg], k = 1, . . . , K, l = 1, . . . , L 1, (10)
xjkl+1[parenrightBigg],
k = 1, . . . , K, l = 1, . . . , L 1, (11)
rkl
J
[summationdisplay]
j=1
rkl
J
[summationdisplay]
j=1
tsj xjkl+1
J
[summationdisplay]
j=1
tejxjkl + Mykl + MQ[parenleftBigg]1
J
[summationdisplay]
j=1
xjkl+1[parenrightBigg],
k = 1, . . . , K, l = 1, . . . , L 1, (12)
K
[summationdisplay]
k=1
tsj xjkl+1
J
[summationdisplay]
j=1
tejxjkl Mykl MQ[parenleftBigg]1
J
[summationdisplay]
j=1
L
[summationdisplay]
l=1
xjkl = 1, j = 1, . . . , J, (13)
xikl + xjkl+1 1 + vij, k = 1, . . . , K, l = 1, . . . , L 1,
j = 1, . . . , J, i = 1, . . . , J, (14)
1 + vij sij , i = 1, . . . , J, j = 1, . . . , J, (15)
xik1 + xjkl tij + [parenleftBigg]
J
[summationdisplay]
j=1
,
x jkl+1
k = 1, . . . , K, l = 1, . . . , L 1,
i = 1, . . . , J, j = 1, . . . , J, (16)
xik1 + xjkl 1 + uij + [parenleftBigg]
J
[summationdisplay]
j=1
x jkl+1[parenrightBigg],
k = 1, . . . , K, j = 1, . . . , J,
l = 1, . . . , L 1, i = 1, . . . , J, (17)
A Bus Driver Scheduling Problem: a new mathematical model 449
xik1 + xjkL tij , i = 1, . . . , J, j = 1, . . . , J,
k = 1, . . . , K, (18) xjk1 depj , k = 1, k = 1, . . . , K, j = 1, . . . , J,xjkl, ykl {0, 1}, j = 1, . . . , J, k = 1, . . . , K, l = 1, . . . , L, vij, uij {0, 1}, i = 1, . . . , J, j = 1, . . . , J,
T Ek 0, T Sk 0, rkl 0, k = 1, . . . , K, l = 1, . . . , L,
(19)
where M and MQ are given constant parameters. The objective function minimizes the total number of shifts and/or the total operational costs. Constraints (1) impose that at most a single Piece-Of-Work j is in position l in shift k. Constraints (2) impose that, if there is a Piece-Of-Work at position l + 1, then there is a Piece-Of-Work at
position l; constraints (3) assert that the ending time of Piece-Of-Work j in shift k at position l must not exceed the starting time of Piece-Of-Work j in shift k at position l + 1.
Constraints (4), along with (5) and (6), impose limits on the total time between the starting and the ending time of the shift (i.e. the spreadover). Constraints (7) limit the number of breaks between Pieces-Of-Work and constraints (8) impose an upper bound on the number of occurrences of idle times. Constraints (9)(12) impose a limit on the total duration of the journey in any shift (i.e. working time). In particular, constraints (10)(12) impose that rkl is exactly the rest time between positions l and l + 1 in shift k unless there is idle time. Constraints (13) ensure that each Piece-Of-
Work is covered exactly once.
Constraints (14) and (15) impose compatibility between Pieces-Of-Work (two Pieces-Of-Work i and j are compatible if and only if they can be executed consecutively by the same driver, i.e. j can immediately follow i: tei +ij tsj ). Constraints
(16)(19) assert that the starting depot of any shift k must be the same as the ending one.
1.1 Computational results
The exact solutions for the mathematical model introduced in this subsection have been obtained by using (GAMS 2005) (General Algebraic Modelling System) and Cplex 9.1.2. Tables 1 and 2 show the computational results for our model. The rst column contains the total number of Pieces-Of-Work; then, for each problem type we indicate three different objective functions (minimization of total number of shifts, of total operational costs, and nally a combination of both). In Table 1, for 16, 19, and 25 Pieces-Of-Work we report the optimal solution cost, the rst integer feasible solution cost, and the running times needed to nd them. In Table 2 we report the rst integer feasible solution cost for 30, 38, and 50 Pieces-Of-Work. Note that, for 70 Pieces-Of-Work, we report the rst integer feasible solution only for the minimization of the total number of shifts, since in the other cases the model is not able to nd a solution.
The results obtained show that, unfortunately, the exact model can only be used to solve small or medium size instances of the problem. Given the high computational
450 R. De Leone et al.
Table 1 Experimental results for our mathematical model on 16, 19, and 25 Pieces-Of-Work
Problem Objective Optimal Time First Feasible Time
Function Cost (in sec.) Solution Cost (in sec.)
min. shift 5.00 1.40 5.00 0.86
16 POWs min. costs 2680.00 443.32 2710.00 0.95
min. comb 2685.00 575.33 2715.00 0.87
min. shift 6.00 2.07 6.00 1.17
19 POWs min. costs 3150.00 630.32 3150.00 1.44
min. comb 3156.00 999.06 3186.00 1.11
min. shift 8.00 117.97 8.00 1.90
25 POWs min. costs 4060.00 6239.26 4090.00 1.67
min. comb 4068.00 65598.96 4098.00 1.78
Table 2 Experimental results for our mathematical model on 30, 38, 50, and 70 Pieces-Of-Work
Problem Objective First Feasible Time
Function Solution Cost (in sec.)
min. shift 10.00 2.51
30 POWs min. costs 4475.00 2.48
min. comb 4485.00 2.52
min. shift 12.00 4.90
38 POWs min. costs 5615.00 5.54
min. comb 5627.00 4.94
min. shift 17.00 6.41
50 POWs min. costs 8420.00 6.50
min. comb 8437.00 6.49
min. shift 23.00 344242.92
70 POWs min. costs
min. comb
intractability of the problem, feasible solutions of good quality for large instances can be obtained in a reasonable computational time only by applying a heuristic technique.
2 Greedy randomized adaptive search procedure
Greedy Randomized Adaptive Search Procedure (GRASP) is a constructive multi-start metaheuristic which has been applied to a wide range of well known combinatorial optimization problems, including academic and industrial problems in scheduling, routing, logic, partitioning, location and layout, graph theory, assignment, manufacturing, transportation, telecommunications, electrical power systems, and VLSI
A Bus Driver Scheduling Problem: a new mathematical model 451
algorithm grasp(MaxIter, , c) 1 xb := ;
2 for k = 1 to MaxIter do
3 x :=ConstructGreedyRandomizedSolution();
4 x :=LocalSearch(x);
5 if (c x < c xb) then xb := x;
6 endfor
7 return(xb);
end grasp
Fig. 3 General GRASP procedure for a minimization problem
design (see, for example, Feo and Resende 1989, 1995; Festa and Resende 2002, 2009a, 2009b).
At each iteration, GRASP produces a new feasible solution x and applies a local search procedure to identify in N (x) (the neighborhood of the current point x) a
better feasible solution. Each GRASP iteration consists of two phases (see Fig. 3):
1. a construction phase, where a feasible solution is produced;2. a local search phase, where a local optimum in the neighborhood of the current solution is sought.
The basic GRASP construction phase is similar to the semi-greedy heuristic proposed by Hart and Shogan (1987).
Since experience shows that the better the feasible solution x is the better the neighbor solution x and the output solution xb results, the construction phase of a
GRASP procedure (line 3) aims at nding a good starting solution x (for the local search). This is achieved by adopting a randomized and adaptive greedy strategy. Starting from an empty solution, a new candidate element to the current partial solution is added until a complete feasible solution is obtained. The choice of which new element to add is determined by the order of all candidate elements in a candidate list J . This order reects a prexed greedy criterion based on the myopic benet connected to the selection of that particular element. However, this benet is not constant, but adaptive, and it is updated at each iteration of the construction phase to take into account the previous selected elements. The probabilistic component of the construction phase is in the random choice of one of the best candidates in the list; therefore, not necessarily the best candidate will be added. The set of these good candidates is called Restricted Candidate List (RCL); clearly RCL J and within the
RCL an element is randomly selected. In Fig. 3, as stopping criterion, the reaching of a predened maximum number of iterations MaxIter is used, similarly to other meta-heuristics.
3 GRASP for the bus driver scheduling problem
The use of GRASP for the BDSP has been already proposed in literature. Souza et al. (2003), for instance, have suggested a hybrid approach to solve School Timetabling
452 R. De Leone et al.
Problems, that uses a greedy randomized construction phase to obtain a feasible solution, which is then followed by a Tab Search procedure.
Sosnewska (2000), instead, describes two heuristic procedures based on Simulated Annealing and GRASP for a simplied Fleet Assignment Problem. Both heuristics are based on swapping parts of sequence of ight legs assigned to an aircraft (rotation cycle) between two randomly chosen aircrafts.
Argello et al. (1997) have proposed a neighborhood search technique that uses a different approach for constructing the initial feasible solution. Moreover, two types of partial route exchange operations are proposed. The rst operation exchanges ight sequences with identical endpoints; in the second operation, the exchanged sequence of ights must have the same origination airport, but the termination airports are swapped.
The rst attempt to apply GRASP to the BDSP, that is the core of our investigation, is done by Loureno et al. (2001). They have used GRASP not only as a solution method to solve the BDSP, but also as a procedure inside a multi-objective Tab Search and Genetic Algorithms. In the construction phase, they use a greedy criterion based on the costs associated with the shifts. The local search procedure utilizes a 1-exchange neighborhood. The computational results are analyzed according to the different meta-heuristics applied to real instances. These methods have been successfully incorporated in the GIST Planning Transportation Systems. In the next subsection, we describe GRASP for BDSP applied to our model.
3.1 GRASP construction phase
The GRASP construction phase builds a feasible schedule T , i.e., a set of feasible shifts Tk, by selecting nk compatible Pieces-Of-Work, one at a time, until all Pieces-
Of-Work have been assigned.
The restricted candidate list depends on a parameter that is randomly selected in the interval [0, 1] and this value is not changed during the construction phase.
The value of reects the ratio of randomness versus greediness in the construction process. A value = 1 corresponds to a pure random selection, i.e., between all
compatible Pieces-Of-Work we select in random way a Piece-Of-Work to be added to the partial solution, whereas = 0 leads to a pure greedy selection, i.e., between all
compatible Pieces-Of-Work we select a candidate for which the difference between its starting time and the ending time of previous Piece-Of-Work is minimum.
The solution T is initially empty and the set J of candidate Pieces-Of-Work is the set of all Pieces-Of-Work. A candidate list is constructed for each Piece-Of-Work according to pairwise compatibility.
Initially, we sort the Pieces-Of-Work by the time of departure, and then we select the j-th (1 j |J | 1) Piece-Of-Work to be added to the solution. The restricted
candidate list RCL includes all Pieces-Of-Work in the candidate set J with time tj
t + (t t), where
t = min
j
{tsj+1 tej } and t = max j
{tsj+1 tej }.
A Bus Driver Scheduling Problem: a new mathematical model 453
Then, a Piece-Of-Work j RCL is randomly selected and added to the partial so
lution. Once the Piece-Of-Work j is selected, the set of Pieces-Of-Work must be adjusted to take into account that j is now part of the current solution and must be removed from the current set of candidates.
The construction procedure is adaptive because, starting from the partial solution, each time a new Piece-Of-Work is added, we rebuild the RCL, taking into account the characteristics of the specic element added to the current partial solution. The set of remaining candidates may change, because some Pieces-Of-Work may be not anymore compatible with the new choice.
Once the current shift is completed, a new shift is constructed using the same steps. The updating procedure for the candidate list is the computational bottleneck of the construction phase. The procedure ends when all Pieces-Of-Work have been assigned.
3.2 GRASP local search phase
Starting from the feasible solution obtained in the construction phase, the local search procedure is applied. In this phase a neighborhood of the current solution is dened and a better trial solution is searched.
The neighborhood structures depend on the problem to be solved and tting efcient neighborhood functions that with high probability lead to high quality local optima can be viewed as one of the major challenges of local search procedure design. Often, for the same problem several different neighborhood functions have been proposed and tested to experimentally validate their efciency.
For the BDSP, we have dened and used three different neighborhoods: a 1-swap neighborhood, a variable neighborhood swap, and an extension of the latter. In the rst case, we only interchange compatible Pieces-Of-Work, while the variable neighborhood swap is based on the interchange of compatible partial shifts (a partial shift is a sequence of compatible Pieces-Of-Work).
3.2.1 1-swap neighborhood
A feasible solution T = {T1, T2, . . . , TN} corresponds to a set of N shifts with
N = |K|, where the shift Tk is a set of rk Pieces-Of-Work (POWs):
T =
Given T = {T1, T2, . . . , TN} we dene a neighborhood N (T ) as the set of feasible
neighbor solutions T that can be obtained selecting two shifts Tk, Ti T , two Pieces-
Of-Work POWh Tk and POWl Ti, and interchanging the assignment of the two
Pieces-Of-Work, i.e. T k = Tk \ POWh POWl, while T i = Ti \ POWl POWh.
In order to preserve feasibility of the neighbor solution generated so far, POWl and POWh have to be compatible.
N
[uniondisplay]
k=1
rk
[uniondisplay]
j=1
Tk, Tk =
POWj .
454 R. De Leone et al.
Formally, N (T ) is dened as follows:
N(T ) = [braceleftbig]T = {
T 1, T 2, . . . , T N } | i = 1, 2, . . . , N 1,
k = 1, 2, . . . , N, k > i,
s = 1, 2, . . . , N,
l = 1, 2, . . . , ri,
h = 1, 2, . . . , rk,
T s = Ts s = i, k
T k = Tk \ POWh POWl, T i = Ti \ POWl POWh[bracerightbig].
Note that, the above dened neighborhood N (T ) is a variant of the classical swap
neighborhood where we exchange compatible Pieces-Of-Work, and shifts with better costs can thus be found. However, this technique does not reduce the number of shifts, since each element in N (T ) is still made of N shifts.
3.2.2 Variable neighborhood swap
An alternative neighborhood structure is the Variable Neighborhood Swap. Given a feasible solution T = {T1, T2, . . . , TN}, we dene a neighborhood N1(T ) as the set
of feasible neighbor solutions T that can be obtained selecting two shifts Tk, Ti T ,
k, i {1, 2, . . . , N = |K|}, k = i, and interchanging two sequences of Pieces-Of-
Work not necessarily of the same length but preserving compatibility. In particular, we decompose Tk in partial shifts, each having hk and rk Pieces-Of-Work, respectively. In more detail, assuming that hk rk, Tk is decomposed as follows:
Tk1 =
A similar decomposition can be applied to Ti T , i = k to obtain Ti1 and Ti2 and
then the interchange is performed as shown in Fig. 4.
Fig. 4 Interchange operation for the variable neighborhood swap
hk
[uniondisplay]
j=1
POWj , Tk2 =
rk
[uniondisplay]
j=hk+1
POWj .
A Bus Driver Scheduling Problem: a new mathematical model 455
Formally, the neighborhood structure is dened as follows:
N1(T ) = [braceleftbig]T = {
T 1, T 2, . . . , T N } | i = 1, 2, . . . , N 1,
i < k N,
s = 1, 2, . . . , N,
i1 = 1, 2, . . . , hi,
i2 = hi + 1, . . . , ri,
k1 = 1, 2, . . . , hk,
k2 = hk + 1, . . . , rk, T s = Ts, s = i, k,
T k = Tk1 Ti2,
T i = Ti1 Tk2[bracerightbig].
Unlike the 1-swap neighborhood, this technique not only guarantees the possibility of constructing shifts of lower cost, but can also reduce the number of shifts.
In exploring this neighborhood, the following two cases are of particular interest:
hi = 0, hk = rk Ti1 = , Tk2 = , T k = Tk1 Ti2 = Tk Ti,
T i = ;
hi = ri, hk = 0 Ti2 = , Tk1 = , T i = Ti1 Tk2 = Ti Tk,
T k = .
In both cases, shift i and shift k are merged in a single shift (while feasibility is still satised).
Moreover, the following cases correspond to the construction of feasible shifts by combining original shifts in different ways.
0 < hi < ri, 0 < hk < rk T i = Ti1 Tk2, T k = Tk1 Ti2,
0 < hi < ri, hk = 0
Tk1 = ,T i = Ti1 Tk2 = Ti1 Tk,
T k = Ti2,
0 < hi < ri, hk = rk
Tk2 = ,T i = Ti1 Tk2,
T k = Tk1 Ti2 = Tk Ti2,
456 R. De Leone et al.
Fig. 5 Interchange operations for the variable neighborhood swap with > 1
hi = 0, 0 < hk < rk
Ti1 = , T i = Tk2,
T k = Tk1 Ti2 = Tk1 Ti,
Ti2 = ,T i = Ti1 Tk2 = Ti Tk2,
T k = Tk1.
In general, if we decompose Tk in + 1 partial shifts as follows:
Tk1 =
h1k
[uniondisplay]
j=1
hi = ri, 0 < hk < rk
POWj , Tk2 =
h2k
[uniondisplay]
j=h1k+1
POWj , . . . , Tk+1 =
nk
[uniondisplay]
j=hk+1
POWj ,
with h1k h2k h( 1)k hk nk and apply the same decomposition
also to Ti, then a set of interchanges can be performed as shown in Fig. 5.
Formally, the neighborhood structure is dened as follows:
N(T ) = [braceleftbig]T = {T 1, T 2, . . . , T N } | i = 1, 2, . . . , N 1,
i < k N,
i1 = 1, 2, . . . , h1i,
i2 = h1i + 1, . . . , h2i, ...
i = h( 1)i + 1, . . . , hi,
k1 = 1, 2, . . . , h1k,
k2 = h1k + 1, . . . , h2k, ...
k = h( 1)k + 1, . . . , hk,T s = Ts s = 1, 2, . . . , N, s = i, k (20)
T k = Tk1 Ti2 Tk3 Ti Tk+1,
= 2l, l
N\ {0}, (21)
A Bus Driver Scheduling Problem: a new mathematical model 457
T i = Ti1 Tk2 Ti3 Tk Ti+1,
= 2l, l
N\ {0}, (22)
T k = Tk1 Ti2 Tk3 Tk Ti+1,
= 2l + 1, l
N, (23)
T i = Ti1 Tk2 Ti3 Ti Tk+1,
= 2l + 1, l
N
. (24)
Note that, for = 1, the neighborhood N(T ) is exactly the neighborhood N1(T )
previously dened (see p. 455). For > 1, N(T ) can be easily obtained from N1(T ). In fact,when is even, Tk+1 and Ti+1 are the last partial shifts of T k (21) and T i (22),
respectively;when is odd, Ti+1 and Tk+1 are the last partial shifts of T k (23) and T i (24),
respectively.
4 Computational results
In this section, we report computational results for real-world problems and comparisons between the solution produced by an exact method based on Set Covering and by the GRASP procedure. The exact method we used solves the problem in two steps: at rst it solves the Vehicle Scheduling Problem using a formulation similar to the one proposed by Lbel (1998), generating a set of running boards (Vehicle Schedule). Then, the running boards are divided, generating the Pieces-of-Work. The Pieces-Of-Work are combined to obtain feasible shifts, using a k-decision tree: as k increases, the number of generated shifts increases, too. The upper bound for the number of generated shifts is xed to 2 millions. Once the feasible shifts have been generated, we solve a classical Set-Covering problem using Cplex 9.1. The parameter k controls the total number of columns (feasible shifts generated). Starting from a partial shift we construct k new partial shifts by adding to the current shift a new Piece-of-Work. This procedure is iterated until a feasible shift is obtained and the corresponding column is added. In this kbranches tree, trimming occurs (and therefore
the corresponding column is not added) if the cost for the shift is above a pre-specied limit. In this way, only a small subset of good shifts are included in the optimization problem.
With respect to the model provided in Sect. 1, for this Set Covering formulation and the GRASP method a more complex objective function is used to take more precisely into account some quality requirements of the solution. For example, a specic cost can be assigned to each generated feasible shift, we consider, in addition to the quantities already included in the model in Sect. 1, costs related to the effective length of the idle times and breaks and costs related to extra working time and overspread.
All numerical tests were carried out on a Pentium 4 with CPU 3.20 GHz and with 1.00 GB RAM. Both exact method and GRASP procedure were coded in C and compiled with DEV-C++ (2005) version 5.0 beta 9.2.
458 R. De Leone et al.
The real data sets have been provided by the PluService Srl. The results are summarized in Table 3. For each problem instance, we report for both algorithms the total number of trips, the value of the objective function, the total number of shifts, the total number of vehicles (running boards), the total number of the Pieces-Of-Work, and the time in seconds for obtaining the solution. We set the GRASP MaxIter parameter equal to 1000. For each algorithm, the last column reports the average efciency of the schedule, i.e., a measure of the relative efciency calculated as the mean value of working times per spreadover unit. Note that some problem instances could not be solved exactly while for some others the special character (*) indicates that the exact method was not able to nd the optimal solution in a reasonable computational time. For such instances, Table 3 shows the rst feasible integer solution found by the exact method using a smaller value of k.
4.1 Probability distribution of solution time in GRASP for BDSP
In this subsection, we describe a procedure recently proposed by Aiex et al. (2007) to create time-to-target solution value plots for measured CPU times that are assumed to t a shifted exponential distribution. This is often the case in local search based heuristics for combinatorial optimization, such as Simulated Annealing, Genetic Algorithms, Iterated Local Search, Tab Search, WalkSAT, and GRASP. Such plots are used to compare algorithms for combinatorial optimization problems; in particular, this technique has been used for comparing different heuristics, the same algorithm on different instances, parallel implementation using several number of processors or parallelization strategies, algorithms using different strategies and an algorithm using different parameter settings (for more details the reader can refer to Aiex et al. 2007).
The hypothesis is that the run times t a two parameter exponential distribution. We consider two test problems out of the 16 that we have solved and we measure the time needed to nd a value of the objective function which is equal or better than a given target value. The analysis has been performed using a target value (the best value produced by GRASP performing 1000 iterations). The rst set is made of 76 trips and the target value is 15438086, while the second of 104 trips and the target value is 13917766. We run the GRASP procedure for n = 100 independent times for
each instance/target pair with different seed for the number generator.
Following Aiex et al. (2000), we compare the empirical and theoretical distributions using a standard graphical methodology for data analysis based on Chambers et al. (1983).
For each instance, we sort in increasing order the running times ti to which a probability pi = (i 12)/n is associated and we draw the points zi = (ti, pi), i =
1, . . . , n.
A theoretical Q-Q plot is obtained by drawing the quantiles of an empirical distribution against the quantiles of a theoretical distribution of the data. In other words, we rst sort the data in increasing order and then we calculate the quantiles of the theoretical exponential distribution and nally we draw the data against the theoretical quantiles.
To test if the Q-Q plots follow the progress of the line in Fig. 6, we apply a variability information to each point. More precisely, we calculate an interval for the
A Bus Driver Scheduling Problem: a new mathematical model 459
Table 3 Computational results obtained by an exact method and by GRASP on real-world BDSP problems provided by PluService Srl
Problem Method Cost no of no of no of time eff.
shifts vehicles POWs in sec. %
24 trips exact 5228983 4 3 27 0.77 74.43
grasp 5370930 4 3 27 0.00 81.50
60 trips(*) exact 13384164 9 3 65 124.80 68.83
(k = 10)grasp 8541870 7 5 65 0.00 45.43
62 trips exact 14662692 14 12 74 2.98 56.25
grasp 15412000 14 12 74 1.00 56.25
63 trips exact 14712334 13 13 76 2.55 54.74
grasp 14846189 13 13 76 1.00 72.92
69 trips exact 24372774 15 12 81 2.17 61.80
grasp 27799160 16 12 81 0.00 51.88
72 trips exact 12859590 12 12 84 0.22 40.11
grasp 17002600 12 12 84 0.00 48.25
104 trips exact 15811450 15 33 114 3090.72 73.77
grasp 18303800 17 33 114 5.00 69.00
110 trips(*) exact 17902000 17 9 119 1655.19 65.62
(k = 5)grasp 16189400 14 9 119 4.00 73.21
136 trips exact 5 141
grasp 15038200 14 5 141 4.00 100.00
142 trips(*) exact 43012665 26 23 165 949.47 66.29
(k = 3)grasp 30108700 27 23 165 13.00 61.37
150 trips(*) exact 43097989 28 24 173 214.31 69.04
(k = 5)grasp 30915000 29 24 173 14.00 60.76
153 trips(*) exact 22 175
grasp 30582000 28 22 175 22.00 66.64
153 trips(*) exact 26162329 25 20 173 740.97 57.73
(k = 5)grasp 28294400 26 20 173 19.00 59.20
460 R. De Leone et al.
Table 3 (Continued)
Problem Method Cost no of no of no of time eff.
shifts vehicles POWs in sec. %
158 trips(*) exact 39467120 25 21 179 403.36 68.18
(k = 3)grasp 27187800 25 21 179 3.00 60.72
161 trips(*) exact 65751000 44 34 195 19738.39 50.79
(k = 10)grasp 45454000 43 34 195 59.00 64.11
estimate zi, i = 1, . . . , n of the standard deviation in the vertical direction from the
line tted to the plot. In Fig. 6 we draw the Q-Q plot with this additional variability information.
Finally, in Fig. 6 we show a superimposed plot of the empirical and theoretical distributions. All analysis can be executed by using the Perl language program (see for more detail Aiex et al. 2007) to create time-to-target solution plots for measured run times.1 With regards the set of data made of 76 trips and target value equal to 15438086, we conclude that the probability of the heuristic nding a solution at least as good as the target value in at most 100 seconds is about 70%, in at most 150 seconds is about 80%, and in at most 200 seconds is about 90%. Moreover, for the second set of data made of 104 trips and target value is 13917766, the probability of nding a solution at least as good as the target value in at most 1000 seconds is about 60%, in at most 1500 seconds is about 75%, and in at most 2000 seconds is about 90%.
4.2 A numerical comparison for random data instances
Huisman et al. (2005)2 provided two different models and algorithms (based on a combination of column generation and Lagrangian relaxation) for the integration of the Vehicle and Crew Scheduling in the Multiple-Depot case, and compare those integrated approaches with the traditional sequential approach.
They consider two types of instances (1 and 2), which differ in the travel speed. As the travel speed increases, trips are shorter and vehicles as well as drivers will cover more trips.
In their article, they considered six cases: 3 instances, where there are four lines (from A to B, A to C, A to D and B to C) and 3 instances with ve lines (adding to the four lines previously seen a line from C to E). All these points are relief locations.
Huisman et al. (2005) have tested the algorithms on 10 instances randomly generated (10, 20 and 40 trips per line/direction with four and ve lines). Therefore, the total number of trips ranges from 80 to 400. The 2 depots case has been executed for
1The Perl program can be downloaded from http://www.research.att.com/~mgcr/tttplots
Web End =http://www.research.att.com/~mgcr/tttplots .
2We use the random data instances available at http://www.few.eur.nl/few/people/huisman/instances.htm
Web End =http://www.few.eur.nl/few/people/huisman/instances.htm .
A Bus Driver Scheduling Problem: a new mathematical model 461
Fig. 6 Probability distribution of solution time in GRASP for BDSP
all the instances of both 1 and 2, while the 4 depots case has not been executed for the 320 and 400 trips instances.
In Tables 45 and 89, we report the results obtained in Huisman et al. (2005) for instances of both type with 2 and 4 depots, respectively, for the traditional sequential
462 R. De Leone et al.
Table 4 Average results random data instances2 depotstype 1
trips 80 100 160 200 320 400
seq. vehicles 9.2 11.0 14.8 18.4 26.7 32.9
drivers 23.8 29.0 35.9 44.5 60.8 74.9
total 33.0 40.0 50.7 62.9 87.5 107.8
int. 1 vehicles 9.2 11.0 14.8 18.4 26.7 32.9
drivers 20.6 24.8 33.5 40.7 60.1 73.2
total 29.8 35.8 48.3 59.1 86.8 106.1
int. 2 vehicles 9.2 11.0 14.8 18.4 26.7 32.9
drivers 20.6 24.6 33.5 41.0 60.0 74.2
total 29.8 35.6 48.3 59.4 86.7 107.1
Table 5 Average results random data instances2 depotstype 2
trips 80 100 160 200 320 400
seq. vehicles 11.3 13.8 19.3 24.4 35.8 44.2
drivers 26.9 32.9 44.4 54.7 79.0 96.8
total 38.2 46.7 63.7 79.1 114.8 141.0
int. 1 vehicles 11.3 13.8 19.3 24.4 35.8 44.2
drivers 24.9 29.1 42.3 51.4 77.8 95.0
total 36.2 42.9 61.6 75.8 113.6 139.2
int. 2 vehicles 11.3 13.8 19.3 24.4 35.8 44.2
drivers 24.7 29.1 42.6 52.2 78.0 95.6
total 36.0 42.9 61.9 76.6 113.8 139.8
approach and the two integrated approaches. We report the number of trips, the average number of vehicles, the average number of drivers and the sum of both vehicles and drivers.
We also have used these same random instances in our sequential approach. First, we have solved the Vehicle Scheduling Problem producing a set of feasible vehicle schedules and then, we have solved the Crew Scheduling Problem with pure GRASP, producing the feasible shift schedules. While Huisman et al. (2005) have analyzed ve different shift types, the feasible shift schedules we have generated are sets of Pieces-Of-Work with no particular properties; our working time corresponds to 6 hours and a half, while the spreadover is 12 hours.
Tables 67 and 1011 show the results we have obtained when applying pure GRASP to the same random instances used by Huisman et al. (2005) with 2 and 4 depots, respectively. Here, we see that the average number of vehicles is in essence the same as in Huisman et al. (2005) for both types 1 and 2, and both in case of 2 and 4 depots. When analyzing the rst case we see an increase of 0.1 percent in two instances out of six, while in the second case we obtain a decrease of 0.2 percent in one instance out of six and this result holds both in case of 2 and 4 depots.
A Bus Driver Scheduling Problem: a new mathematical model 463
Table 6 Average results random data instances2 depotstype 1
trips 80 100 160 200 320 400
seq. vehicles 9.3 11.0 14.8 18.5 26.7 32.9
drivers 20.3 23.7 30.7 37.6 53.6 65.7
total 29.6 34.7 45.5 56.1 80.3 98.6
time 17.0 15.0 53.6 71.1 157.2 204.0
total time 33.7 43.8 117.7 143.2 366.9 458.9
Table 7 Average results random data instances2 depotstype 2
trips 80 100 160 200 320 400
seq. vehicles 11.3 13.6 19.3 24.4 35.8 44.2
drivers 22.3 26.7 37.1 45.8 67.1 83.4
total 33.6 40.3 56.4 70.2 102.9 127.6
time 14.9 18.2 45.1 63.0 127.9 267.6
total time 29.8 41.9 104.0 141.1 325.6 455.9
Table 8 Average results random data instances4 depotstype 1
trips 80 100 160 200
seq. vehicles 9.2 11.0 14.8 18.4
drivers 25.8 29.9 38.8 47.1
total 35.0 40.9 53.6 65.5
int. 1 vehicles 9.2 11.0 14.8 18.4
drivers 20.5 25.3 34.1 41.6
total 29.7 36.3 48.9 60.0
int. 2 vehicles 9.2 11.0 14.8 18.4
drivers 20.4 25.2 34.7 42.0
total 29.6 36.2 49.5 60.4
As far as the average number of drivers is concerned, we obtain different results due to the fact that, both in case 1 and 2, with 2 or 4 depot, respectively, we generate shifts of a different type. Looking at Tables 67 and 1011, in case of 4 depots and for instances with less than 160 trips, the average number of drivers is less than or equal to the average number of drivers in case of 2 depots.
Tables 67 and 1011 contain also information about running times in seconds. All tables report for all input instances the mean time (time) needed to nd the better solution and the mean time (total time) needed to run a total of 1000 iterations. Looking at the results, our GRASP nds the output solution in at most 50% out of the total running time.
464 R. De Leone et al.
Table 9 Average results random data instances4 depotstype 2
trips 80 100 160 200
seq. vehicles 11.3 13.8 19.3 24.4
drivers 28.3 34.1 45.9 56.8
total 39.6 47.9 65.2 81.2
int. 1 vehicles 11.3 13.8 19.3 24.4
drivers 25.1 30.3 42.9 52.1
total 36.4 44.1 62.2 76.5
int. 2 vehicles 11.3 13.8 19.3 24.4
drivers 24.8 30.0 44.0 53.6
total 36.1 43.8 63.3 78.0
Table 10 Average results random data instances4 depotstype 1
trips 80 100 160 200
seq. vehicles 9.3 11.0 14.8 18.5
drivers 19.0 23.7 30.4 38.9
total 28.3 34.7 45.2 57.4
time 25.4 22.1 68.6 55.1
total time 55.3 52.4 129.4 163.7
Table 11 Average results random data instances4 depotstype 2
trips 80 100 160 200
seq. vehicles 11.3 13.6 19.3 24.4
drivers 22.2 26.3 36.5 46.6
total 33.5 39.9 55.8 71.0
time 25.4 23.0 82.5 78.6
total time 48.4 48.4 121.5 149.2
5 Conclusions and future works
This paper deals with the problem of determining the best scheduling for Bus Drivers,i.e., with a N P-hard problem consisting of nding the minimum number of drivers
to cover a set of Pieces-Of-Work subject to a variety of rules and regulations that must be enforced such as the spreadover and the working time. A new mathematical model has been formulated for a special variant of the problem faced by Italian transportation companies that have to satisfy particular collective agreements and labour rules. Since this model can only be usefully applied to small or medium size problem instances, to solve large problem instances, a Greedy Randomized Adaptive Search Procedure (GRASP) has been proposed and numerical results carried out on real-world BDSP instances provided by PluService Srl show the effectiveness of the designed metaheuristic approach.
A Bus Driver Scheduling Problem: a new mathematical model 465
Since recent literature has shown that GRASP benets from the combination with other meta-heuristics (e.g. Festa et al. 2002), as future work we are planning without adding much additional computational burden to design new hybrid heuristics that combine GRASP with other modern and efcient meta-heuristics, such as VNS (Variable Neighborhood Search) and PR (Path-Relinking).
Acknowledgement The authors would like to thank the anonymous reviewers for their comments and suggestions which have been revealed useful to improve both quality and readability of the manuscript.
References
Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: Probability distribution of solution time in GRASP: An experimental investigation. J. Heuristics 8, 200212 (2000)
Aiex, R.M., Resende, M.G.C., Ribeiro, C.C.: TTTplots: a Perl program to create time-to-target plots.
Optim. Lett. 1, 355366 (2007)
Argello, M., Bard, J., Yu, G.: A GRASP for aircraft routing in responce to groundings and delays. J. Combin. Optim. 1, 211228 (1997)
Carraresi, P., Nonato, M., Girardi, L.: Network models, Lagrangian relaxation and subgradients bundle approach in crew scheduling problems. In: Daduna, J.R., Branco, I., Paixo, J.R. (eds.) Computer-Aided Transit Scheduling, Lisbon, pp. 187212. Springer, Berlin (1993)
Chambers, J.M., Cleveland, W.S., Kleiner, B., Tukey, P.A.: Graphical Methods for Data Analysis. Chapman & Hall, London (1983)
Cunha, J.F., Sousa, J.P.: The bus stops hereGIST: A decision support system problem. OR/MS Today
27(2), 324335 (2002)
Curtis, S.D., Smith, B.M., Wren, A.: Forming bus driver schedules using constraint programming. Technical Report, University of Leeds, School of Computer Studies, Report 99.05 (1999)
Daduna, J.R., Wren, A.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 308. Springer, Heidelberg (1988)
Daduna, J.R., Branco, I., Paixo, J.M.P.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430. Springer, Heidelberg (1995)
Desaulniers, G., Hickman, M.D.: Public transit. Technical Report, Les Cahiers du GERAD, G-2003-77
(2003)
Desrochers, M., Rousseau, J.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and
Mathematical Systems, vol. 386. Springer, Heidelberg (1992)
Desrochers, M., Soumis, F.: A column generation approach to the urban transit crew scheduling problem.
Transp. Sci. 23(1), 113 (1989)
DEV-C++: http://www.bloodshed.net/dev/index.html
Web End =http://www.bloodshed.net/dev/index.html (2005)
Dias, T.G., Sousa, J.P., Cunha, J.F.: A genetic algorithm for the bus driver scheduling problem. In: 4th
Metaheuristics International Conference (2001)
Dias, T.G., Sousa, J.P., Cunha, J.F.: A multiobjective genetic algorithm for the bus driver scheduling problem. In: The 6th Metaheuristics International Conference (2005)
Feo, T.A., Resende, M.G.C.: A probabilistic heuristic for a computationally difcult set covering problem.
Oper. Res. Lett. 8, 6771 (1989)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedures. J. Glob. Optim. 6, 109133
(1995)
Festa, P., Resende, M.G.C.: GRASP: An annotated bibliography. In: Ribeiro, C.C., Hansen, P. (eds.) Essays and Surveys in Metaheuristics, pp. 325367. Kluwer Academic, Dordrecht (2002)
Festa, P., Resende, M.G.C.: An annotated bibliography of GRASPPart I: algorithms. Int. Trans. Oper.
Res. 16(1), 124 (2009a)
Festa, P., Resende, M.G.C.: An annotated bibliography of GRASPPart II: applications. Int. Trans. Oper.
Res. 16(2), 131172 (2009b)
Festa, P., Pardalos, P., Resende, M., Ribeiro, C.: Randomized heuristics for the max-cut problem. Optim.
Methods Softw. 7, 10331058 (2002)
Fischetti, M., Martello, S., Toth, P.: The xed job schedule problem with spread-time constraints. Oper.
Res. 35, 849858 (1987)
466 R. De Leone et al.
Fischetti, M., Martello, S., Toth, P.: The xed job schedule problem with working-time constraints. Oper.Res. 37, 395403 (1989)
Fores, S.: Column generation approaches to bus driver scheduling. Ph.D. Thesis, The University of Leeds,School of Computer Studies (1996)
Fores, S., Proll, L., Wren, A.: Experiences with a exible driver scheduler. In: Vo, S., Daduna, J.R. (eds.)Computer-Aided Scheduling of Public Transport, pp. 137152. Springer, Berlin (2001)
Fores, S., Proll, L., Wren, A.: TRACS II: a hybrid IP/heuristic driver scheduling system for public transport. J. Oper. Res. Soc. 53, 10931100 (2002)
GAMS: General Algebraic Modelling System. http://www.gams.com/docs/gams/document.html
Web End =http://www.gams.com/docs/gams/document.html (2005) Hart, J., Shogan, A.: Semi-greedy heuristics: an empirical study. Oper. Res. Lett. 6, 107114 (1987) Hartley, T.: A glossary of terms in bus and crew scheduling. In: Wren, A. (ed.) Computer Scheduling of
Public Transport, pp. 353359. North-Holland, Amsterdam (1981)
Huisman, D.: Integrated and dynamic vehicle and crew scheduling. Ph.D. Thesis, Erasmus UniversiteitRotterdam (2004)
Huisman, D., Freling, R., Wagelmans, A.P.M.: Multiple-depot integrated vehicle and crew scheduling.Transp. Sci. 39(4), 491502 (2005)
Kroon, L., Fischetti, M.: Crew scheduling for Netherlands railways destination: customer. In: Vo, S., Daduna, J.R. (eds.) Computer-Aided Scheduling of Public Transport, pp. 181201. Springer, Berlin (2001)
Lbel, A.: Vehicle scheduling in public transit and Lagrangian pricing. Oper. Res. 44(12), 16371649(1998)
Loureno, H., Paixo, J., Portugal, P.: Multiobjective metaheuristics for the bus-driver scheduling problem.Transp. Sci. 35, 331343 (2001)
Mesquita, M., Paias, A., Respcio, A.: Branching approaches for integrated vehicle and crew scheduling.Public Transp. 1, 2137 (2009)
Moz, M., Respcio, A., Pato, M.V.: Bi-objective evolutionary heuristics for bus driver rostering. PublicTransp. 1, 189210 (2009)
Portugal, R., Loureno, H., Paixo, J.: Driver scheduling problem modelling. Public Transp. 1, 103120(2009)
Rousseau, J.M.: Computer Scheduling of Public Transport 2. North-Holland, Amsterdam (1985) Rousseau, J.M., Blais, J.Y.: Hastus: An interactive system for buses and crew scheduling. In: Rousseau,
J.M. (ed.) Computer Scheduling of Public Transport 2, pp. 4560. North-Holland, Amsterdam (1985) Rousseau, J.M., Desrosiers, J.: Results obtained with crew-opt: a column generation method for transit crew scheduling. In: Daduna, J.R., Branco, I., Paixo, J.R. (eds.) Computer-Aided Transit Scheduling, Lisbon, pp. 349358. Springer, Berlin (1993)
Shen, Y.: Tab search for bus and train driver scheduling with time windows. Ph.D. Thesis, The University of Leeds, School of Computing (2001)
Sosnewska, D.: Optimization of a simplied eet assignment problem with metaheuristics: simulated annealing and GRASP. In: Pardalos, P.M. (ed.) Approximation and Complexity in Numerical Optimization: Continuous and Discrete Problems, pp. 477488. Kluwer Academic, Dordrecht (2000)
Souza, M., Maculan, N., Ochi, L.: A GRASP-tab search algorithm for school timetabling problems. In: Resende, M., Sousa, J. (eds.) Metaheuristics: Computer Decision-Making, pp. 659672. Kluwer Academic, Dordrecht (2003)
Vo, S., Daduna, J.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and MathematicalSystems, vol. 505. Springer, Heidelberg (2001)
Wilson, N.H.M.: Computer-Aided Transit Scheduling. Lecture Notes in Economics and MathematicalSystems, vol. 471. Springer, Heidelberg (1999)
Wren, A.: Computer Scheduling of Public Transport. North-Holland, Amsterdam (1981)
Wren, A.: Scheduling vehicles and their drivers-forty years experience. Technical Report, University ofLeeds, School of Computing Research Report Series, Report 2004.03 (2004)
Wren, A., Rousseau, J.M.: Bus driver scheduling probleman overview. In: Daduna, J., Branco, I., Paixo, J. (eds.) Computer-Aided Transit Scheduling. Lecture Notes in Economics and Mathematical Systems, vol. 430, pp. 173187. Springer, Heidelberg (1995)
Springer Science+Business Media, LLC 2011