Constraints

For a duty to be classified as feasible, it has to satisfy many constraints imposed by labor contracts and union regulations, among others. The most important constraints are, for every duty:

1.

For each pair of consecutive trips, i and j:

(a)

$(\emph{start time})_i + (\emph{duration})_i\leq (\emph{start time})_j$

(b)

$(\emph{final depot})_i = (\emph{initial depot})_j$

2.

$\emph{total working time} \leq \emph{maximum working time}$;

3.

$\emph{rest time} + \max\{0, \emph{Workday} - \emph{total working time}\,\} \geq \emph{Min\_Rest}$; and

4.

At most one long rest interval is allowed;

Due to union regulations and operational constraints, the following values were used in our experiments: $\emph{Idle\_Limit}=120$, $\emph{Workday}=440$, $\emph{Min\_Rest}=30$ and $\emph{Max\_Overtime}=0$, measured in minutes. A duty which satisfies all problem constraints is called a feasible duty. Any set of feasible duties constitutes a schedule and for a schedule to be acceptable it must partition the set of trips. The cost of a schedule is the sum of the costs of all its duties. As we are interested in minimizing the number of crews needed to operate the bus line, all duties are treated equally and their costs are set to one. With this assumption, minimizing the cost of a schedule reduces to minimizing the number duties (crews) in the solution. Finally, a minimal schedule is any acceptable schedule with minimum cost.