topic Re: Simple optimal route application in ArcGIS Network Analyst Questions

Simple optimal route application

PhuNguyen3 — Mon, 07 Nov 2011 14:13:31 GMT

I want to code a simple application using java that read data from street shapefile, calculate the shortest path between two vertices using an algorithm and display the route in MapBean of my app. What is want is a custom and simple route solver, for algorithm demo purpose only.

It might be simple task but the problem is that I am new with ArcGIS, and new with geographic field too. So I found many difficults in implementing the demo. I think the trouble is how to determine the adjacent edges of a vertex in the network. Is there any kind of junction connectivity table stored in shapefile and how to read these data, using java.

Any help would be greatly appreciated !

Re: Simple optimal route application

JaySandhu — Mon, 07 Nov 2011 21:29:52 GMT

A road dataset such as in shapefile format does not store any adjaceny (network topology information) with it. In fact there are no junctions. A road line feature class contains only roads. The actual road topology needs to be built from a set of rules that govern how roads connect, model bridge, tunnels, turn restrictions, etc. This is what the Network Analyst provides. It contains ways to make a network dataset from input line feature classes. The network dataset contains junctions and connectivity information and that can be queried. Network Analyst also provides the shortest path solver. So is your goal to write the shortest path solver or use an existing one?

Jay Sandhu

Re: Simple optimal route application

PhuNguyen3 — Tue, 08 Nov 2011 06:20:56 GMT

Thanks for your reply !

Actually, i want to write a new shortest path solver that used an algorithm like A* algorithm. So what I need is the connectivity information of the network, like knowing adjacent vertices of a junction. Do you mean the dataset that I used must contain those information in its attribute table ?

I take a look at sample data for network analyst in my ArcGIS dir, it contains road feature class and junction feature class, but in the attribute table of street junction, there is only FID, Shapefile and ZELEV, no information about connectivities. So, how the shortest path solver of NetworkAnalyst obtain those information?

Sorry for my bad English.

Re: Simple optimal route application

JaySandhu — Tue, 08 Nov 2011 13:36:32 GMT

The first part of using a shapefile for routing is to create the connectivity graph. As I explained in my previous post, first part is to create a network dataset that goes along with the shape file and then you can use that to query the adjacencies and write your own algorithm.

Here is how you can create the network dataset:
http://help.arcgis.com/en/arcgisdesktop/10.0/help/index.html#/Creating_a_network_dataset/00470000000w000000/

If you have seen the network sample data and you see shapefiles for streets and junctions then there will also be another folder with a .ND extension that contains the adjaceny information in a binary format.

You can take a look at the INetworkJunction object in this sample:
http://help.arcgis.com/en/sdk/10.0/java_ao_adf/conceptualhelp/engine/index.html#//0001000004t0000000

Basically once you have a networkjunction then you can call its QueryEdge method to find the adjacengt edges.
Some more help here:

http://help.arcgis.com/en/sdk/10.0/java_ao_adf/api/arcobjects/com/esri/arcgis/geodatabase/inetworkjunction.html

Jay Sandhu

Re: Simple optimal route application

PhuNguyen3 — Tue, 08 Nov 2011 16:27:45 GMT

Thank you Jay !

This field is really new to me and I've got stuck by this problem for some days. Thanks alot for your help.:D

Phu Nguyen.

Re: Simple optimal route application

PatrickStevens — Wed, 09 Nov 2011 13:38:15 GMT

Just to further the help that Jay has already given...

There are a couple of resources to help you code a custom solver. Using .NET, there is some code that uses our API to create a breadth-first solver algorithm here.

There is also a custom solver written in C++ that helps determine connectivity within a network here.

There is always the chance, too, that we provide the functionality that you are looking for, without the use of a custom solver. Are you writing one for the experience? Or are there specific capabilities that we don't provide yet?

Re: Simple optimal route application

PhuNguyen3 — Thu, 17 Nov 2011 18:26:11 GMT

Hi Patrick,

This product is great. I just want to write a piece of code to get optimal path bw 2 points in the network using a kind of heuristic algorithm. Its for my project in the university.

I have one more question. How to get the distance between two junctions in a street network in meter. I've tried several ways but all of them give the same result as using Pythagorean theorem for x, y coordinates of the two Point. This result make no sense when compare with the result from Measure tool in ArcMap. Is there any thing that need to be converted or processed before we can get real distance ? (I want to get the distance using java).

Thanks in advance for your help!

Re: Simple optimal route application

PatrickStevens — Thu, 17 Nov 2011 19:50:47 GMT

Thanks for your kind words.

As to your questions, what network are you using? Does it have a length cost attribute? If so, you can query each edge directly to find out what its cost is using AttributeValueByName. To do this programmatically, follow these steps:

Create a edge using INetworkQuery.CreateNetworkElement.
Populate the edge your are interested in using its EID in INetworkQuery.QueryEdge.
Then call AttributeValueByName, passing in the name of the length attribute.

If the length attribute on your network is not in the right units, and your network is not readonly, you can change the units to the ones you desire. If you network is read-only, then you'll need to do some manual conversion.

Re: Simple optimal route application

PatrickStevens — Thu, 17 Nov 2011 20:34:35 GMT

Sorry, I misunderstood your last post. You are looking for distance estimates to use as input to your A* algorithm?

I'm not sure exactly how the measure tool works, but perhaps the results from there are using geodesic distance around the globe, rather than true straight lines from your pythagorean estimates. That could explain the discrepancy.

Re: Simple optimal route application

MichaelRice — Thu, 17 Nov 2011 21:02:08 GMT

