next up previous
Next: Bibliography Up: Solving Very LargeCrew Scheduling Previous: Computational Results

   
Conclusions and Future Work

We have integrated pure Constraint Programming and pure Integer Programming techniques in a hybrid column generation algorithm that is able to solve very large instances of some real world crew scheduling problems to optimality. These problems appear intractable for both approaches when taken in isolation. Our methodology combines the strengths of both methods, getting over their main weaknesses.

Complex operational constraints could easily be expressed using declarative statements in a constraint programming language. The resulting model proved to be very efficient when looking for feasible duties with a negative reduced cost. A linear programming relaxation of the original problem formulation produced good lower bounds. Combining these two behaviors, it was possible to develop a very successful branch-and-price scheme. Using this hybrid method, a desktop PC was able to find optimal solutions for large one-depot instances in a reasonable time. The two-depot case, however, having a different structure and a larger search space, presented more difficulties. When we restricted the problem to the first 150 trips of the day, which already correspond to 12 million feasible duties, the hybrid algorithm produced an optimal solution. Nevertheless, even increasing the computation time limit to 24 hours, the hybrid algorithm was not able to compute an optimal schedule to the complete set of trips, which contained an excess of 122 million feasible duties. Further investigation is needed in order to devise more effective strategies to deal with such large two-depot instances.


next up previous
Next: Bibliography Up: Solving Very LargeCrew Scheduling Previous: Computational Results

1999-12-16