Paper #582

Títol:

Exploiting fitness distance correlation of set covering problems

Autors:

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

Data:

Novembre 2001

Resum:

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.

Paraules clau:

Set covering, iterated local search

Codis JEL:

C61, C63, D83

Àrea de Recerca:

Gestió de la Producció i de les Operacions

Publicat a:

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)

Descarregar el paper en format PDF