Network Analyst - Slope-Switch at Junctions

[ThomasSchmidt]

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

[MichaelRice]

Okay, this will require knowledge in two particular areas:

1. The Bellman-Ford Algorithm


2. 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/D46...


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.

[ThomasSchmidt]

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!

[MichaelRice]

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.

[DougSterling]

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.

[ThomasSchmidt]

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! 🙂

[MichaelRice]

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/Traversa...

[ThomasSchmidt]

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.

[MichaelRice]

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-...

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.

[ThomasSchmidt]

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?

[MichaelRice]

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/INATraversalResultQue...

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.