Skip to main content

I have about 20,000 adresses and 10 locations of the same sort of destination (eg. a doctor). I have already a network.

I'd like to calculate the shortest path between each adress and the nearest doctor over the network.

Is there a way to utilize the shortestpathfinder for this?

I tried the fromToBuilder to create from-to-lines. However, the fromToBuilder requires a join field for each from and to location. Which I would then have to create manually for each adress (and so create 200,000 paths; 20,000 * 10). The shortest path could then be recalculated after the shortestpathfinder to get the closest doctor for each house.

Is there perhaps a more efficient way to do this?

 

  • You can use a NeighborFinder to do this.
    • Adresses are bases
    • Doctors are candidates.
    • No maximum distance.
    • No maximum number of candidates.
    • Create a list.
  • ListExploder to explode the lists to features get all combinations.
  • VertexCreator to add a point and create a from to line.
    • closest candidate x,y attributes

If the adresses are not on the network you need to snap these to the network first to get the ShortestPathFinder to work. Can be done using an AnchoredSnapper. Maybe also a topologybuilder.


To do a quick solution, use the VoronoiDiagrammer on the doctor locations. It will produce a set of polygons. Whichever polygon an address falls inside, that’s their nearest doctor. Obviously, that’s straight line distance, not by road.

Another solution might be the NetworkCostCalculator. I believe that it can create a network of travel times which you can then feed the addresses into. It’s been a while since I used it though, so I’m not 100% sure the order of operations.

But, actually the ShortestPathFinder is a good solution. What I would do is:

  • Use a CoordinateExtractor to get the x/y values of each doctor.
  • Use a FeatureMerger to join the doctors (supplier) to each address (requestor)
    • Set the join as a:a (i.e. don’t select a join attribute, just enter a into each field)
    • Turn on Process Duplicate Suppliers and Generate List
  • Explode the list. Now you have 200,000 features you need.
  • Use a VertexCreator to add the doctor x/y to each of the existing address points.
  • Run it all through the ShortestPathFinder

I would use simple values for the ShortestPathFinder. You don’t need to be doing hour long calculations for each address. In fact, since you only have a start and end point - and no intermediate points - you probably won’t need to set any parameters at all.

Hope this helps. This is my kind of question (my favourite transformer) but I’m a bit pushed for time this morning!


  • You can use a NeighborFinder to do this.
    • Adresses are bases
    • Doctors are candidates.
    • No maximum distance.
    • No maximum number of candidates.
    • Create a list.
  • ListExploder to explode the lists to features get all combinations.
  • VertexCreator to add a point and create a from to line.
    • closest candidate x,y attributes

If the adresses are not on the network you need to snap these to the network first to get the ShortestPathFinder to work. Can be done using an AnchoredSnapper. Maybe also a topologybuilder.

Thanks. It took a few iterations to find the problem: the ShortestPathFinder needs the points to be connected to a vertex on the network. Therefore I needed to snap the adresses to the segments first before creating a from-to line from them. 

  • used a separate AnchoredSnapper for both to and end points with end point snapping with distance 1500 to fix them to the network beforehand.
  • used the process as described by mark2atsafe above (CoordinateExtractor => FeatureMerger a:a => ListExploder => VertexCreator) to get the from-to lines.
  • used the Snapper > TopologyBuilder to create the network.

 

Total process including up- and downstream now takes 30 min as apposed to an estimated 9 hours before.

NB: Using segment snapping and/or vertex snapping in the AnchoredSnapper did produce almost no matches without snapping in the ShortestPathFinder. Most of the adresses where rooted to NoPath as not being a valid node in the network.

 


Used the process as described by mark2atsafe above (CoordinateExtractor => FeatureMerger a:a => ListExploder => VertexCreator) to get the from-to lines.

 

Ah yes this is a nicer solution than to use the NeighborFinder.

 

NB: Using segment snapping and/or vertex snapping in the AnchoredSnapper did produce almost no matches without snapping in the ShortestPathFinder. Most of the adresses where rooted to NoPath as not being a valid node in the network.

 

If you have start and endpoints snapped to the network lines, and you run these through the TopologyBuilder, the lines wil get vertices where the start and enpoints are snapped. I think this will return more accurate results, because with snapping in the ShortestPathFinder the from and to points are pulled to the closest endpoints in the network.


Reply