[OSRM-talk] routing with GPUs or mapD

[Daniel Patterson]

Bjorn,

  This paper outlines one approach that is very fast:

  http://www.cs.princeton.edu/~rwerneck/papers/DKW14-crp-gpu.pdf <http://www.cs.princeton.edu/~rwerneck/papers/DKW14-crp-gpu.pdf>  

  and there are others:

  https://pdfs.semanticscholar.org/0c17/805ab324006d40a8dd37d3550815824498fb.pdf <https://pdfs.semanticscholar.org/0c17/805ab324006d40a8dd37d3550815824498fb.pdf>
  http://research.ijcaonline.org/volume72/number18/pxc3889386.pdf <http://research.ijcaonline.org/volume72/number18/pxc3889386.pdf>
  http://public.lanl.gov/sunil/pubs/ipdps14.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

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstreetmap.org/pipermail/osrm-talk/attachments/20160331/45dbc7ef/attachment.html>