topic Re: Computing OD Matrix using Network Analyst in ArcGIS Network Analyst Questions

Computing OD Matrix using Network Analyst

TDGoswami — Tue, 11 May 2010 19:50:17 GMT

Our current situation is that we have around 40,000 geolocated settlements across Africa, and each is located on a detailed road network shapefile. We would like to calculate the shortest distances by road from each settlement to every other settlement (i.e. creating a huge 40,000 x 40,000 Origin-Destination matrix of distances) - we have a methodology to do this for smaller datasets within GIS software, but are held back by memory limitations for such a large operation. Hence, we were interested to explore your methods before we consider developing our own solutions. Do you have any advice or suggestions on proceeding with this please ?

Re: Computing OD Matrix using Network Analyst

JaySandhu — Wed, 12 May 2010 13:54:08 GMT

40,000 by 40,000 is quite large. One way to tackle this is to create an OD Matrix Layer, set the output shape type to none (why bother creating straight lines is all you want is distance) and load these 40,000 locations as destinations. Then in a loop do the following: select the first 100 destinations, load them as origins, Solve, Write out the results to a file geodatabase table. Remove the 100 origins and repeate this for the next 100.

So basically do a 100 by 40000, 400 times. You maybe able to 200 by 40000.

If you have the ArcGIS 10 pre-release, you could run this on a machine with at least 4 GB of RAM and 64 bit OS (windows 7 or vista) then you can run larger problems. Also in ArcGIS 10, if you upgrade your network dataset and dissolve it with a new tool, you will get better performance.

Regards,
Jay Sandhu

Re: Computing OD Matrix using Network Analyst

TDGoswami — Fri, 14 May 2010 14:44:49 GMT

Thanks for the reply Jay. Can you show me how to write the loop to automate this. I am a fresh newbie to this and would really appreciate any help.

Best Regards
TD

Re: Computing OD Matrix using Network Analyst

TDGoswami — Fri, 14 May 2010 14:46:40 GMT

Also to let you know, I am using ArcGIS 9.3. How do I create a geodatabase?

TD

Re: Computing OD Matrix using Network Analyst

JaySandhu — Fri, 14 May 2010 19:44:19 GMT

Creating a geodatabase:

Start ArcCatalog. Navigate to the location you want to create the geodatabase.
Right-click in the folder and choose New and then File Geodatabase. Give it a name.

May I ask what will you be doing with the 1.6 Billion distance pairs you plan to compute?

Jay Sandhu

Re: Computing OD Matrix using Network Analyst

TDGoswami — Sat, 15 May 2010 13:40:19 GMT

After computing the pairwise distance matrix, I would like to write the contents of this matrix into a text file. Subsequently, I plan to use this matrix in a C++ and/or Matlab program which I have written, for doing some data mining. This is all a part of my research that I am doing on finding some useful patterns in the data. I work as a post-doc at the University of Florida.

Re: Computing OD Matrix using Network Analyst

TDGoswami — Sat, 15 May 2010 14:30:50 GMT

Hi Jay,

I was wondering if you can show me some script that can show how to compute the matrix (looping through all the destinations and a subset of the sources each time) . Also, how and where will I run this script please?

Thanks for your help,
TD

Re: Computing OD Matrix using Network Analyst

TDGoswami — Tue, 18 May 2010 16:27:15 GMT

I noticed that the road network I have has several discontinuities along thje roads. So, is there a tool (like Create Topology) that I can use which sets the tolerance and joins these discontinuities with small line fragments.

Thanks,
TD

Re: Computing OD Matrix using Network Analyst

CedricWannaz — Tue, 18 May 2010 18:01:06 GMT

I never used Network Analyst and OD matrices in ArcGIS, but here are some thoughts/hints before you obtain a better answer..

One way to build a loop is by programming it in Python and calling the ArcGIS Geoprocessor's methods (that correspond to the tool(s)) that you need to use. If you already program in C++/MATLAB, Python will not be an issue. An easy way to start is to open the Model Builder in ArcMap, drag and drop the tool(s) that you want to use, parameterize it/them, and export your model as a Python script (this way you will see how to create the Geoprocessor object, set the license, etc). Once done, try to run it and see if it works (on a small dataset) by typing "python yourScriptName.py" in a shell from the relevant folder (see note 1). If python is not recognized as an executable, you will have to update your PATH (environment variables, update the PATH by adding the path to your Python25 directory). When this simple code (directly exported from the Model Builder) works, the next step is to nest part of it in a loop that modifies the input/output parameters of the different tools/functions/methods calls.

