# A Column Generation Based Hyper-Heuristic to the Bus Driver Scheduling Problem

Authors: Hong Li; Ying Wang; Shi Li; Sujian Li
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

Public transit providers are facing continuous pressure to improve service quality and reduce operating costs. Bus driver scheduling is among the most studied problems in this area. Based on this, flexible and powerful optimization algorithms have thus been developed and used for many years to help them with this challenge. Particularly, real-life large and complex problem instances often need new approaches to overcome the computational difficulties in solving them. Thus, we propose a column generation based hyper-heuristic for finding near-optimal solutions. Our approach takes advantages of the benefits offered by heuristic method since the column selection mode is driven by a hyper-heuristic using various strategies for the column generation subproblem. The performance of the proposed algorithm is compared with the approaches in the literature. Computational results on real-life instances are presented and discussed.


---

## Body

## 1. Introduction

The bus driver scheduling problem (BDSP) is an extremely complex and important part of the operational planning process of transport companies. Efficient schedules can make significant monetary savings for transportation operators since driver wages are a very large cost element. Furthermore, good crew planning ensures a high job satisfaction.The process of bus driver scheduling involves partitioning the vehicle work into a set of legal driver shifts that should reflect the operator’s definition of efficiency [1]. While the constraints according to labor rules and requirement differ from country to country, even company to company, the evaluation criteria and objectives may differ as well.A great deal of research efforts on this problem has been made in this area since the 1960s. Many scientific approaches and systems to bus diver scheduling have been reported in a series of workshops [2–6]. Useful review and relevant review to these approaches have been given by [7]. Among these planning and scheduling processes, driver scheduling remains to be a challenging problem, and new approaches have been constantly sought to solve this problem [8].Column generation is introduced by [9] and has been widely used in the past several years for problems in transportation, scheduling, and combinatorial optimization. The approach requires one to decompose the original problem into two problems, which are termed restricted master problem and subproblem, respectively. In the literature, column generation has been effectively applied to solve crew scheduling and other related problems (see [9–11]), particularly for real-world problems of bus driving scheduling (see [12]). However, it is well-known that one of the drawbacks of column generation is the so-called “tailing-off” effect: a lot of iterations that do not significantly modify the optimal value of the restricted master problem (RMP). Although successfully used, this method suffers from slow convergence that somewhat limits its efficiency and usability [13]. Meanwhile, hyper-heuristic is an emerging methodology in search and optimization [14]. Instead of using exact methods in most column generation, we propose a column generation based hyper-heuristic method for achieving good quality solutions in short running time.This paper is organized in the following way. In Section2, we give a problem definition of bus driver scheduling problem. A discussion of the proposed approach is given in Section 3. In Section 4, comparative results using real-life instance, some of which are large instances, are given. Finally, we conclude in Section 5.


## 2. The Bus Driver Scheduling Problem

### 2.1. Terminology

Before scheduling the drivers tasks, the vehicle routes have to be constructed. Atrip is a movement of a vehicle in a given path. It is the basic unit of service in the sense that each trip must be operated by a single vehicle. Avehicle block is a sequence of trips to be done by one vehicle from the time that it leaves the depot until it returns to the depot. From the viewpoint of driver scheduling, drivers can only be relieved at some designated places calledrelief points, which are represented by letter codes (A, B, and C) in Figure 1. The times when the vehicles are at the relief points, marked on the horizontal timescale, are known asrelief opportunities. The work between two consecutive relief opportunities on the same vehicle is calledpiece of work (or task) for the driver. The work of a driver in a day is known as aduty (or shift). Note that not all relief opportunities will be used to relieve drivers and therefore a driver may be covering a number of consecutive pieces of work, called aspell.Figure 1
Relationship in vehicle block.An example of a duty built between two vehicle blocks is given in Figure1. The duty is composed of two spells from the two vehicle blocks.According to which time period the duties cover, the legal duties can be classified to the following five types.Early Duty starts early in the morning taking the buses out of garage before the morning peak. The working time of a day that this duty covers is between 05:00 and 12:00.
Late Duty starts in the afternoon and ends in the night. The working time of a day that this duty covers is between 12:00 and 20:00.
Night Duty works in the late evening buses returning the buses to the garage. The working time of a day that this duty covers is between 22:00 and 05:00.
Day Duty starts in the morning and ends in the afternoon. The working time of a day that this duty covers is between 08:00 and 16:00.
Middle Duty works during the period of the morning and the evening peaks. The working time of a day that this duty covers has two parts. One is between 05:00 and 08:00 and the other is between 16:00 and 22:00.The user could impose certain constraints on any of these duties to ensure that the final schedule does not contain too many or too few duties of particular type. The constrains can be imposed either initially or when reoptimizing an existing solution.


### 2.2. Mathematical Formulation

The set covering model is the fundamental model of the bus driver scheduling. In the public transport such models have been popular for solving crew scheduling problems for many years [9, 15]. In the formulation adopted here, we will consider our approach based on the set covering formulation of the problem. Although the schedule must ultimately have only one duty assigned to each piece of work, it is better to allow the formulation to include the possibility of overcover and to use set covering rather than set partitioning. On one hand, integer solutions may have some constraints covered by two or more nonzero variables, which in scheduling terms would mean two or more duties assigned to the same piece of work. The reason for this is that there can be a danger that there may be no feasible solution that “fit-together” without causing any over-cover. On the other hand, the produced solutions do not usually have overcovered pieces of work; the set covering model most commonly results in two duties overlapping slightly. If overcover occurs, it can be easily eliminated by editing the schedule afterwards.LetN
=
{
D
1
,
D
2
,
D
3
,
…
,
D
n
} be the set of legal duties and M
=
1,2
,
…
,
m be the set of pieces of work to be covered. We can define the problem as the construction of a matrix, where drivers appear in columns and pieces of works in lines. For each element a
i
j
∈
0,1, i
∈
M, j
∈
N, a
i
j
=
1 indicates the duty j covers piece of work i, and it is 0 otherwise. It can be formulated as follows:(1)
min
⁡
W
1
∑
j
=
1
n
‍
c
j
x
j
+
W
2
∑
j
=
1
n
‍
x
jsubject to(2)
∑
j
=
1
n
‍
a
i
j
x
j
≥
1
,
i
∈
M
,
(3)
x
j
∈
0,1
,
j
∈
N
,where n is the number of duties; m is number of work pieces; c
j is the cost of duty j; x
j is equal to 1 if duty j is used in the solution and 0 otherwise. W
1 and W
2 are weight constants. Generally, the main objective of the transport company is to obtain a solution with a minimum number of duties. For this objective, we consider here W
2
≫
W
1.The constraints (2) indicate that each piece of work must be covered by at least one duty. We consider the costs c
j in our work based on [15]:(4)
c
j
=
OV
j
+
IT
j
,where(5)
OV
j
=
max
⁡
0
,
FT
t
lst
-
ST
t
fst
-
NWT
,
(6)
IT
j
=
max
⁡
0
,
NWT
-
FT
t
lst
-
ST
t
fst
+
⋯
∑
i
=
1
m
-
1
‍
max
⁡
0
,
ST
t
i
+
1
-
FT
t
i
,where c
j is the cost of the driver j;  OV
j is the extra-time over the normal time of work established by law for driver j (8 hours); IT
j is the idle time of driver j (time the driver is not working during his shift); NWT is the normal working time (8 hours); FT
(
t
i
) is the finish time of the task i;  ST
(
t
i
) is the start time of the task i;  t
fst is the first task of the j driver’s shift; t
lst is the last task of the j driver’s shift.


## 2.1. Terminology

