0

Imagine we have the location of a person (point) and 100 restaurants (each is a point). My objective is to calculate the path from the person to the nearest restaurant (just one), but I want to avoid calculating 100 shortest paths (which is what pgr_dijkstra one-to-many does), because it is time consuming.

Logically, this should be possible, as Dijkstra's algorithm analyzes cost cumulatively. Therefore, if the algorithm has already reached the first restaurant and the cost is 50, then all paths whose cost is higher than 50 could be dropped.

How can I implement this in PostgreSQL, preferably using pg_routing?

7
  • Welcome to Geographic Information Systems! Welcome to GIS SE! We're a little different from other sites; this isn't a discussion forum but a Q&A site. Your questions should as much as possible describe not just what you want to do, but precisely what you have tried and where you are stuck trying that. Please check out our short tour for more about how the site works.
    – Ian Turton
    Jul 30 '20 at 12:55
  • We do this for students to schools, but have implemented a custom function in PostGIS that makes an HTTP call to an OSRM routing server... basically it is called ST_Routed_Distance(a.geom, b.geom) and is insanely fast and very accurate. The SQL logic is very easy, that is you can use the KNN distance operator for the 'closest' school, and use things like rownumber() to limit how many results you want. I can share the SQL logic, and I think I can get at the SQL for the function if you want... the OSRM part is a bit more of a lift, but on my list to publish as documentation. Jul 30 '20 at 14:20
  • 1
    Actually, I forgot I started doing this with PGRouting a long time ago - try this solution to see if it works for you - basically it allows you to create a custom set of source points and destination points (or a single point) and route them all: gis.stackexchange.com/a/233502/9880 Jul 30 '20 at 14:25
  • While, as you said, technically Dijkstra would be able to do what you describe, the pgRouting implementation has no 'first-target-reached' drop out. The one-to-many version likely only uses a single iteration of the algorithm to find distances to all given target nodes, so 'time consuming' is extremely relative. I get what you want, and why, but the only option I can think of with on-board functions would be to create and store a distance matrix of your network, select the relevant vertex pair combination from it and route between them.
    – geozelot
    Jul 31 '20 at 9:54
  • That being said, it may be worth to contract the graph (there are also other options in the proposed/experimental section) and use the withPoints functionality to speed up some searches. As @DPSSpatial mentioned, OSRM is stupid fast, but lacks the immediate flexibility of an in-DB routing (you can do a lot, but it needs proper setup, and the lua profiling is not extensively documented; took me quite some time to comfortably work with custom profiles).
    – geozelot
    Jul 31 '20 at 10:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.