The travelling salesman problem with precedence constraints

The Travelling Salesman Problem with Precedence Constraints (TSP-PC) is the usual Travelling Salesman Problem with the restrictions that the salesman should start from a prescribed node (i.e., a headquarters) and each admissible tour is to satisfy k precedence relations denoted by ir < jr; r=1,2,...,k. That is, the node jr should not be visited unless node ir is already visited. This problem is NP-hard and arises in practical transportation and sequencing problems. In this paper, a lexisearch algorithm has been developed for obtaining exact optimal solution. Also, simple and hybrid genetic algorithms have been developed for obtaining heuristically optimal solution to the problem. The efficiency of the genetic algorithms to the TSP-PC as against lexisearch approach has been examined for a variety of randomly generated test problems.