topic Re: Network Analyst - Slope-Switch at Junctions in ArcGIS Network Analyst Questions

Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Wed, 11 Aug 2010 08:28:27 GMT

Hello everyone,

Im using a street data set with calculated slope and fuel consumption. In my data set there are some roads with a large slope, so the fuel consumption on negative slope is much lower than on positive slope. My goal is to model a network (Routes and/or Service Area), that can pick on the junctions/nodes between the streets the following slope direction (+ or -) and accumulate the fuel consumption.
My tests so far didnt work out properly, the larger the route got, the worse the results became.

Looking forward to your ideas!

Greetings,
Thomas

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Wed, 11 Aug 2010 14:56:05 GMT

Why not store the positive/negative slope information on the edges themselves (e.g., using a descriptor attribute)? Having +/- slope information stored on the junction can be misleading since each junction can connect to multiple edges, some of which may have positive slope, and some of which may have negative slope.

Please let me know if I have misunderstood your use case.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Wed, 11 Aug 2010 15:13:14 GMT

Right now I got two fields of slope in my street network attribute table: one for the positive slope and one for the negative slope. My goal is to get the exact results over a route with several ups and downs, which lead to different fuel consumption (obviously u need more fuel when driving uphill than downhill). When i want to receive the whole fuel consumption for that route, id like to have my network accumulate the consumption numbers from my attribute table according to the positive and negative slope.
When im "driving" over a route with 4 lines, first + slope, 2nd -, 3rd +, 4th - etc., id like the network analyst to "jump" in the attribute table to one field from another to get the exact consumption over this route.

Hopefully this made it a little more understandable 🙂 I dont have the Slope itsself on the Junctions, i just thought it would be possible to adjust to junctions so they belong to the right slope numbers of the next part of the road.

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Wed, 11 Aug 2010 15:29:29 GMT

Here is what I would suggest:

Create two fields in your streets feature class called "FT_FuelConsumption" and "TF_FuelConsumption" to represent the fuel consumption for both directions (From-To and To-From) of a given street, respectively.

Calculate these field values (e.g., using a VBScript formula in the Field Calculator) based on whether they have a positive or negative slope for that direction.

Create a cost attribute called "FuelConsumption" in your network dataset. Specify the "FT_FuelConsumption" and "TF_FuelConsumption" fields as the sources for this attribute for your streets in the From-To and To-From directions, respectively.

Solve your route as before, but specify to accumulate "FuelConsumption" (this can be specified from the Accumulation tab on your Route analysis layer property pages). You can then open your Routes attribute table after a solve and see the total fuel consumption in the "Total_FuelConsumption" field.

Let me know if you have any further questions.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Thu, 12 Aug 2010 08:53:54 GMT

This actually worked out and the Accumulation-Results looked right!
I just have to adjust my Consumption-Formula now, since I have + and - in one attribute field now. (That was the reason why I calculated one field to positive and one to negative slope, so I can use the mathematical expressions easier). As u mentioned, the VBScript will be the way to go 🙂

Will hopefully work out, thx for your help Michael!

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Tue, 14 Sep 2010 13:27:02 GMT

Hey,

its me again and I got one more question 🙂 The routing worked out perfectly, but now ive been trying to solve a service area with the same attributes I already used for solving the routing problems. My goal is to produce range maps for the car type im working with. Ive been using the FuelConsumption attribute as impedance setting and the maximum value of fuel the car can handle as my default break.
The problem with solving the service areas now, is, that they arent using the the maximum value, i rather get some random results in between, changing from every location I start from.
Do you have any ideas on how to fix this? I was thinking about service areas cant handle negative values, since there are some in my fuelconsumption attributes.
Thx in advance for any ideas !

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Tue, 14 Sep 2010 14:44:51 GMT

Negative values for an impedance attribute will be considered as "restricted" by the solvers, and the solver will not be allowed to traverse an element with such negative values. This is because the search algorithm is based on a variant of the well-known Dijkstra's algorithm, which cannot properly handle negative values. Therefore, the only way to include such negative values in the results would be to use this as an accumulated attribute rather than the impedance attribute itself.

Is there a reason that some of these values are negative? I would assume that fuel consumption is always a non-negative value. Am I misunderstanding something?

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Tue, 14 Sep 2010 15:22:56 GMT

its actually for electric vehicles. when they are driving downhill section and when they are recuperating (reusing breakenergy) then they actually receive some energy when driving downhill, thus the negative values 😉

