Travelling Salesman which can repeat cities In the TSP problem, we usually assume a complete graph. If we can only visit each city once, we need a complete graph to ensure that there will be a path from every city to every other city. This is easy to accomplish as if there is no straight path between A and B, we can simply assign a new edge whose length is the shortest path between A and B.

However, if we have a sparse graph, maybe we can benefit from not having a complete graph. In this case, we might be forced to repeat vertices. If our graph is only 3 cities, and only two edges, connecting (1, 2) and (2, 3), then the solution must repeat city 2: 1 - 2 - 3 - 2 - 1.

I am struggling to find examples of TSP in the scientific literature which assume a non complete directed graph. Any known references? Any keywords I may be missing? In this case, cycles are allowed.

I am especially interested in how we could separate subtour inequalities when cycles are present.  I am hoping for a solution based on integer linear programming and branch-and-bound, and am wondering how to add subtour elimination inequalities.  Any ideas?
This is directly equivalent to metric TSP. That is, TSP in which the distances obey the triangle inequality: for all cities $A$, $B$ and&nbsp;$C$, the distance from $A$ to&nbsp;$B$ is no greater than the distance from $A$ to $C$ to&nbsp;$B$.

As Raphael points oun in the comments, you can reduce an instance of your problem to metric TSP by setting the distance from $A$ to&nbsp;$B$ to be the length of the shortest $A$&ndash;$B$ path in the original graph. This shows that your problem is no harder than metric TSP. But, conversely, every instance of metric TSP is already an instance of your problem. This is because, in metric TSP, the triangle inequality guarantees that it's never necessary to revisit a vertex so allowing revisiting doesn't change the optimal solution.