[pgrouting-dev] Gsoc 2013 Preliminary project proposal

Wed Apr 10 19:50:19 PDT 2013

Thanks for the reply steve . i have already cloned the github repository
and looking into various aspects of it .

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.

On Thu, Apr 11, 2013 at 1:42 AM, Stephen Woodbridge <woodbri at swoodbridge.com
> wrote:

> On 4/10/2013 3:23 PM, Mukul priya wrote:
>
>>
>> Hi ,
>>
>
> Hi Mukul,
>
> Thank you for your interest in pgRouting.
>
>                I am a  B.tech fourth year student at IIIT-Hyderabad
>> pursuing a degree in computer science and engineering and i will be soon
>> pursuing a Masters Degree in the field of Spatial Informatics and the
>> research topic that i have been working on is *"In route nearest
>> neighbour querries".*
>>
>>
>>               Last year i worked on a project that was funded by
>> Honeywell technology solutions and it gave me a lot of insight about
>> open source programming and industrial work culture.
>>
>> I was introduced to pgrouting by *Prof. Venkatesh Raghavan* who visited
>>
>> our college last summer. i have also used pgrouting for implementing one
>> of my Honors project.
>>
>> i have gone through the updated ideas page and i am listing out a topic
>> that i feel i can contribute to.
>>
>> *Idea *
>>
>> Network Partitioning
>>
>> A very simple method using which it can be done is :
>>
>>   * *Existence of a natural Hierarchy*
>>
>>
>>           Generally road networks are organized such that there is some
>> natural hierarchy for example if we look at the road network of USA we
>> observe that there are national highways which connect multiple large
>> regions , inter state roads connect places within these regions , multi
>> lane roads connect city areas and then there are small roads to connect
>> individual houses.
>>
>>             so what we can do is first rank these classes that
>> constitute the road network and then use the highest level roads to
>> divide the road network into large regions enclosed by these roads. each
>> of the divided regions can further be divided again using next lower
>> level road.
>>
>>             so suppose we have a road network which n classes of
>> different roads then we can create a tree of depth n-1 where the root of
>> the tree will represent the entire road network and children of the the
>> root node will represent the area formed by partitioning the root using
>> the level 1 ( highest ) edges and so on . the nodes will basically
>> represent a smaller part of the road network.
>>
>>              The idea seems to be very naive right now but if anyone can
>> give some feedback whether it is achievable or not or may be suggest
>> some modifications.
>>
>
> 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.
>
> So for the natural hierarchy, you can for a SQL query like:
>
> select * from edges where st_dwithin(the_geom, start_pnt, radius)
> union
> select * from edges where st_dwithin(the_geom, end_pnt, radius)
> union
> select * from edges
>   where st_expand(st_makeline(start_**pnt, end_pnt), pct)
>     and road_class < 4;
>
> 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.
>
> 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.
>
> 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.
>
> If you think about your edges sorted into say 1 degree grid partitions,
> 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! :)
>
>
>                In route nearest neighbour querries( IRNN) which handle
>> querries like computation of shortest path , provided that the user
>> wants to visit facilities F1 , F2 ,.....FN while he/she drives or walks
>> from source to destination. Network partitioning can optimize these
>> computations  too as the search space reduces significantly once we have
>> the partitions. Handling such querries have not been implemented yet. It
>> will be very helpful if we can have some discussion about whether
>> implementing it is feasible or not.
>>
>
> What is we just added via support to routing? Then we could do something
> like say generate a route: Start, F1, F2, ... Fn, End
> 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.
>
>
>
>                It would be great if someone could give a general idea
>> how  to go about learning more about the areas mentioned  with respect
>> to the organization's projects.Specially suggest those ideas which the
>> developers think are achievable for now . I will also be grateful if
>> somebody can guide me regarding the development framework of pgrouting
>> so that i get familiar with the whole framework in the coming days.
>>
>
> 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.
>
> Ask questions, There is a tutorial floating around and lots of people that
> are will to help.
>
> -Steve
>
>  Thank you .
>>
>> Mukul Priya
>> Lab for spatial Informatics
>> IIIT-Hyderabad
>>
>>
>> ______________________________**_________________
>> pgrouting-dev mailing list
>> pgrouting-dev at lists.osgeo.org
>> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>>
>>
> ______________________________**_________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130411/a005e19d/attachment-0001.html>