Using the fuel consumption as accumulated attribute works fine, when i would look for a service area with a certain distance, like 100 km, but thats unfortunately not the case 😕

so is there really no possible way to get this thing worked out with the fuelconsumption as impedance attribute?

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Tue, 14 Sep 2010 15:33:42 GMT

Ah, I see. This is quite an interesting use-case.

so is there really no possible way to get this thing worked out with the fuelconsumption as impedance attribute?

Theoretically, yes; there are shortest path algorithms which will work for negative weight values (assuming no negative weight cycles in the graph). However, this would require some programming to create a custom solver within the Network Analyst framework to handle such negative values appropriately as, unfortunately, there are no out-of-the-box solvers in Network Analyst which can handle this scenario as an impedance attribute. Additionally, programming a custom solver is no trivial task. If you are interested, however, I can point you to some useful resources on this.

Please let me know, and we can proceed from there.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Tue, 14 Sep 2010 15:46:06 GMT

Since I dont see any other option at the moment, i would like to take a look at this, yes. It would be great, when u could link me to some resources. I would take a look at those informations and then I know if I would be able to do this or not.
Looking forward to it, thanks !

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Tue, 14 Sep 2010 19:37:37 GMT

Okay, this will require knowledge in two particular areas:

The Bellman-Ford Algorithm

Programming Custom Network Analyst Solvers

Let's start with the algorithmic requirements. The Bellman-Ford (BF) algorithm is discussed in sufficient detail here: http://en.wikipedia.org/wiki/Bellman_Ford. If necessary, you can, of course, find more detailed discussions elsewhere on the web simply by searching for "Bellman-Ford". This algorithm provides the foundation for which you can find single-source shortest paths in graphs which may have negative weight edge costs.

However, after thinking about your use case some more, I have found a potential wrinkle in using this algorithm for service areas based on fuel tank capacity. You cannot simply run the BF algorithm and then choose those nodes whose shortest path distance from your source is less than or equal to your fuel tank capacity.

Consider the following problem, in which we want to find the shortest path (based on your potentially negative fuel consumption values) from some point A to some point C. Suppose that the shortest path from point A to point C travels through some other, intermediate point B. Suppose also that we have a fuel tank capacity of 20 fuel units (whatever units they may be).

If we simply used the standard BF algorithm, we could potentially end up in the following scenario. The shortest path from A to C costs 10 fuel units total. This is clearly within the fuel tank capacity. However, this path is made up of two subpaths: the shortest path from A to B and the shortest path from B to C.

We may have that the shortest path from A to B is 30 fuel units, but the shortest path from B to C is -20 fuel units. This, of course, gives us our total of 10 fuel units altogether, but there is one slight problem: the subpath just to get from A to B takes well over the 20 unit tank capacity, so this represents an infeasible route. That is, the vehicle could never even get to point B without running out of fuel!

Therefore, it seems you will have to modify the algorithm to somehow account for this capacity. In the original algorithm (using pseudocode from the link provided above), during each iteration each edge, (u,v), is "relaxed" using the following logic:

if u.distance + uv.weight < v.distance:
[INDENT]v.distance := u.distance + uv.weight[/INDENT]
[INDENT]v.predecessor := u[/INDENT]

To account for your capacity, we must adjust this logic using some additional constraints, such as follows:

if u.distance + uv.weight < v.distance AND u.distance <= capacity:
[INDENT]v.distance := u.distance + uv.weight[/INDENT]
[INDENT]v.predecessor := u[/INDENT]

Otherwise, if we allowed to relax an edge from node u and u.distance > capacity, this could result in an infeasible solution similar to the above. This adjustment should provide you with the shortest possible path to each node, v, for which no subpath exceeds fuel capacity. Then, after running the algorithm, you should only need to select those nodes, v, for which v.distance <= capacity, and this should effectively give you your desired "service area" of nodes within fuel capacity from the source. Of course, if needed, you would then be responsible for building some form of polygon around those nodes to represent the actual area. I will leave it to you to decide how to do that.

Okay, now on to the second part: programming a custom solver in Network Analyst. As I said before, this is no trivial task, but it is certainly achievable. We have provided a (simple) custom solver sample online which shows how to determine connectivity from a given set of source nodes in a graph. The sample can be found here: http://resources.esri.com/help/9.3/arcgisdesktop/com/samples/NetworkAnalyst/Solvers/CustomSolver/D463AD8F-83BE-4641-A39A-B4EA5597A7B4.htm

