<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Apr 11, 2013 at 11:50 AM, Mukul priya <span dir="ltr"><<a href="mailto:mukul2047@gmail.com" target="_blank">mukul2047@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div dir="ltr"><div>Thanks for the reply steve . i have already cloned the github repository and looking into various aspects of it .<br>
<br></div>For IRNN querry implementation i think it is a good idea to sub divide the whole route and generate n+1 routes separately , say from S to F1 , F1-F2 ,..... F(n-1)-Fn , Fn to D . i wanted to know if we have that kind of a data where each and every facility is mentioned on the map as a point (node ) . even if it is not directly connected to the road network we can basically treat it a pseudo node and then call the router . The other thing about optimization yes we can do that using spatial range querries suppose there are several instances of the same facility that a user wants to access then we can use spatial range querries to locate that facility which is the nearest.<br>
</div></blockquote><div><br></div><div><br></div><div style>Hi Mukul,</div><div style><br></div><div style>Last year I attended an Oracle Spatial Routing workshop ... errrm ... product show ;-)</div><div style>They face the same issue with long distance queries as pgRouting. What seems to help them is what they call "partitioning".</div>
<div style>I don't know details how they do, but what I remember was, that you specify the size of a partition and then nodes are assigned to it.</div><div style>Then for a routing query partitions are loaded "on-demand".</div>
<div style><br></div><div style>Well, not sure this is really correct description or not, but here is some of their documentation:</div><div style><a href="http://docs.oracle.com/cd/B28359_01/appdev.111/b28400/sdo_route_server.htm">http://docs.oracle.com/cd/B28359_01/appdev.111/b28400/sdo_route_server.htm</a><br>
</div><div style><br></div><div style>So you could take a look and also make sure that this is not some patented idea.</div><div style>I mean, we could call it "clustering" ;-)</div><div style><br></div><div style>
Anyway it is important to keep in mind, that pgRouting is not a routing library for road networks only. So defining a "natural" hierarchy should not only allow a single use case, such as for cars for example. </div>
<div style>So as Steve mentioned, one idea would be to only load chunks of data on demand.</div><div style>Another idea is to get a hierarchy based on geometry. I think the "Contraction Hierarchy" algorithm is doing something like that: <a href="http://en.wikipedia.org/wiki/Contraction_hierarchies">http://en.wikipedia.org/wiki/Contraction_hierarchies</a></div>
<div style>pgRouting tries to avoid pre-processing based on attributes, such as road classes for example. Pre-processing based on geometry would be the best.</div><div style><br></div><div style>Daniel</div><div><br></div>
<div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<div dir="ltr">
</div><div class=""><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">On Thu, Apr 11, 2013 at 1:42 AM, Stephen Woodbridge <span dir="ltr"><<a href="mailto:woodbri@swoodbridge.com" target="_blank">woodbri@swoodbridge.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">On 4/10/2013 3:23 PM, Mukul priya wrote:<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
<br>
Hi ,<br>
</blockquote>
<br>
Hi Mukul,<br>
<br>
Thank you for your interest in pgRouting.<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>
I am a B.tech fourth year student at IIIT-Hyderabad<br>
pursuing a degree in computer science and engineering and i will be soon<br>
pursuing a Masters Degree in the field of Spatial Informatics and the<br></div>
research topic that i have been working on is *"In route nearest<br>
neighbour querries".*<div><br>
<br>
Last year i worked on a project that was funded by<br>
Honeywell technology solutions and it gave me a lot of insight about<br>
open source programming and industrial work culture.<br>
<br></div>
I was introduced to pgrouting by *Prof. Venkatesh Raghavan* who visited<div><br>
our college last summer. i have also used pgrouting for implementing one<br>
of my Honors project.<br>
<br>
i have gone through the updated ideas page and i am listing out a topic<br>
that i feel i can contribute to.<br>
<br></div>
*Idea *<div><br>
Network Partitioning<br>
<br>
A very simple method using which it can be done is :<br>
<br></div>
* *Existence of a natural Hierarchy*<div><br>
<br>
Generally road networks are organized such that there is some<br>
natural hierarchy for example if we look at the road network of USA we<br>
observe that there are national highways which connect multiple large<br>
regions , inter state roads connect places within these regions , multi<br>
lane roads connect city areas and then there are small roads to connect<br>
individual houses.<br>
<br>
so what we can do is first rank these classes that<br>
constitute the road network and then use the highest level roads to<br>
divide the road network into large regions enclosed by these roads. each<br>
of the divided regions can further be divided again using next lower<br>
level road.<br>
<br>
so suppose we have a road network which n classes of<br>
different roads then we can create a tree of depth n-1 where the root of<br>
the tree will represent the entire road network and children of the the<br>
root node will represent the area formed by partitioning the root using<br>
the level 1 ( highest ) edges and so on . the nodes will basically<br>
represent a smaller part of the road network.<br>
<br>
The idea seems to be very naive right now but if anyone can<br>
give some feedback whether it is achievable or not or may be suggest<br>
some modifications.<br>
</div></blockquote>
<br>
Yes this is the basics of how this could work. Because we build our graphs dynamically for each route request, we can do something like this today. Typically you have to feed the route request and SQL query that provides the edges needed to build the graph and this can be simply the bounding box of the start and end point of the route expanded slightly to allow the route move outside that bounds by a little if needed. A case in point are start and end points that form a vertical of horizontal line.<br>
<br>
So for the natural hierarchy, you can for a SQL query like:<br>
<br>
select * from edges where st_dwithin(the_geom, start_pnt, radius)<br>
union<br>
select * from edges where st_dwithin(the_geom, end_pnt, radius)<br>
union<br>
select * from edges<br>
where st_expand(st_makeline(start_<u></u>pnt, end_pnt), pct)<br>
and road_class < 4;<br>
<br>
So this gets all edges regardless of class at the start and end and then gets all the major roads and highways between the start and end points. We can dynamically select the edges that we want when we build the graph.<br>
<br>
Regardless of how you implement the routing, the problem is all about the data. If you have a road segment the is misqualified, you might end up with a network that is broken between start and end. This can alsoo happen if ramps are not coded correctly.<br>
<br>
One of the challenges we have today is that we have to be able to construct the whole graph in memory before we can start routing. This is ok for small areas but it is a problem if you want to generate a route between say Miami, Florida and Seattle, Washington. An interesting problem would be the ability to partition the data in spatial chucks and only load them as the solver needed them.<br>
<br>
If you think about your edges sorted into say 1 degree grid partitions,<br>
then you load the partition for the start point and start routing using A* search, when you frontier get to an edge of the grid you are in, then you load the adjacent grid and continue, if you bump into another grid boundary that is not loaded yet, you load, if it is already loaded you continue. Anyway food for thought! :)<div>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
In route nearest neighbour querries( IRNN) which handle<br>
querries like computation of shortest path , provided that the user<br>
wants to visit facilities F1 , F2 ,.....FN while he/she drives or walks<br>
from source to destination. Network partitioning can optimize these<br>
computations too as the search space reduces significantly once we have<br>
the partitions. Handling such querries have not been implemented yet. It<br>
will be very helpful if we can have some discussion about whether<br>
implementing it is feasible or not.<br>
</blockquote>
<br></div>
What is we just added via support to routing? Then we could do something like say generate a route: Start, F1, F2, ... Fn, End<br>
This would allow us to build a graph one time and then generate multiple sub-routes with in the graph. Today if you want to do that you have to generate n+1 routes and build the graph n+1 times. We could also do some preliminary optimization of the via points based on Euclidean distance using something like TSP before calling the router.<div>
<br>
<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
It would be great if someone could give a general idea<br>
how to go about learning more about the areas mentioned with respect<br>
to the organization's projects.Specially suggest those ideas which the<br>
developers think are achievable for now . I will also be grateful if<br>
somebody can guide me regarding the development framework of pgrouting<br>
so that i get familiar with the whole framework in the coming days.<br>
</blockquote>
<br></div>
I would clone the github repository and look at branch sew-devel-2_0 this is our new tree structure and it has code, doc, and test all organized in a nice way that makes it easy to multiple contributors work with the tree.<br>
<br>
Ask questions, There is a tutorial floating around and lots of people that are will to help.<br>
<br>
-Steve<br>
<br>
<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>
Thank you .<br>
<br>
Mukul Priya<br>
Lab for spatial Informatics<br>
IIIT-Hyderabad<br>
<br>
<br></div>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
<br>
</blockquote>
<br>
______________________________<u></u>_________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org" target="_blank">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/<u></u>mailman/listinfo/pgrouting-dev</a><br>
</blockquote></div><br></div>
</div></div><br>_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br><span style="font-family:arial,sans-serif;font-size:13px;border-collapse:collapse">Georepublic UG & Georepublic Japan<br>eMail: <a href="mailto:daniel.kastl@georepublic.de" style="color:rgb(66,99,171)" target="_blank">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de/" style="color:rgb(66,99,171)" target="_blank">http://georepublic.de</a></span>
</div></div>