Primary supervisor
Edward LamShortest path algorithms are used to advise travelers on the best route from an origin to destination across various modes including car and public transport. One important variant of the standard shortest path problem is the inclusion of resource constraints, where a user has a limited budget in cost, time, carrying capacity, etc. and needs to find a shortest path within this budget. Unlike the regular shortest path problem, the resource-constrained shortest path problem is theoretically proven to be NP-hard, making its computation difficult. This project will involve implementing existing and designing new data structure to improve solve time for the resource-constrained shortest path problem.
Aim/outline
Students will learn to implement high-performance data structures and algorithms and learn to optimize and tune code to reduce solve time. This topic remains an unanswered research question. High-achieving students may have an opportunity to publish their findings in a scientific paper.
Required knowledge
- Strong background in mathematics and/or computer science
- C, C++ or Rust required
- Completed algorithms and data structures units
- Mathematics, operations research, optimisation, graph theory and AI search would be beneficial