Before scheduling the drivers tasks, the vehicle routes have to be constructed. Atrip is a movement of a vehicle in a given path. It is the basic unit of service in the sense that each trip must be operated by a single vehicle. Avehicle block is a sequence of trips to be done by one vehicle from the time that it leaves the depot until it returns to the depot. From the viewpoint of driver scheduling, drivers can only be relieved at some designated places calledrelief points, which are represented by letter codes (A, B, and C) in Figure 1. The times when the vehicles are at the relief points, marked on the horizontal timescale, are known asrelief opportunities. The work between two consecutive relief opportunities on the same vehicle is calledpiece of work (or task) for the driver. The work of a driver in a day is known as aduty (or shift). Note that not all relief opportunities will be used to relieve drivers and therefore a driver may be covering a number of consecutive pieces of work, called aspell.Figure 1
Relationship in vehicle block.An example of a duty built between two vehicle blocks is given in Figure1. The duty is composed of two spells from the two vehicle blocks.According to which time period the duties cover, the legal duties can be classified to the following five types.Early Duty starts early in the morning taking the buses out of garage before the morning peak. The working time of a day that this duty covers is between 05:00 and 12:00.
Late Duty starts in the afternoon and ends in the night. The working time of a day that this duty covers is between 12:00 and 20:00.
Night Duty works in the late evening buses returning the buses to the garage. The working time of a day that this duty covers is between 22:00 and 05:00.
Day Duty starts in the morning and ends in the afternoon. The working time of a day that this duty covers is between 08:00 and 16:00.
Middle Duty works during the period of the morning and the evening peaks. The working time of a day that this duty covers has two parts. One is between 05:00 and 08:00 and the other is between 16:00 and 22:00.The user could impose certain constraints on any of these duties to ensure that the final schedule does not contain too many or too few duties of particular type. The constrains can be imposed either initially or when reoptimizing an existing solution.


## 2.2. Mathematical Formulation

The set covering model is the fundamental model of the bus driver scheduling. In the public transport such models have been popular for solving crew scheduling problems for many years [9, 15]. In the formulation adopted here, we will consider our approach based on the set covering formulation of the problem. Although the schedule must ultimately have only one duty assigned to each piece of work, it is better to allow the formulation to include the possibility of overcover and to use set covering rather than set partitioning. On one hand, integer solutions may have some constraints covered by two or more nonzero variables, which in scheduling terms would mean two or more duties assigned to the same piece of work. The reason for this is that there can be a danger that there may be no feasible solution that “fit-together” without causing any over-cover. On the other hand, the produced solutions do not usually have overcovered pieces of work; the set covering model most commonly results in two duties overlapping slightly. If overcover occurs, it can be easily eliminated by editing the schedule afterwards.LetN
=
{
D
1
,
D
2
,
D
3
,
…
,
D
n
} be the set of legal duties and M
=
1,2
,
…
,
m be the set of pieces of work to be covered. We can define the problem as the construction of a matrix, where drivers appear in columns and pieces of works in lines. For each element a
i
j
∈
0,1, i
∈
M, j
∈
N, a
i
j
=
1 indicates the duty j covers piece of work i, and it is 0 otherwise. It can be formulated as follows:(1)
min
⁡
W
1
∑
j
=
1
n
‍
c
j
x
j
+
W
2
∑
j
=
1
n
‍
x
jsubject to(2)
∑
j
=
1
n
‍
a
i
j
x
j
≥
1
,
i
∈
M
,
(3)
x
j
∈
0,1
,
j
∈
N
,where n is the number of duties; m is number of work pieces; c
j is the cost of duty j; x
j is equal to 1 if duty j is used in the solution and 0 otherwise. W
1 and W
2 are weight constants. Generally, the main objective of the transport company is to obtain a solution with a minimum number of duties. For this objective, we consider here W
2
≫
W
1.The constraints (2) indicate that each piece of work must be covered by at least one duty. We consider the costs c
j in our work based on [15]:(4)
c
j
=
OV
j
+
IT
j
,where(5)
OV
j
=
max
⁡
0
,
FT
t
lst
-
ST
t
fst
-
NWT
,
(6)
IT
j
=
max
⁡
0
,
NWT
-
FT
t
lst
-
ST
t
fst
+
⋯
∑
i
=
1
m
-
1
‍
max
⁡
0
,
ST
t
i
+
1
-
FT
t
i
,where c
j is the cost of the driver j;  OV
j is the extra-time over the normal time of work established by law for driver j (8 hours); IT
j is the idle time of driver j (time the driver is not working during his shift); NWT is the normal working time (8 hours); FT
(
t
i
) is the finish time of the task i;  ST
(
t
i
) is the start time of the task i;  t
fst is the first task of the j driver’s shift; t
lst is the last task of the j driver’s shift.


## 3. Solution Methodology

The column generation algorithm for the BDSP is initialed by giving a small set of duties (columns). These duties constitute the initial columns in a restricted master problem (RMP). Feedback from the optimal dual values of the RMP is then used to solve a pricing subproblem, which aims to identify duties with a negative reduced cost that improves the objective function value of the RMP. The pricing subproblem for the BDSP is typically modeled as a constrained shortest path problem solved over a directed acyclic graph and then solved using dynamic programming techniques [9]. Nevertheless, because of the drawback that the subproblems for generating the columns would be computationally expensive in real problem instances [16], column generation did not make much progress toward solving large instances. Thus, the main work relies on the subproblem to speed up the whole process of column generation. Here, we propose the column generation based hyper-heuristic methodology to solve the BDSP. This approach provides two significant advantages. First, due to the fact that column generation is known for its poor convergence, it is not necessary to select only one column with lowest reduced cost; in fact, any column with a negative reduced cost will do. Using this observation can improve the overall efficiency. In our research the idea of “rapid adding columns” is to add a set of columns quickly by iteratively solving subproblem using a set of low heuristics. Thus, more than one duty with negative reduced costs may even be possible to be brought into the restricted subset per iteration. Second, the diverse columns with negative reduced cost that are selected (or generated) can be performed efficiently, see [13], to avoid the rapid and useless increase in RMP size. In fact, our approach may select a good “diversity” of duties by using these low heuristics to improve the solution without a large increase in computation time. The pricing step plays an important role in terms of the efficiency of the column generation method.An outline of the algorithm is given as follows.Step 0 (preprocessing). Generate all valid duties. Then, these duties form a column pool P.Step 1 (construct an initial solution). Take a small subset of the duties p
⊂
P as initial set of columns.Step 2 (solving the RMP). Solve the LP over the current duty subset and compute the shadow prices of the set of columns p.Step 3 (duty management). Control the column pool P and remove the columns in the RMP if necessary.Step 4 (selection of new duties). Select duties with negative reduced cost which will improve the solution, and add them to the RMP.Step 5 (stopping criterion). If the stopping criterion is met, then go to Step 6; else go to Step 2.Step 6 (finding integer solutions). Solve ILP and obtain an integer solution.The overall execution is iterated between Steps2 and 6. In the first iteration it uses the columns created in Step 0.In the remainder of this section, we provide details of each of the above steps.


### 3.1. Step 0: Preprocessing

