The set covering problem is an NP-hard combinatorial optimization problem
that arises in applications ranging from crew scheduling in airlines to
driver scheduling in public mass transport. In this paper we analyze search
space characteristics of a widely used set of benchmark instances through
an analysis of the fitness-distance correlation. This analysis shows that
there exist several classes of set covering instances that have a largely
different behavior. For instances with high fitness distance ...
The set covering problem is an NP-hard combinatorial optimization problem
that arises in applications ranging from crew scheduling in airlines to
driver scheduling in public mass transport. In this paper we analyze search
space characteristics of a widely used set of benchmark instances through
an analysis of the fitness-distance correlation. This analysis shows that
there exist several classes of set covering instances that have a largely
different behavior. For instances with high fitness distance correlation,
we propose new ways of generating core problems and analyze the performance
of algorithms exploiting these core problems.
+