[pgrouting-users] TSP and how to contribute

[Emre Koc]

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 ?

/emre


On Fri, Jan 14, 2011 at 8:01 AM, Stephen Woodbridge <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>>
>>
>>
>>    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
> http://lists.osgeo.org/mailman/listinfo/pgrouting-users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/pgrouting-users/attachments/20110114/42b15d17/attachment-0001.html