Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
2  
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
add comment

1 Answer 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]
share|improve this answer
add comment

Your Answer

 
discard

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.