A recent trend in local search concerns the exploitation of several different neighborhoods so as to increase the ability of the algorithm to navigate the search space. In this work we investigate a hybridization technique, that we call Neighborhood Portfolio Approach, that consists in the interleave of local search techniques based on various combinations of neighborhoods. In particular, we are able to select the most effective search technique through a systematic analysis of all meaningful combinations built upon a set of basic neighborhoods. The proposed approach is applied to two practical problems belonging to the timetabling family, and systematically tested and compared on real-world instances. The experimental analysis shows that our approach leads to automatic design of new algorithms that provide better results than basic local search techniques.

Neighborhood portfolio approach for local search applied to timetabling problems

DI GASPERO, Luca;SCHAERF, Andrea
2006-01-01

Abstract

A recent trend in local search concerns the exploitation of several different neighborhoods so as to increase the ability of the algorithm to navigate the search space. In this work we investigate a hybridization technique, that we call Neighborhood Portfolio Approach, that consists in the interleave of local search techniques based on various combinations of neighborhoods. In particular, we are able to select the most effective search technique through a systematic analysis of all meaningful combinations built upon a set of basic neighborhoods. The proposed approach is applied to two practical problems belonging to the timetabling family, and systematically tested and compared on real-world instances. The experimental analysis shows that our approach leads to automatic design of new algorithms that provide better results than basic local search techniques.
File in questo prodotto:
File Dimensione Formato  
fulltext5.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 489.92 kB
Formato Adobe PDF
489.92 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
05-mntt_jmma.pdf

non disponibili

Tipologia: Altro materiale allegato
Licenza: Non pubblico
Dimensione 489.92 kB
Formato Adobe PDF
489.92 kB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11390/877122
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 75
  • ???jsp.display-item.citation.isi??? ND
social impact