Algorithm to generate TSP solutions randomly

The most common heuristics to solve the TSP problem (in particular the Kernighan–Lin heuristic) require to work on a randomly generated tour and to improve the solution starting from that. However, the only way I came up with to do that is to generate a random permutation of the vertices and to check if it is a solution or not.

For large instances of the problem (for example 1000 vertices) this process can take a while. Is there another smart way to generate a random tour for TSP problem faster?? Note that I'm looking for a tour, no matter the cost, and not an optimal solution.

Thanks in advance

If you're just looking for any tour, you can use Breadth or Depth First Search to generate a path while marking the nodes visited.

You could just create an array which contains ths problem's cities and then randomly shuffle that array (there are methods that could do this). The resulting array is in fact a random permutation.

You want to use a space-filling-curve.