Oh you better believe Google has thought about things like bike routing: the 'avoid highways' checkbox is their nod to it. But they're a mass-market company and there's no mass-market for bicycle routing (yet!)
<br><br>A year ago I did a bit of research and came up with the following notes on heirarcical encoding for shortest-path approximation on very large graphs, which I strongly suspect is the technology Google has expanded upon to create their system. Here are my a few things I wanted to follow up on, unedited and unordered:
<br><br>Heirarchical Optimizations of Optimal Path Finding for Transportation Applications<br> 1996 foundational text outlining HEPV (heirarchical encoded path views).<br> See: ref 13 for algorithm on <span class="nfakPe">
graph</span> partitioning, multi-levels
<br><br>Heirarchical Encoded Path Views...<br> 1998 expansion of (1) much more readable, prettier graphs<br><br>A Performance Analysis...<br> 1997 analysis of a 2-level heirarchical <span class="nfakPe">graph</span>, with 10x as many nodes in the test
<span class="nfakPe">graph</span> as (1)
<br><br>Approximate Shortest-path Algorithms<br> post-2002. Proposes
a "Network Tree Model" as an alternative to HEPV for extremely large
networks (millions of nodes). Results are not optimal.<br><br>Approximating Shortest-Paths in Large Scale Networks
<br> 1998 proposition of a non-optimal heirarchical <span class="nfakPe">graph</span> system<br><br>An efficeint path computation model for heirarchically structured...<br> 1998/2000 proposed heirarchical search method uses much less space than HEPV. Touches base on storage methods, recommends [
<a href="http://scholar.google.com/scholar?hl=en&lr=&q=CCAM%253A+shekhar&btnG=Search" target="_blank">40</a>]. Also As this is a major heirarchical paper search <a href="http://scholar.google.com/scholar?hl=en&lr=&cites=5835360768894073554" target="_blank">
things that reference it</a>. One 2006 paper on speed-up has been added.<br><br>Combining Speed-up Techniques<br> shortest path for trains and busses: see<br> "FATES: Finding A Time dEpendent Shortest path"
<br><br>I have a little more and I'll elaborate when I get some time.<br><br>-B<br><br><br><div class="gmail_quote">On Nov 8, 2007 12:21 PM, Gerald A <<a href="mailto:geraldablists@gmail.com" target="_blank">geraldablists@gmail.com
</a>> wrote:<br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
I'm a relative newbie in the mapping domain, so this might be old news to some,<br>but it caught my eye:<br><a href="http://googleblog.blogspot.com/2007/11/road-to-better-path-finding.html" target="_blank">http://googleblog.blogspot.com/2007/11/road-to-better-path-finding.html
</a><br><br>While we don't have access to some of the resources of Google, if we<br>can use what they've learned to simplify or speed up our routing, that<br>can't hurt, can it? (I'm sure they haven't thought about things like
<br>bike specific routing, but if they are discussing general routing<br>techniques then that should still help).<br><font color="#888888"><br>Gerald.<br></font><div><div></div><div><br>_______________________________________________
<br>Routing mailing list<br><a href="mailto:Routing@openstreetmap.org" target="_blank">Routing@openstreetmap.org</a><br><a href="http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing" target="_blank">http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
</a><br></div></div></blockquote></div><br>