1
$\begingroup$

If I need to find a shortest road (not great-circle) route between ~11,000 real world lat, long coordinates within a reasonable period of time. To further complicate things, there is no necessary starting point (however starting on one of the points at the edge would be beneficial), and the route shouldn't return to the initial location.

Clearly it is impractical to poll an online api with 11,000^2 requests for the distance between every point. Google maps is limited to 1000 objects per day (Presumably 2 objects required per distance) as a casual user, and 100,000 as a business user. Bing maps does not list a casual limit (although its likely after a point they would blacklist you), and the business limit is 100,000 requests per day.

To accomplish this using a heuristic algorithm I expect that I would need to utilise two tiers of distance using the great-circle algorithm for a cheap cost and an API request for an expensive cost. To provide greater accuracy than calculating the route using great-circle and finding the accurate distance of that route.

There are numerous heuristic approaches to the travelling salesman, however I have not yet found any that would support a two tier cost approach. Does anyone have experience with implementing a similar algorithm? or Suggestions of how you would implement it?

Thanks

$\endgroup$
  • $\begingroup$ Why can we still not flag questions as belonging on Computer Science SE? This one does IMO. $\endgroup$ – reinierpost Aug 3 '13 at 22:02
  • $\begingroup$ @reinierpost, you can flag it as "it needs ♦ moderator attention" (select "other" and write an explanation) to ask a moderator to migrate it over there. I think only ♦-moderators can migrate questions to CS.SE anyway, so that should be a reasonable way to indicate that it should be migrated. $\endgroup$ – D.W. Aug 4 '13 at 4:25
  • $\begingroup$ Sorry I didn't know there was a different CS SE site when I posted this. $\endgroup$ – Robadob Aug 4 '13 at 9:42
  • $\begingroup$ @reinierpost: And why isn't this a research problem?? $\endgroup$ – Peter Shor Aug 7 '13 at 12:08
  • 1
    $\begingroup$ Why must you poll an online API to get the distances? $\endgroup$ – Austin Buchanan Oct 3 '13 at 1:22
1
$\begingroup$

Here's the first approach that occurs to me. Build a complete graph on 11,000 vertices, and label all edges with the great-circle distance. Apply some travelling salesman algorithm to choose the best route you can find. Then, for every edge on that route, query the map service for the road distance and replace the label on that edge with the road distance. Then, apply the travelling salesman algorithm again on the modified graph. Repeat this basic process until it converges.

I think the great-circle distance should be a lower-bound on the road distance, so I suspect this should be correct (in the sense that it doesn't miss out on a better solution).

One possible complication is that this might cause triangle-inequality violations, so if you are relying upon a heuristic that assumes the triangle inequality, this approach might screw things up. I don't know; you could try it out and see.

If you wanted to reduce the number of queries for the road distance even further, here's one more idea you could try. I suspect that the smaller the great-circle distance, the closer it is to the road distance; or, in other words, I suspect the gap between the distances might be largest for points that are far away. That's something you'd need to validate yourself. If it is correct, then a variant of the algorithm I suggested above is: only query the map service to obtain the road distance for edges where the great-circle distance is above some threshold. (You could even gradually reduce this threshold in each iteration of the above algorithm.)

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Was going to start implementing an ant-colony system, using your method for including real distance, however I've found that the coordinates I've been given aren't remotely long/lat coordinates ([610224, 421708] is supposed to be a location within Ireland :s), so I'm going to delay this till ~Monday. $\endgroup$ – Robadob Aug 4 '13 at 9:46

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.