A Precedence Constraints in a Travelling Salesman Problem (TSP) with Multiple Job Facilities

Abstract

In this paper, we have considered precedence constraints in the travelling salesman problem with multiple job facilities at each station. By precedence constraints one means that the station(s) (cities or links or nodes) are visited (or completed) in such a way that a particular station is to be preceded (completed or visited) by another station (precedence relation need not be immediate). 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 (home station denoted as ‘A₀’) and returns back to it after completing all the jobs. The salesman need not visit all the stations and should not visit a station more than once. Also the salesman has to perform the jobs as early as possible. The objective is to find a tour of the salesman by using the precedence constraints such that the total distance traveled is minimum while completing all the ‘M’ jobs, on the basis of first come first serve.