Supercomputing for the Multi-Driver Routing

Student: Zeyang Ye (Stony Brook University)
Supervisor: Yuefan Deng (Stony Brook University)

Abstract: Supercomputing 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.

ACM-SRC Semi-Finalist: no

Poster: PDF
Poster Summary: pdf
Reproducibility Description Appendix: PDF


Back to Poster Archive Listing