1

I am not able to search for algorithms which can help me solve this problem, I am not sure under which category this problem falls or which algorithm to use.

Problem statement:

There are N number of suppliers who supply Sugar, each supplier has Supplier Location (latitude, longitude) of their warehouse from which they will supply and they also have a 'maximum_radius' to which they can supply.

Now, if a user comes and gives his location User Location (latitude, longitude), how do I find who all suppliers can supply to that place.

The only solution I can think if go to each Supplier Location, calculate the distance to User Location, and check if it falls within maximum_radius of the supplier. But this seems slow, as the number of suppliers will increase over time.

  • What do you mean by “slow”? What hardware do you use and how many suppliers are there so that sqrt(deltaX^2 + deltaY^2) would become the bottleneck in your app? – Arseni Mourzenko Jun 8 '16 at 9:48
  • I have not yet implemented to calculate the speed, but I am just exploring if there is a solution apart from looping over all suppliers. I don't expect more than 1000 suppliers. – rjvim Jun 8 '16 at 9:50
  • 2
    Maybe cluster them by regions. Though there are many variations on how to optimize nearest neighbour search. Most likely using a database that has some kind of spatial indexing would be the easiest option. – thorsten müller Jun 8 '16 at 9:54
  • 2
    @rjvim: That's premature optimization. Don't do that. Computing sqrt(deltaX^2 + deltaY^2) for 1000 points would probably be a matter of microseconds even on slow embedded hardware. – Arseni Mourzenko Jun 8 '16 at 9:55
  • nearest neighbour search might not work as I am not trying to find nearest neighbours to the User Location. I have to find which suppliers can supply to the User Location. Supplier A can have maximum_radius of 50 miles, while Supplier B have 10 miles only. – rjvim Jun 8 '16 at 9:56
2

From the comments, it appears that you are dealing with 1 000 points.

The usual way to compute a distance between two points, p1 and p2, is:

sqrt(pow(p1.x - p2.x, 2), pow(p1.y - p2.y, 2))

I attempted to measure the time it takes to do the operation in C# on a 2.10 GHz CPU (no parallelization, so the number of cores doesn't matter), and failed. With 10 000 000 points, it takes approximately 2 050 milliseconds, which means 0.205 ms. for 1 000 points.

Before trying to optimize your code, make sure that this part is actually the bottleneck, i.e. it was identified by a profiler as the part which makes your application slow. Otherwise, you're doing premature optimization, and you shouldn't do that.

If the profiler actually indicated that this is the slowest part of your code, I would suggest exploring a few optimization alternatives:

  • Compare the actual x and y distances before doing pow and sqrt stuff. If abs(p1.x - p2.x) is 200 and the maximum distance is 100, there is no need to continue: the points are too far away from each other.

  • Use a map (similar to an OLAP cube with coordinates and distances being the dimensions of the cube) and approximate the point coordinates to make the map small enough. Note that you should be very careful with that: the time to do I/O may have a much larger impact than doing the actual calculation.

  • You can't just use the Euclidean distance on latitudes and longitudes, as the relationship between longitude and distance changes with the latitude. And you have to allow for wrap-around at +/- 180 degrees. And it gets really messy near the poles. – Simon B Jun 8 '16 at 11:24
  • @SimonB - You can if you're just trying to get an estimate of the distance. If your warehouse is on the North Pole, you better be prepared to deliver over some vast distances. I can guarantee you in the business world, if a warehouse has a "rule" they won't deliver past 100 km, they'll go 125 if the order is big enough. – JeffO Jun 8 '16 at 11:31
  • 1
    To expand on Simon's comment: To get actual (flight) distance, you would need to use Great-circle distance. See also What is the approximate error of the Pythagorean Theorem vs. Haversine Formula in measuring distances on a sphere at various scales?. Per that answer, Euclidean distance can introduce error exceeding 25%. – Brian Jun 8 '16 at 18:42
0

You are going to have to consider each and every supplier, as each one has a different radius. There is no way you can stop checking suppliers once one fails the distance test as another further one might deliver a larger radius!

What you can do is reduce the calculations by considering all those suppliers distance horizontally, and then if they are closer than their delivery distance, check the direct distance. This kind of approach works well for routine algorithms where the driving distance on a road network matters more than the straight-line distance (eg if there's a river in the way!) - you quickly reduce your set of possibilities and then perform the expensive checking.

That said, unless you have particularly slow maths performance, just calculating the direct pythagorean distance for every supplier is going to be quick enough.

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.