Colabora: Universitat Pompeu Fabra. Departament d'
Economia i Empresa
Autor/es: Markus Finger; Thomas Stützle; Helena Ramalhinho-Lourenço;
Resumen : 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.