If you just wish to get a straight-line Euclidean distance between two junctions in your street network, then using the Pythagorean theorem for your x/y coordinates is fine. However, keep in mind that the x/y coordinates you are using are based on the dataset's associated coordinate system. Therefore, any "distances" you get from using these coordinates will be based on the units of the coordinate system (which may explain why your values are different than what you are seeing from the measure tool).

In order to obtain useful distance values using this approach without having to do more complex calculations, I would suggest that you make sure that your dataset is in a projected coordinate system (PCS). You can then figure out the distance-measure-of-choice per unit in your PCS, based on your desired distance measure (e.g., you can determine "meters per unit", "miles per unit", etc.).

You can then translate the length of the hypotenuse into the appropriate distance measure using this value. However, you should also make sure that any length attribute you are using in the network dataset for your solves is also based on the same unit of measure, for consistency. Additionally, if your impedance attribute is time-based and not length-based, then you would have to further translate this distance into a valid time estimate instead (e.g., using a maximum expected speed limit).

Does this make sense? Please let us know if you have any further questions.

Re: Simple optimal route application

PhuNguyen3 — Fri, 18 Nov 2011 07:12:56 GMT

Thank you all !

My algorithm is an improvement of LPA*, thus, it needs a heuristic estimation like the one of A*.

As Michael said, I look at the coordinate system of my shapefiles, and found out that it is in "GCS_Assumed_Geographic_1". So, i change the Geographic Coordinate System to Projected Coordinate System using Project tool in ArcToolbox. (i changed it to NAD_1983_California_Teale_Albers, pretty uncertain about how they work :D). Is that OK?

After that, i re-create my network dataset and check out the distance using Pythagorean theorem. It work ! The result is real distance in meter 😄

Re: Simple optimal route application

MichaelRice — Fri, 18 Nov 2011 15:21:22 GMT

(i changed it to NAD_1983_California_Teale_Albers, pretty uncertain about how they work ). Is that OK?

It is up to you to decide which projection works best for your particular purposes, as there are certainly many to choose from, and each has their own unique properties. Here are some good resources to become more familiar with projections and their associated properties:

What are map projections?

About map projections

What are projected coordinate systems?

My inclination would be to suggest that you find a good equidistant projection (e.g., see here for an example), as their purpose is to preserve distances as best as possible, and this is what you are ultimately looking for in your algorithm. However, you must also keep in mind any other purposes you might require for your dataset as well.

I hope this helps.

Re: Simple optimal route application

PhuNguyen3 — Fri, 18 Nov 2011 16:32:54 GMT

Thank you, Michael !

I am going to work on the materials.....

Re: Simple optimal route application

PhuNguyen3 — Tue, 22 Nov 2011 19:05:40 GMT

I have two more questions regard to my problem. They're about GUI implementation:

- After running the algorithm and find a shortest route, how can I draw the route on map so that user can easily regconizes that route. I found out piece of code in C#. Can I do the same with Java (I use ArcEngine 9.3)
http://help.arcgis.com/en/sdk/10.0/arcobjects_net/componenthelp/index.html#/RoutingForm/00480000014m000000/

- How I can let user choose a junction or an edge on a map by visually clicking on those elements (for example, choose the start point)

Thanks for any help!

Re: Simple optimal route application

PatrickStevens — Mon, 28 Nov 2011 15:41:24 GMT

You are venturing out of my area of expertise, but I'll try to point you in the right direction.

- After running the algorithm and find a shortest route, how can I draw the route on map so that user can easily regconizes that route. I found out piece of code in C#. Can I do the same with Java (I use ArcEngine 9.3)
http://help.arcgis.com/en/sdk/10.0/arcobjects_net/componenthelp/index.html#/RoutingForm/00480000014m000000/

To draw the route on the map, you will need to have tracked the edges that you have in your solution.

Here is some code that will help go from an elements EID to getting the source feature underlying it:

http://help.arcgis.com/en/sdk/10.0/arcobjects_net/conceptualhelp/index.html#/How_to_access_source_features_referenced_by_a_network_dataset/00010000036r000000/

Once you have your set of source features, it is up to you on how to store it and display it. It is probably more trouble that worth it to set up your work as a custom solver with its own network analysis layer that can be used to display results.

In your case, you can take the street features (and optionally, the junctions and turns) and output them as a feature class to a either a workspace on disk (FileGDB, SDE, SHP) or to an in-memory workspace. Then load the feature class as a layer in the table of contents of your map.

Look around the Managing Data part of the SDK to find a way to manage your results. Not sure this is the best possible way, but in your shoes, I would first look into in-memory workspaces. Then, look into how to display data as layers in the TOC. If this link doesn't get you there, then look around that general area of the SDK for other options.

- How I can let user choose a junction or an edge on a map by visually clicking on those elements (for example, choose the start point)

Once you have the point on the map where the user clicked, you need to find the nearest network location. A good starting point would be this InArcMap portion of this SDK document about how to load points in ArcMap.

I hope all of this helps. Also, note that anything you can do with .NET, you should be able to do with Java, with minor adjustments. That is why I link to the .NET SDK so much. It has a lot more information in it than the Java SDK.

Re: Simple optimal route application

PhuNguyen3 — Thu, 22 Dec 2011 18:17:41 GMT

Thanks a lot, Patrick. I have my problems solved with your comments. (try to work out with in-memory Workspace and finally decide to use just a polyline to display the route :D)

My GUI is now functional. But the problem is that it run very slow, in compare with the running time of non-GUI app. For example, to calculate the route, non-GUI app only need ~1s, but the GUI take about 30s to finished :(. Both apps use the same code, same algorithm.

Could you give me some advice for speeding up this stuff ?

Thanks and MERRY CHRISTMAS TO ALL !!!

Phu Nguyen.