<p>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.</p>

<p>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).</p>

<p>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.</p>

<p>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.)</p>

CC BY-SA 3.0
2013-08-04T09:46:19.853Z
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.
Robadob
CC BY-SA 3.0
2013-08-03T19:20:41.920Z
2013-08-03T19:40:28.747Z
2013-08-03T19:40:28.747Z
D.W.
<p>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.</p>

<p>Clearly it is impractical to poll an online api with 11,000^2 requests for the distance between every point. <a href="https://developers.google.com/maps/documentation/distancematrix/#Limits" rel="nofollow">Google maps</a> is limited to 1000 objects per day (Presumably 2 objects required per distance) as a casual user, and 100,000 as a business user. <a href="http://www.microsoft.com/maps/product/terms.html" rel="nofollow">Bing maps</a> 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.</p>

<p>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.</p>

<p>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?</p>

<p>Thanks</p>

CC BY-SA 3.0
2013-08-03T22:02:02.053Z
Why can we *still* not flag questions as belonging on Computer Science SE? This one does IMO.
reinierpost
CC BY-SA 3.0
2013-08-04T04:25:01.343Z
@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.
D.W.
CC BY-SA 3.0
2013-08-04T09:42:41.217Z
Sorry I didn't know there was a different CS SE site when I posted this.
Robadob
CC BY-SA 3.0
2013-08-07T12:08:43.317Z
@reinierpost: And why isn't this a research problem??
Peter Shor 
CC BY-SA 3.0
2013-10-03T01:22:47.353Z
Why must you poll an online API to get the distances?
Austin Buchanan
CC BY-SA 3.0
2013-11-02T21:09:56.267Z
I am actually researching that thing right now. Would you like to send me your data, including distance function and I will try giving you my best?
Ilya Gazman
<graph-algorithms>
Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances
Robadob
# Finding a Travelling Salesman/Vehicle Routing with cheap and expensive distances

(Asked by: username_0 on 2013-08-02)

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](https://developers.google.com/maps/documentation/distancematrix/#Limits) 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](http://www.microsoft.com/maps/product/terms.html) 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

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: Why can we *still* not flag questions as belonging on Computer Science SE? This one does IMO.  
> **username_2**: @username_1, 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.  
> **username_0**: Sorry I didn't know there was a different CS SE site when I posted this.  
> **username_3**: @username_1: And why isn't this a research problem??  
> **username_4**: Why must you poll an online API to get the distances?  
> **username_5**: I am actually researching that thing right now. Would you like to send me your data, including distance function and I will try giving you my best?  

---

## 1 answers

### Answer by username_2 on 2013-08-03. Score: 1

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.)

> **Comments:**
> **username_0**: 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.  

---

