Thumbnail

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

Cazenave, Tristan; Teytaud, Fabien (2012), Application of the Nested Rollout Policy Adaptation Algorithm to the Traveling Salesman Problem with Time Windows, in Hamadi, Youssef; Schoenauer, Marc, Learning and Intelligent Optimization 6th International Conference, LION 6, Paris, France, January 16-20, 2012, Revised Selected Papers, Springer : Berlin, p. 42-54. 10.1007/978-3-642-34413-8_4

View/Open
Type
Communication / Conférence
Date
2012
Conference title
6th International Conference on Learning and Intelligent Optimization, LION 6
Conference date
2012-01
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
Book author
Hamadi, Youssef; Schoenauer, Marc
Publisher
Springer
Series title
Lecture Notes in Computer Science
Series number
7219
Published in
Berlin
ISBN
978-3-642-34412-1
Number of pages
514
Pages
42-54
Publication identifier
Metadata
Show full item record
Author(s)
Cazenave, Tristan
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Teytaud, Fabien
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
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.
Subjects / Keywords
Nested Monte-Carlo; Nested Rollout Policy Adaptation; Traveling Salesman Problem with Time Windows