In case you want to implement most of the computation by yourself, I did something quite similar 15 years ago based on Dijkstra's algorithm (well described on Wikipedia). I implemented it in C and it was extremely fast. There might be different ways to implement it, more or less fast or/and memory efficient, but I don't know/remember by heart.

If you are using Matlab, there are implementations of Dijkstra on Matlab Central, and you could use the Mapping toolbox - if you have it - to directly read a shapefile that contains edges lengths (or compute them using the distance() function of this toolbox on the lines or polylines that link your nodes).

Best regards,

Cedric

Note 1: editing/running you code in Eclipse would be a good thing to do if you are planning to play a bit with Python. Once you've installed a version of Eclipse (e.g. the Classic), install the PyDev extension ('Help/Install New Software' and specify the PyDev repository: "http://pydev.org/updates"), you just have a few things to do: in 'Windows/Preferences'PyDev/Interpreter - Python', add your python interpreter ("YourPath\Python25\python.exe"). When asked for the PYTHONPATH, check the "YourPath\ArcGIS\bin" entry. When done, you can create a new PyDev project, add a new file (yourFilename.py), and run it ("as Python run"). Cutting and pasting the export from the Model Builder should work if you have absolute paths to your resources (shapefiles, tables/dbf, filegeodatabase/..) in the export (which I guess is the case), otherwise you'll have to update the paths.

Re: Computing OD Matrix using Network Analyst

CedricWannaz — Wed, 19 May 2010 00:28:03 GMT

I thought a little about it and I was wondering if you couldn't first analyze links between clusters before trying to compute shortest paths between all the nodes.

I guess that there are multiple reasons for clustering to happen, rivers and like bridges at specific locations, borders and control points, valleys, etc. Wouldn't it be more efficient to build a solution around the following strategy (?) ..

1. Define clusters based on the aforementioned criteria.
2. Build a list of nodes that connect these clusters.
3. Determine shortest path "intra-cluster" for each cluster.
4. Based on 2. and 3., build a second ("virtual") network whose nodes are connection nodes from 2. and whose edges lengths are the shortest paths between these nodes obtained in 3.

Once done, you can determine the shortest path between two nodes by:
- If the two nodes are in the same cluster, it is given by 3.
- If the two nodes are in different clusters, add them to the virtual network, connected to each connection node of their own clusters by edges whose lengths are the shortest path to these nodes. Compute shortest path on this extended virtual network.

It would have several major advantages I guess. The obvious one is to reduce the dimension of your "objects" (matrices, etc) in memory by splitting it/them into multiple smaller ones. This would also be relevant for your processing in Matlab because it would not require a huge amount of contiguous memory (that is smaller than the free memory that is left on your machine). Moreover, as these clusters are not represented as directly connected within the same matrix, the sum of the smaller matrices are likely to require significantly less memory than a 40,000x40,000 full/dense matrix (you could see all your smaller matrices as blocs of a 40k x 40k bloc/sparse matrix). The price to pay would be a little more algorithm to develop in comparison to the direct, "brute-force" method.

This might not be adapted to the data-mining that you want to perform and I am far to be a specialist, so you might want to ask a real computer/network person or wait for my post to be fairly criticized 😉

Cheers,

Cedric

Re: Computing OD Matrix using Network Analyst

JaySandhu — Wed, 19 May 2010 17:08:34 GMT

Cedric,
I think TD here is not generating all nodes to all nodes OD. I believe he has discrete locations that he wants to use as input. So comuting distances from any location to any location is not as straight-forward as all nodes to all nodes type of algorithms you see in CS books. Also, as the Network Analyst already has this solver implemented why re-invent the wheel but concentrate on other things. Your point on clustering is well taken as 40k by 40 k matrix will be very large and MATLAB will not be able to take the whole thing in. But then TD has not specified if he wants to use the whole matrix or some small part of it for further data mining.
Jay Sandhu

Re: Computing OD Matrix using Network Analyst

TDGoswami — Thu, 20 May 2010 13:29:46 GMT

Thanks for all you help guys.

I am planning to use the contents of the entire matrix. That is, every element in that matrix is equally important for my further work.

I am trying to do a mechanical job of running 80 simulations in subsets of 500 sources covering the entire 40000 points. It is taking a lot of time. Moreover, it is taking even longer time to export the results of the OD Cost Matrix layer into a text file (since it has to write between 9 million to 12 million points). Is there a way I could make this Export faster?

Thanks,
TD

Re: Computing OD Matrix using Network Analyst

