An Alternate Travelling Salesman Problem

We consider Lexi-Search Approach using Pattern Recognition Technique for a Travelling Sales Man Problem (TSP) in which he wants to visit m cities, where m is even. Let N be the set of n stations defined as N= {1, 2, 3, 4…n} and N1UN2=N. The city ‘1’ taken as the home city and it is in N1. He has to starts from head quarter city {1} which is in N1 from there he visits a city in N2. In this way the salesman visits m cities alternatively and m ? n. D (i, j) be the distance or cost matrix. A salesman starts for his tour from a home city (say 1) and come back to it after completing the all the m cities. There is a restriction that he must visit the N1, N2 groups alternatively. An exact algorithm is proposed for this TSP. The algorithm solves the problem on identify the key patterns which optimize the objective of the cost/distance. Hence the objective of the problem is to find a tour with minimum total distance while completing all the m cities alternatively by above considerations.