2
$\begingroup$

Let vertices be defined on the unit sphere by its longitudes $\lambda_i$ and latitudes $\phi_i$. The distance between $i$ and $j$ is defined as follows: $\arccos(\sin(\lambda_i) \sin(\lambda_j) \cos(\phi_i - \phi_j) + \cos(\lambda_i) \cos(\lambda_j))$ which is an angle measure of the shortest distance between two points on unit sphere.

So, I want solve the traveling salesman problem on this unit sphere. Unfortunately, I didn't found any information on this problem.

Are there any approximations, heuristics, etc which utilize this distance definition?

  • 2
    What's the difference to doing it in the plane? (Errh, I mean solving the TSP)2012-04-17
  • 0
    @draks, the difference is that plane is open set instead of surface of a sphere.2012-04-17
  • 0
    But, after you calculated all the distances and put them in an adjacency matrix nobody will recognize the sphere anymore, right?2012-04-17

1 Answers 1