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

[Stephen Woodbridge]

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.