|
|
DISCS Advisor Name : Leong Hon Wai Phone : 874-2903 Email : leonghw | |
External sponsors (if any) : None | |
Project Category (Please specify Hon or Hon/MSc) : Either Hons or Hon/MSc | |
Project Title : Dynamic Shortest Path Problems in Land Transportation | |
Project Description (Hon-part followed by MSc-part (if any)) : | |
(Honours-Project-Part) In a large metropolitan city such as Singapore, an important planning problem for commuters is that of finding an "optimal" path from one point to within the city. This problem is generally called the point-to-point "shortest" path problem in the underlying road network and there are many algorithms for solving the problem. | |
Today, with modern traffic monitoring infrastructure, it is now possible to obtain dynamic information on the traffic conditions, such as average travelling speed along individual roads. This project considers a dynamic version of the point-to-point shortest path problem in which dynamic information on travelling speed is available. Assume that we already know (or can easily compute) the shortest path between two given points. We are interested in efficient algorithms for updating this shortest path using the dynamic information on travelling speed. We will first evaluate several proposed algorithms for the problem. Experimental evaluation on the effectiveness of these algorithms will also be carried out. | |
(The-Optional-MSc-Part) This project can be extended to an MSc project. For the MSc part, we shall consider design of new algorithms for the dynamic point-to-point shortest path problem. We shall also consider extensions of the underlying model to include, for example, multiple modes of transportation, or to include computing multiple shortest paths. | |
Start Date: ASAP Duration: 8 months Allocation (by bidding?): Interview | |
Lab: Algorithms Lab Coordinator: Leong Hon Wai Signature/Date: | |
Requirements/Availability of Hardware/Software: C++ or Visual C++ | |
Knowledge/skill required: Interest in R&D; Motivated to learn new things; Good background in algorithms & data structures; | |
Benefits/Significance of Project: Student experience labour and joy of applied R&D Student gain experience in complex software development; Research results potentially used by LTA. | |
|
|
Reviewer Name:
Comments:
Signature/Date |
Reviewer Name:
Comments:
Signature/Date |