2
$\begingroup$

According to the TSP Gallery moats provide lower bounds for the optimal solution of TSP instances.
On the webpage they are depicted as blue rings around red disks, whose radii represent maximal vertex weights that, when subtraced from adjacent edges' lengths do not yield negative values.

One statement on the page says: "any tour must have length at least twice the sum of the radii of the red "zones" plus twice the sum of the widths of the blue "moats"; this proves that the indicated tour is optimal." but that doesn't quite comply with the visualisation:

enter image description here

If you look at the moats around disks that I have marked with a yellow boundary, you will see that they do not contribute to tour length and no explanation of what moats actually are is given.

Question:
what are the moats actually, i.e. am I right if I suspect that they resemble circles of minimal radius sum whose convolution with the connected components of the red disks yields a biconnected image of contacting or overlapping convoluted disks?

Improve this question
$\endgroup$
3
  • $\begingroup$ In the picture there are 5 moats ( one very narrow) and each is crossed twice . The moat at the top left surrounds a chain of 5 tangent circles. The tour crosses the moat , traverses the chain, and crosses the moat again. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 23, 2020 at 7:17
  • $\begingroup$ @AaronMeyerowitz IMHO the visualization of moats would be clearer if the boundary of the moats were drawn in a different color; currently it is from visual inspecion not immediately clear whether the blue areas are the union of annuli on whcih the red disks are drawn or whether they are single areas with points within a fixed distance from a maximal collection of red disks in contact. $\endgroup$
    – Manfred Weis
    Commented Nov 23, 2020 at 15:47
  • $\begingroup$ I suppose. Since it is stated that each moat is crossed twice, it becomes clear from the illustration that a moat is not a single annulus. Dig around in that gallery staring at lower bounds math.uwaterloo.ca/tsp/methods/opt/opt.htm and continuing on to control zones and sub-tour elimination. Then see if the definition or the gallery gives a better idea. $\endgroup$
    – Aaron Meyerowitz
    Commented Nov 23, 2020 at 17:58

1 Answer 1

Reset to default
1
$\begingroup$

The moat is not the disk width between independent cities, but the disk filling between several tangent circular city subsets. Moat should be a by-product of solving TSP problem through linear programming method. If you have used the geodual software released by the University of Cologne(as shown in fig.1), you will find that when solving TSP, the path will be generated from the interior of the urban subset first, and then connected to each subset. Therefore, the significance of moat should be the maximum extension radius between several tangent circle subsets.

enter image description here

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .