[pgrouting-users] Some ideas for upcoming GSoC

[Max Weninger]

Hi

On Fri, 24 Feb 2012 10:00:52 +0900
Daniel Kastl <daniel at georepublic.de> wrote:
 
> I thought the "contraction hierarchies" algorithm does a lot of
> pre-processing. That's why it's fast.
> Do you think this pre-processing is suitable for pgRouting and doesn't
> constrain it's flexibility to select data by attributes, geometries,
> etc.?

It really depends on the "use case"

Of course the calculation of the required preprocessed data
must be solved e.g. by creating extra tables in the DB after importing.
Or "recreating" at later time if parameters that influence
route selection are changed (costs) and when the extra "penality"
of time needed to recreate is not a limiting factor.

You are right that this kind of routing engine is not really
made to support things like "dynamic" cost changes on a 
"query to query" basis. If you need this kind of things it
would be the wrong "choice" since the advantages would 
not apply.

It is more of a "static" kind of routing with "pre selected"
cost factors. So things like turn restrictions or costs based
on "static" factors like length, speed, ...

But still since it is so fast I could imagine also solutions
where the combination of multiple routing engines can make sense
e.g. use fast routing from city to city limit and then
use a more sophisticated one for the "last mile". 

So it depends on the reponsible people to decide if this
"fit" into the pgrouting "portfolio" or not :)

To be honest I just had a quick look at the implementation
and have by far not the knowledege how much effort it would be
and if it "makes sense" at all :)

But my plan is to have a closer look when I have more time :(
Having a 9to5 job does not make that easier ;)

Regards

max

> But if we have a GSoC candidate with a strong and feasible proposal
> for "contraction hierarchies" (and at least two mentors, who will
> support), such a candidate's proposal would be probably ranked high.
> 
> Daniel
> 
> 
> On Fri, Feb 24, 2012 at 8:57 AM, Max Weninger
> <max.weninger at gmail.com>wrote:
> 
> > Hi
> >
> > Has the "pgrouting team" ever thought about implementing
> > a routing solution based on "contraction hierarchies"
> >
> > Details about the concepts can be found here
> > http://algo2.iti.kit.edu/routeplanning.php
> > http://code.google.com/p/monav/wiki/ContractionHierarchies
> >
> > Example implementaions e.g. here
> > http://project-osrm.org/
> > http://code.google.com/p/monav/
> >
> > Routing with such engines is extremely fast (milisecs)
> > even for really large networks
> >
> > Regards
> >
> > max
> >
> > On Thu, 16 Feb 2012 14:52:46 +0900
> > Venkatesh Raghavan <raghavan at media.osaka-cu.ac.jp> wrote:
> >
> > > Dear All,
> > >
> > > As most of you must be aware, the
> > >
> > > Google Summer of Code 2012 has been announced [1,2]
> > >
> > > Some ideas that comes to my mind are
> > >
> > > 1) Implementing of map-matching algorithms as of the pgRouting
> > > function. Python code for the algorithms that we implemented in
> > > 2010 (See
> > > http://cs-test.ias.ac.in/cs/Downloads/article_45523.pdf) could be
> > > made available and the main work would be to integrate/improve
> > > them for implementation as pgRouting and/or SORouting (see item 2
> > > below)
> > >
> > > 2) Implementing routing as a service. a) Use Web Feature Service
> > > (WFS) as input b) implement routing functions as Web Processing
> > > Service (WPS) c) Publish
> > > routing result as WFS. That would be SORouting (Service Oriented
> > > Routing instead
> > > of pgRouting. Since I am also a ZOO-Project (www.zoo-project.org)
> > > PSC member which is a OGC compliant open-source WPS
> > > implementation, I would take this opportunity to promote the use
> > > of ZOO for implementing SORouting.
> > >
> > > 3) Route selection based on multi-criteria decision model to
> > > enable alternative
> > > route selection based on conditions at the destination. For
> > > example, route to
> > > the nearest hospital depending not only upon road conditions but
> > > also conditions at several destination hospitals (bed
> > > availability, availability of
> > > medicare specialists, availability of ICU etc). The condition of
> > > destination could be implemented using the OGC SOS standard.
> > > Regarding multi-criteria decision using AHP (analytical hierarchy
> > > process). There are several literature available [3],[4]. My
> > > student Sittichai (who writes
> > > on the pgRouting users list) has already started some work and
> > > could perhaps take up the work if he finds a mentor.
> > >
> > > Best
> > > Venka
> > >
> > > P.S. Also Cc to ZOO-PSC since there may be some mentors there to
> > > help with the WPS implementation for SORouting
> > > ------
> > > Prof. Venkatesh Raghavan
> > > Osaka City University
> > > Japan
> > >
> > > [1]http://www.google-melange.com/gsoc/homepage/google/gsoc2012
> > > [2]
> > >
> > http://google-opensource.blogspot.com/2012/02/google-summer-of-code-2012-is-on.html
> > > [3]
> > > http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5567840
> > > [4]
> > > http://www.tandfonline.com/doi/abs/10.1080/13658810601135692#preview
> > >
> > >
> > > _______________________________________________
> > > Pgrouting-users mailing list
> > > Pgrouting-users at lists.osgeo.org
> > > http://lists.osgeo.org/mailman/listinfo/pgrouting-users
> >
> > _______________________________________________
> > Pgrouting-users mailing list
> > Pgrouting-users at lists.osgeo.org
> > http://lists.osgeo.org/mailman/listinfo/pgrouting-users
> >
> 
> 
>