Find all the special graphs which can reduced to the shortest paths graph
Nearest neighbor, nearest insertion, farthest insertion, and cheapest insertion are just some heuristics to get you started. You can also model the problem as a maximum flow integer program.

http://www.ida.liu.se/~TDDB19/reports_2003/htsp.pdf