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

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 di fferent definition of neighborhood structures required in many local and ra ndom search approaches. Accordingly, a parallelizable search strategy is pr oposed based upon local search with random restarts that exploits the chara cteristics of the representation. Preliminary experimental results on sever al sets of test problems, among which very well-known benchmarks, show that the representation developed, matched with the search strategy proposed, a ttains high quality near-optimal solutions in moderate execution times. (C) 2001 Elsevier Science Ltd. All rights reserved.