Thumbnail

A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem

Likas, Aris; Paschos, Vangelis (2002), A note on a new greedy-solution representation and a new greedy parallelizable heuristic for the traveling salesman problem, Chaos, Solitons and Fractals, 13, 1, p. 71-78. http://dx.doi.org/10.1016/S0960-0779(00)00227-7

View/Open
Type
Article accepté pour publication ou publié
Date
2002
Journal name
Chaos, Solitons and Fractals
Volume
13
Number
1
Publisher
Elsevier
Pages
71-78
Publication identifier
Metadata
Show full item record
Author(s)
Likas, Aris
Paschos, Vangelis
Abstract (EN)
A new approach is presented to the traveling salesman problem (TSP) relying on a novel greedy representation of the solution space and leading to a different definition of neighborhood structures required in many local and random search approaches. Accordingly, a parallelizable search strategy is proposed based upon local search with random restarts that exploits the characteristics of the representation. Preliminary experimental results on several sets of test problems, among which very well-known benchmarks, show that the representation developed, matched with the search strategy proposed, attains high quality near-optimal solutions in moderate execution times.
Subjects / Keywords
Traveling salesman problem