Copyright ACM, 2000
Solving Very Large
Crew Scheduling Problems to Optimality
Tallys H. Yunes1
Arnaldo V. Moura
Cid C. de Souza2
Institute of Computing, University of Campinas
P.O. Box 6176, ZIP 13083-970
Campinas, SP, Brazil
In this article, we present a hybrid methodology for the
exact solution of large scale real world crew scheduling problems.
Our approach integrates mathematical programming and constraint
satisfaction techniques, taking advantage of their particular
abilities in modeling and solving specific parts of the problem.
An Integer Programming framework was responsible for guiding the
overall search process and for obtaining lower bounds on the
value of the optimal solution.
Complex constraints were easily expressed, in a declarative
way, using a Constraint Logic Programming language. Moreover, with
an effective constraint-based model, the huge space of feasible
solutions could be implicitly considered in a fairly efficient way.
Our code was tested on real problem instances arising from the
daily operation of an ordinary urban transit company that serves a
major metropolitan area with an excess of two million inhabitants.
Using a typical desktop PC, we were able find, in an acceptable
running time, an optimal solution to instances with more than 1.5
Keywords: Crew Scheduling, Constraint Programming,
Mathematical Programming, Hybrid Algorithms, Column Generation
Copyright 2000 ACM
Permission to make digital or hard copies of all or part of this work for
personal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy
otherwise, to republish, to post on servers or to redistribute to lists,
requires prior specific permission and or fee.
SAC 2000 March 19-21 Como, Italy
(c) 2000 ACM 1-58113-239-5/00/003>...>$5.00