TSP taking into account shapes of cities

118 views Asked by At

I'm looking for a solution of symmetric Traveling Salesman Problem in which we take into account shapes of cities. For example, in the graph from geeksforgeeks.org, the shortest path is 1-2-4-3-1 TSP sample graph

We can imagine that cities aren't points but e.g. horizontal lines (because in a case of choose another shapes the problem will be much harder to solve). In above case we can make two points from one point e.g. point 1 became points: 1' and 1'' and the weight (connected to point 1) in the graph will change.

Are there well-known algorithms to solve TSP in case that if I visit city 1' I must visit city 1'' (and symmetrically)?

0

There are 0 answers