[pgrouting-dev] Gsoc 2013 Preliminary project proposal
Daniel Kastl
daniel at georepublic.de
Thu Apr 11 00:24:30 PDT 2013
On Thu, Apr 11, 2013 at 11:50 AM, Mukul priya <mukul2047 at gmail.com> wrote:
> 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.
>
Hi Mukul,
Last year I attended an Oracle Spatial Routing workshop ... errrm ...
product show ;-)
They face the same issue with long distance queries as pgRouting. What
seems to help them is what they call "partitioning".
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.
Then for a routing query partitions are loaded "on-demand".
Well, not sure this is really correct description or not, but here is some
of their documentation:
http://docs.oracle.com/cd/B28359_01/appdev.111/b28400/sdo_route_server.htm
So you could take a look and also make sure that this is not some patented
idea.
I mean, we could call it "clustering" ;-)
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.
So as Steve mentioned, one idea would be to only load chunks of data on
demand.
Another idea is to get a hierarchy based on geometry. I think the
"Contraction Hierarchy" algorithm is doing something like that:
http://en.wikipedia.org/wiki/Contraction_hierarchies
pgRouting tries to avoid pre-processing based on attributes, such as road
classes for example. Pre-processing based on geometry would be the best.
Daniel
>
>
> 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>
>>
>
>
> _______________________________________________
> pgrouting-dev mailing list
> pgrouting-dev at lists.osgeo.org
> http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
>
>
--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl at georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20130411/aa15d307/attachment.html>
More information about the pgrouting-dev
mailing list