Pathfinding in Multi-dimensional Road Networks
Project Description
The criteria in multi-dimensional road networks are divided into two types: additive criteria (AC) and non-additive criteria (NAC). AC includes factors like travel time, distance, and carbon emissions, which are aggregated using a weighted sum to evaluate road segments. NAC, such as maximum edge height and lane occupancy rate, present a challenge in aggregation methods and may require other techniques like lexicographic or conjunctive/disjunctive methods.
The project's aim is to design an algorithm that efficiently handles queries involving both AC and NAC. For example, finding a path for a 40-ton truck that minimizes fuel consumption and keeps toll charges under $40, considering both AC (fuel and tolls) and NAC (weight limits of edges).
The project's aim is to design an algorithm that efficiently handles queries involving both AC and NAC. For example, finding a path for a 40-ton truck that minimizes fuel consumption and keeps toll charges under $40, considering both AC (fuel and tolls) and NAC (weight limits of edges).
Supervisor
LIU, Ziyi
Quota
2
Course type
UROP1100
UROP2100
UROP3100
UROP4100
Applicant's Roles
We seek 2 students with an interest in spatial data indexing and query processing. Fundamental understanding of data structures, graph, and proficiency in C++ programming are highly recommended
Applicant's Learning Objectives
Project goals include:
1. Collecting and analysing real-world multi-dimensional road networks.
2. Reviewing current algorithms for multi-dimensional road networks.
3. Developing an effective algorithm to determine optimal paths considering both AC and NAC.
4. Conducting experiments and preparing detailed reports.
1. Collecting and analysing real-world multi-dimensional road networks.
2. Reviewing current algorithms for multi-dimensional road networks.
3. Developing an effective algorithm to determine optimal paths considering both AC and NAC.
4. Conducting experiments and preparing detailed reports.
Complexity of the project
Challenging