Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED
I don't know how to solve your problem or show its NP-Hardness but you can find all pair shortest path to convert your graph to metric one, just replace $e_{a,b}$ with shortest path from a&rarr;b and if there isn't edge between $a,b$ add new edge with shortest path weight, now you can run some approximation for TSP to find approximation for your problem, as I know best approximation for TSP is currently $O({\log n \over \log{ \log n}})$. Base idea is using Held-Karp relaxation and finding special spanning tree then using method like Christofides algorithm. (it has some new definitions like Thin tree, ... which makes it harder than other methods for asymmetric case), you can also use known $O(\log n)$ approximations. Also I thought about your problem to approximate it with a minimum cycle cover, but I couldn't get good result. If I found anything I'll update this answer.