A travelling salesman problem (TSP) with multiple job facilities

In this paper we have considered a variation of usual travelling salesman problem introducing a more realistic situation. The problem can be described as follows: There are N stations to be visited and M distinct jobs to be performed by a salesman. The distance between each pair of stations and facilities for jobs at each station, are known. The salesman starts from a station and returns to it after completing all the jobs. The salesman need not visit all the stations and should not visit a station more than once. The problem is to find a tour of the salesman such that the total distance travelled is minimum while completing all the M jobs. Kumar and Bansal used the Dynamic programming technique to solve the problem. We have considered the Lexicographic Search Approach to find the optimal solution.