The authors consider a generalization of the classical traveling salesman problem (TSP) called the precedence constrained traveling salesman problem (PCTSP), i.e. given a directed complete graph G(V,E), a distance Dij on each arch (i,j)∈E, precedence constraints ¸≺ on V, they want to find a minimum distance tour that starts node 1∈V, visits all the nodes in V-∈1∈, and returns node 1 again so that node i is visited before node j when i≺j. The authors present a branch and bound algorithm for the exact solutions to the PCTSP incorporating lower bounds computed from the Lagrangean relaxation. The present lower bounding procedure is a generalization of the restricted Lagrangean method that has been successfully adapted to the TSP by Balas and Christofides. The branch and bound algorithm also incorporates several heuristics and variable reduction tests. The computational results with up to 49 nodes show that the present algorithm computes exact solutions to several classes of precedence constraints within acceptable computational requirements.
