Paper #582

Título:

Exploiting fitness distance correlation of set covering problems

Autores:

Markus Finger, Thomas Stützle y Helena Ramalhinho-Lourenço

Fecha:

Noviembre 2001

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.

Palabras clave:

Set covering, iterated local search

Códigos JEL:

C61, C63, D83

Área de investigación:

Gestión de la Producción y de las Operaciones

Publicado en:

Applications of Evolutionary Computing, S. Cagnoni, J. Gottlieb, E. Hart, M. Middenford, and G. R. Raidl (eds.), Springer-LNCS, vol. 2279, pp. 61-71 (2002)

Descargar el paper en formato PDF