In our approach we generate all feasible duties explicitly in a preprocessing step. That is, all the possible combinations of pieces of work are valid according to a set of labor contracts and regulations. One of the advantages of generating duties beforehand is that different duty sets can be identified so that experienced schedulers can “share” their own knowledge rather than relying on a “black box” to produce the schedules. Error correction or experimental changes can thus be carried out relatively quickly before searching for resulting schedules [17]. Moreover, preprocessing is an important procedure to express “preferences” and “undesirableness,” which are defined by a user-defined strategy. As discussed in [16], soft parameters are used to limit the generation of duties, for example, limiting the maximum number of spells in a duty to four. Meanwhile, a set of preferred duties can be identified relatively quickly; for example, duties with idle time less than average are preferred. Here, this kind of preprocessing could help us to find a subset of “good” duties when we need to use them during the search process.Formally, we make the following definitions.Definition 1.
Given a dutyD
j, let R
i
j denote a relief opportunity which is start point in a piece of work i covered by the duty D
j. For a given relief opportunity R
i
j, we define a relief time and relief point in R
i
j as ST
(
t
i
) and AS
(
t
i
), respectively. Then, R
i
j
=
(
ST
(
t
i
)
,
AS
(
t
i
)
).Definition 2.
Given a dutyD
j, let L
i
j denote a relief opportunity which is end point in a piece of work i covered by the duty D
j. For a given relief opportunity R
i
j, we define a relief time and relief point in L
i
j as FT
(
t
i
) and DS
(
t
i
), respectively. Then, L
i
j
=
(
FT
(
t
i
)
,
DS
(
t
i
)
).Based on the above definitions, a piece of worki covered by the duty D
j  is denoted by(7)
M
j
i
=
R
i
j
,
L
i
j
.Hence,n pieces of work composed of a duty D
j can be defined as(8)
D
j
=
M
j
1
,
M
j
2
,
…
,
M
j
n
.According to Definitions1 and 2, each duty is forced to satisfy all the following basic constraints:(9)
FT
t
lst
-
ST
t
fst
≤
MWT
,
(10)
∑
t
i
∈
D
j
‍
FT
t
i
-
ST
t
i
≤
MVT
,
(11)
FT
t
i
≤
ST
t
i
+
1
,
(12)
AS
t
i
=
DS
t
i
+
1
,
(13)
AS
t
i
≠
DS
t
i
+
1
,
ST
t
i
+
1
-
FT
t
i
≥
T
i
,
i
+
1
,where MWT is the maximum working time (8 hours + 2 hours); MVT is the maximum valid working time; AS
(
t
i
) is an arrival station of task i;  DS
(
t
i
+
1
) is a depart station of task (
i
+
1
);  T
i
,
i
+
1 is the necessary time to reach DS
(
t
i
+
1
) from AS
(
t
i
).Here we propose a method to generate the valid potential duties as follows in Algorithm1. The algorithm is initialized by setting a number of pieces N
p and i equal to 0. The relief opportunities are selected to generate a set of all the possible pieces of work M according to a given bus schedule. Notice that a maximum number of pieces, which is limited to compose a duty, are different in some practical cases, for example, no more than four spells in [18]. Another example is from [19] and in their case the maximum is equal to 2. Hence, we will refer to a required number of pieces given by the bus company as N
r. Let us denote t
min
⁡ corresponding to the shortest length of piece in M (line (
4
)). Then, we can compute a maximum number of pieces N
max
⁡ (maximum working time of duty divided by the shortest time of piece) on line (
5
). N
p is thus determined by N
r and N
max
⁡. Finally, the process adds one piece of work after one piece of work into a duty until the maximum number of pieces is met. Nested loops on lines (7)–(19) are iterated gradually through all pieces of work of each vehicle. Line (
12
) checks if the duties satisfy the constrains (9)–(13) before adding the duties to the pool P.Algorithm 1:Generation of all valid potential duties.
(1) Given a bus schedule, a maximum working time of dutyT, and a required number of pieces N
r; Set N
p
=
1
,
j
=
1
(2)for all bus vehicles V  do
(3)  Select the relief opportunities to generate a set of piece of workM
=
M
1
,
M
2
,
…
,
M
m
(4)  Find the pieceM
i
∈
M such that the length is shortest (denoted as t
min
⁡) in M
(5)  Compute a maximum number of pieceN
max
⁡
=
T
/
t
min
⁡
(6)end for
(7)while  N
p
≤
Min
⁡
(
N
r
,
N
max
⁡
)  do
(8)for piece of work M
[
j
]
[
i
]
∈
M  do
(9)for piece of work M
[
j
]
[
i
+
1
]
∈
M  do
(10)    ⋯
(11)for piece of work M
[
j
]
[
N
p
]
∈
M  do
(12)if Duty D
i which covers (M
[
j
]
[
i
]
,
M
[
j
]
[
i
+
1
]
,
…
,
M
[
j
]
[
N
p
]) satisfies the constrains (9)–(13)   then
(13)      Add generated dutyi to set of duties D
(14)N
p++;
j++
(15)end if
(16)end for
(17)
end for
(18)
end for
(19)end while1111eq:eps


### 3.2. Step 1: Construct an Initial Solution

For computing initial shadow prices, we propose a greedy constructive heuristic. An initial solution is made by a sequential mechanism, whose main objective is to obtain initial values of dual variables to select more duties and improve the linear solution in Step2. The procedure is presented in Algorithm 2. Given a set of legal duties S
=
{
D
1
,
D
2
,
D
3
,
…
,
D
n
} and a set of pieces of work to be covered M
=
1,2
,
…
,
m, let Q be a set of the pieces of work covered so far. As it is a constructive heuristic, a new duty not yet assigned is added in a greedy way to the current schedule at each iteration. With this objective, we calculate a new cost of duty c
′ as a greedy function for our choice at each iteration. The new cost of duty c
j
′ can be computed as the following:(14)
c
j
′
=
c
j
∑
i
=
1
m
β
i
j
,
j
=
1,2
,
…
,
n
,where c
j is the cost of duty D
j in the r
th iteration; β
i
j
=
1  if not yet covered piece of work i is covered by D
j after the r
th iteration, and 0 otherwise. Particularly, if ∑
i
=
1
m
β
i
j
=
0,  c
j
′
=
c
j.Algorithm 2:Greedy constructive heuristic.
(1) InitializeQ
←
∅
(2)while  Q
≠
M  do
(3)  ChooseD
j
∈
S with minimize cost c
j
′
(4)Q
k
+
1
=
Q
k
∪
D
j
(5)end while
(6) Find an initial solution to BDSPFinally, the process is repeated until all pieces of work are covered.


### 3.3. Step 2: The Restricted Master Problem

Following a typical column generation, the LP relaxation of the IP is necessary to be applied; that is, we relax the integer constraints (4). Thus, constraints (4) can be rewritten as(15)
x
j
∈
R
,
j
∈
N
.The purpose of solving RMP is to find the dual prices, or shadow prices, corresponding to the pieces of work in the problem. These values are used to calculate the reduced cost of new duties described in Step4.


### 3.4. Step 3: Duty Management

Duty management (or column management) is an integral part of any successful column generation algorithm as discussed in [18–20].In this research, there are two reasons why this process is applied.Firstly, at each column generation iteration we insert all columns with negative reduced costs that have been found by the pricing algorithms into the RMP (see Step4). Thus, it is clear that the procedure to RMP is not efficient if there are more columns than a certain maximum amount. In our test, all the duties with reduced cost greater than a given threshold will be removed whenever the number of duties exceeds 50,000. Similar strategies are used in [21]. This process is particularly important when the RMP keeps growing enormously during the column generation process.Secondly, the selection of duties (see Step4) can sometimes be sped up without loss of quality if the number of duties generated can be reduced intelligently [18]. Since the number of duties for some real-life problems may be quite large, we consider to take measures to prevent “bad” quality of duty into our procedure. The following procedure is iterated as long as the number of duties stays above 100,000. Each potential duty will be ranked by combining two attributes: an index which reflects its apparent efficiency (driving time divided by working time) and a ratio which reflects the identical duties; for example, a ratio of duty which is wholly contained by another duty is 0. Then, the lowest ranked duties are discarded until some definitive conditions are met. The removal of these duties reduces the overall size of a subproblem, which reduces run-time and memory usage requirement.


