Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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