New formulations for the elementary shortest-path problem visiting a given set of nodes

• We introduce new formulations of the shortest-path problem visiting given nodes.
• Theoretical results are illustrated with examples.
• We adapt Martin’s subtour elimination constraints for digraphs.
• We solve efficiently TSPLIB instances with up to four hundred nodes.

Consider a directed graph G=(V,A)G=(V,A) with a set of nodes V and a set of arcs A, and let cuv denote the length of an arc uv ∈ A. Given two nodes s and t of V, we are interested in the problem of determining a shortest-path from s to t in G   that must visit only once all nodes of a given set P⊆V−{s,t}P⊆V−{s,t}. This problem is NP-hard for P=V−{s,t}P=V−{s,t}. In this paper, we develop three new compact formulations for this problem. The first one is based on the spanning tree polytope. The second model is a primal-dual mixed integer model presenting a small number of variables and constraints; and the last one is obtained from a flow-based compact model for the Steiner traveling salesman problem (TSP). Numerical experiments indicate that the second compact model allows the efficient solution of randomly generated and benchmark (from the TSPLIB) instances of the problem with hundreds of nodes.