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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Aarts, E. and Lenstra, J. K. (eds.): Local Search in Combinatorial Optimization, Wiley, Chirchester, UK, 1997.
Ahuja, R. K., Orin, J. B. and Sharma, D.: Very large scale neighborhood search, Int. Trans. Oper. Res. 7 (2000), 301–317.
Birattari, M., Stützle, T., Paquete, L. and Varrentrapp, K.: A racing algorithm for configuring metaheuristics, in W. B. Langdon, E. Cantú-Paz, K. Mathias, R. Roy, D. Davis, R. Poli, K. Balakrishnan, V. Honavar, G. Rudolph, J. Wegener, L. Bull, M. A. Potter, A. C. Schultz, J. F. Miller, E. Burke and N. Jonoska (eds.), GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, NY, USA, 2002, pp. 11–18.
Conover, W.: Practical Nonparametric Statistics, 3rd edn., John Wiley & Sons, New York, NY, USA, 1999.
Di Gaspero, L. and Schaerf, A.: \(\textsc{EasyLocal++}\): An object-oriented framework for flexible design of local search algorithms, Softw. Pract. Exp. 33(8) (2003), 733–765.
Glover, F. and Laguna, M.: Tabu Search, Kluwer, Boston, MA, USA, 1997.
Hansen, P. and Mladenović, N.: An introduction to variable neighbourhood search, in S. Voß, S. Martello, I. Osman and C. Roucairol (eds.), Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, MA, USA, 1999, pp. 433–458.
Hoos, H. H. and Stützle, T.: Stochastic Local Search Foundations and Applications, Morgan Kaufmann, San Francisco, CA, USA, 2005.
Itai, A., Rodeh, M. and Tanimoto, S. L.: Some matching problems for bipartite graphs, Technical Report TR93, IBM Israel Scientific Center, Haifa, Israel, 1977.
Kirkpatrick, S., Gelatt, C. D. Jr. and Vecchi, M. P.: Optimization by simulated annealing, Science 220 1983, 671–680.
Lourenço, H. R., Martin, O. and Stützle, T.: Applying iterated local search to the permutation flow shop problem, in F. Glover and G. Kochenberger (eds.), Handbook of Metaheuristics, Kluwer, Boston, MA, USA, 2003.
Pesant, G. and Gendreau, M.: A constraint programming framework for local search methods, J Heuristics 5 (1999), 255–279.
Rossi-Doria, O. et al.: A comparison of the performance of different metaherustic on the timetabling problem, in E. Burke and P. D. Causmaecker (eds.), Proc. of the 4th Int. Conf. on the Practice and Theory of Automated Timetabling (PATAT-2002), Selected Papers, Vol. 2740 of Lecture Notes in Computer Science. Berlin-Heidelberg, Germany, 2003, pp. 329–351.
Schaerf, A.: Tabu search techniques for large high-school timetabling problems, in Proc. of the 13th Nat. Conf. on Artificial Intelligence (AAAI-96), Portland, OR, USA, 1996, pp. 363–368.
Schaerf, A.: A survey of automated timetabling, Artif. Intell. Rev. 13(2) (1999), 87–127.
Selman, B., Kautz, H. A. and Cohen, B.: Noise strategies for improving local search, in Proc. of the 12th Nat. Conf. on Artificial Intelligence (AAAI-94). Seattle, WA, USA, 1994, pp. 337–343.
Stützle, T.: Iterated local search for the quadratic assignment problem, Technical Report AIDA-99-03, FG Intellektik, TU Darmstadt, 1998.
Vaessens, R., Aarts, E. and Lenstra, J. K.: Job shop scheduling by local search, INFORMS J. Comput. 8(3) 1996, 302–317.
Voß, S., Martello, S., Osman, I. and Roucairol, C. (eds.): Meta-Heuristics: Advances and Trends in Local Search Paradigms for Optimization, Kluwer, Boston, MA, USA, 1999.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Di Gaspero, L., Schaerf, A. Neighborhood Portfolio Approach for Local Search Applied to Timetabling Problems. J Math Model Algor 5, 65–89 (2006). https://doi.org/10.1007/s10852-005-9032-z
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10852-005-9032-z
Mathematical Subject Classifications (2000)
- 90B40 Search theory
- 68W20 Randomized algorithms
- 68W40 Analysis of algorithms
- 90B35 Scheduling theory
- deterministic