I have a network of candidate links for a single end to end utility line route. I would like to find every possible route in the network.
I figured out a way to get all the routes for a set of links. I ran the identity tool between the end point and the start point of each which will serve as a many to many table between the links (after a dissolve). I wrote a Python script that recursively looks through the table from the start link to the end link and writes out a link combination for each. Came up with about 2200 routes for the project I am working on.
Here is the recursive function:
def follow_connections_recursive(
self, this_upstream_link, start_nodes, this_route_string, destination_link):
# loop through input points and find start point
fields = ["To_Link"]
with arcpy.da.SearchCursor(
start_nodes, fields, "From_Link = '"+this_upstream_link+ "'") as cursor:
for this_start_point in cursor:
this_link = this_start_point[0]
#arcpy.AddMessage(this_link)
temp_route_string = this_route_string
this_route_string = this_route_string + '-'+ this_link
if (this_link == destination_link):
arcpy.AddMessage("Route : " + this_route_string)
else:
self.follow_connections_recursive(this_link, start_nodes, this_route_string, destination_link)
this_route_string = temp_route_string
return
In that case, use the internet to search (see my previous post for search hint) for an external algorithm as Network Analyst does not have an all possible paths solver built in.
Jay Sandhu
Paths to reachable locations would not be helpful. That is just the network. I am identifying end to end routes.
I have been asked to find a way to find all possible routes between a start point and an end point on networks of about 100 links. Many of the links will be one-way links to enforce forward progression.
From your original post of finding all paths to now finding 10 or 20, it is not clear what you need to achieve. Perhaps if you specify what is your end goal then someone could think of a more appropriate methodology.
Can you use the Service Area solver with the lines option to return back everything that is connected/reachable from the start node? Will that give you the information that you are trying to find all possible paths?
Or you can search the net for something like "print all paths from a given source to destination" for a possible solution.
But as caution, and I am sure you are aware of this, finding all possible paths can return a lot of paths as the network size increases and may not be tractable.
Here is a helpful post about using barrier to effect different routes on successive runs.
https://community.esri.com/thread/63897
I am experimenting with creating a point barrier for each link used in a route and setting it's mileage to the original miles * 0.1 as an added cost. The points stack up as a link is used more than once, so the cost keeps increasing. This does yield a nice variety of routes. The same route can get picked more than once, but I can filter those out. I wish I knew how many of these routes to generate before I can feel confident I have found the 10 or 20 shortest routes.
Without knowing how the routing algorithms work, it seems clear that they can't and shouldn't find every route before they identify the chosen route. So my original question cannot be answered by routing software. I think that an exhaustive list of possible routes is something that sounds useful, but would really just be a very long list of no value.
To provide a more conceptual background on what Dan_Patterson suggested:
What is a utility network?—ArcGIS Pro | ArcGIS Desktop
Benefits of a utility network—ArcGIS Pro | ArcGIS Desktop
Chris Donohue, GISP
Somewhat related. May trigger some ideas from folks on a way to do what the OP is asking.
Travelling salesman problem - GIS Wiki | The GIS Encyclopedia
networkx NetworkX - Wikipedia (comes with ArcGIS Pro's anaconda distribution but needs to be conda installed)
the Utility Network toolset An overview of the Network Diagrams toolset—Utility Network Toolbox | ArcGIS Desktop
which is an add on
An overview of the Network Diagrams toolset—Utility Network Toolbox | ArcGIS Desktop
I have created a network dataset for this sole purpose in desktop 10.5. We do not use Network Analyst for anything else in the process. These networks represent imaginary routing opportunities and contain a small number of links, usually less than 100. The routing problem has one start point and one endpoint. We can make most of the links one-way to prevent looping or non-forward progressing routes. We would like to generate a list of possible routes for analysis outside of Network Analyst.
Some questions to help in helping folks answer this:
If you have a geometric network, there apparently is a Trace function that may work for what you need (I have never used it myself):
About tracing on geometric networks—Help | ArcGIS for Desktop
Aangemelde leden kunnen berichten plaatsen, updates volgen en meer. Nieuw hier? Registreer een gratis account.
Find useful guides, FAQs, and documents to help you navigate and make the most of Esri Community.
