TSP allow loops

TSP allow loops

par Jonas Reichhardt,
Nombre de réponses : 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

En réponse à Jonas Reichhardt

Re: TSP allow loops

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