This shows the basics of which interfaces must be supported to have your solver appropriately recognized by the Network Analyst framework, as well as some of the basics of programmatically traversing the network dataset graph representation. Reviewing this sample should be a good starting point for you, and should at least give you some initial idea of what it will take to create your own custom solver.

Please let me know if you have any further questions.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Tue, 14 Sep 2010 20:16:25 GMT

Thanks, will take a look at this tomorrow morning when im at work.

In the best possible case, I dont just want to find the shortest path or the path which lets the car drive the most. It actually should count the paths in every direction, its obvious that some paths require more or less fuel. Maybe I misunderstood you, but just wanted to point this out again. Lets see if I can get this going!

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Tue, 14 Sep 2010 20:22:05 GMT

Yes, what I was suggesting should let you identify the entire range of the network which you can successfully reach within your specified fuel tank capacity. This will consider paths in all directions starting from the source, and not just a single path (I was just using the single path example to illustrate some potential problems to be aware of). For each node reachable within this capacity, this will also tell you how much fuel it took to get there.

Re: Network Analyst - Slope-Switch at Junctions

DougSterling — Tue, 14 Sep 2010 21:41:57 GMT

its actually for electric vehicles. when they are driving downhill section and when they are recuperating (reusing breakenergy) then they actually receive some energy when driving downhill, thus the negative values 😉

Using the fuel consumption as accumulated attribute works fine, when i would look for a service area with a certain distance, like 100 km, but thats unfortunately not the case 😕

so is there really no possible way to get this thing worked out with the fuelconsumption as impedance attribute?

One possibility is to create a new impedance attribute for your roads where the downhill traversal cost is zero (if you have more than say a negative two percent grade). This isn't technically correct but it is probably very close to what you will encounter in the real world. A real world calculation would need to take into consideration the coefficient of drag of the vehicle, speed of the vehicle when traversing the edge, rolling resistance of the tires, etc. Simply saying that traversing an edge is "free" will probably come very close to the actual cost and you can then use the route solver to estimate the difference between this new attribute and your older attribute with negative costs. Best of all you could use this new attribute in the route and service area solvers to generate least energy consumption routes and service areas.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Wed, 15 Sep 2010 13:01:36 GMT

Checked everything today and it looks like I could get this going, when I would have more time left. I have to finish the work on this in one week and its not the only thing I have left for this work.

Today I was thinking about the option to take the distance as the impedance attribute and choose a value much higher than the car actually could drive without refueling. I then wanted to make a selection from the accumulated fuel-attribute with "to_fuelconsumption <= maximum fuel in car". From this point on, I could create a new layer from the selected features or even make a buffer around it to visualize the results. I wanted to check if the service area accumulates the negative values for the fuel consumption but couldnt find a line where it was working. I checked for lines with "from_fuelconsumption > to_fuelconsumption" which should select me all the lines with an energy reward for the car. Do I have to change anything in the network properties (besides the stuff which you already told me before in the thread) for the accumulation of the fuel with negative values?

I also thought about the option to make all negative values = 0, this would make it easier to work and visualize everything without a problem. The point is, that those negative values is actually a main part of this work Im doing so not recognizing this part doesnt seem to be an option for me, sorry. You are obviously right though, that there are a lot of other parameters having impact on the fuelconsumption. However, this would be the topic of following, related works, this one is designed for a simple model considering the slope and the length of the streetsegments. The results dont look too bad either. Thanks for your idea though! 🙂

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Wed, 15 Sep 2010 15:31:33 GMT

Do I have to change anything in the network properties (besides the stuff which you already told me before in the thread) for the accumulation of the fuel with negative values?

You should not have to change anything. Just check on the FuelConsumption attribute in the Accumulation tab on the analysis layer's property pages. If it is not accumulating the values properly for some reason, please post an example of what appears to be incorrect.

I was thinking about the option to take the distance as the impedance attribute and choose a value much higher than the car actually could drive without refueling. I then wanted to make a selection from the accumulated fuel-attribute with "to_fuelconsumption <= maximum fuel in car"

This is certainly a reasonable approximation. However, please note that if you simply select those parts of the network for which "to_fuelconsumption <= maximum fuel in car", then you could run into the exact same problem I was mentioning earlier about finding infeasible routes due to having a subpath which itself exceeds fuel capacity (even if the full shortest path does not).

