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

Thumbnail
View/Open
Date
2012
Collection title
Lecture Notes in Computer Science
Collection Id
7219
Dewey
Recherche opérationnelle
Sujet
Nested Monte-Carlo; Nested Rollout Policy Adaptation; Traveling Salesman Problem with Time Windows
DOI
http://dx.doi.org/10.1007/978-3-642-34413-8_4
Conference name
6th International Conference on Learning and Intelligent Optimization, LION 6
Conference date
01-2012
Conference city
Paris
Conference country
France
Book title
Learning and Intelligent Optimization 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers
Author
Hamadi, Youssef; Schoenauer, Marc
Publisher
Springer
Publisher city
Berlin
Year
2012
Pages number
514
ISBN
978-3-642-34412-1
Book URL
http://dx.doi.org/10.1007/978-3-642-34413-8
URI
https://basepub.dauphine.fr/handle/123456789/11619
Collections
Metadata
Show full item record
Author
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
Item number of pages
42-54
Abstract (EN)
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.