Constrained shortest path tour problem: models, valid inequalities, and Lagrangian heuristics

The constrained shortest path tour problem (CSPTP) is an NP-hard combinatorial optimization problem defined on a connected directed graphD=(V,A), whereVis the set of nodes andAis the set of nonnegative weighted arcs. Given two distinct nodess,t is an element of V, an integer valueN>1, and node disjoint subsetsTi subset of V,i=1,MIDLINE HORIZONTAL ELLIPSIS,N, the CSPTP aims at finding the shortest trail fromstotwhile visiting at least one node in every subsetT1,T2,MIDLINE HORIZONTAL ELLIPSIS,TN, in this order. In this paper, we perform a comparative analysis between two integer programming (IP) models for the problem. We also propose valid inequalities and a Lagrangian-based heuristic framework. Branch-and-bound algorithms from the literature, as well as a metaheuristic approach, are used for comparison. Extensive computational experiments carried out on benchmark data sets show the effective use of valid inequalities and the quality of bounds obtained by the Lagrangian framework. Because benchmark instances do not require a great computational effort of IP models in the sense that their optimality is reached at the root node of the CPLEX branch-and-cut search tree, we introduce new challenging CSPTP instances for which our solution approaches outperform existing ones for the problem.