Efficient Trip Generation with a Rule Modeling System for Crew Scheduling Problems

Publication Type:

Journal Article


Systems and Software, Elsevier Science, Volume 69, Issue 1-2, p.43-56 (2004)


Crew scheduling, Performance improvement, Rule modeling, Trip generation


Trip generation is the most time consuming phase in the solution
process of crew scheduling problems faced by large transportation
companies such as airlines and railways. A large number of trips must
be constructed while satisfying a complex set of regulations. In this
paper, we present an efficient trip generation method that utilizes
originally a rule modeling system in order to reduce the corresponding
search space. Special pruning rules are defined using a high-level rule
language, which also supports the modeling of the business regulations
required in the scheduling process. In addition, the legality checking
mechanism involved has been tuned to perform efficiently in order to
cope with the vast amount of the legality checks required by the trip
generator. The algorithms are tested as a module for a crew scheduling
application satisfying the tight response time requirements of a
production system. We present experimental results based on problems
provided by a major European airline that validate the usefulness and
applicability of our work.