The Precedence Constrained Traveling Salesman Problem

We 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 D_<ij> on each arc (i,j) ∈ E, precedence constraints ≺ on V, we 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. We present a branch and bound algorithm for the exact solutions to the PCTSP incorporating lower bounds computed from the Lagrangean relaxation. Our lower bounding procedure is a generalization of the restricted Lagrangean method that has been successfully adapted to the TSP by Balas and Christofides [2]. Our branch and bound algorithm also incorporates several heuristics and variable reduction tests. The computational results with up to 49 nodes b-how that our algorithm computes exact solutions to several classes of precedence constraints within acceptable computational requirements.