Constraint handling in genetic algorithms: The set partitioning problem

In this paper we present a genetic algorithm-based heuristic for solving th e set partitioning problem (SPP). The SPP is an important combinatorial opt imisation problem used by many airlines as a mathematical model for flight crew scheduling. A key feature of the SPP is that it is a highly constrained problem, all co nstraints being equalities. New genetic algorithm (GA) components: separate fitness and unfitness scores, adaptive mutation, matching selection and ra nking replacement, are introduced to enable a GA to effectively handle such constraints. These components are generalisable to any GA for constrained problems. We present a steady-state GA in conjunction with a specialised heuristic im provement operator for solving the SPP. The performance of our algorithm is evaluated on a large set of real-world problems. Computational results sho w that the genetic algorithm-based heuristic is capable of producing high-q uality solutions.