Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows

Arpad Rimmel 1 Fabien Teytaud 2, 3 Tristan Cazenave 1
3 TAO - Machine Learning and Optimisation
CNRS - Centre National de la Recherche Scientifique : UMR8623, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique
Abstract : The traveling salesman problem with time windows is known to be a really difficult benchmark for optimization algorithms. In this paper, we are interested in the minimization of the travel cost. To solve this problem, we propose to use the nested Monte-Carlo algorithm combined with a Self-Adaptation Evolution Strategy. We compare the efficiency of several fitness functions. We show that with our technique we can reach the state of the art solutions for a lot of problems in a short period of time.
Type de document :
Communication dans un congrès
Evostar, Apr 2011, Turin, Italy. 2011
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00563668
Contributeur : Fabien Teytaud <>
Soumis le : lundi 7 février 2011 - 10:31:41
Dernière modification le : mardi 10 avril 2018 - 15:26:01
Document(s) archivé(s) le : dimanche 8 mai 2011 - 02:53:43

Fichier

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

Identifiants

  • HAL Id : inria-00563668, version 1

Collections

Citation

Arpad Rimmel, Fabien Teytaud, Tristan Cazenave. Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows. Evostar, Apr 2011, Turin, Italy. 2011. 〈inria-00563668〉

Partager

Métriques

Consultations de la notice

377

Téléchargements de fichiers

466