[pgrouting-users] Re:Some ideas for upcoming GSoC

sittichai_Choosumron · February 16, 2012, 7:46pm

Dear all,

First of all I would like to thank you Prof.Venkatesh Raghavan to introduce me again to this mailing list.

About using AHP with pgRouting, I was started using AHP for assign a priority weigth to the elements that depending on their perceived relative importance for computing route result.
For example, If we need to find the route from start point to the destination point such as hospital in case of emergency route. The elements were used for a judgments are Distance, Speed limit, Road width, Road type, Junction delay, etc. (If we first thinking only about the road condition). Then, from AHP analysis we can get the priority weights values like this;

Criteria | Priority (%)

| distance | 15.89%
| Speel limit | 8.82%
| Road width | 4.83%
| Road type | 6.78%
| Junction delay | 12.88%
| … | …
| … | …

| Sum | 100%

Next step, I need to integrate this values with road netwrok attribute data to compute the minimum cost for a route result.

Any ideas how to do this process?

Best regards,
Sittichai

On Fri, Feb 17, 2012 at 2:00 AM, <pgrouting-users-request@lists.osgeo.org> wrote:

Send Pgrouting-users mailing list submissions to
pgrouting-users@lists.osgeo.org

To subscribe or unsubscribe via the World Wide Web, visit
http://lists.osgeo.org/mailman/listinfo/pgrouting-users
or, via email, send a message with subject or body ‘help’ to
pgrouting-users-request@lists.osgeo.org

You can reach the person managing the list at
pgrouting-users-owner@lists.osgeo.org

When replying, please edit your Subject line so it is more specific
than “Re: Contents of Pgrouting-users digest…”

Today’s Topics:

Some ideas for upcoming GSoC (Venkatesh Raghavan)

Code tidy up? (Dave Potts)

Re: [pgrouting-dev] Some ideas for upcoming GSoC
(Stephen Woodbridge)

Re: Re: [pgrouting-dev] Some ideas for upcoming GSoC
(Jose Carlos Martinez)

Re: Code tidy up? (Stephen Woodbridge)

Message: 1
Date: Thu, 16 Feb 2012 14:52:46 +0900
From: Venkatesh Raghavan <raghavan@media.osaka-cu.ac.jp>
Subject: [pgrouting-users] Some ideas for upcoming GSoC
To: pgRouting developers mailing list <pgrouting-dev@lists.osgeo.org>,
pgRouting users mailing list <pgrouting-users@lists.osgeo.org>,
zoo-psc <zoo-psc@gisws.media.osaka-cu.ac.jp>
Message-ID: <4F3C99AE.9050909@media.osaka-cu.ac.jp>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

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

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)

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.

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

Message: 2
Date: Thu, 16 Feb 2012 07:55:55 -0000
From: “Dave Potts” <dave.potts@pinan.co.uk>
Subject: [pgrouting-users] Code tidy up?
To: pgrouting-users@lists.osgeo.org
Message-ID:
<e0a177d49878044779d3289cc58acbb4.squirrel@dp2642.f9.co.uk>
Content-Type: text/plain;charset=iso-8859-1

Hi list

Is there ever going to be a tidy up off the code associated with the demos
of the pgr functions?

In some cases you have to set the cost field to the value length.
In some cases you have to set the primary key to id
Some methods allow you to list the reverse_cost.
For the traveling sales man you have to include a 2nd undocumented table

Please note I am not suggesting a total rewrite off the code, just a tidy
up, a bit of renaming, tidying up the api, better documentation.

Something like a common interface

e.g.

