UM E-Theses Collection (澳門大學電子學位論文庫)

check Full Text

Towards online shortest paths computation

English Abstract

The online shortest path problem aims at computing the shortest path based on live traffic circumstances. This is very important in modern car navigation systems as it helps drivers to make sensible decisions based on traffic circumstances. To our best knowledge, there is no efficient system/solution that can offer affordable costs at both client and server sides for the online shortest path computation. Unfortunately, the conventional client-server architecture scales poorly with the number of clients. A promising approach is to let the server collect live traffic information and then broadcast them over radio or wireless network. This approach has excellent scalability with the number of clients. Thus, we develop a new framework called live traffic index (LTI) which enables driver to quickly and effectively collect the live traffic information on the broadcasting channel. An impressive result is that the driver can compute/update their shortest path result by receiving only a small fraction of the index which is significantly smaller than the volume of traffic updates. Our experimental study shows that LTI is robust to various parameters and it achieves a tune-in size smaller than competitors by an order of magnitude.

Issue date



Zhao, Hong Jun


Faculty of Science and Technology


Department of Computer and Information Science




Computer networks

Automotive telematics


Gong, Zhi Guo

U, Leong Hou

Files In This Item

TOC & Abstract

Full-text (Intranet only)

1/F Zone C
Library URL