MHB Optimal TSP-Tour in Grid-City: Let's Find Out

  • Thread starter Thread starter mathmari
  • Start date Start date
AI Thread Summary
The discussion focuses on finding the optimal Traveling Salesman Problem (TSP) tour in a grid-like city structure, where distances are calculated using Manhattan metrics. The input consists of 203 points defined by specific coordinates, and participants explore potential starting points and the sequence of visits to minimize travel distance. The proposed optimal tour is confirmed to be correct, with a specific transition noted between points $(103,0)$ and $(100,2)$. Additionally, participants discuss approximation methods, such as the Nearest-Neighbor and Nearest-Insertion algorithms, questioning if both yield the same tour length. The complexity of the TSP in this grid context is emphasized, highlighting the need to consider all possible routes for an optimal solution.
mathmari
Gold Member
MHB
Messages
4,984
Reaction score
7
Hey! :o

We consider the TSP in Grid-City.
The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system.
The distance of $2$ points $C=(x,y)$ and $D=(x',y')$ is defined as $d(C,D)=|x-x'|+|y-y'|$.
An input for the TSP consists of $203$ points with the following coordinates:
$$(i,0), \text{ for } i=0, 1, \dots , 100, \\ (i,2), \text{ for } i=0, 1, \dots , 100, \\ (103, 0)$$
I want to give the optimal TSP-Tour. We have the following grid, or not?
View attachment 5787
(Wondering)

To find the optimal TSP-Tour from which point do we start? From which point we want? (Wondering)
If we choose one point to start, let's consider the $S=(0,0)$.
The second point will be either $A=(0,2)$ or $B=(1,0)$, right? Since $2=d(S,A)>d(S,B)=1$, the second point is $B=(1,0)$.
Or can we consider for the second point also the diagonal one, $(1,2)$ ? (Wondering)
Or is this not the correct way to find the optimal TSP-Tour? (Wondering)

When the roads are just the vertical and horizontal lines, we have that the distance of a point $(i,j)$ to an other is either $d_1=1$ or $d_2=2$, or not? (Wondering)
If this is true, is the optimal TSP-Tour the following?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (103,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$
But how do we get from the point $(103,0)$ to the point $(100,2)$ ? (Wondering)
 

Attachments

  • tsp.png
    tsp.png
    1.3 KB · Views: 100
Last edited by a moderator:
Physics news on Phys.org
mathmari said:
Hey! :o

We consider the TSP in Grid-City.
The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system.
The distance of $2$ points $C=(x,y)$ and $D=(x',y')$ is defined as $d(C,D)=|x-x'|+|y-y'|$.
An input for the TSP consists of $203$ points with the following coordinates:
$$(i,0), \text{ for } i=0, 1, \dots , 100, \\ (i,2), \text{ for } i=0, 1, \dots , 100, \\ (103, 0)$$
I want to give the optimal TSP-Tour. We have the following grid, or not?

(Wondering)

To find the optimal TSP-Tour from which point do we start? From which point we want? (Wondering)
If we choose one point to start, let's consider the $S=(0,0)$.
The second point will be either $A=(0,2)$ or $B=(1,0)$, right? Since $2=d(S,A)>d(S,B)=1$, the second point is $B=(1,0)$.
Or can we consider for the second point also the diagonal one, $(1,2)$ ? (Wondering)
Or is this not the correct way to find the optimal TSP-Tour? (Wondering)

When the roads are just the vertical and horizontal lines, we have that the distance of a point $(i,j)$ to an other is either $d_1=1$ or $d_2=2$, or not? (Wondering)
If this is true, is the optimal TSP-Tour the following?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (103,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$
But how do we get from the point $(103,0)$ to the point $(100,2)$ ? (Wondering)

Hey mathmari! (Smile)

That looks all correct to me. (Nod)
In principle any point could be connected to any other point, but in this particular case your solution will be optimal.
We can get from $(103,0)$ to $(100,2)$ with a normal transition that has distance $5$. (Emo)
 
I like Serena said:
In principle any point could be connected to any other point

So the road aren't just these gray lines, right? (Wondering)
View attachment 5792

Are the roads also the red lines:
View attachment 5793
? (Wondering)
I like Serena said:
in this particular case your solution will be optimal.

How do we know that? (Wondering)
 

Attachments

  • tsp.png
    tsp.png
    2 KB · Views: 90
  • tsp.png
    tsp.png
    4.4 KB · Views: 100
mathmari said:
So the road aren't just these gray lines, right? (Wondering)


Are the roads also the red lines:

? (Wondering)

Yep! (Nod)
That's pretty much the problem with TSP - we have to consider all possible roads to find the solution, which is why it is so hard to find an optimal solution.

How do we know that? (Wondering)

It follows from common sense.
If we pick any of your red lines, the total path length will surely increase.
I'm not exactly sure how to prove it though. (Worried)
 
I like Serena said:
That's pretty much the problem with TSP - we have to consider all possible roads to find the solution, which is why it is so hard to find an optimal solution.

Ah ok... (Thinking) After that I have to find the approximation for the TSP-Tour through the NEAREST-NEIGHBOR and then through the NEAREST-INSERTION with starting point $(0,0)$.

Do we get the following result through the NEAREST-NEIGHBOR?
$$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (100,0)\rightarrow (100,2) \rightarrow (99,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (103,0) \rightarrow (0,0)$$
(Wondering)

Is the length of this Tour equal to $410$ ? (Wondering) The NEAREST-INSERTION algorithm is the following:
Code:
T <- {1} 
while |T|<n do 
   j <- vertex with minimal d(T,j), j notin T 
   insert j with minimal cost into T 
return T

So, we have the following:
T={(0,0)}
j=(1,0)
T={(0,0), (1,0)}
...
T={(0,0), (1,0), ... , (i,0), ... , (100,0), (100,2), ... , (j,2), ... , (1,2), (0,0)}
or not? (Wondering)

So, do we get the same result with both approximations? (Wondering)
 
Last edited by a moderator:
Back
Top