Find every possible route

492
13
07-20-2018 03:21 PM
Highlighted
New Contributor III

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.

Reply
0 Kudos
13 Replies
Highlighted
MVP Frequent Contributor

Some questions to help in helping folks answer this:

  • Is the data in a Geometric Network?  Or are a Network Dataset?  Or something else?
  • Are you using ArcGIS DesktopArcGIS ProArcGIS Online?  Another platform?
  • What version?

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 

Chris Donohue, GISP

Reply
0 Kudos
Highlighted
New Contributor III

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.

Reply
0 Kudos
Highlighted
MVP Esteemed Contributor

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 

Highlighted
Esri Regular Contributor

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.

 

Jay Sandhu

Reply
0 Kudos
Highlighted
New Contributor III

Paths to reachable locations would not be helpful. That is just the network. I am identifying end to end routes.

Reply
0 Kudos
Highlighted
MVP Esteemed Contributor

Shortest Paths — NetworkX 1.10 documentation 

like what I suggested before

Reply
0 Kudos
Highlighted
New Contributor III

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

Reply
0 Kudos
Highlighted
MVP Frequent Contributor

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 

Chris Donohue, GISP

Reply
0 Kudos
Highlighted
MVP Frequent Contributor
Reply
0 Kudos