Exact and heuristic procedures for the Traveling Salesman Problem with Precedence Constraints, based on dynamic programming

The Traveling Salesman Problem with Precedence Constraints is to find an hamiltonian tour of minimum cost in a graph G=(X,A) of n vertices, starting from vertex 1, visiting every vertex that must precede i before i (i=2,3,...,n) and returning to vertex 1. This problem is NP-hard and arises in practical transportation and sequencing problems. In this paper the authors describe a new bounding procedure and a new optimal algorithm, based on dynamic programming. Computational results are given for randomly generated test problems, including the ‘dial-a-ride’ problem with the classical TSP objective function.