### 3.5. Step 4: Selection of New Duties

The major component of column generation is the procedure for selecting (generating) candidate duties to bring into the restricted subset in each iteration. The goal is to improve the LP relaxation of the restricted master problem. Thus, the objective of this subproblem is to select the negative reduced cost of duties not already in the restricted subset. We now provide the details of this procedure to identify duties with negative reduced costs at each iteration. The reduced cost is obtained from the cost and dual valuesj of each corresponding set covering constraint as given in the previous section. As only negative reduced-cost routes can enter the restricted master problem, the reduced cost should be minimized or constrained to be negative. Using the dual variables from the LP solution, the reduced cost of each duty is calculated by(16)
c
~
=
c
j
-
∑
i
=
1
m
‍
π
i
a
i
j
,
j
=
1,2
,
…
,
n
,where c
~ is the reduced cost of duty (column) j;  c
j is cost of duty j;  π
i is the dual price of task i.In this research, we develop a heuristic method based on the idea of hyper-heuristic that, while efficient, is not guaranteed to identify all the columns. To speed up the search for columns with negative reduced cost, we perform heuristic pricing. Besides saving computing time, this also allows generating multiple columns in each run. For one heuristic method is greedy, by applying different heuristic methods, we can keep the diversity of columns and avoid getting into a local optimal direction. Based on the framework of hyper-heuristic [14, 22], the competition rules are applied to guide the selection of the low-level heuristic during the search process. When a low-level heuristic is applied, the performance of this low-level heuristic will be selected by a function Δ. To prevent holding a large computation time by a poor performance of low heuristic, the simple ranking [23] is used to exclude the worst heuristic according to its scores in the last application at each iteration. There are four different cases (shown in Table 1) to reflect the important performance of a low-level heuristic.Table 1
Reward in the particular cases.
Case
Description
Score
Case 1
A negative reduced cost of duty found is the minimum among others.
3
Case 2
The execution time is less than other heuristics.
2
Case 3
The CPU seconds elapsed is much more than other heuristics since it was last called.
1
Case 4
No duty with negative reduced cost found.
−1At each iteration,Δ of each low-level heuristic is calculated by(17)
Δ
=
∑
k
=
1
4
‍
r
k
,where r
k is the score of case k.Note that if each low-heuristic has the same total score at given iteration, no low-heuristic will be excluded. Five heuristics select new duties in the same time at the beginning.


#### 3.5.1. Swap Heuristic

The authors in [24] consider that if a column in the optimal solution obtained by Step 2 is modified appropriately, it is likely to get a new column with negative reduced cost. For this reason, we try to select a number of columns in this heuristic.Swap heuristic is formally written as follows. Given a duty D
j from optimal solution S
=
{
D
1
,
D
2
,
…
,
D
n
} of the restricted master problem, we decompose the duty D
j that is randomly selected in partial consecutive duty into h,  k pieces of work (POW). Moreover, assuming that h
≤
k and h
+
k
=
n, then D
j is decomposed as D
j
1
=
∪
i
=
1
h
POW,  D
j
2
=
∪
i
=
h
+
1
n
POW. Therefore, all the duties which contain either D
j
1
=
∪
i
=
1
h
POW or D
j
2
=
∪
i
=
h
+
1
n
POW can be found in P (see in Step 0). Thus, we can select the duty with negative reduced cost to RMP. This process is executed until either at least one new duty with negative reduced cost can be found or a predefined number of attempts without success is reached.


#### 3.5.2. Local Search Version 1

As we know, the element of search space consists of various duties. Thus, we could consider several neighborhood relations according to the properties of a duty, that is, duty type, number of spells, and cost. Then, one of neighbors is randomly selected in order to obtain an enough “good” duty after applying a local search. In the following, we will describe a neighborhood relation that we consider in our case.It was mentioned earlier that five types of a duty are specified: Early Duty, Late Duty, Night Duty, Day Duty, and Middle Duty. LetS
i
′
=
(
D
1
′
,
D
2
′
,
…
,
D
n
′
) be a subset of duties that each duty D
i
′
∈
S
i
′ is performed in the same duty type. As illustrated in the pseudo code of Algorithm 3, the neighborhoods S
i
′ allow the search to move (Step (
3
) of Algorithm 3). Then, the local search starts from a duty D
i by using 2-exchange, which follows a random sequence of duties in S
i
′ (Steps (5)–(7) of Algorithm 3). If D
current with less reduced cost is found, D
incumbent will be replaced (Step (
8
) of Algorithm 3). All the above steps will be repeated until the predefined number of iterations is reached.Algorithm 3:Local search.
(1) Determine properties of each duty: number of spells, duty type and cost.
(2) Construct different neighborhood structures.
(3) Begin with one neighborhood structureS
i
′ which is randomly selected to search.
(4)while countmove < Maxumummove do
(5)  Candidate dutyD
i is chosen randomly in S
i
′
(6)D
incumbent
←
D
i
(7)D
current
← Apply 2-exchange
(8)if current duty is better than incumbent then
(9)D
incumbent
←
D
curren
t
(10) end if
(11) countmove++
(12)end while
(13) AddD
incumbent to RMP if it has a negative reduced cost


#### 3.5.3. Local Search Version 2

This heuristic is similar tolocal search version1, except the neighborhood selection mode that a greedy strategy is used. We define a set of neighborhoods used according to the number of spells. Thus, these different neighborhoods can be ranked in a descendant order. The duty with the maximum number of spells will be checked at each iteration. However, another neighbor will be selected according to the rank if a duty with negative reduced cost cannot be found in this neighbor after 10 attempts without success. And so on like this way to search, the entire search stops when a suitable stopping condition is met (here we use a maximum allowed number of iterations based on the CPU time).


#### 3.5.4. A Greedy-Based Heuristic Version 1

Instead of searching the whole space, the first heuristic attempts to drive the search towards definitive zone of space. We maintain a reasonable size of the duties which are deemed to search efficiently (i.e., a limited number of dutiesN
limit
⊂
N). Then we try to find a “desired” duty in this subset.More exactly, letP
cost be a pool which only stores the duties in which the costs are less than an adaptive threshold. This threshold is dynamically controlled by a parameter η. Then, the duties are ordered in a descendant order according to their costs. Duties, therefore, will be checked one by one according to this ranking order until one of some stopping criteria is met, which is either a time limit or finding one duty with negative reduced cost. In fact, the heuristic cannot find a “desired” duty after a certain time when entire search is stopped; it perhaps means that the threshold should be increased. Here we define that the threshold will be updated by min
⁡
(
c
j
).


#### 3.5.5. A Greedy-Based Heuristic Version 2

This heuristic is similar to a greedy-based heuristic version 1, except that a duty which is selected randomly in the poolP will be checked at each iteration.


### 3.6. Step 5: Stopping Criterion

In the context of this work, two stopping criteria are defined in our approach: (1) no duty with negative reduced cost is found and (2) the time limit is reached.


### 3.7. Step 6: Finding Integer Solutions

