[OSRM-talk] routing with GPUs or mapD

[Bjorn Madsen]

That was a quick response...! :-) Thanks;

Well - if anyone else is working on this - experimental or not - then
please keep me posted as I'm interested in what you find.

On Thu, Mar 31, 2016 at 11:06 PM, Daniel Patterson <daniel at mapbox.com>
wrote:

> Bjorn,
>
>   This paper outlines one approach that is very fast:
>
>   http://www.cs.princeton.edu/~rwerneck/papers/DKW14-crp-gpu.pdf
>
>   and there are others:
>
>
> https://pdfs.semanticscholar.org/0c17/805ab324006d40a8dd37d3550815824498fb.pdf
>   http://research.ijcaonline.org/volume72/number18/pxc3889386.pdf
>   http://public.lanl.gov/sunil/pubs/ipdps14.pdf
>
>   The Contraction Heirachy approach that OSRM uses is not all that
> amenable to GPU acceleration unfortunately.
>
> daniel
>
> On Mar 31, 2016, at 2:50 PM, Bjorn Madsen <bm at multiagenttechnology.com>
> wrote:
>
> Brief introduction:
> The difference between (1) routing + overlaying congestion data and (2)
> routing with congestion data is that the former simply provides a route
> which is extended with the delay given by the reduced travel speed inferred
> from the congestion (option 1). We can do that easily today.
>
> Routing with congestion data (option 2) requires that the quickest path is
> computed based on the congestion currently and the predicted congestion in
> the near future. This results in completely different routes as the road
> network velocity drops, whereby the fastest route (often) ends up being the
> shortest, though junctions with accidents can generate minor detours. The
> shift between the two modes of computation, is not linear, so walking the
> graph is necessary in most cases. However as the walks could be performed
> in concurrent lock-steps, it seems feasible to push such kind of workload
> onto GPUs.
>
> Question:
> I've been looking at mapD for a while and wondered whether it would be the
> better alternative solution for routing that may include dynamic congestion
> data into the routing process. Is anyone out there working with similar
> thoughts - or, on using GPUs in the process?
>
> Kind regards
>
> --
> Bjorn Madsen
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>
>
> _______________________________________________
> OSRM-talk mailing list
> OSRM-talk at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/osrm-talk
>
>


-- 
Bjorn Madsen
Director, Global Operations

Multi-Agent Technology Ltd.
Bessemer Drive,
Stevenage,
SG1 2DX

bm at multiagenttechnology.com
Mobile: +44 779 20 307 20
Main Office: +44 1438 310 035
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160401/bb603251/attachment.html>