A genetic algorithm for the generic crew scheduling problem

摘要

A topic of interest in genetic algorithm (GA) research is the design of GAs for highly constrained optimization problems. We believe that the most general approach hich may be taken in dealing with such difficulty is incorporating domain-specific knowledge into GA architecture. To demonstrate this idea, we consider application of Ga to a highly constrained combinatorial optimization problem, the generic crew scheduling problem (CSP). We design a steady-state genetic algorithm for solving the CSP. Computational results are given for a number of standard test problems. Experimental results demonstrate the effectiveness of the proposed algorithm and support the applicability of our idea.