[Routing] A-Star meet-in-the-middle

[Jon Bright]

Hi Nic,

Nic Roets wrote:
> 
> * Rewrite in C and use hash tables.

While we're still at the stage of working out which algorithms to use 
how, I much prefer using ruby/similar.  Prototyping is far easier.  When 
it's clear what's best, a C implementation may be worthwhile.

> * Change the A* heuristic from sqrt(sqr(dx)+sqr(dy)) to 1.1*sqrt(...)
> or larger. This acknowledges that roads the shortest route between two
> points is usually 10% longer than a straight route. And if you're
> wrong the route may be slightly suboptimal, who cares.

Tried it.  1.1 is too high, you easily get suboptimal routes.  I then 
tried a similar approach:

distance > 100km -> distance*1.2
distance > 50km  -> distance*1.1
distance > 10km  -> distance*1.05
distance <= 10km -> distance

I tried this with varying factors/limits.  Depending on the parameters, 
the result was (in general terms) that it produced suboptimal routes or 
that it didn't help too much with speed.  I didn't find a happy medium 
for my test routes.

> (Why aren't we discussing the important issues, like adding a penalty
> to right turns at intersections... ?)

Because we didn't yet work out which algorithm to use to get acceptable 
speed on long routes.  Once you've got this and solved the 
less-knotty-but-still-not-trivial problem of whether you want to 
penalise right (UK) or left (Europe, US) turns, actual implementation 
should be simple.

--
Jon