Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows

Tristan Cazenave 1 Fabien Teytaud 1, 2
1 LAMSADE - Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision
2 HEC Paris - Ecole des Hautes Etudes Commerciales
Abstract : In this paper, we are interested in the minimization of the travel cost of the traveling salesman problem with time windows. In order to do this minimization we use a Nested Rollout Policy Adaptation (NRPA) algorithm. NRPA has multiple levels and maintains the best tour at each level. It consists in learning a rollout policy at each level. We also show how to improve the original algorithm with a modified rollout policy that helps NRPA to avoid time windows violations.
Keywords : Nested Monte-Carlo Nested Rollout Policy Adaptation Trav- eling Salesman Problem with Time Windows
Type de document :
Communication dans un congrès
LION, Jan 2012, Paris, France. pp.42 - 54, 2012, Learning and Intelligent Optimization. 〈10.1007/978-3-642-34413-8_4〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/hal-01406457
Contributeur : Fabien Teytaud <>
Soumis le : jeudi 1 décembre 2016 - 11:15:25
Dernière modification le : jeudi 11 janvier 2018 - 06:17:30
Document(s) archivé(s) le : mardi 21 mars 2017 - 12:58:20

Fichier

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

Identifiants

Collections

PSL

Citation

Tristan Cazenave, Fabien Teytaud. Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows. LION, Jan 2012, Paris, France. pp.42 - 54, 2012, Learning and Intelligent Optimization. 〈10.1007/978-3-642-34413-8_4〉. 〈hal-01406457〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

104

Téléchargements de fichiers

41

Contact


archive-ouverte@inria.fr