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?