Shortest path (SP) computation in Road Networks is the building block for various real-life applications such as the vehicle navigation, logistic transportation, carpooling, take-out delivery, etc. Over the decades, many SP algorithms have been proposed to improve the computation efficiency. However, they all represent a road network with one weighted graph. Our recent research and experimental study suggest that the road network characteristics (such as the topology and functional area distribution) have great effect on the performance of SP computation. This project aims to observe and explore this effect through comprehensive experimental study on road networks with different characteristics, which can further provide more insights to novel SP algorithms or other graph algorithm design in Road Networks.
Research tasks
We will carry out this project by implementing the following tasks step by step:
- Familiarize with the well-known SP algorithms like Dijkstra’s algorithm, Pruned Landmark Labeling [1] and Hierarchical 2-Hop Index [2].
- Obtain graph data and characteristics of different Road Networks in OpenStreetMap
- Conduct comprehensive experimental study and analyze the results
More potential research about novel Road Network Partition method design beneficial to the downstream graph-related algorithms can be further explored after this project.
Reference
[1] Akiba, Takuya, Yoichi Iwata, and Yuichi Yoshida. “Fast exact shortest-path distance queries on large networks by pruned landmark labeling.” In Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data, pp. 349-360. 2013.
[2] Ouyang, Dian, Lu Qin, Lijun Chang, Xuemin Lin, Ying Zhang, and Qing Zhu. “When hierarchy meets 2-hop-labeling: Efficient shortest distance queries on road networks.” In Proceedings of the 2018 International Conference on Management of Data, pp. 709-724. 2018.
[3] Sun, Fengze, Jianzhong Qi, Yanchuan Chang, Xiaoliang Fan, Shanika Karunasekera, and Egemen Tanin. “Urban Region Representation Learning with Attentive Fusion.” ICDE 2024.
Requirement
Background and experience in data structure, graph theory or graph-related algorithms. Programming experience in C++ is essential.
Contact
If you are interested in this project, contact Dr. Mengxuan Zhang.