A Lexi Search Approach to Generalized Travelling Salesman Problem

Abstract

There are n cities and N = {1, 2, 3… n}. The cost matrix C(i, j) [i, j=1,2,3,…..,n] is the cost of the
salesman visiting from city i to city j is given. We are given a partition of cities into groups. The
restriction for the salesman is that he should visit from one group to another group. The problem is to find
a feasible tour for n cities for the salesman with minimum total cost with the above restriction. We
propose a Lexi Search Algorithm based on Pattern Recognition Technique for solving “Generalized
Traveling Salesman Problem†with an illustrative example.
For this problem a computer program is developed for the algorithm and is tested. It is observed that it
takes less time for solving fairly higher dimension problem also.