How well does this scale?

[datawookie]

So a brute force approach works well with a few locations. But as the number of locations increases, it becomes progressively less efficient.

How would you change things if you needed to handle a few hundred locations?

[GerardWalsh]

Indeed, it essentially scales exponentially but modern hardware can still handle the computational problem quite effectively as the computation (calculating a permutation matrix, adding up the distances and finding the smallest combination) is quite simple. The time-critical issue is waiting for a response from the geocoding service and populating the distance matrix variable - this is the bottleneck in the script. Time could be saved/ the application made more efficient when I populate the distance metric by only populating a upper or lower triangular matrix as the distance from location 1 to location 6 should be the same as the reverse.

The actual shortest distance computation could possibly be accelerated by maybe clustering the locations and choosing outlying points as start/end points, but this still doesn't solve the problem of the slow response from the geocoding service.

[datawookie]

Distance matrix is generally almost symmetric. But time matrix can be surprisingly asymmetric.

On Thu, 27 Dec 2018, 11:43 Gerard Walsh <notifications@github.com wrote:

Indeed, it essentially scales exponentially but modern hardware can still handle the computational problem quite effectively as the computation (calculating a permutation matrix, adding up the distances and finding the smallest combination) is quite simple. The time-critical issue is waiting for a response from the geocoding service and populating the distance matrix variable - this is the bottleneck in the script. Time could be saved/ the application made more efficient when I populate the distance metric by only populating a upper or lower triangular matrix as the distance from location 1 to location 6 should be the same as the reverse.

The actual shortest distance computation could possibly be accelerated by maybe clustering the locations and choosing outlying points as start/end points, but this still doesn't solve the problem of the slow response from the geocoding service.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/gerrywalsh/routePlanning/issues/1#issuecomment-450116137, or mute the thread https://github.com/notifications/unsubscribe-auth/AF2aic6Nr8jU8JwTXLH_9puKD3eSUsuMks5u9JY2gaJpZM4ZYgiE .

[GerardWalsh]

I agree, that time matrix could very well be highly asymmetric!