ThinkGeo.com    |     Documentation    |     Premium Support

Time and Distances Matrix creation

#1

Hello,


I need to create a reasonably large times and road distances matrix. (150 x 150 to 300x300). The approach used in the post gis.thinkgeo.com/Support/Dis...fault.aspx Time and Distance matrix is too slow for this I think.


I think, but I don't know how to implement this in ThinkGeo,the routing process could be made faster by



        
  • ignoring the route segments, I am only after the value

    •     
  • taking advantage of the calculations handled in one point - to many points way (the searching algorithms have to go through large parts of the tree anyhow, so going from 1 to 50 points is not 50 times more expensive than single From and To calculation.


150 * 150 = 22500. If I want my calculations to take up to 15mins (15*60=900s) I should be able to generate at least 25 routing results in a second (22500/900).


Any ideas on how to achieve this ?


Tomas


 



#2

Tomas, 
  
   I think I understand your points on how to speed things up.  Have you tried the sample you referenced?  How long did it take with your sample data?  About how far apart are the points in your sample?  I am wondering because we can setup a test where we generate some point of our own and test the speed.  If you have a test set of points and road network that would be great also.  What are your expectations on time? 
  
 David

#3

My expectations on time would be in the range of 25 values per second. Since I don't imagine asking for times in the one-to-one fashion is efficient, the time estimate is more of an average.


The points in my sample are about 50 km apart. I selected them by mouse clicking.


i have tried a 10x10 matrix : 70 seconds (only A->B creation) 

                        15x15 matric: 180 seconds


 


My data are taken from the OpenStreetMap shapefiles outputs - Czech Republic, roads. download.geofabrik.de/osm/


The rtg file was created by therouting explorer (and the first creation failed (file produced, but threw exceptions when routing attempted)).


I am sending you the test project I have been messing with. (no clean code guarentee :) )



HelloRoutingWorld.zip (40.3 KB)

#4

Any word of progress or ideas ?

#5

Tomas, 
  
   Nothing yet.  We are having a hard time downloading the data.  The zip file always ends up corrupted.  We also will need to setup the sample and get into the internals of the routing engine.  I want to see how much time we save by not returning the shapes.  We are pretty busy at the moment but I think we can get some progress made tomorrow. 
  
 David

#6

David,  
 Thank you for the reply. If you have problems with getting the data I can send you mine. Point me to a ftp path. I can understand you guys are busy :) I generally need to have some idea you are having a look at it rather than have an immediate answer. I would like to know the answer so I can either start implementing ThinkGeo in my project or ditch it and since I am aiming to ship my product in couple weeks I need to make that decision. Thanks for all your efforts.

#7

Tomas, 
  
   I was able to download it now.  For some reason Chrome always corrupts the file.  I used a download manager and was able to get it.   
  
   We are defiantly working on it and are not going to let you slip through the cracks.  We just need more than one day to get your sample setup and get to the internals.  Give us until tomorrow and I think we will have a solid answer.  In my opinion I think there are many ways we can get the time down.  We need to really look at the data as well as maybe it is not optimized very well for routing.  I will keep you posted. 
  
 David

#8

Tomas, 
  
   I talked to our routing guy here and there are some other ways we can speed it up.  We can modify the index format a bit to drop off some unused data.  This should really speed things up as we will cut our disk I/O by more than half.  We can do this because you don’t need the road segments.  We can also write a little code to take advantage of multicore processors.  In this way you can get all your cores on this.  This could be as easy as a few threads and a few instances of the routing engine.  In any event we are up to the task in meeting your requirements.  We just need a little time. 
  
 David

#9

David, 
  
 thank you for the reassurance. I am a developer working with optimization and lot of processing and I can understand, that until the need arises, there is little reason to optimize a special circumstance of a process (such as what I want). The multicore processing would be of a great benefit as this should process would usually run on a server / powerfull machine to speed things up. 
  
 Tomas

#10

