[pgrouting-dev] Re: pgrouting-dev Digest, Vol 19, Issue 1

Ashraf_Hossain · January 10, 2012, 6:34pm

Hi Steve,
I am going through this paper and I have collected several papers on this topics.
Regards
Roni

On Tue, Jan 10, 2012 at 11:00 PM, <pgrouting-dev-request@lists.osgeo.org> wrote:

Send pgrouting-dev mailing list submissions to
pgrouting-dev@lists.osgeo.org

To subscribe or unsubscribe via the World Wide Web, visit
http://lists.osgeo.org/mailman/listinfo/pgrouting-dev
or, via email, send a message with subject or body ‘help’ to
pgrouting-dev-request@lists.osgeo.org

You can reach the person managing the list at
pgrouting-dev-owner@lists.osgeo.org

When replying, please edit your Subject line so it is more specific
than “Re: Contents of pgrouting-dev digest…”

Today’s Topics:

Alternative paths (Stephen Woodbridge)

Re: Alternative paths (Daniel Kastl)

Re: Alternative paths (Stephen Woodbridge)

Message: 1
Date: Mon, 09 Jan 2012 19:07:13 -0500
From: Stephen Woodbridge <woodbri@swoodbridge.com>
Subject: [pgrouting-dev] Alternative paths
To: pgRouting Dev List <pgrouting-dev@lists.osgeo.org>, Ashraf
Hossain <ashraf10bd@gmail.com>
Message-ID: <4F0B8131.9030302@swoodbridge.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

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

Message: 2
Date: Tue, 10 Jan 2012 11:14:43 +0900
From: Daniel Kastl <daniel@georepublic.de>
Subject: Re: [pgrouting-dev] Alternative paths
To: pgRouting developers mailing list <pgrouting-dev@lists.osgeo.org>
Cc: Ashraf Hossain <ashraf10bd@gmail.com>
Message-ID:
<CABXBSH_wAuftnSMzAaiZDrtnNXVGQbidnY5vd0RCQ=vBQxer3g@mail.gmail.com>
Content-Type: text/plain; charset=“iso-8859-1”

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<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<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<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de
Web: http://georepublic.de
-------------- next part --------------
An HTML attachment was scrubbed…
URL: http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120110/65ec4e87/attachment-0001.html

Message: 3
Date: Mon, 09 Jan 2012 21:17:04 -0500
From: Stephen Woodbridge <woodbri@swoodbridge.com>
Subject: Re: [pgrouting-dev] Alternative paths
To: pgRouting developers mailing list <pgrouting-dev@lists.osgeo.org>
Cc: Ashraf Hossain <ashraf10bd@gmail.com>
Message-ID: <4F0B9FA0.2030906@swoodbridge.com>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed

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](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>

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>

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](mailto:pgrouting-dev@lists.osgeo.org)
http://lists.osgeo.org/ mailman/listinfo/pgrouting-dev
<http://lists.osgeo.org/mailman/listinfo/pgrouting-dev>

–
Georepublic UG & Georepublic Japan
eMail: daniel.kastl@georepublic.de mailto:[daniel.kastl@georepublic.de](mailto:daniel.kastl@georepublic.de)
Web: http://georepublic.de <http://georepublic.de/>

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

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

End of pgrouting-dev Digest, Vol 19, Issue 1