Hi Steve,<br>I am going through this paper and I have collected several papers on this topics.<br>Regards<br>Roni<br><br><div class="gmail_quote">On Tue, Jan 10, 2012 at 11:00 PM, <span dir="ltr"><<a href="mailto:pgrouting-dev-request@lists.osgeo.org">pgrouting-dev-request@lists.osgeo.org</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Send pgrouting-dev mailing list submissions to<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<br>
To subscribe or unsubscribe via the World Wide Web, visit<br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
or, via email, send a message with subject or body 'help' to<br>
<a href="mailto:pgrouting-dev-request@lists.osgeo.org">pgrouting-dev-request@lists.osgeo.org</a><br>
<br>
You can reach the person managing the list at<br>
<a href="mailto:pgrouting-dev-owner@lists.osgeo.org">pgrouting-dev-owner@lists.osgeo.org</a><br>
<br>
When replying, please edit your Subject line so it is more specific<br>
than "Re: Contents of pgrouting-dev digest..."<br>
<br>
<br>
Today's Topics:<br>
<br>
1. Alternative paths (Stephen Woodbridge)<br>
2. Re: Alternative paths (Daniel Kastl)<br>
3. Re: Alternative paths (Stephen Woodbridge)<br>
<br>
<br>
----------------------------------------------------------------------<br>
<br>
Message: 1<br>
Date: Mon, 09 Jan 2012 19:07:13 -0500<br>
From: Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>><br>
Subject: [pgrouting-dev] Alternative paths<br>
To: pgRouting Dev List <<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a>>, Ashraf<br>
Hossain <<a href="mailto:ashraf10bd@gmail.com">ashraf10bd@gmail.com</a>><br>
Message-ID: <<a href="mailto:4F0B8131.9030302@swoodbridge.com">4F0B8131.9030302@swoodbridge.com</a>><br>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed<br>
<br>
So the question about alternative paths came up on the users list and<br>
this seems like a good paper discussing how to implement that.<br>
<br>
<a href="http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf" target="_blank">http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf</a><br>
<br>
This would be a cool GSoC project or just something someone might want<br>
to tackle.<br>
<br>
Did Jay or someone implement k-shortest paths? I see we have a ticket<br>
for this some maybe not:<br>
<br>
<a href="https://github.com/pgRouting/pgrouting/issues/11" target="_blank">https://github.com/pgRouting/pgrouting/issues/11</a><br>
<br>
-Steve<br>
<br>
<br>
------------------------------<br>
<br>
Message: 2<br>
Date: Tue, 10 Jan 2012 11:14:43 +0900<br>
From: Daniel Kastl <<a href="mailto:daniel@georepublic.de">daniel@georepublic.de</a>><br>
Subject: Re: [pgrouting-dev] Alternative paths<br>
To: pgRouting developers mailing list <<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a>><br>
Cc: Ashraf Hossain <<a href="mailto:ashraf10bd@gmail.com">ashraf10bd@gmail.com</a>><br>
Message-ID:<br>
<CABXBSH_wAuftnSMzAaiZDrtnNXVGQbidnY5vd0RCQ=<a href="mailto:vBQxer3g@mail.gmail.com">vBQxer3g@mail.gmail.com</a>><br>
Content-Type: text/plain; charset="iso-8859-1"<br>
<br>
On Tue, Jan 10, 2012 at 9:07 AM, Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a><br>
> wrote:<br>
<br>
> So the question about alternative paths came up on the users list and this<br>
> seems like a good paper discussing how to implement that.<br>
><br>
> <a href="http://algo2.iti.kit.edu/**download/altgraph_tapas_**extended.pdf" target="_blank">http://algo2.iti.kit.edu/**download/altgraph_tapas_**extended.pdf</a><<a href="http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf" target="_blank">http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf</a>><br>
><br>
> This would be a cool GSoC project or just something someone might want to<br>
> tackle.<br>
><br>
> Did Jay or someone implement k-shortest paths? I see we have a ticket for<br>
> this some maybe not:<br>
><br>
> <a href="https://github.com/pgRouting/**pgrouting/issues/11" target="_blank">https://github.com/pgRouting/**pgrouting/issues/11</a><<a href="https://github.com/pgRouting/pgrouting/issues/11" target="_blank">https://github.com/pgRouting/pgrouting/issues/11</a>><br>
<br>
<br>
<br>
Hi Steve,<br>
<br>
This hasn't been done yet. And it could be interesting project for GSoC, I<br>
agree.<br>
<br>
It's also not clear to me, if k-shortest path doesn't mean often just a<br>
tiny permutation in the path. This wouldn't be really what we want, right?<br>
I guess, that alternate routes as Google provides them are probably<br>
calculated with different costs.<br>
<br>
Daniel<br>
<br>
<br>
<br>
<br>
<br>
<br>
<br>
><br>
><br>
> -Steve<br>
> ______________________________**_________________<br>
> pgrouting-dev mailing list<br>
> <a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/**mailman/listinfo/pgrouting-dev</a><<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a>><br>
><br>
<br>
<br>
<br>
--<br>
Georepublic UG & Georepublic Japan<br>
eMail: <a href="mailto:daniel.kastl@georepublic.de">daniel.kastl@georepublic.de</a><br>
Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a><br>
-------------- next part --------------<br>
An HTML attachment was scrubbed...<br>
URL: <a href="http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120110/65ec4e87/attachment-0001.html" target="_blank">http://lists.osgeo.org/pipermail/pgrouting-dev/attachments/20120110/65ec4e87/attachment-0001.html</a><br>
<br>
------------------------------<br>
<br>
Message: 3<br>
Date: Mon, 09 Jan 2012 21:17:04 -0500<br>
From: Stephen Woodbridge <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>><br>
Subject: Re: [pgrouting-dev] Alternative paths<br>
To: pgRouting developers mailing list <<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a>><br>
Cc: Ashraf Hossain <<a href="mailto:ashraf10bd@gmail.com">ashraf10bd@gmail.com</a>><br>
Message-ID: <<a href="mailto:4F0B9FA0.2030906@swoodbridge.com">4F0B9FA0.2030906@swoodbridge.com</a>><br>
Content-Type: text/plain; charset=ISO-8859-1; format=flowed<br>
<br>
On 1/9/2012 9:14 PM, Daniel Kastl wrote:<br>
><br>
><br>
> On Tue, Jan 10, 2012 at 9:07 AM, Stephen Woodbridge<br>
> <<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a> <mailto:<a href="mailto:woodbri@swoodbridge.com">woodbri@swoodbridge.com</a>>> wrote:<br>
><br>
> So the question about alternative paths came up on the users list<br>
> and this seems like a good paper discussing how to implement that.<br>
><br>
> <a href="http://algo2.iti.kit.edu/" target="_blank">http://algo2.iti.kit.edu/</a> download/altgraph_tapas_ extended.pdf<br>
> <<a href="http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf" target="_blank">http://algo2.iti.kit.edu/download/altgraph_tapas_extended.pdf</a>><br>
><br>
> This would be a cool GSoC project or just something someone might<br>
> want to tackle.<br>
><br>
> Did Jay or someone implement k-shortest paths? I see we have a<br>
> ticket for this some maybe not:<br>
><br>
> <a href="https://github.com/pgRouting/" target="_blank">https://github.com/pgRouting/</a> pgrouting/issues/11<br>
> <<a href="https://github.com/pgRouting/pgrouting/issues/11" target="_blank">https://github.com/pgRouting/pgrouting/issues/11</a>><br>
><br>
><br>
><br>
> Hi Steve,<br>
><br>
> This hasn't been done yet. And it could be interesting project for GSoC,<br>
> I agree.<br>
><br>
> It's also not clear to me, if k-shortest path doesn't mean often just a<br>
> tiny permutation in the path. This wouldn't be really what we want, right?<br>
> I guess, that alternate routes as Google provides them are probably<br>
> calculated with different costs.<br>
<br>
Correct, I would agree the k-shortest path just does little<br>
permutations, so read the pdf link above. That is what we need for what<br>
google is doing.<br>
<br>
-Steve<br>
<br>
> Daniel<br>
><br>
><br>
><br>
><br>
><br>
><br>
><br>
> -Steve<br>
> ______________________________ _________________<br>
> pgrouting-dev mailing list<br>
> <a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a> <mailto:<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a>><br>
> <a href="http://lists.osgeo.org/" target="_blank">http://lists.osgeo.org/</a> mailman/listinfo/pgrouting-dev<br>
> <<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a>><br>
><br>
><br>
><br>
><br>
> --<br>
> Georepublic UG & Georepublic Japan<br>
> eMail: <a href="mailto:daniel.kastl@georepublic.de">daniel.kastl@georepublic.de</a> <mailto:<a href="mailto:daniel.kastl@georepublic.de">daniel.kastl@georepublic.de</a>><br>
> Web: <a href="http://georepublic.de" target="_blank">http://georepublic.de</a> <<a href="http://georepublic.de/" target="_blank">http://georepublic.de/</a>><br>
><br>
><br>
> _______________________________________________<br>
> pgrouting-dev mailing list<br>
> <a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
> <a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
<br>
------------------------------<br>
<br>
_______________________________________________<br>
pgrouting-dev mailing list<br>
<a href="mailto:pgrouting-dev@lists.osgeo.org">pgrouting-dev@lists.osgeo.org</a><br>
<a href="http://lists.osgeo.org/mailman/listinfo/pgrouting-dev" target="_blank">http://lists.osgeo.org/mailman/listinfo/pgrouting-dev</a><br>
<br>
<br>
End of pgrouting-dev Digest, Vol 19, Issue 1<br>
********************************************<br>
</blockquote></div><br>