Exploiting fitness distance correlation of set covering problems
| Contribuinte(s) |
Universitat Pompeu Fabra. Departament d'Economia i Empresa |
|---|---|
| Data(s) |
15/09/2005
|
| Resumo |
The set covering problem is an NP-hard combinatorial optimization problemthat arises in applications ranging from crew scheduling in airlines todriver scheduling in public mass transport. In this paper we analyze searchspace characteristics of a widely used set of benchmark instances throughan analysis of the fitness-distance correlation. This analysis shows thatthere exist several classes of set covering instances that have a largelydifferent behavior. For instances with high fitness distance correlation,we propose new ways of generating core problems and analyze the performanceof algorithms exploiting these core problems. |
| Identificador | |
| Idioma(s) |
eng |
| Direitos |
L'accés als continguts d'aquest document queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons info:eu-repo/semantics/openAccess <a href="http://creativecommons.org/licenses/by-nc-nd/3.0/es/">http://creativecommons.org/licenses/by-nc-nd/3.0/es/</a> |
| Palavras-Chave | #Operations Management #set covering #iterated local search |
| Tipo |
info:eu-repo/semantics/workingPaper |
