[pgrouting-users] TSP and how to contribute

[Stephen Woodbridge]

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