ACM Student Research Competition
Supercomputing for the Multi-Driver Routing
Event Type
ACM Student Research Competition
Registration Categories
TimeTuesday, November 13th8:30am - 5pm
DescriptionSupercomputing is essential for routing traffic by providing drivers the optimal routes with minimal traveling distances or time. The unique challenges that require supercomputers to overcome are of multiple folds: numerous drivers, massive simultaneous requests, multiple locations, and needs of instant gratifications, etc. We developed two parallel methods, PSAD and PSAD-M, by using domain decomposition and state-mixing techniques. On the same computing platform with 96 cores, for the same problem, our PSAD methods outperform all published benchmarks by over a hundred times, while improving the solution quality. For the same routing problem on 384 cores, our PSAD-M reduced the elapsed time from the unbearable ten minutes to the reasonable 5 seconds, achieving a record-breaking speedup of 170. By providing instant routing solutions that enable online recommendations, our methods break the bottleneck of the widely adopted offline approaches.
Back To Top Button