What you really want is to find only those parts of the network which are reachable within your fuel capacity and for which no subpath from the source exceeds fuel capacity. Does this make sense?

You could still do this using the Service Area solver and a slight variation of your suggested approach above (of using a length-based impedance attribute while accumulating FuelConsumption). After solve, for each element which is reachable within the fuel capacity, you would need to trace the shortest path back to the source and only if every element along this subpath is itself reachable within capacity would you select that original element.

There is an older online sample (in VB6) which shows how to trace paths back to the source for service area traversal results. You can find this sample here:
http://edndoc.esri.com//arcobjects/9.2/CPP_VB6_VBA_VCPP_Doc/COM_Samples_Docs/NetworkAnalyst/TraversalResult/47680c4c-c854-4a0d-b975-d27cebc3ec8b.htm

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Wed, 15 Sep 2010 16:09:25 GMT

You should not have to change anything. Just check on the FuelConsumption attribute in the Accumulation tab on the analysis layer's property pages. If it is not accumulating the values properly for some reason, please post an example of what appears to be incorrect.

I am not at my working computer anymore, so I cant provide you any screens. I did a service area solve and had a look at the attribute table of the lines (~20k). I had a look through them and couldnt find a To_FuelConsumption having a lower value than the From_Fuel. I tried to select those lines then via select all lines "to_fuelconsumption < from_fuelconsupmtion". I havent received any result. I cant imagine that theres no single line in roughly 20000 lines which wouldnt have had a single negative value. By the way: approximately 30% of my street segments include a negative value on either From_ or To_FuelCon. Maybe theres a fault from me to think that this selection would give results, but it should be right, I suppose.
(I havent had any restriction attribute activated and used the right attribute fields for the From-To and To-From Values. I checked that already)

When you would have any ideas on this, they would be very welcome.

This is certainly a reasonable approximation. However, please note that if you simply select those parts of the network for which "to_fuelconsumption <= maximum fuel in car", then you could run into the exact same problem I was mentioning earlier about finding infeasible routes due to having a subpath which itself exceeds fuel capacity (even if the full shortest path does not).

What you really want is to find only those parts of the network which are reachable within your fuel capacity and for which no subpath from the source exceeds fuel capacity. Does this make sense?

This definitely makes sense 😉 Have to try out the VB file u linked me tomorrow.

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Wed, 15 Sep 2010 19:29:59 GMT

Thomas,

I have investigated this some more, and there actually appears to be a logic error in accumulating negative values for the Service Area solver. Therefore, it appears that your unique use-case scenario has uncovered a previously-unknown issue. Thanks for bringing this to our attention! 🙂 I have logged this as a bug, and we will take care of it as soon as possible.

In the meantime, you still have valid information which you can use for your purposes. Instead of using the field values from your Lines feature class, you can use the field values from the traversal results. Traversal results are just feature class representations of the individual edges, junctions, and turns that were traversed for a given solution, and the cost information associated with them.

The sample I pointed you to earlier shows how to work with traversal results to trace paths back to the source facilities for service area solutions. There is another add-in for ArcMap which allows you to automatically generate the traversal results for a given solution and it adds this information to ArcMap as new feature layers. Please see this sample here: http://resources.arcgis.com/gallery/file/arcobjects-net-api/details?entryID=C8A2186E-1422-2418-3494-48812C8DB8DE

Using this add-in, you can solve your service area, then generate the traversal results in ArcMap, and look at the field values on the traversal result feature layer named "Edges". The features in this layer represent all traversed edges for your solution, and the cost field values should correctly identify any negative-weight edge traversals.

Re: Network Analyst - Slope-Switch at Junctions

ThomasSchmidt — Thu, 16 Sep 2010 10:09:58 GMT

Im glad that I could help you out on this 😉

Ive succesfully used the "Select Transversed Features" Script u linked me, but unfortunately Im using ArcGis 9.3 and not Version 10, which is required for the lastest link u gave me... Any chance to get this working in 9.3?

Re: Network Analyst - Slope-Switch at Junctions

MichaelRice — Thu, 16 Sep 2010 14:47:55 GMT

Any chance to get this working in 9.3?

Absolutely. There are some simple code snippets showing how to do this same thing located here: http://resources.esri.com/help/9.3/ArcGISDesktop/ArcObjects/esriNetworkAnalyst/INATraversalResultQuery.htm

If you use the Visual Basic version of the code linked to above, you can simply copy and paste this into your ArcMap VBA editor and run it directly from there.