Bi-Directional Routing problem

[John]

The problem: bi-directional routing seems to behave as if 2 vehicle are leaving the origin and destination and meeting in the middle. The result is the path taken from the destination is following one-way roads as if being driven FROM the destination.

It is our assumption (and prehaps this is the problem) that bi-directional routing will resolve a route by  solving the route from the original and destination and meet in the "middle".  The output would be a valid route if driving from the original to the destination.

As such the route from the destination would actually travel the "wrong way" on a highway so it would meet the route being generated from the origin. If not, and as is the case with our results, the "middle" was the end of a common off-ramp segment.

Attached are 2 pictures of our results. Picture 1 show the route from the Destination. Please notice the route is leaving the destination and entering the highway to travel north west. However, if you want to get to the destination from the origin, you would have to be getting OFF the highway at this interchange.

Picture 2 show the entire route. The "middle" if the "spike" on the right where both the routes from the origin and destination met at a common highway junction.

Is our auumption on how this solves a route incorrect?

Thanks,

-John

 

[John]

Hello? Is anyone out there to answer my question? 
  
 -John

[Johnny]

Hi John,
We apologize for the delay and any inconvenience this may cause.
Just as you guessed, we take a similar way for Bi-direction algorithm, I agree with you that maybe there is a problem here, but i didn’t get a proper data for recreating, is it possible to give your test data to us? Just a slice is ok.
Btw, do you process the shape file for route using “MapSuite Routing Exploerer -> Data -> Generate Routable Date” to build a routable shape file before doing the route?
Thanks,
Johnny

[John]

 

Johnny,



I have attached 2 zip files. Together they contain the routing shapefile and the RTG/RTX files. Note, they are called "son of snippet" since our "snippet" database was larger than we wanted to test bi-directional routing.



We wrote the code to create the RTG file since we are using oneways and overpasses. Furthermore, and please understand we are knowledgable about routing data, this dataset was build to include hierarchical routing.



What does this mean? The RTG file is built to remove connnectivity from higher class roads to lower class roads. Therefore once the route has moved from a lower class (neightborhood) road to a higher class (highway) it can never connect to a lower class road again.



Given the nature of bi-directional routing, the route would typically "meet in the middle" on a higher class road. This solution is being tested to see if MapSuite routing components may be able to handle larger dataset (state of Pennsylvania, USA).



Currently routing from Erie, PA to Philadelphia, PA using Dijkstra's takes 26 seconds. The bi-directional routing takes 2 seconds. Given our modified routing database, we should be able to route from Erie to Philly with a "good" route in 2 seconds.



Does this make sense? See the routing data attached.



Thanks.



-John



 

snippet1.zip (233 KB)
snippet2.zip (403 KB)

[Johnny]

Hi John, 



Thank you very much for providing the demo data and screenshot, I can guess what happened to you. Just as you have mentioned, there is something wrong with the algorithm we took, I’m working on it now. Any progress will let you know.

Actually, the A* algorithm should get the similiar performance "2 seconds" to the "Bi-Direction" algorithm, it doesn't take the shortest route but an optimized shortest route, maybe high-way first or something like that, can you have a try if it fits your requirements while my development.



Thanks, 

Johnny 

 

[John]

Thanks Johnny. Hopefully this can be a hot-fix to the current release. We have a lot of software installed with customers and we’re not ready to move them to the .net framework 4.0. 
  
 If you need any additional info from me, please let me know. 
  
 Also, do you like the hierarchical routing data? Should work great with bi-directional! 
  
 -John

[Johnny]

Thanks John, things provided is really what I expected, Seems like it’s a bit complicated to fix it in a short time, just as mentioned, we shouldn’t take the middle point calculated from endpoint, now I’m considering some improvements here. 



Honestly, I like the way that you create the hierarchical data, it makes possible for routing with large data, such as a state roads. Thanks for your idea, we will try to resolve the issue to make sure it can route with Bidirectional algorithm. And then it look much better.



Thanks, 

Johnny 

 

[Johnny]

Hi John, 



Sorry for a long waiting, the problem has been fixed it now, just as far as we tested with one-way data, it works fine, but we didn't test it with a big data, such as state roads, i'm not sure if it fits your performance requirement, anyway, please get the latest "Production version" 6.0.0.121 or higher to have a try. Any question or problem, please let me know.

Btw, it's still based on .NET Framwork 3.5,  so please don't worry about the upgrade issue.



Thanks, 

Johnny

[John]

Johnny, 
  
 We downloaded the update. It appears to work, but not with our dataset. Is you use the data I supplied and try to run the route as displayed in the image above, no route is found. Maybe you could use the inspector to see the connectivity of our data and see why it is not solving a route? 
  
 By the way, the Dijkstra route using the new component seems to reduce the statewide routing from 25 seconds to 21 seconds…not sure if anything you changed would have impacted Dijkstra’s. 
  
 Thanks. 
  
 -John

[Johnny]

 

John,
Thanks for posting further information here, yes, we are sure we tested with the data you supplied. Before the Bidirectional algorithm gives the wrong routing result, because of some mistakes by us, I apologize for it. Actually, there isn’t any route between the start point and end point shown in the image posted before. We also carefully tracked all the possible segments between these 2 points manually one by one using the “information” tool in toolbar of “Routing Exploerer”,  I think we are sure there isn’t any route between them because of the one-way, but if we reverse the start and end point, route is there. Following is the key points around the end point, please check it:
 

Thanks,
Johnny