TSP allow loops

TSP allow loops

von Jonas Reichhardt -
Anzahl Antworten: 1

Good afternoon,

are loops allowed in the randomly generated distance matrix for the Travelling Salesman Problem.

If loops are not allowed which my intuition suggests, the diagonal of the matrix has to be zeroed.

Does these zeros count to the percentage which should be zeroed out?

Thanks in advance,
Jonas

Als Antwort auf Jonas Reichhardt

Re: TSP allow loops

von Wolfgang Schreiner -

I assume that by "loops" you mean edges "x->x" from a node "x" to itself.

Yes, such edges may also exist (but apparently they will never appear in a shortest path), i.e., d(x,x) may be non-zero. You need not treat this case specially, just set (by application of a random number generator) for every node pair (x,y) the distance d(x,y) with the same probability "p" to a non-zero value.