<html><head><meta http-equiv="Content-Type" content="text/html charset=us-ascii"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space;" class="">Bjorn,<div class=""><br class=""></div><div class=""> This paper outlines one approach that is very fast:</div><div class=""><br class=""></div><div class=""> <a href="http://www.cs.princeton.edu/~rwerneck/papers/DKW14-crp-gpu.pdf" class="">http://www.cs.princeton.edu/~rwerneck/papers/DKW14-crp-gpu.pdf</a> </div><div class=""><br class=""></div><div class=""> and there are others:</div><div class=""><br class=""></div><div class=""> <a href="https://pdfs.semanticscholar.org/0c17/805ab324006d40a8dd37d3550815824498fb.pdf" class="">https://pdfs.semanticscholar.org/0c17/805ab324006d40a8dd37d3550815824498fb.pdf</a></div><div class=""> <a href="http://research.ijcaonline.org/volume72/number18/pxc3889386.pdf" class="">http://research.ijcaonline.org/volume72/number18/pxc3889386.pdf</a></div><div class=""> <a href="http://public.lanl.gov/sunil/pubs/ipdps14.pdf" class="">http://public.lanl.gov/sunil/pubs/ipdps14.pdf</a></div><div class=""><br class=""></div><div class=""> The Contraction Heirachy approach that OSRM uses is not all that amenable to GPU acceleration unfortunately.</div><div class=""><br class=""></div><div class="">daniel</div><div class=""><br class=""><div><blockquote type="cite" class=""><div class="">On Mar 31, 2016, at 2:50 PM, Bjorn Madsen <<a href="mailto:bm@multiagenttechnology.com" class="">bm@multiagenttechnology.com</a>> wrote:</div><br class="Apple-interchange-newline"><div class=""><div dir="ltr" class=""><div class="">Brief introduction:</div><div class="">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.<br class=""></div><div class=""><br class=""></div><div class="">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.</div><div class=""><br class=""></div><div class="">Question:</div><div class=""><div class="">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?</div></div><div class=""><br class=""></div><div class="">Kind regards<br class=""></div><div class=""><div class=""><br class=""></div>-- <br class=""><div class="gmail_signature"><div dir="ltr" class=""><div dir="ltr" class=""><div dir="ltr" class=""><div style="font-size:small" class="">Bjorn Madsen</div><div style="font-size:small" class=""><br class=""></div></div></div></div></div>
</div></div>
_______________________________________________<br class="">OSRM-talk mailing list<br class=""><a href="mailto:OSRM-talk@openstreetmap.org" class="">OSRM-talk@openstreetmap.org</a><br class="">https://lists.openstreetmap.org/listinfo/osrm-talk<br class=""></div></blockquote></div><br class=""></div></body></html>