Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows

Arpad Rimmel 1 Fabien Teytaud 2, 3 Tristan Cazenave 1
3 TAO - Machine Learning and Optimisation
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The traveling salesman problem with time windows is known to be a really difficult benchmark for optimization algorithms. In this paper, we are interested in the minimization of the travel cost. To solve this problem, we propose to use the nested Monte-Carlo algorithm combined with a Self-Adaptation Evolution Strategy. We compare the efficiency of several fitness functions. We show that with our technique we can reach the state of the art solutions for a lot of problems in a short period of time.
Complete list of metadatas

Cited literature [16 references]  Display  Hide  Download

https://hal.inria.fr/inria-00563668
Contributor : Fabien Teytaud <>
Submitted on : Monday, February 7, 2011 - 10:31:41 AM
Last modification on : Tuesday, April 10, 2018 - 3:26:01 PM
Long-term archiving on : Sunday, May 8, 2011 - 2:53:43 AM

File

tsptw.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00563668, version 1

Collections

Citation

Arpad Rimmel, Fabien Teytaud, Tristan Cazenave. Optimization of the Nested Monte-Carlo Algorithm on the Traveling Salesman Problem with Time Windows. Evostar, Apr 2011, Turin, Italy. ⟨inria-00563668⟩

Share

Metrics

Record views

520

Files downloads

1289