Neighborhood Portfolio Approach for Local Search Applied to Timetabling Problems |
| |
Authors: | Luca Di Gaspero Andrea Schaerf |
| |
Institution: | (1) Dipartimento di Ingegneria Elettrica, Gestionale e Meccanica – Università di Udine, Udine, Italy |
| |
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. |
| |
Keywords: | 90B40 Search theory 68W20 Randomized algorithms 68W40 Analysis of algorithms 90B35 Scheduling theory deterministic |
本文献已被 SpringerLink 等数据库收录! |