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
    $\begingroup$ What's the difference to doing it in the plane? (Errh, I mean solving the TSP) $\endgroup$ – draks ... Apr 17 '12 at 11:07
  • $\begingroup$ @draks, the difference is that plane is open set instead of surface of a sphere. $\endgroup$ – 0x2207 Apr 17 '12 at 17:53
  • $\begingroup$ But, after you calculated all the distances and put them in an adjacency matrix nobody will recognize the sphere anymore, right? $\endgroup$ – draks ... Apr 17 '12 at 18:04

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]

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.