As mentioned earlier, column generation is used to solve the relaxed master problem. Hence, the resulting LP solution produced a solution with fractional numbers of duties and an integer solution must be found. In this case, a branch and bound procedure is used in order to deliver an integer solution. Several branching strategies compatible with column generation techniques are discussed [21, 25]. Constraint branching, which was originally proposed in [26], is widely used for branching strategies. In theory, constraint branching is used to set partitioning models and could lead to suboptimality if applied to inequality constraints, but since the optimal integer solution to the current problem will not necessarily equate to the optimal schedule and users can seldom specify what they mean by optimality, the emphasis is on finding a good integer solution quickly. Formally, let J
(
s
,
t
) be a set of variables from the optimal fractional solution in the RMP, where each variable covers tasks  s and t simultaneously and ∑
j
∈
J
(
s
,
t
)
x
j as the sum of solution values of the variables in the set J
(
s
,
t
). In [26], any optimal fractional solution contains at least one constraint pair s,  t, for which ∑
j
∈
J
(
s
,
t
)
x
j lies strictly between zero and one (see a proof in [27]):(18)
0
<
∑
j
∈
J
(
s
,
t
)
‍
x
j
<
1
.The equivalent of the zero branch and the one branch are, respectively,(19)
∑
j
∈
J
(
s
,
t
)
‍
x
j
≤
0
,
(20)
1
≤
∑
j
∈
J
s
,
t
‍
x
j
.Applying the above branching strategy on our problem, branching is done by dividing the solution space into two sets. The branching can be imposed on the 0-branch:(21)
∑
j
∈
J
(
s
,
t
)
‍
x
j
=
0
.The 0-branch forces all duties covering both tasks are banned. Then on the 1-branch,(22)
1
≤
∑
j
∈
J
s
,
t
‍
x
j
.The 1-branch implies that any duty which coversr
1 (or r
2) but not r
2 (or r
1) must be excluded.Instead of solving the linear program to optimality, we can choose to prematurely end the process if the relative gap between upper bound and the lower bound is smaller thanɛ. Upper bound on the objective value is given by the integer solutions found.A lower bound can be obtained by Step3.LB is the lower bound on the optimal solution value computed by solving the LP relaxation of (1) and rounding up the corresponding value. Column generation iterations can be terminated when this gap is less than a user-defined tolerance, giving a near-optimal solution of defined quality.Definition 3.
T
b is the total running time of bus, which can be computed from a bus schedule.Assuming that the users predefineMWT as the maximum working time of a driver per day, N
E given to estimate the number of drivers expected is calculated by(23)
N
E
=
T
b
MWT
.Proposition 4.
N
E is a tight low bound.Proof.
Given a bus schedule,T
b is constant. Let D
S
=
(
d
1
,
d
2
,
…
,
d
n
) be the set of duties in an optimum solution S. Note N
S is a number of drivers in S.
Case
a. the effective working hours of duty d
∈
D
S are the maximum working time MWT. Therefore,(24)
N
E
=
N
S
=
T
b
MWT
.
Case
b. It has occurred when there is at least one duty d
i
∈
D
S such that the effective working hours are not equal to MWT:(25)
N
E
<
N
S
=
T
b
MWT
+
n
,where 1
≤
n and integer.
HenceN
E is a tight low bound.The process continues until the gap is less than a user-defined tolerance, giving a near-optimal solution of defined quality. However, this could be time consuming for large problems. Therefore, the branching process will terminate the search once one integral solution has been found if a given execution time is exceeded.


## 3.1. Step 0: Preprocessing

In our approach we generate all feasible duties explicitly in a preprocessing step. That is, all the possible combinations of pieces of work are valid according to a set of labor contracts and regulations. One of the advantages of generating duties beforehand is that different duty sets can be identified so that experienced schedulers can “share” their own knowledge rather than relying on a “black box” to produce the schedules. Error correction or experimental changes can thus be carried out relatively quickly before searching for resulting schedules [17]. Moreover, preprocessing is an important procedure to express “preferences” and “undesirableness,” which are defined by a user-defined strategy. As discussed in [16], soft parameters are used to limit the generation of duties, for example, limiting the maximum number of spells in a duty to four. Meanwhile, a set of preferred duties can be identified relatively quickly; for example, duties with idle time less than average are preferred. Here, this kind of preprocessing could help us to find a subset of “good” duties when we need to use them during the search process.Formally, we make the following definitions.Definition 1.
Given a dutyD
j, let R
i
j denote a relief opportunity which is start point in a piece of work i covered by the duty D
j. For a given relief opportunity R
i
j, we define a relief time and relief point in R
i
j as ST
(
t
i
) and AS
(
t
i
), respectively. Then, R
i
j
=
(
ST
(
t
i
)
,
AS
(
t
i
)
).Definition 2.
Given a dutyD
j, let L
i
j denote a relief opportunity which is end point in a piece of work i covered by the duty D
j. For a given relief opportunity R
i
j, we define a relief time and relief point in L
i
j as FT
(
t
i
) and DS
(
t
i
), respectively. Then, L
i
j
=
(
FT
(
t
i
)
,
DS
(
t
i
)
).Based on the above definitions, a piece of worki covered by the duty D
j  is denoted by(7)
M
j
i
=
R
i
j
,
L
i
j
.Hence,n pieces of work composed of a duty D
j can be defined as(8)
D
j
=
M
j
1
,
M
j
2
,
…
,
M
j
n
.According to Definitions1 and 2, each duty is forced to satisfy all the following basic constraints:(9)
FT
t
lst
-
ST
t
fst
≤
MWT
,
(10)
∑
t
i
∈
D
j
‍
FT
t
i
-
ST
t
i
≤
MVT
,
(11)
FT
t
i
≤
ST
t
i
+
1
,
(12)
AS
t
i
=
DS
t
i
+
1
,
(13)
AS
t
i
≠
DS
t
i
+
1
,
ST
t
i
+
1
-
FT
t
i
≥
T
i
,
i
+
1
,where MWT is the maximum working time (8 hours + 2 hours); MVT is the maximum valid working time; AS
(
t
i
) is an arrival station of task i;  DS
(
t
i
+
1
) is a depart station of task (
i
+
1
);  T
i
,
i
+
1 is the necessary time to reach DS
(
t
i
+
1
) from AS
(
t
i
).Here we propose a method to generate the valid potential duties as follows in Algorithm1. The algorithm is initialized by setting a number of pieces N
p and i equal to 0. The relief opportunities are selected to generate a set of all the possible pieces of work M according to a given bus schedule. Notice that a maximum number of pieces, which is limited to compose a duty, are different in some practical cases, for example, no more than four spells in [18]. Another example is from [19] and in their case the maximum is equal to 2. Hence, we will refer to a required number of pieces given by the bus company as N
r. Let us denote t
min
⁡ corresponding to the shortest length of piece in M (line (
4
)). Then, we can compute a maximum number of pieces N
max
⁡ (maximum working time of duty divided by the shortest time of piece) on line (
5
). N
p is thus determined by N
r and N
max
⁡. Finally, the process adds one piece of work after one piece of work into a duty until the maximum number of pieces is met. Nested loops on lines (7)–(19) are iterated gradually through all pieces of work of each vehicle. Line (
12
) checks if the duties satisfy the constrains (9)–(13) before adding the duties to the pool P.Algorithm 1:Generation of all valid potential duties.
(1) Given a bus schedule, a maximum working time of dutyT, and a required number of pieces N
r; Set N
p
=
1
,
j
=
1
(2)for all bus vehicles V  do
(3)  Select the relief opportunities to generate a set of piece of workM
=
M
1
,
M
2
,
…
,
M
m
(4)  Find the pieceM
i
∈
M such that the length is shortest (denoted as t
min
⁡) in M
(5)  Compute a maximum number of pieceN
max
⁡
=
T
/
t
min
⁡
(6)end for
(7)while  N
p
≤
Min
⁡
(
N
r
,
N
max
⁡
)  do
(8)for piece of work M
[
j
]
[
i
]
∈
M  do
(9)for piece of work M
[
j
]
[
i
+
1
]
∈
M  do
(10)    ⋯
(11)for piece of work M
[
j
]
[
N
p
]
∈
M  do
(12)if Duty D
i which covers (M
[
j
]
[
i
]
,
M
[
j
]
[
i
+
1
]
,
…
,
M
[
j
]
[
N
p
]) satisfies the constrains (9)–(13)   then
(13)      Add generated dutyi to set of duties D
(14)N
p++;
j++
(15)end if
(16)end for
(17)
end for
(18)
end for
(19)end while1111eq:eps