Tomas, 
  
   No problem and it is exactly like what you said.  The team is going to dedicate tomorrow to looking into your issues.  We have the data, index build, and your sample so we can see what we can do. 
  
   Can you verify one thing for me?  When you created your index files you side it had an error?  Can you look at your roads file and tell me the size of the .idx & ids files?  The same thing happened to me and the files were built incorrectly.  I built them again from code but I wonder if the index not being correct is slowing things down.  I don’t think so but curious all the same. 
  
 David

#11

The error wasn’t in the creation, but when routing I would get a null object reference coming from the routing engine. 
  
 .idx 13 647 872 bytes 
 .ids 4 054 448 bytes 
  
 Tomas 


#12

Tomas, 
  
   I have some progress for you.  Just by adding 4 threads we were able to cut the time by more than half and that without any modifications on our end just some changes to your sample.  I think we will be able to half it again with a change in the index.  We will know more tomorrow. 
  
   The point locations have allot do do with the time.  Could you send a screenshot of where you are putting your points?  I just want to make sure we are doing the same thing.  Better yet send a list of points and we can have a proper test. 
  
 David

#13

 Tomas,


  More good news..  We tweaked a few more things in the sample and was able to get a 15x15 matrix down to 24 seconds.  Of course it all depends where you place the points.  See the attached screenshot.


David




#14

David, 
  
 great news ! The point placement is very similar to what I have done - I think the comparison would be valid. I placed my points in Moravia (the eastern bit), but that wouldn’t have changed much. 
  
 Tomas

#15

Tomas, 
  
   Letting it crunch through 100 points spread all around the country.  Pretty interested in what I will get back.  The good news is that the memory seems to be good on the 100 point trial, it goes up to over a gig and then garbage collects and drops down to two hundred meg or so…  I will let you know the times when it is finished.  
  
  I’m now wondering if modifying the index structure will buy us much, maybe a little but it seems that any large amount of point seems to end up loading the index into memory.  The process is cranking along but not all of disk access.  I think by not returning the actual route data just the distance will speed things up though. 
  
   Heading home soon so I might post those results tomorrow morning. 
  
 David

#16

David, 
  
 thanks for all your efforts. I still can’t quite figure out what time zone you are in :) Hawai ? 
  
 Tomas

#17

Tomas, 
  
   I travel quite a bit so I am in different time zones all the time.  Currently I am in our Asian Pacific office so its GMT+8 here I think… 
  
   The 100 point matrix finished and it took 33 minutes.  Not sure of this is good or bad, that is quite a few routes to calculate.  I think there is still room for improvements that we will try today.  If nothing else I will send you my code modifications to your sample. 
  
 David

#18

Tomas, 
  
   We added some more code to allow you to turn off the much of the data returned in the RoutingResult.  If you turn that off the we have the 15x15 matrix down to about 19 seconds.  Of course the time all depends where you put the points.  We have one other thing we want to do that will take about a day which is to optimize our file format. 
  
   Many of these enhancements we have been planning on for some time just just never had the push to do them.  The way we have out system setup is that we have an abstract RoutingSource so to implement a new index type is really easy for us and we can add new ones without changing the core code.  We are going to streamline the index a bit, remove a few binary searches we were doing and I think we can get the time down further still. 
  
 David

#19

David, 
  
 thanks again for all the effort. What would be the best way for me to give this a shot ? I will work on the mapping functionality in the next couple days and would like to setup the the routing as well. 
 We are aiming at a test deployment at the client site next week Friday. (only a trial not everything has to work flawlessly) 
  
 Tomas

#20

Tomas, 
  
   I can package up my changes tomorrow and post the changes here on the forum.  I also updated the routing assembly to allow you to turn off getting the feature lines.  You will need to get those from the daily builds on our website.  Are you familiar with the daily builds? 
  
   I know another guy is working on a more optimized format and I expect him to finish that tomorrow or Monday.  All the changes will roll out on the daily builds. 
  
 David