Large-step markov chains for the TSP incorporating local search heuristics

Olivier Martin, Steve W. Otto, Edward W. Felten

Research output: Contribution to journalArticlepeer-review

137 Scopus citations

Abstract

We consider a new class of optimization heuristics which combine local searches with stochastic sampling methods, allowing one to iterate local optimization heuristics. We have tested this on the Euclidean Traveling Salesman Problem, improving 3-opt by over 1.6% and Lin-Kernighan by 1.3%.

Original languageEnglish (US)
Pages (from-to)219-224
Number of pages6
JournalOperations Research Letters
Volume11
Issue number4
DOIs
StatePublished - May 1992

All Science Journal Classification (ASJC) codes

  • Software
  • Management Science and Operations Research
  • Industrial and Manufacturing Engineering
  • Applied Mathematics

Keywords

  • Markov
  • TSP
  • optimization
  • simulated annealing

Fingerprint

Dive into the research topics of 'Large-step markov chains for the TSP incorporating local search heuristics'. Together they form a unique fingerprint.

Cite this