## 3.2. Step 1: Construct an Initial Solution

For computing initial shadow prices, we propose a greedy constructive heuristic. An initial solution is made by a sequential mechanism, whose main objective is to obtain initial values of dual variables to select more duties and improve the linear solution in Step2. The procedure is presented in Algorithm 2. Given a set of legal duties S
=
{
D
1
,
D
2
,
D
3
,
…
,
D
n
} and a set of pieces of work to be covered M
=
1,2
,
…
,
m, let Q be a set of the pieces of work covered so far. As it is a constructive heuristic, a new duty not yet assigned is added in a greedy way to the current schedule at each iteration. With this objective, we calculate a new cost of duty c
′ as a greedy function for our choice at each iteration. The new cost of duty c
j
′ can be computed as the following:(14)
c
j
′
=
c
j
∑
i
=
1
m
β
i
j
,
j
=
1,2
,
…
,
n
,where c
j is the cost of duty D
j in the r
th iteration; β
i
j
=
1  if not yet covered piece of work i is covered by D
j after the r
th iteration, and 0 otherwise. Particularly, if ∑
i
=
1
m
β
i
j
=
0,  c
j
′
=
c
j.Algorithm 2:Greedy constructive heuristic.
(1) InitializeQ
←
∅
(2)while  Q
≠
M  do
(3)  ChooseD
j
∈
S with minimize cost c
j
′
(4)Q
k
+
1
=
Q
k
∪
D
j
(5)end while
(6) Find an initial solution to BDSPFinally, the process is repeated until all pieces of work are covered.


## 3.3. Step 2: The Restricted Master Problem

Following a typical column generation, the LP relaxation of the IP is necessary to be applied; that is, we relax the integer constraints (4). Thus, constraints (4) can be rewritten as(15)
x
j
∈
R
,
j
∈
N
.The purpose of solving RMP is to find the dual prices, or shadow prices, corresponding to the pieces of work in the problem. These values are used to calculate the reduced cost of new duties described in Step4.


## 3.4. Step 3: Duty Management

Duty management (or column management) is an integral part of any successful column generation algorithm as discussed in [18–20].In this research, there are two reasons why this process is applied.Firstly, at each column generation iteration we insert all columns with negative reduced costs that have been found by the pricing algorithms into the RMP (see Step4). Thus, it is clear that the procedure to RMP is not efficient if there are more columns than a certain maximum amount. In our test, all the duties with reduced cost greater than a given threshold will be removed whenever the number of duties exceeds 50,000. Similar strategies are used in [21]. This process is particularly important when the RMP keeps growing enormously during the column generation process.Secondly, the selection of duties (see Step4) can sometimes be sped up without loss of quality if the number of duties generated can be reduced intelligently [18]. Since the number of duties for some real-life problems may be quite large, we consider to take measures to prevent “bad” quality of duty into our procedure. The following procedure is iterated as long as the number of duties stays above 100,000. Each potential duty will be ranked by combining two attributes: an index which reflects its apparent efficiency (driving time divided by working time) and a ratio which reflects the identical duties; for example, a ratio of duty which is wholly contained by another duty is 0. Then, the lowest ranked duties are discarded until some definitive conditions are met. The removal of these duties reduces the overall size of a subproblem, which reduces run-time and memory usage requirement.


## 3.5. Step 4: Selection of New Duties

The major component of column generation is the procedure for selecting (generating) candidate duties to bring into the restricted subset in each iteration. The goal is to improve the LP relaxation of the restricted master problem. Thus, the objective of this subproblem is to select the negative reduced cost of duties not already in the restricted subset. We now provide the details of this procedure to identify duties with negative reduced costs at each iteration. The reduced cost is obtained from the cost and dual valuesj of each corresponding set covering constraint as given in the previous section. As only negative reduced-cost routes can enter the restricted master problem, the reduced cost should be minimized or constrained to be negative. Using the dual variables from the LP solution, the reduced cost of each duty is calculated by(16)
c
~
=
c
j
-
∑
i
=
1
m
‍
π
i
a
i
j
,
j
=
1,2
,
…
,
n
,where c
~ is the reduced cost of duty (column) j;  c
j is cost of duty j;  π
i is the dual price of task i.In this research, we develop a heuristic method based on the idea of hyper-heuristic that, while efficient, is not guaranteed to identify all the columns. To speed up the search for columns with negative reduced cost, we perform heuristic pricing. Besides saving computing time, this also allows generating multiple columns in each run. For one heuristic method is greedy, by applying different heuristic methods, we can keep the diversity of columns and avoid getting into a local optimal direction. Based on the framework of hyper-heuristic [14, 22], the competition rules are applied to guide the selection of the low-level heuristic during the search process. When a low-level heuristic is applied, the performance of this low-level heuristic will be selected by a function Δ. To prevent holding a large computation time by a poor performance of low heuristic, the simple ranking [23] is used to exclude the worst heuristic according to its scores in the last application at each iteration. There are four different cases (shown in Table 1) to reflect the important performance of a low-level heuristic.Table 1
Reward in the particular cases.
Case
Description
Score
Case 1
A negative reduced cost of duty found is the minimum among others.
3
Case 2
The execution time is less than other heuristics.
2
Case 3
The CPU seconds elapsed is much more than other heuristics since it was last called.
1
Case 4
No duty with negative reduced cost found.
−1At each iteration,Δ of each low-level heuristic is calculated by(17)
Δ
=
∑
k
=
1
4
‍
r
k
,where r
k is the score of case k.Note that if each low-heuristic has the same total score at given iteration, no low-heuristic will be excluded. Five heuristics select new duties in the same time at the beginning.


### 3.5.1. Swap Heuristic

The authors in [24] consider that if a column in the optimal solution obtained by Step 2 is modified appropriately, it is likely to get a new column with negative reduced cost. For this reason, we try to select a number of columns in this heuristic.Swap heuristic is formally written as follows. Given a duty D
j from optimal solution S
=
{
D
1
,
D
2
,
…
,
D
n
} of the restricted master problem, we decompose the duty D
j that is randomly selected in partial consecutive duty into h,  k pieces of work (POW). Moreover, assuming that h
≤
k and h
+
k
=
n, then D
j is decomposed as D
j
1
=
∪
i
=
1
h
POW,  D
j
2
=
∪
i
=
h
+
1
n
POW. Therefore, all the duties which contain either D
j
1
=
∪
i
=
1
h
POW or D
j
2
=
∪
i
=
h
+
1
n
POW can be found in P (see in Step 0). Thus, we can select the duty with negative reduced cost to RMP. This process is executed until either at least one new duty with negative reduced cost can be found or a predefined number of attempts without success is reached.


### 3.5.2. Local Search Version 1

