On Neighborhood Tree Search

Houda Derbel 1 Bilel Derbel 2, 3
3 DOLPHIN - Parallel Cooperative Multi-criteria Optimization
LIFL - Laboratoire d'Informatique Fondamentale de Lille, Inria Lille - Nord Europe
Abstract : We consider the neighborhood tree induced by alternating the use of different neighborhood structures within a local search descent. We investigate the issue of designing a search strategy operating at the neighborhood tree level by exploring different paths of the tree in a heuristic way. We show that allowing the search to 'backtrack' to a previously visited solution and resuming the iterative variable neighborhood descent by 'pruning' the already explored neighborhood branches leads to the design of effective and efficient search heuristics. We describe this idea by discussing its basic design components within a generic algorithmic scheme and we propose some simple and intuitive strategies to guide the search when traversing the neighborhood tree. We conduct a thorough experimental analysis of this approach by considering two different problem domains, namely, the Total Weighted Tardiness Problem (SMTWTP), and the more sophisticated Location Routing Problem (LRP). We show that independently of the considered domain, the approach is highly competitive. In particular, we show that using different branching and backtracking strategies when exploring the neighborhood tree allows us to achieve different trade-offs in terms of solution quality and computing cost.
Type de document :
Communication dans un congrès
Genetic and Evolutionary Computation Conference (GECCO'12), Sep 2012, Philadelphie, United States. ACM, 2012
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00728531
Contributeur : Bilel Derbel <>
Soumis le : vendredi 28 décembre 2012 - 11:41:20
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13
Document(s) archivé(s) le : vendredi 29 mars 2013 - 02:20:09

Fichiers

nts.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00728531, version 1
  • ARXIV : 1212.6510

Citation

Houda Derbel, Bilel Derbel. On Neighborhood Tree Search. Genetic and Evolutionary Computation Conference (GECCO'12), Sep 2012, Philadelphie, United States. ACM, 2012. 〈hal-00728531〉

Partager

Métriques

Consultations de la notice

284

Téléchargements de fichiers

155