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?

  • 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

1

Searching for "spherical TSP" one finds a number of resources on this problem. For example, Ben Nolting's blog post A Traveling Salesman on a Sphere: Pitbull's Arctic Adventure contains Mathematica-based solution. I quote the main steps here:

positionVec[{u_, v_}] := {Cos[v °] Cos[u °], Sin[v °] Cos[u ° ], Sin[u °]}; distance[{u1_,v1_},{u2_,v2_}] := VectorAngle[ positionVec[{u1,v1}], positionVec[{u2,v2}]]; tour=FindShortestTour[citylocations, DistanceFunction->distance]