next up previous
Next: A Hybrid Approach Up: Solving Very LargeCrew Scheduling Previous: Constraints

Pure Approaches

The crew scheduling problem, as described here, presents a classical difficulty: finding the optimal schedule reduces to choosing from an extremely large set F of feasible duties, a minimal subset that partitions the set of trips to be serviced. The very large size of F poses serious problems, since a provably optimal solution can only be found if all elements of F are considered, either implicitly or explicitly.

When adopting IP approaches to solve this problem, one usually ends up with a set partitioning formulation where the elements of F constitute the columns of the coefficient matrix. The pure IP formulation of the problem is:

    $\displaystyle \min \sum_{j=1}^{n} x_j$ (1)
$\displaystyle \mbox{\rm subject to}$   $\displaystyle \sum_{j=1}^{n} a_{ij} x_j = 1, \;\; i = 1, 2, \ldots, m$ (2)
    $\displaystyle x_j \in \{0,1\}, \;\; j = 1, 2, \ldots, n$ (3)

where m is the total number of trips and n is the size of F. The xj's are 0-1 decision variables that indicate which duties belong to the solution. The coefficient aij equals 1 if duty j contains trip i, otherwise, aij is 0.

Due to the size of F, an implicit way to treat the set of feasible duties is needed. Column generation [1] is a technique that is widely used to handle linear programs which have a very large number of columns in the coefficient matrix. The method works by repeatedly executing two phases. In a first phase, instead of solving a linear relaxation of the whole problem, in which all columns are required to be loaded in memory, we quickly solve a smaller problem. This problem is called the master problem, and deals only with a subset of the original columns. That smaller problem solved, we start phase two, looking for columns with a negative reduced cost. If there are no such columns, we have proved that the solution at hand indeed minimizes the objective function. Otherwise, we augment the master problem by bringing in a number of columns with negative reduced costs, and start over on phase one. From the IP formulation above, the reduced cost of a feasible duty d is given by $1 - \sum_{j \in T}u_j$, where T is the set of trips serviced by d and uj is the value of the dual variable associated with trip j. The problem of computing columns with negative reduced costs is called the slave subproblem. When the original variables are restricted to integer values, this algorithm must be embedded in a branch-and-bound strategy. The resulting algorithm is usually referred to as branch-and-price. The slave subproblem can be modeled as a constrained shortest path problem over a directed acyclic graph and it can be solved by a dynamic programming algorithm [3]. Nevertheless, the pseudo-polynomial algorithms that arise from this strategy turn out to be very time consuming. This is mainly because of the looseness of our problem constraints [8].

Difficulties also arise when trying to solve crew scheduling problems using pure constraint satisfaction techniques [2,6,8]. The huge search space can only be dealt with efficiently when pruning is enforced by strong local constraints. Besides, a simple search strategy, lacking good problem specific heuristics, is very unlikely to succeed. When solving scheduling problems of this naturem to optimality, none of the these requirements can be easily met, rendering it intrinsically difficult for pure CP techniques to produce satisfactory results in these cases.

next up previous
Next: A Hybrid Approach Up: Solving Very LargeCrew Scheduling Previous: Constraints