An efficient technique to solve TSP and its extension to spatially spread vertices

摘要

Many research references are available to solve the conventional Travelling Salesman Problem (TSP). A recent heuristic approach, GENI, by Michel Gendreau et al.(1) is said to provide path efficient solutions. Our present paper proposes a novel strategy called FANI (Farthest neighbour nearest insertion) which tackles the twin issues of the algorithm performance namely, path efficiency and time efficiency. It is demonstrated through extensive experimentation that our method is better than GENI(1). To solve a conventional TSP, this paper proposes a two-phase approach. In the first phase, farthest neighbour concept is adopted, and an initial tour spanning through three farthest neighbours is constructed. In the subsequent phase, the remaining vertices are inserted, one at a time, considering the nearest neighbour concept. Further, it is proposed to extend this strategy to solve a more pragmatic TSP, a problem in which the vertices are not dimensionless us often dealt in literature, but they have spatial spread, as found in several situations. The vertices may have lengthwise and/or breadthwise stretches (spread), Such points can be identified as spatially spread vertices (SSV) since such SSVs provide entry-exit options. Solving such TSPs becomes more complicated, and it is this issue which is taken up in this paper, and to the best of our knowledge such a problem has not been dealt in the TSP literature. [References: 19]