xxxx('table_name,cost_field,reverse_cost_field,method_specfic_stuff)

It might also help if we had a standard network for testing purpose and a
list of expected results.

Currently I find it very hard to program up a solution for pgr_route
without knowning what the correct results should be. If I had a test
database, it would make life easier.

Having test data might cut down on the number of questions that are being
asked on the list.

Dave.

Message: 3
Date: Thu, 16 Feb 2012 10:07:51 -0500
From: Stephen Woodbridge <woodbri@swoodbridge.com>
Subject: [pgrouting-users] Re: [pgrouting-dev] Some ideas for upcoming
GSoC
To: pgrouting-dev@lists.osgeo.org, pgRouting Users List
<pgrouting-users@lists.osgeo.org>
Message-ID: <4F3D1BC7.9050004@swoodbridge.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Venkatesh,

I have looked into map-matching and I think this would be a wonderful
addition to pgRouting. I have collected an extensive library of
map-matching articles. One of the real challenges in map-matching is
dealing with multiple parallel paths like an exit ramp the parallels the
highway and you can not be certain which one you are on until the paths
diverge from one or the other. This implies tracking multiple potential
paths and scoring them or some kind of back tracking and path
correction. These problems are compounded when you have low quality GPS
fix and your positional error increases, like in urban canyons or other
conditions that provide a poor fix.

I would be interested in looking at what you have accomplished, but I
think this is an excellent GSoC project.

-Steve

On 2/16/2012 12:52 AM, Venkatesh Raghavan 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

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)

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.

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-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Message: 4
Date: Thu, 16 Feb 2012 16:21:40 +0100
From: Jose Carlos Martinez <jomarlla@cgf.upv.es>
Subject: Re: [pgrouting-users] Re: [pgrouting-dev] Some ideas for
upcoming GSoC
To: pgRouting users mailing list <pgrouting-users@lists.osgeo.org>
Message-ID: <4F3D1F04.6020606@cgf.upv.es>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Hi Venka,
Even though is not my research if I can do something to help you, please
let me know. Ive been working lately a little bit with OSM data and
pgrouting too.
Anyways greetings from Valencia.
Jose

On 16/02/2012 16:07, Stephen Woodbridge wrote:

Venkatesh,

I have looked into map-matching and I think this would be a wonderful
addition to pgRouting. I have collected an extensive library of
map-matching articles. One of the real challenges in map-matching is
dealing with multiple parallel paths like an exit ramp the parallels
the highway and you can not be certain which one you are on until the
paths diverge from one or the other. This implies tracking multiple
potential paths and scoring them or some kind of back tracking and
path correction. These problems are compounded when you have low
quality GPS fix and your positional error increases, like in urban
canyons or other conditions that provide a poor fix.

I would be interested in looking at what you have accomplished, but I
think this is an excellent GSoC project.

-Steve

On 2/16/2012 12:52 AM, Venkatesh Raghavan 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

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)

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.

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-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

Message: 5
Date: Thu, 16 Feb 2012 11:17:50 -0500
From: Stephen Woodbridge <woodbri@swoodbridge.com>
Subject: Re: [pgrouting-users] Code tidy up?
To: pgrouting-users@lists.osgeo.org
Message-ID: <4F3D2C2E.2010101@swoodbridge.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

Hi Dave,

These are all items on the we need to do this list and most of them have
tickets open. Daniel and I are buried in project work and our developer
Anton, has moved on to other stuff. So we are looking for a developer or
someone that is interested in working with us to tackle any of these tasks.

I understand you frustration, in the past I wrote my own set of standard
wrapper functions because the existing one was somewhat random. I had
planned to generalize them and contribute them, but I never got the time
to do that.

We definitely need a test suit. The chaos that we current have with
shooting star is the result of not having one. Things got released
without any formal testing.

I don’t know if you have had a chance to look at git/github but if you
are working on any of these pieces, it would be nice if you cloned the
pgrouting repository and checked all you changes into that clone, then
it would be easy for us to pull and merge your changes int he future.

If you want to discuss changes before you make them, I would suggest
moving the discussion over to the dev list and I will help you out
there. I hope to have time in march to pull some of these isues together.

Thank you for your thoughts and suggestions, I fully support them.

Best regards,
-Steve

On 2/16/2012 2:55 AM, Dave Potts wrote:

Hi list

Is there ever going to be a tidy up off the code associated with the demos
of the pgr functions?

In some cases you have to set the cost field to the value length.
In some cases you have to set the primary key to id
Some methods allow you to list the reverse_cost.
For the traveling sales man you have to include a 2nd undocumented table

