[pgrouting-dev] Alternative paths

pgRouting pgrouting-dev
1

So the question about alternative paths came up on the users list and this seems like a good paper discussing how to implement that.

http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf

This would be a cool GSoC project or just something someone might want to tackle.

Did Jay or someone implement k-shortest paths? I see we have a ticket for this some maybe not:

https://github.com/pgRouting/pgrouting/issues/11

-Steve

2

On Tue, Jan 10, 2012 at 9:07 AM, Stephen Woodbridge <woodbri@swoodbridge.com> wrote:

So the question about alternative paths came up on the users list and this seems like a good paper discussing how to implement that.

http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf

This would be a cool GSoC project or just something someone might want to tackle.

Did Jay or someone implement k-shortest paths? I see we have a ticket for this some maybe not:

https://github.com/pgRouting/pgrouting/issues/11

Hi Steve,

This hasn’t been done yet. And it could be interesting project for GSoC, I agree.

It’s also not clear to me, if k-shortest path doesn’t mean often just a tiny permutation in the path. This wouldn’t be really what we want, right?
I guess, that alternate routes as Google provides them are probably calculated with different costs.

Daniel

-Steve

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

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de

3

On 1/9/2012 9:14 PM, Daniel Kastl wrote:

On Tue, Jan 10, 2012 at 9:07 AM, Stephen Woodbridge
<woodbri@swoodbridge.com <mailto:woodbri@swoodbridge.com>> wrote:

    So the question about alternative paths came up on the users list
    and this seems like a good paper discussing how to implement that.

    http://algo2.iti.kit.edu/ download/altgraph_tapas_ extended.pdf
    <http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf&gt;

    This would be a cool GSoC project or just something someone might
    want to tackle.

    Did Jay or someone implement k-shortest paths? I see we have a
    ticket for this some maybe not:

    https://github.com/pgRouting/ pgrouting/issues/11
    <https://github.com/pgRouting/pgrouting/issues/11&gt;

Hi Steve,

This hasn't been done yet. And it could be interesting project for GSoC,
I agree.

It's also not clear to me, if k-shortest path doesn't mean often just a
tiny permutation in the path. This wouldn't be really what we want, right?
I guess, that alternate routes as Google provides them are probably
calculated with different costs.

Correct, I would agree the k-shortest path just does little permutations, so read the pdf link above. That is what we need for what google is doing.

-Steve

Daniel

    -Steve
    ______________________________ _________________
    pgrouting-dev mailing list
    pgrouting-dev@lists.osgeo.org <mailto:pgrouting-dev@lists.osgeo.org>
    http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
    <http://lists.osgeo.org/mailman/listinfo/pgrouting-dev&gt;

--
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de <mailto:daniel.kastl@georepublic.de>
Web: http://georepublic.de/&gt;

_______________________________________________
pgrouting-dev mailing list
pgrouting-dev@lists.osgeo.org
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev