A note on characterizing the k-OPT neighborhood via group theory

Authors
Colletti, BW Barnes, JW Dokov, S
Citation
Bw. Colletti et al., A note on characterizing the k-OPT neighborhood via group theory, J HEURISTIC, 5(1), 1999, pp. 47-51
Citations number
6
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
JOURNAL OF HEURISTICS
ISSN journal
13811231 → ACNP
Volume
5
Issue
1
Year of publication
1999
Pages
47 - 51
Database
ISI
SICI code
1381-1231(199904)5:1<47:ANOCTK>2.0.ZU;2-H
Abstract
Group theory can be used to model and synthesize the neighborhood of Travel ing Salesman tours reachable through k-OPT exchanges. A primary concept is that a dihedral group action partitions the sets of cut arcs so that k-OPT exchanges of orbital elements are conjugate. Also presented is a method to produce all k-OPT exchanges for a given set of cut area.