Basics of Hierarchy

Question

Hi
I am a complete beginner and when I say beginner I mean that I am on the tutorial level. So it will be probably very easy to answer my question:)
I read about Hierarchy in Network Analysis when finding the shortest path between two points. From what I understood whenever the "Use Hierarchy" button is checked the solver goes simultaneously from origin and end points omitting lower hierarchy roads whenever it gets to a higher hierarchy road (if it starts at the HierarchyMultinet 5 then omit roads in this category as soon as it finds the HierarchyMultinet 4 then 3 and so on). The on line Arc GIS help says that the solver may not find the solution and fail. When can that happen?? In my case I try to find a shortest way between 1 Cam Alto  and 4995 Hedge Ln (San Francisco"Exercise 3, Network Analyst"), and everything works perfectly fine when I look for the best route with Hierarchy on. However when I add some polygon barrier span between 92 Marina Green Dr, 63 Green St, 84 Zoe St, 331 Lake St the solution fails. I followed the HierarchyMultinet of each element of the found connection in both cases and they are built similarly. I mean in the first case the solution follows the 5th hierarchy then converts to 4th then 3rd then 2nd then goes to the 3rd again then again to the 2nd...why if the Hierarchy is checked on!!?? The same is in the second case but this time the Hierarchy is unchecked...I can understand that:) but I still don't get the meaning of the hierarchy in the first described  case. Can somebody try to shed some light on this??

Thank you

MichaelRice · Answer

(the solver descends and ascends when the hierarchy button is on!!!). Shouldn't it have failed??....

Not necessarily. Do not think of it as "ascending" or "descending", as this is where the confusion typically comes from. Rather, think of it as applying a filter during the search, which can be progressively restricted. Let's call this filter value f. During the search, any edge which is reached for the first time with a hierarchy value > f is ignored/restricted.

For example, as the search starts out, the filter is very relaxed (e.g., f = 5), meaning that the search will allow paths that cover *all* levels of the hierarchy (1 through 5 in your case). After the search reaches some number, k, of entries into the next level higher than the current value of f (this would be level 4 at this point), then the value of the filter is decreased by one (e.g., f = 4). Now, the search will only allow paths on edges from levels 1-4 (and level 5 edges will be ignored from that point on). This process iterates until the two searches meet to establish a valid path, assuming one exists. Note that this meeting point does not necessarily have to occur on the highest level of the hierarchy. For example, in your case, you noticed that the shortest path did not include a level 1 edge. This is likely because your stops were close enough that the shortest path did not really need to get on a level 1 edge (such as an interestate, typically).

Additionally, in your example where you said that the solver "descends" and then "ascends" again (going from level 2 to level 3 and then back to level 2), it is most likely that the filter value was simply still "relaxed" enough at that point during the search (e.g., f = 3) to allow this path. Does this make sense?.... and the when we have the same start and end points and only add some barriers the solver shows an error. Why it cannot descend and ascend this time??

I cannot say for sure without seeing the exact case you are referring to, but it is likely that you have simply blocked (effectively, disconnecting) the only levels of the hierarchy that it could use to reach the destination. Remember, it was not truly "descending" before. It was just that the filter was relaxed enough to allow those lower level edges. It is possible that when the search reaches the areas which are blocked by the barriers, the filter is set too low to allow any "descent" into the surrounding area along lower-level edges, so that it cannot bypass the barriers.When I uncheck the hierarchy (in the example with barriers) the solver responds giving a solution.

This is because without using hierarchies, you are performing an exact shortest path search, which will find the true shortest path (around the barriers), if one exists. There is no hierarchical filtering going on in this case, which is why the search can find the path.

Please be aware that hierarchies are only used as a technique for speeding up the search times for long-distance paths. This is because most long-distance paths (e.g., Los Angeles to New York) will very quickly travel up to the high-level edges, such as interstates, and then travel along these high-level edges for most of the way, ignoring all (or most) lower-level edges. Hierarchical searches therefore attempt to mimic this travel pattern to avoid having to consider all of the possible detours along the way. This speeds up the search time considerably (but does not guarantee to find the true shortest path, since some edges are simply ignored during the search based on their hierarchy value).

Therefore, for short-distance routes (e.g., local routes within a small region of a city), it may not make sense to use hierarchies (since it might force you to go out of the way to take the interstate, due to the hierarchical filtering, when there is a more direct, and shorter, path).

Hopefully, this answers some of your questions. Please let me know if there are any other issues.

przemyslawbielecki · Answer

Thank you for the reply!! That partially explains my problem.

The model I am working on has 5 hierarchy levels. I was wondering why the solver finds the shortest way going from the elements designed as a 5th hierarchy level finds the connection to the elements in the 4th hierarchy level then finds the connection to the elements in the 3rd hierarchy level then the 2nd and then when it cannot find the elements from the 1st hierarchy level in order to continue its performance it finds elements from the 3rd hierarchy level (so basically goes one step lower in the hierarchy) and continue w/o any problems (the solver descends and ascends when the hierarchy button is on!!!). Shouldn't it have failed??.... and the when we have the same start and end points and only add some barriers the solver shows an error. Why it cannot descend and ascend this time?? When I uncheck the hierarchy (in the example with barriers) the solver responds giving a solution. I hope I explained it better...did I ??

MichaelRice · Answer

The on line ArcGIS help says that the solver may not find the solution and fail. When can that happen??

This can happen when one of the upper levels of the hierarchy is disconnected. Specifically, if the solver starts to filter all but the highest levels of hierarchy, but these upper levels are disconnected, then it may fail to find a path (even if there is a connecting path on some of the lower levels of hierarchy). This can usually be avoided by ensuring proper hierarchy value assignments when creating your network dataset.I mean in the first case the solution follows the 5th hierarchy then converts to 4th then 3rd then 2nd then goes to the 3rd again then again to the 2nd...why if the Hierarchy is checked on!!??

I don't really understand exactly what you are asking. Can you try to clarify?

Only once the search has explored "far enough" will it start to filter all but the higher hierarchy levels. Specifically, the search begins by allowing all hierarchy levels to be explored. Once it has reached a certain number of entries from its starting point into the next higher level, it will begin filtering all lower levels. This process iterates, progressively moving up in the hierarchy for long-range routes.

However, if your stops are relatively close together (or if there are not very many nearby entries into the next level), a path may be found before the search starts to filter out the lower levels of your hierarchy, which can give the results you are seeing (i.e., where the hierarchy values along the path do not always simply monotonically decrease and then monotonically increase).

Does this answer your second question?