Progress Control in Variable Neighbourhood Search

T. Curtois, L. Fijn van Draat, Gerhard F. Post, Jan C.W. van Ommeren

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

Abstract

The methods of intensification and diversification are indispensable in successful meta heuristics for local search. Intensification corresponds in some sense to local optimisation; the neighbourhood of a solution is searched intensively for solutions which are better or have better opportunities. On the other hand, diversification tries to escape from (relatively small) neighbourhoods to solutions which might lead to better final results. A heuristic that is well aware of the intensification versus diversification problems, is the Variable Neighbourhood Search (VNS), see [2]. In this method, more than one neighbourhood structure is considered. After finishing intensification with respect to one neighbourhood, the heuristic diversifies to another neighbourhood. In this way one hopes to escape from poor local optima. In this work we introduce a model to predict the quality of a neighbourhood. We use this model to identify 'bad' neighbourhoods and avoid searching them. We call this process 'Progress Control'. Computational results are presented to show that progress control helps us finding better solutions in the same amount of time.
Original languageUndefined
Title of host publicationProceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling
EditorsE.K. Burke, H. Rudová
Place of PublicationBrno, The Czech Republic
PublisherFaculty of Informatics, Masaryk University
Pages376-380
Number of pages5
ISBN (Print)80-210-3726-1
Publication statusPublished - 2006
Event6th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2006 - Brno, Czech Republic
Duration: 30 Aug 20061 Sep 2006
Conference number: 6

Publication series

Name
PublisherFaculty of Informatics, Masaryk University
Number10

Conference

Conference6th International Conference on the Practice and Theory of Automated Timetabling, PATAT 2006
Abbreviated titlePATAT 2006
CountryCzech Republic
CityBrno
Period30/08/061/09/06

Keywords

  • EWI-8348
  • METIS-237670
  • IR-63728

Cite this