# [Routing] Routing algorithms

Thu Nov 8 17:43:53 GMT 2007

```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 [
Also As this is a major heirarchical paper search things that
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:
>
> 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/002fda48/attachment.html>
```