Skip to Main content Skip to Navigation
Conference papers

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

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.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/hal-01406457
Contributor : Fabien Teytaud <>
Submitted on : Thursday, December 1, 2016 - 11:15:25 AM
Last modification on : Thursday, January 21, 2021 - 10:54:03 PM
Long-term archiving on: : Tuesday, March 21, 2017 - 12:58:20 PM

File

tsptwnrpa.pdf
Files produced by the author(s)

Identifiers

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, ⟨10.1007/978-3-642-34413-8_4⟩. ⟨hal-01406457⟩

Share

Metrics

Record views

267

Files downloads

749