TDGoswami — Tue, 15 Jun 2010 21:55:21 GMT

Thanks to everyone for their help. I am faced with a peculiar problem now. I find that the distance computed by the OD Cost Matrix Layer is not symmetric. That is, for example, the distance between settlement 1 and settlement 500 is not the same as that between settlement 500 and settlement 1.

Do you guys have a reason for this behavior? Whats the solution?

Thanks
TD

Re: Computing OD Matrix using Network Analyst

JaySandhu — Wed, 16 Jun 2010 14:35:04 GMT

OD Matrix does not have to be symmetric. A road network may have many one-way streets, turn restrictions or penalties and the fact that it is a directed network, so travel to and travel from impedances may be different for the same edge. All of these can cause the travel time from location 1 to location 500 be different. If you want symmetric values, then either create a network without the above mentioned things (i.e., no turn penalties, no one-way information, no restrictions, and same travel-to/from impedances) OR use one half of the matrix and fill the other side to make it symmetric after the fact.
Regards,
Jay Sandhu

Re: Computing OD Matrix using Network Analyst

TDGoswami — Mon, 28 Jun 2010 21:52:30 GMT

I am now faced with an extremely peculiar problem.

I first created the network and then I was running the OD Cost Layer matrix on it. I find that some of the settlements have merged into one, although, these settlements were originally very far away from each other and had no similarities. Is there a reason for this behavior?

Re: Computing OD Matrix using Network Analyst

ToreBorvik — Tue, 29 Jun 2010 07:45:02 GMT

have you geocoded the points? Adresses with inaccurate quality might risk being placed in the centerpoint of a region (for instance a county, if county name is the only match of the address). In this occation, several villages might be placed at the same location.

Re: Computing OD Matrix using Network Analyst

bogdanpalade1 — Fri, 02 Jul 2010 08:51:57 GMT

Hello,
Sorry to jump in to the discussion with my own problem but its very similar to the original post and I thought its not necessary to open a new thread. In my case, I do not have to worry about memory problems because I have only 131 cities.
I thought that OD matrix would solve the problem by putting the 131 cities as origins and the same 131 cities as destinations and solve it. But the output is always 131 routes with 0 value because it computes only the closest distance between the points that will be given by the distance between the same city (once in origins and once in destination)

How can I do it to compute all the possible 131X131 distances?

I'm not expert in python but I can manage basic stuff

Thank you,

Bogdan

Re: Computing OD Matrix using Network Analyst

JaySandhu — Fri, 02 Jul 2010 14:51:30 GMT

Bogdon,
What network dataset are you using to computer the OD? If the 131 by 131 is returning only 1 closest the most likely there is no path from where those locations are being snapped on the network to rest of the points. Have you tried running a simple shortest path (Route) on a pair of cities and does that work. Possible reasons for not finding paths could be related to the way the network was set up. And of course make sure the OD is not set to compute only 1 closest, by default it is set to find "<All>".
Regards,
Jay Sandhu

Re: Computing OD Matrix using Network Analyst

JonathanWeyman — Thu, 03 Mar 2011 02:43:11 GMT

Hi Everyone,

I know this thread is quite old, but I am faced with a similar problem as the original poster. I am trying to compute an OD Cost Matrix with accumulated impedance values for distance from approx. 50,000 origins to ALL of approx. 34,000 destinations.

The "python loop" approach described above sounds promising, and I will certainly experiment with creating an initial model in modelbuilder and exporting to python in order to edit further. But, as I have little experience with Python, I'm wondering if anyone might be able to point me on the right track as far as coding the "loop" described above to select 100 or 200 records, run the OD cost matrix, export results, select the next batch of records, and so on?

This would be extremely helpful to me.

Thank you,

Tosh

Re: Computing OD Matrix using Network Analyst

jp — Wed, 29 Feb 2012 18:59:08 GMT

Hi Jay,

Can we restrict the network analysis results to filter calculation between origin and destination with same name or ID? Or can we make the results symmetric so distance between A to B is calculated but not B to A?

I couldn't find any such property in ArcMap.

Thanks.

OD Matrix does not have to be symmetric. A road network may have many one-way streets, turn restrictions or penalties and the fact that it is a directed network, so travel to and travel from impedances may be different for the same edge. All of these can cause the travel time from location 1 to location 500 be different. If you want symmetric values, then either create a network without the above mentioned things (i.e., no turn penalties, no one-way information, no restrictions, and same travel-to/from impedances) OR use one half of the matrix and fill the other side to make it symmetric after the fact.
Regards,
Jay Sandhu