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

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

doi:10.1016/0167-6377(92)90028-2

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

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

Research output: Contribution to journal › Article › peer-review

130 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 language	English (US)
Pages (from-to)	219-224
Number of pages	6
Journal	Operations Research Letters
Volume	11
Issue number	4
DOIs	https://doi.org/10.1016/0167-6377(92)90028-2
State	Published - May 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

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

Keywords

Markov
TSP
optimization
simulated annealing

Access to Document

10.1016/0167-6377(92)90028-2

Cite this

@article{3c5775f5d4bf4081ae6a57a427ae6d0b,

title = "Large-step markov chains for the TSP incorporating local search heuristics",

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%.",

keywords = "Markov, TSP, optimization, simulated annealing",

author = "Olivier Martin and Otto, {Steve W.} and Felten, {Edward W.}",

note = "Funding Information: * This work was supported in part by the grants DOE-FG03-85ER25009 and NSF-ECS-8909127, and by a grant from the PSC-CUNY Research Award Program. Correspondence to: Prof. Steve W. Otto, Dept. of Computer Science and Engineering, Oregon Graduate Institute of Science and Technology, 19600 NW Von Neuman Drive, Beaver-ton, OR 97006-1999, USA. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.",

year = "1992",

month = may,

doi = "10.1016/0167-6377(92)90028-2",

language = "English (US)",

volume = "11",

pages = "219--224",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "4",

}

TY - JOUR

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

AU - Martin, Olivier

AU - Otto, Steve W.

AU - Felten, Edward W.

N1 - Funding Information: * This work was supported in part by the grants DOE-FG03-85ER25009 and NSF-ECS-8909127, and by a grant from the PSC-CUNY Research Award Program. Correspondence to: Prof. Steve W. Otto, Dept. of Computer Science and Engineering, Oregon Graduate Institute of Science and Technology, 19600 NW Von Neuman Drive, Beaver-ton, OR 97006-1999, USA. Copyright: Copyright 2014 Elsevier B.V., All rights reserved.

PY - 1992/5

Y1 - 1992/5

N2 - 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%.

AB - 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%.

KW - Markov

KW - TSP

KW - optimization

KW - simulated annealing

UR - http://www.scopus.com/inward/record.url?scp=0001463650&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0001463650&partnerID=8YFLogxK

U2 - 10.1016/0167-6377(92)90028-2

DO - 10.1016/0167-6377(92)90028-2

M3 - Article

AN - SCOPUS:0001463650

SN - 0167-6377

VL - 11

SP - 219

EP - 224

JO - Operations Research Letters

JF - Operations Research Letters

IS - 4

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this