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 we 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.
No takes yet. Share an insight, caveat, or question.
Bianco et al. (1994) studied this question.