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

Thumbnail
Ouvrir
Date
2012
Titre de la collection
Lecture Notes in Computer Science
n° dans la collection
7219
Indexation documentaire
Recherche opérationnelle
Subject
Nested Monte-Carlo; Nested Rollout Policy Adaptation; Traveling Salesman Problem with Time Windows
Réf version publiée
http://dx.doi.org/10.1007/978-3-642-34413-8_4
Titre du colloque
6th International Conference on Learning and Intelligent Optimization, LION 6
Date du colloque
01-2012
Ville du colloque
Paris
Pays du colloque
France
Titre de l'ouvrage
Learning and Intelligent Optimization 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers
Auteur
Hamadi, Youssef; Schoenauer, Marc
Nom de l'éditeur
Springer
Ville de l'éditeur
Berlin
Année
2012
Nombre total de pages
514
ISBN
978-3-642-34412-1
URL de l'ouvrage
http://dx.doi.org/10.1007/978-3-642-34413-8
URI
https://basepub.dauphine.fr/handle/123456789/11619
Collections
Métadonnées
Afficher la notice complète
Auteur
Cazenave, Tristan
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Teytaud, Fabien
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Nombre de pages du document
42-54
Résumé en anglais
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.