DAISy Dynamic Ambient Intelligent Systems Unit

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.