Paper #582

Title:

Exploiting fitness distance correlation of set covering problems

Authors:

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

Date:

November 2001

Abstract:

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.

Keywords:

Set covering, iterated local search

JEL codes:

C61, C63, D83

Area of Research:

Operations Management

Published in:

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)

Download the paper in PDF format