Please note I am not suggesting a total rewrite off the code, just a tidy
up, a bit of renaming, tidying up the api, better documentation.

Something like a common interface

e.g.

xxxx('table_name,cost_field,reverse_cost_field,method_specfic_stuff)

It might also help if we had a standard network for testing purpose and a
list of expected results.

Currently I find it very hard to program up a solution for pgr_route
without knowning what the correct results should be. If I had a test
database, it would make life easier.

Having test data might cut down on the number of questions that are being
asked on the list.

Dave.

Pgrouting-users mailing list
Pgrouting-users@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-users

End of Pgrouting-users Digest, Vol 41, Issue 18

–

■□■□■□■□■□■□■□■□■
Free and Open Source Software for Geospatial
GIS Laboratory
Osaka City University 大阪市立大学
Sittichai Choosumrong
TEL +81-90-6558-8559
■□■□■□■□■□■□■□■□■

Stephen_Woodbridge1 · February 16, 2012, 9:34pm

On 2/16/2012 2:46 PM, sittichai choosumrong wrote:

Dear all,

First of all I would like to thank you Prof.Venkatesh Raghavan to
introduce me again to this mailing list.

About using AHP with pgRouting, I was started using AHP for assign a
priority weigth to the elements that depending on their perceived
relative importance for computing route result.
For example, If we need to find the route from start point to the
destination point such as hospital in case of emergency route. The
elements were used for a judgments are Distance, Speed limit, Road
width, Road type, Junction delay, etc. (If we first thinking only about
the road condition). Then, from AHP analysis we can get the priority
weights values like this;

------------------------------------------------
Criteria | Priority (%)
-----------------------------------------------
| distance | 15.89%
| Speel limit | 8.82%
| Road width | 4.83%
| Road type | 6.78%
| Junction delay | 12.88%
| .... | ....
---------------------------------------------------
| Sum | 100%

Next step, I need to integrate this values with road netwrok attribute
data to compute the minimum cost for a route result.

Any ideas how to do this process?

Best regards,
Sittichai

Hi Sittichai,

In general when dealing with graph algorithm you have a cost associated with traversing an edge or possible a node. So in your example above, the problem becomes trivial is you can unify you analysis into a common denominator like time.

So the cost to traverse an edge could be represented as time and then all you have to do is convert your attributes into an equivalent impact in seconds.

cost = distance/speed + junction delay + etc

you reference speed limit, but what you really want to know is what is the average speed at the time you plan to take the route. If you have traffic feed data or historical speed-by-time data this might be useful.

Road width and road type are again trying to assess some average speed, or whether or not the vehicle in use is classed to use that road.

Since the graph edges are passed to the solver via a query, you can construct a complex query the joins multiple tables and dynamically computes the edge weights. If You have multiple destinations, then these can all get extracted and you can add the additional analysis of the end conditions to the various destination drive times.

So think in terms of some unified cost function that returns a number that can be used as a cost. The only condition is that any two edges that get the same cost from your function will have equal weights in the solution.

Hope this helps,
-Steve

PS: Please trim excess text if you reply from a digest.

[pgrouting-users] Re:Some ideas for upcoming GSoC

Criteria | Priority (%)

| distance | 15.89%
| Speel limit | 8.82%
| Road width | 4.83%
| Road type | 6.78%
| Junction delay | 12.88%
| … | …
| … | …

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting

Dave.

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting

[pgrouting-users] Re:Some ideas for upcoming GSoC

Criteria | Priority (%)

| distance | 15.89% | Speel limit | 8.82% | Road width | 4.83% | Road type | 6.78% | Junction delay | 12.88% | … | … | … | …

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help with the WPS implementation for SORouting

Dave.

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help with the WPS implementation for SORouting

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help with the WPS implementation for SORouting

| distance | 15.89%
| Speel limit | 8.82%
| Road width | 4.83%
| Road type | 6.78%
| Junction delay | 12.88%
| … | …
| … | …

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting

P.S. Also Cc to ZOO-PSC since there may be some mentors there to help
with the WPS implementation for SORouting