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
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.