topic Re: Find every possible route in ArcGIS Network Analyst Questions

Find every possible route

AustinStreetman — Fri, 20 Jul 2018 22:21:28 GMT

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.

Re: Find every possible route

ChrisDonohue__GISP — Fri, 20 Jul 2018 22:32:33 GMT

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 Desktop? ArcGIS Pro? ArcGIS 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

Re: Find every possible route

AustinStreetman — Fri, 20 Jul 2018 22:48:43 GMT

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.

Re: Find every possible route

DanPatterson_Retired — Sat, 21 Jul 2018 22:11:27 GMT

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

Re: Find every possible route

ChrisDonohue__GISP — Mon, 23 Jul 2018 14:49:42 GMT

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

Re: Find every possible route

ChrisDonohue__GISP — Mon, 23 Jul 2018 16:19:13 GMT

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

Re: Find every possible route

AustinStreetman — Mon, 23 Jul 2018 16:36:05 GMT

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.

Re: Find every possible route

JaySandhu — Mon, 23 Jul 2018 16:40:54 GMT

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

Re: Find every possible route

JaySandhu — Mon, 23 Jul 2018 16:51:29 GMT

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.

Jay Sandhu

Re: Find every possible route

AustinStreetman — Mon, 23 Jul 2018 17:14:39 GMT

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.

Re: Find every possible route

AustinStreetman — Mon, 23 Jul 2018 17:22:23 GMT

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

Re: Find every possible route

JaySandhu — Mon, 23 Jul 2018 17:44:03 GMT

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

Re: Find every possible route

DanPatterson_Retired — Mon, 23 Jul 2018 20:19:23 GMT

Shortest Paths — NetworkX 1.10 documentation

like what I suggested before

Re: Find every possible route

AustinStreetman — Thu, 09 Aug 2018 15:58:41 GMT

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