[Routing] [OSM-dev] pre-compute routing

[Marcus Wolschon - Wolschon Softwaredesign]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

- -----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Robert (Jamie) Munro schrieb:
> I think we only need to store the first one. The second one is the same
> as the route from that node to the destination. I.e. if the route is
> A->B->C->D, then we just need to store A->D=B, then lookup B->D=C, then
> C->D=D.
>
> In many, probably most, cases, the next node to go to will be the same
> no matter which type of route you are taking, so we only need to store
> different routes for different types of route when they actually differ.

So you would
a: still calculate O(N^2) routes (for very very large N)
and
b: find the longest-common-subsequence.

a) is hard because of the large N and thus incredibly large N^2.
b) is NP-complete if solved for a variable number of routes
but polynomial for a fixed number using dynamic programming.

The question remains:
Does this make sense and is not simple
on-demand-routing far too fast?


- - ---------- Offer:

I will go on vacation for a few days.
When I am back, I will implement the web-UI for
Traveling-Salesman and put it up for public use.

You can then see if the speed of an on-demand-router
is enough for you or if such a costly optimization is
really called for.

Other optimizations, like
A)
  hirarchical routing:
1: route on the graph of motorways first,
1: then on everything down to tertiary,
3: then on service-roads, tracks,...
  and
b)
  generating a database that has nodes, ways and
  attributes not required for routing collapsed or removed

could go a long way in speeding up routing and would
not only benefit the web-page but also offline-navigation
in a car using less ressources and the same development-effort.

Marcus
- - --
 Marcus Wolschon
 Wolschon Softwaredesign und Beratung
 UStID: DE238951181
 Marcus at Wolschon.biz
 +49 177/6272871 (m-a-r-c-u-s-1)
- -----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHAjEvf1hPnk3Z0cQRAhOVAKCVyLRYaacpuakeFURrm25R6+r3rACg1KT+
81AYYl2Wo+1XBg2lxOhig80=
=DYno
- -----END PGP SIGNATURE-----

- --
 Marcus Wolschon
 Wolschon Softwaredesign und Beratung
 UStID: DE238951181
 Marcus at Wolschon.biz
 +49 177/6272871 (m-a-r-c-u-s-1)
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHAjFnf1hPnk3Z0cQRAnqOAKDHayL9fwHZIc9V8uJ2nfIurRnicgCeMwPD
AYYgkipWNDr380Lto52aDCY=
=Qijh
-----END PGP SIGNATURE-----