As we know, the element of search space consists of various duties. Thus, we could consider several neighborhood relations according to the properties of a duty, that is, duty type, number of spells, and cost. Then, one of neighbors is randomly selected in order to obtain an enough “good” duty after applying a local search. In the following, we will describe a neighborhood relation that we consider in our case.It was mentioned earlier that five types of a duty are specified: Early Duty, Late Duty, Night Duty, Day Duty, and Middle Duty. LetS
i
′
=
(
D
1
′
,
D
2
′
,
…
,
D
n
′
) be a subset of duties that each duty D
i
′
∈
S
i
′ is performed in the same duty type. As illustrated in the pseudo code of Algorithm 3, the neighborhoods S
i
′ allow the search to move (Step (
3
) of Algorithm 3). Then, the local search starts from a duty D
i by using 2-exchange, which follows a random sequence of duties in S
i
′ (Steps (5)–(7) of Algorithm 3). If D
current with less reduced cost is found, D
incumbent will be replaced (Step (
8
) of Algorithm 3). All the above steps will be repeated until the predefined number of iterations is reached.Algorithm 3:Local search.
(1) Determine properties of each duty: number of spells, duty type and cost.
(2) Construct different neighborhood structures.
(3) Begin with one neighborhood structureS
i
′ which is randomly selected to search.
(4)while countmove < Maxumummove do
(5)  Candidate dutyD
i is chosen randomly in S
i
′
(6)D
incumbent
←
D
i
(7)D
current
← Apply 2-exchange
(8)if current duty is better than incumbent then
(9)D
incumbent
←
D
curren
t
(10) end if
(11) countmove++
(12)end while
(13) AddD
incumbent to RMP if it has a negative reduced cost


### 3.5.3. Local Search Version 2

This heuristic is similar tolocal search version1, except the neighborhood selection mode that a greedy strategy is used. We define a set of neighborhoods used according to the number of spells. Thus, these different neighborhoods can be ranked in a descendant order. The duty with the maximum number of spells will be checked at each iteration. However, another neighbor will be selected according to the rank if a duty with negative reduced cost cannot be found in this neighbor after 10 attempts without success. And so on like this way to search, the entire search stops when a suitable stopping condition is met (here we use a maximum allowed number of iterations based on the CPU time).


### 3.5.4. A Greedy-Based Heuristic Version 1

Instead of searching the whole space, the first heuristic attempts to drive the search towards definitive zone of space. We maintain a reasonable size of the duties which are deemed to search efficiently (i.e., a limited number of dutiesN
limit
⊂
N). Then we try to find a “desired” duty in this subset.More exactly, letP
cost be a pool which only stores the duties in which the costs are less than an adaptive threshold. This threshold is dynamically controlled by a parameter η. Then, the duties are ordered in a descendant order according to their costs. Duties, therefore, will be checked one by one according to this ranking order until one of some stopping criteria is met, which is either a time limit or finding one duty with negative reduced cost. In fact, the heuristic cannot find a “desired” duty after a certain time when entire search is stopped; it perhaps means that the threshold should be increased. Here we define that the threshold will be updated by min
⁡
(
c
j
).


### 3.5.5. A Greedy-Based Heuristic Version 2

This heuristic is similar to a greedy-based heuristic version 1, except that a duty which is selected randomly in the poolP will be checked at each iteration.


## 3.5.1. Swap Heuristic

The authors in [24] consider that if a column in the optimal solution obtained by Step 2 is modified appropriately, it is likely to get a new column with negative reduced cost. For this reason, we try to select a number of columns in this heuristic.Swap heuristic is formally written as follows. Given a duty D
j from optimal solution S
=
{
D
1
,
D
2
,
…
,
D
n
} of the restricted master problem, we decompose the duty D
j that is randomly selected in partial consecutive duty into h,  k pieces of work (POW). Moreover, assuming that h
≤
k and h
+
k
=
n, then D
j is decomposed as D
j
1
=
∪
i
=
1
h
POW,  D
j
2
=
∪
i
=
h
+
1
n
POW. Therefore, all the duties which contain either D
j
1
=
∪
i
=
1
h
POW or D
j
2
=
∪
i
=
h
+
1
n
POW can be found in P (see in Step 0). Thus, we can select the duty with negative reduced cost to RMP. This process is executed until either at least one new duty with negative reduced cost can be found or a predefined number of attempts without success is reached.


## 3.5.2. Local Search Version 1

As we know, the element of search space consists of various duties. Thus, we could consider several neighborhood relations according to the properties of a duty, that is, duty type, number of spells, and cost. Then, one of neighbors is randomly selected in order to obtain an enough “good” duty after applying a local search. In the following, we will describe a neighborhood relation that we consider in our case.It was mentioned earlier that five types of a duty are specified: Early Duty, Late Duty, Night Duty, Day Duty, and Middle Duty. LetS
i
′
=
(
D
1
′
,
D
2
′
,
…
,
D
n
′
) be a subset of duties that each duty D
i
′
∈
S
i
′ is performed in the same duty type. As illustrated in the pseudo code of Algorithm 3, the neighborhoods S
i
′ allow the search to move (Step (
3
) of Algorithm 3). Then, the local search starts from a duty D
i by using 2-exchange, which follows a random sequence of duties in S
i
′ (Steps (5)–(7) of Algorithm 3). If D
current with less reduced cost is found, D
incumbent will be replaced (Step (
8
) of Algorithm 3). All the above steps will be repeated until the predefined number of iterations is reached.Algorithm 3:Local search.
(1) Determine properties of each duty: number of spells, duty type and cost.
(2) Construct different neighborhood structures.
(3) Begin with one neighborhood structureS
i
′ which is randomly selected to search.
(4)while countmove < Maxumummove do
(5)  Candidate dutyD
i is chosen randomly in S
i
′
(6)D
incumbent
←
D
i
(7)D
current
← Apply 2-exchange
(8)if current duty is better than incumbent then
(9)D
incumbent
←
D
curren
t
(10) end if
(11) countmove++
(12)end while
(13) AddD
incumbent to RMP if it has a negative reduced cost


## 3.5.3. Local Search Version 2

This heuristic is similar tolocal search version1, except the neighborhood selection mode that a greedy strategy is used. We define a set of neighborhoods used according to the number of spells. Thus, these different neighborhoods can be ranked in a descendant order. The duty with the maximum number of spells will be checked at each iteration. However, another neighbor will be selected according to the rank if a duty with negative reduced cost cannot be found in this neighbor after 10 attempts without success. And so on like this way to search, the entire search stops when a suitable stopping condition is met (here we use a maximum allowed number of iterations based on the CPU time).


## 3.5.4. A Greedy-Based Heuristic Version 1

Instead of searching the whole space, the first heuristic attempts to drive the search towards definitive zone of space. We maintain a reasonable size of the duties which are deemed to search efficiently (i.e., a limited number of dutiesN
limit
⊂
N). Then we try to find a “desired” duty in this subset.More exactly, letP
cost be a pool which only stores the duties in which the costs are less than an adaptive threshold. This threshold is dynamically controlled by a parameter η. Then, the duties are ordered in a descendant order according to their costs. Duties, therefore, will be checked one by one according to this ranking order until one of some stopping criteria is met, which is either a time limit or finding one duty with negative reduced cost. In fact, the heuristic cannot find a “desired” duty after a certain time when entire search is stopped; it perhaps means that the threshold should be increased. Here we define that the threshold will be updated by min
⁡
(
c
j
).


## 3.5.5. A Greedy-Based Heuristic Version 2

This heuristic is similar to a greedy-based heuristic version 1, except that a duty which is selected randomly in the poolP will be checked at each iteration.


## 3.6. Step 5: Stopping Criterion

In the context of this work, two stopping criteria are defined in our approach: (1) no duty with negative reduced cost is found and (2) the time limit is reached.


