Conclusions and Future Work

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.