[pgrouting-users] TSP and how to contribute

[Stephen Woodbridge]

On 1/14/2011 3:15 AM, Emre Koc wrote:
> Steve,
>
> To trick the algorithm can't we switch reverse_cost and cost values in
> driving directions ? I think that if driving directions can output a
> connected road network that will both cover your 5 min roads to store
> and fire-station reachability. Am I wrong about this ?

Yes this might work for the way that pgRouting has implemented this. 
This only works because the graph is built with edges in both direction. 
I you eliminated the anti-oneway edges when the graph was built, this 
would not work. When I implemented, in another program, something 
similar I did not have edges with high weights on them to indicate a one 
way street. My graph was a directed graph and I just did not include the 
edge at all. If you have a lot of oneway streets like in a city, then 
you get a smaller graph to start with. I have also seen pgRouting 
actually route the wrong way down one of these high cost edges. I think 
I would rather it just fail than to silently do that.

-Steve

> /emre
>
>
> On Fri, Jan 14, 2011 at 8:01 AM, Stephen Woodbridge
> <woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>> wrote:
>
>     On 1/13/2011 10:15 PM, Daniel Kastl wrote:
>
>
>
>         2011/1/14 Stephen Woodbridge <woodbri at swoodbridge.com
>         <mailto:woodbri at swoodbridge.com>
>         <mailto:woodbri at swoodbridge.com <mailto:woodbri at swoodbridge.com>>>
>
>
>             On 1/13/2011 3:18 AM, Emre Koc wrote:
>
>                 Hello,
>
>                 I am intereted in using TSP functions of pgRouting but I
>                 couldn't find
>                 any tutorial or documentation on it. Does anyone have a
>                 documentation
>                 for TSP functions ? I am using Dijkstra with a custom
>         query. Is it
>                 possible to use TSP with custom query?
>
>                 Also I want to extend pgRouting functionality by
>         calculating a
>                 distance
>                 network from a point or towards a point. How can I
>         integrate my
>                 source
>                 to pgRouting ?
>
>
>             Yes, I asked for this functionality also. I did a little
>         research
>             into how to do this. I seems that in boost you need to
>         reverse the
>             graph. We already build the graph but would need to then add
>         a step
>             to reverse it to change the sense of direction. I think this
>         is the
>             function that is needed:
>         http://www.systomath.com/include/Boost-1_35/libs/graph/doc/reverse_graph.html
>
>
>         Maybe someone wants to add an RFC for that
>         (http://www.pgrouting.org/rfc/index.html).
>         Soon there will be GSoC and students will be looking for project
>         ideas.
>
>         Recently "SRC" (don't know the real name) wrote some
>         bidirectional patch
>         for pgRouting. I applied the patch to my fork at GitHub called
>         "Two-Way
>         A-Star": https://github.com/dkastl/pgrouting
>         Is this somehow related?
>
>
>     Daniel,
>
>     This might apply to this problem, but I have not looked at what he
>     did or how it is implemented. On an undirected graph routing from
>     A->B is the same as B->A, on a directed graph this does not have to
>     be the case.
>
>     For bi-directional routing on a directed graph, you need to reverse
>     the graph or otherwise trick the algorithm when it is routing FROM
>     the destination toward the start. At the destination you need to ask
>     what node could I have come FROM to get here, but at the start you
>     have to ask what nodes can I go TO from here. So you need a graph
>     and a reverse graph or you need to maintain enough a list of
>     outgoing nodes AND a separate list of incoming nodes.
>
>     For drive time analysis, you might want to compute what is the area
>     covered by consumers that are willing to drive 20 min to get to my
>     store located "here". So "here" is the destination. But if you are a
>     municipal planner, you might want to know what coverage area do my
>     fire-stations have with a drive time of 5 mins or 10 mins. In this
>     case the fire-station is the start point.
>
>     For undirected graphs, there is no difference.
>
>     -Steve
>
>     _______________________________________________
>     Pgrouting-users mailing list
>     Pgrouting-users at lists.osgeo.org <mailto: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