## 3.7. Step 6: Finding Integer Solutions

As mentioned earlier, column generation is used to solve the relaxed master problem. Hence, the resulting LP solution produced a solution with fractional numbers of duties and an integer solution must be found. In this case, a branch and bound procedure is used in order to deliver an integer solution. Several branching strategies compatible with column generation techniques are discussed [21, 25]. Constraint branching, which was originally proposed in [26], is widely used for branching strategies. In theory, constraint branching is used to set partitioning models and could lead to suboptimality if applied to inequality constraints, but since the optimal integer solution to the current problem will not necessarily equate to the optimal schedule and users can seldom specify what they mean by optimality, the emphasis is on finding a good integer solution quickly. Formally, let J
(
s
,
t
) be a set of variables from the optimal fractional solution in the RMP, where each variable covers tasks  s and t simultaneously and ∑
j
∈
J
(
s
,
t
)
x
j as the sum of solution values of the variables in the set J
(
s
,
t
). In [26], any optimal fractional solution contains at least one constraint pair s,  t, for which ∑
j
∈
J
(
s
,
t
)
x
j lies strictly between zero and one (see a proof in [27]):(18)
0
<
∑
j
∈
J
(
s
,
t
)
‍
x
j
<
1
.The equivalent of the zero branch and the one branch are, respectively,(19)
∑
j
∈
J
(
s
,
t
)
‍
x
j
≤
0
,
(20)
1
≤
∑
j
∈
J
s
,
t
‍
x
j
.Applying the above branching strategy on our problem, branching is done by dividing the solution space into two sets. The branching can be imposed on the 0-branch:(21)
∑
j
∈
J
(
s
,
t
)
‍
x
j
=
0
.The 0-branch forces all duties covering both tasks are banned. Then on the 1-branch,(22)
1
≤
∑
j
∈
J
s
,
t
‍
x
j
.The 1-branch implies that any duty which coversr
1 (or r
2) but not r
2 (or r
1) must be excluded.Instead of solving the linear program to optimality, we can choose to prematurely end the process if the relative gap between upper bound and the lower bound is smaller thanɛ. Upper bound on the objective value is given by the integer solutions found.A lower bound can be obtained by Step3.LB is the lower bound on the optimal solution value computed by solving the LP relaxation of (1) and rounding up the corresponding value. Column generation iterations can be terminated when this gap is less than a user-defined tolerance, giving a near-optimal solution of defined quality.Definition 3.
T
b is the total running time of bus, which can be computed from a bus schedule.Assuming that the users predefineMWT as the maximum working time of a driver per day, N
E given to estimate the number of drivers expected is calculated by(23)
N
E
=
T
b
MWT
.Proposition 4.
N
E is a tight low bound.Proof.
Given a bus schedule,T
b is constant. Let D
S
=
(
d
1
,
d
2
,
…
,
d
n
) be the set of duties in an optimum solution S. Note N
S is a number of drivers in S.
Case
a. the effective working hours of duty d
∈
D
S are the maximum working time MWT. Therefore,(24)
N
E
=
N
S
=
T
b
MWT
.
Case
b. It has occurred when there is at least one duty d
i
∈
D
S such that the effective working hours are not equal to MWT:(25)
N
E
<
N
S
=
T
b
MWT
+
n
,where 1
≤
n and integer.
HenceN
E is a tight low bound.The process continues until the gap is less than a user-defined tolerance, giving a near-optimal solution of defined quality. However, this could be time consuming for large problems. Therefore, the branching process will terminate the search once one integral solution has been found if a given execution time is exceeded.


## 4. Computational Results

In this section, we present the results obtained for the proposed approach on several real-world instances. These instances vary in size and complexity. The instances, denoted by A1–A5in Table 2, are from Mauri & Lorena [15]. For the last two instances, the test data comes from two lines of bus in Beijing. Table 2 shows the size (pieces of work) and the best known results of real-world problems.Table 2
Comparative results against the best known schedules.
Data
Number of pieces of work
Number of legal duties
Best known solutions
Number of  duties in schedule
Time (seconds)
A1
25
1,006
12
0.10
A2
50
10,552
20
4.63
A3
100
42,473
40
1.88
A4
250
990,065
81
70.90
A5
500
8,388,608
145
6567.80
B1
200
17,131
25
—
B2
265
19,835
73
—In order to evaluate the quality of the solution obtained by our approach presented here, the measure of the quality of a heuristic schedule is shown as follows:(26)
Devation
=
result
-
bestknown
bestknown
×
100
%
.All computational experiments were performed in a personal computer with Intel Core 2 Duo CPU T5870 that is processor of2.00GHz, 1.99 GHz with 2.00 G of RAM memory on Microsoft Windows 2002. The whole implementation was developed in the C # language and has been complied using the NET framework version 2.2
.
30729. The ILP solver used in experiments is LINGO 11.0. This software has been used to solve RMP after each pricing iteration. The threshold has been set to 5min c
~ in Step 3. The computation time to explore search space in the subproblem is limited to 2 hours (3,600 seconds).The results of Table3 show that in most of cases of instances A1–A5 our method could find solutions which are the same as the best known solutions. We can also find that our method does not perform well in some small size instances like A1–A3 compared to PTA/LP and TA/LP, even to SA. However, as the size of instance increases, our method performs better. This is because that, for small instance, our method is too complex and its computing time is long. But for large instance, the classic methods meet the problem of combinational explosion which is the typical feature of NP problem, while our method begins to show its advantage of saving computing time.Table 3
Comparative results against the best known schedules.
Problem
Used method
Number of  duties
Deviation%
Times
A1
PTA/LPa
12
0
0.10
TA/LPb
12
0.30
SAc
12
1.90
SA_20d
12
35.48
CGBHe
12
10.58
A2
PTA/LP
20
0
4.63
TA/LP
20
41.64
SA
20
42.87
SA_20
20
949.04
CGBH
20
39.53
A3
PTA/LP
40
2.5
1.88
TA/LP
40
4.98
SA
40
7.60
SA_20
40
173.26
CGBH
41
150.25
A4
PTA/LP
81
1.23
70.90
TA/LP
82
229.68
SA
85
199.86
SA_20
83
3749.02
CGBH
82
1309.07
A5
PTA/LP
145
6.89
6567.80
TA/LP
151
6717.30
SA
153
7061.52
SA_20
153
143565.20
CGBH
155
4038.13
Average
2.12
aPopulation training algorithm/linear programming with more iterative.
bPopulation training algorithm/linear programming with few iterative.
cSimulated annealing.
dSimulated annealing with 20 executions.
eColunm generation based hyper-heuristic approach.In Table4 we present the “manual” solutions of last two instances currently used in the company and the solutions obtained with our approach. Our solutions represent a reduction of -
8
% and -
8.22
%, respectively, on the manual solutions. This improved schedule was very acceptable to the user.Table 4
Comparison with manual solutions.
Type of Duty
B1
B2
Manual Solution
Our Solution
Deviation%
Manual Solution
Our Solution
Deviation%
Early Duty
8
6
27
25
Late Duty
8
2
27
19
Day Duty
0
4
0
6
Middle Duty
9
11
19
17
Total Duty
25
23
−8
73
67
−8.22


## 5. Conclusion

We describe a methodology for finding near-optimal solutions to bus driver scheduling problem. Suitable combination of column generation and hyper-heuristic can benefit much from synergy and exhibit higher performance with respect to solution quality and time for some cases, whereas the combination of column generation and hyper-heuristic also needs substantial further research in order to make them fully developed. Our future work on such hybrid approach will be still continued.



---

*Source: 638104-2015-04-12.xml*