Exploring the Effect of Road Network Characteristics on Shortest Path Computation

Picture of mengxuan-zhang.md Mengxuan Zhang

7 May 2024

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:

  1. Familiarize with the well-known SP algorithms like Dijkstra’s algorithm, Pruned Landmark Labeling [1] and Hierarchical 2-Hop Index [2].
  2. Obtain graph data and characteristics of different Road Networks in OpenStreetMap
  3. 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.

You are on Aboriginal land.

The Australian National University acknowledges, celebrates and pays our respects to the Ngunnawal and Ngambri people of the Canberra region and to all First Nations Australians on whose traditional lands we meet and work, and whose cultures are among the oldest continuing cultures in human history.

arrow-left bars search times arrow-up