[Routing] Routing algorithms

Brandon Martin-Anderson badhill at gmail.com
Thu Nov 8 17:44:37 GMT 2007


Sorry I didn't make it clear but these are titles of academic papers pretty
easily findable on Google Scholar.

-B

On Nov 8, 2007 12:43 PM, Brandon Martin-Anderson <badhill at gmail.com> wrote:

> 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!)
>
> 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:
>
> Heirarchical Optimizations of Optimal Path Finding for Transportation
> Applications
>    1996 foundational text outlining HEPV (heirarchical encoded path
> views).
>    See: ref 13 for algorithm on graph partitioning, multi-levels
>
> Heirarchical Encoded Path Views...
>    1998 expansion of (1) much more readable, prettier graphs
>
> A Performance Analysis...
>    1997 analysis of a 2-level heirarchical graph, with 10x as many nodes
> in the test graph as (1)
>
> Approximate Shortest-path Algorithms
>     post-2002. Proposes a "Network Tree Model" as an alternative to HEPV
> for extremely large networks (millions of nodes). Results are not optimal.
>
> Approximating Shortest-Paths in Large Scale Networks
>     1998 proposition of a non-optimal heirarchical graph system
>
> An efficeint path computation model for heirarchically structured...
>     1998/2000 proposed heirarchical search method uses much less space
> than HEPV. Touches base on storage methods, recommends [ 40<http://scholar.google.com/scholar?hl=en&lr=&q=CCAM%253A+shekhar&btnG=Search>].
> Also As this is a major heirarchical paper search things that reference it<http://scholar.google.com/scholar?hl=en&lr=&cites=5835360768894073554>.
> One 2006 paper on speed-up has been added.
>
> Combining Speed-up Techniques
>     shortest path for trains and busses: see
>     "FATES: Finding A Time dEpendent Shortest path"
>
> I have a little more and I'll elaborate when I get some time.
>
> -B
>
>
>
> On Nov 8, 2007 12:21 PM, Gerald A <geraldablists at gmail.com > wrote:
>
> > I'm a relative newbie in the mapping domain, so this might be old news
> > to some,
> > but it caught my eye:
> > http://googleblog.blogspot.com/2007/11/road-to-better-path-finding.html
> >
> > While we don't have access to some of the resources of Google, if we
> > can use what they've learned to simplify or speed up our routing, that
> > can't hurt, can it? (I'm sure they haven't thought about things like
> > bike specific routing, but if they are discussing general routing
> > techniques then that should still help).
> >
> > Gerald.
> >
> > _______________________________________________
> > Routing mailing list
> > Routing at openstreetmap.org
> > http://lists.openstreetmap.org/cgi-bin/mailman/listinfo/routing
> >
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/routing/attachments/20071108/524751eb/attachment.html>


More information about the Routing mailing list