NetworkX and alternatives to Network Analyst in ArcGIS

[Dmitriy Tarasov]

I had a problem similar to what the Closest Facility solver in Network Analyst solves, i.e., for every point in an "incident" feature class, find the closest point in a "facility" feature class and find the shortest route between the two. Not having access to Network Analyst, though, I tried to do this using NetworkX, with a road network extracted from OpenStreetMap by means of OSMnx. However, the shortest routes returned by NetworkX consist of straight segments from one node of the road network to the next, not following the curves in the road. This may or may not be good enough for my purposes; I am yet to find out. Nicolas Cadieux has also suggested QNEAT3 in QGIS for finding shortest routes; based on my past experience, I may or may not have the authorization to install QGIS on my computer. What other alternatives to the Closest Facility solver in ArcGIS are there?

[Nicolas Cadieux]

Hi,

I think you can now install QGIS without administration password if you used the advanced OSGeo4w installer and choose (only me).  I you have access to Python, you could modify the following algorithm found in https://gitlab.com/njacadieux/upstream_downstream_shortests_path_dijkstra.  That currently makes and "all point" to "all point" Dijkstra but I am in the process of making a Closest Facility solver using the actual network as input and output (not strait lines).  I currently have other projects so this is not a top priority for me (I could be convinced to place it on top of the list if you have a budget...) but for now, I have a PHD to finish!  This algorithm does not take traffic rules into consideration.  It was built for rivers. You can see this module in action here https://www.youtube.com/watch?v=qQrHcKtmr3o.  Keep in mind that I used this video to show a float point problem I had that has since been solved.

The other problem is that it has no tolerance for network error (like disconnected edges in the network).  I therefore just finish a (free) QGIS model that will find and correct network file errors.  Look for "Fix Directional Network models" 1 to 3. Use QGIS 3.20. (https://plugins.qgis.org/models/)

This YouTube video explains what the 3 models do. https://youtu.be/v61PafSByvM

Nicolas

On 2021-09-21 12:06 p.m., Dmitriy Tarasov wrote:

I had a problem similar to what the Closest Facility solver in Network Analyst solves, i.e., for every point in an "incident" feature class, find the closest point in a "facility" feature class and find the shortest route between the two. Not having access to Network Analyst, though, I tried to do this using NetworkX, with a road network extracted from OpenStreetMap by means of OSMnx. However, the shortest routes returned by NetworkX consist of straight segments from one node of the road network to the next, not following the curves in the road. This may or may not be good enough for my purposes; I am yet to find out. Nicolas Cadieux has also suggested QNEAT3 in QGIS for finding shortest routes; based on my past experience, I may or may not have the authorization to install QGIS on my computer. What other alternatives to the Closest Facility solver in ArcGIS are there?

--
You received this message because you are subscribed to the Google Groups "networkx-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to networkx-discu...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/20945446-dff1-4e9d-8f35-b3d67fddf41an%40googlegroups.com.

-- 
Nicolas Cadieux
https://gitlab.com/njacadieux

[Dmitriy Tarasov]

Thank you! I've now found an answer about how to have NetworkX return the true geometry of the underlying network (rather than straight lines from node to node); there is a description at https://stackoverflow.com/a/62179444/9728072 .

[Nicolas Cadieux]

Hi,

That post makes sense.  I will find the nearest entry node and exit node to the Graph.  So if are 500m away from the nearest node, you will have a 500m error.  At least that is my understanding of the code.  

Nicolas Cadieux

https://gitlab.com/njacadieux

Le 24 sept. 2021 à 13:32, Dmitriy Tarasov <dmitriy...@uconn.edu> a écrit :

Thank you! I've now found an answer about how to have NetworkX return the true geometry of the underlying network (rather than straight lines from node to node); there is a description at https://stackoverflow.com/a/62179444/9728072 .

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/db1be8ea-4e57-4495-9e27-5c5b826b740bn%40googlegroups.com.

[Dmitriy Tarasov]

The script I'm writing is similar to that example, except that there are multiple origins and destinations and, for every origin, the script finds the nearest destination and saves the path to it. I am now trying to incorporate the tie_outside_node() function into it, so that it can trace routes all the way to and from the points.

[Nicolas Cadieux]

Great,

The beta version of the code does not change much (some float point errors) but is much easier to read as I also did a lot of code style formatting.  I would look at that version.  

Nicolas Cadieux

https://gitlab.com/njacadieux

Le 27 sept. 2021 à 11:51, Dmitriy Tarasov <dmitriy...@uconn.edu> a écrit :

The script I'm writing is similar to that example, except that there are multiple origins and destinations and, for every origin, the script finds the nearest destination and saves the path to it. I am now trying to incorporate the tie_outside_node() function into it, so that it can trace routes all the way to and from the points.

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/2244646f-9220-46c8-8c8f-0d09fdd9142fn%40googlegroups.com.

[Dmitriy Tarasov]

Am I right that the tie_outside_node() function returns a dictionary of all nodes, both the old one and the new, formerly outside nodes that have been tied into the graph?

[Nicolas Cadieux]

Hi,

Almost…. The original graph is created with the input line file only.  The tie_outside_node() and related functions will create a dictionary containing the nodes, the lines (new edges) connecting those nodes to the nearest road section in the graph.  This is made using the all the points in input point file.  It also stores in the dictionary the two split  half’s of the edge ( as nodes are connected to the closest part of the line and not the beginning or end of the line.)

When the shortest path algorithm starts, it checks if the nodes is in the graph.  If this is not the case, it looks in the dictionary and loads the missing node, the line between the node and the graph,  and then the two split lines from the graph. The new nodes and edges are then discarded. 

The goal was to modify the graph on the fly to keep it light and speedy because I had over 360 million shortest paths to calculate.

Hope this helps…

Nicolas Cadieux

https://gitlab.com/njacadieux

Le 8 oct. 2021 à 11:51, Dmitriy Tarasov <dmitriy...@uconn.edu> a écrit :

Am I right that the tie_outside_node() function returns a dictionary of all nodes, both the old one and the new, formerly outside nodes that have been tied into the graph?

To view this discussion on the web visit https://groups.google.com/d/msgid/networkx-discuss/54eddbf1-ab17-480b-81e4-338327f1e742n%40googlegroups.com.