Yes, and additionally the problem is then not Euclidian anymore. For example the triangular inequality (distance from A to B directly is always shorter than or equal to distance from A to B via C) does not hold. I'd guess that that will deteriorate results from this method since it relies on the Euclidian distance from the current circle to the points to be visited.
I don't understand why you think traveling by road breaks the triangle inequality. If the time/distance along roads from A to B is fastest via C, then just go via C...
You misunderstand. I'm saying that a situation such as:
dist(AB): 3km
dist(AC): 1km
dist(CB): 1km
is impossible even if those are road distances rather than Euclidean distances. If the road distance of traveling A->C->B is 2km then dist(AB) should not be greater than 2km.
So long as you're measuring in kilometers, as the bird flies. If you're talking about the distance a car would have to drive... okay, you're correct that it'd be possible to drive through C and thereby cut down on cost, but that's somewhat besides the point.
The algorithm this article is talking about assumes that all points are on an Euclidean map, and the distance between them is simply the Euclidean distance. This requires the triangle inequality to hold for straight lines, and allows optimizations based on that assumption.
The inequality in itself is a weaker statement than saying the whole thing is euclidean, and I haven't read it carefully enough to be sure which is required, but any violation of it is necessarily a violation of the assumptions that make this heuristic work.
Your best bet is to calculate a full cost (time/distance) matrix upfront before running the optimisation.
Both Google and GraphHopper offer cost matrix calculations as part of their web API. I imagine in both cases you need an expensive API key though.
If you're going to use GraphHopper, you might as well install it yourself, import the OpenStreetMap file for the region you want, and use it to calculate the cost matrix on your own computer for free!
Yes good point. Pre-loading the full distance matrix is the right thing to do here. That's what we were doing at a startup as I was at a few years ago. GraphHopper is quite expandable so it is nice to work with once you understand how it functions.
But you definitely need to put your Java hat on :).
This would significantly impact performance though.