Towards Online Shortest Path Computation

Towards Online Shortest Path Computation

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. To our best knowledge, there is no efficient system/solution that can offer affordable costs at both client and server sides for 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 drivers 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. Our experimental study shows that LTI is robust to various parameters and it offers relatively short tune-in cost (at client side), fast query response time (at client side), small broadcast size (at server side), and light maintenance  time (at server side) for online shortest path problem.

EXISTING SYSTEM:

Nowadays, several online services provide live traffic data (by analyzing collected data from road sensors, traffic cameras, and crowdsourcing techniques), such as Google-Map , Navteq , INRIX Traffic Information Provider , and TomTom NV , etc. These systems can calculate the snapshot shortest path queries based on current live raffic data; however, they do not report routes to drivers continuously due to high operating costs. Answering the shortest paths on the live traffic data can be viewed as a continuous monitoring problem in spatial databases, which is termed online shortest paths computation (OSP) in this work. To the best of our knowledge, this problem has not received much attention and the costs of answering such continuous queries vary hugely in different system architectures. Typical client-server architecture can be used to answer shortest path queries on live traffic data.

DISADVANTAGES OF EXISTING SYSTEM:

1. Scalability limitations in terms of network bandwidth and server loading.

 2. Online Shortest Paths computation is not much attention.

PROPOSED SYSTEM:

Motivated by the lack of off-the-shelf solution for OSP, in this paper we present a new solution based on the index transmission model by introducing live traffic index (LTI) as the core technique. LTI is expected to provide relatively short tune-in cost (at client side), fast query response time (at client side), small broadcast size (at server side), and light maintenance time (at server side) for OSP.

The index structure of LTI is optimized by two novel techniques, graph partitioning and stochastic-based construction, after conducting a thorough analysis on the hierarchical index techniques.

ADVANTAGES OF PROPOSED SYSTEM:

1. The server periodically updates the travel times on these paths based on the latest traffic, and reports the current best path to the corresponding user.

2. Efficiently maintains the index for live traffic circumstances.

3. To the best of our knowledge, this is the first work to give a thorough cost analysis on the hierarchical index techniques and apply stochastic process to optimize the index hierarchical structure.

4. LTI efficiently maintains the index for live traffic circumstances by incorporating Dynamic Shortest Path Tree (DSPT) into hierarchial index techniques. In addition, a bounded version of DSPT is proposed to further reduce the broadcast overhead.

5. LTI reduces the tune-in cost up to an order of magnitude as compared to the state-of-the-art competitors; while it still provides competitive query response time, broadcast size, and maintenance time.

SYSTEM REQUIREMENTS:

HARDWARE REQUIREMENTS:

Ø System                          :         Pentium IV 2.4 GHz.

Ø Hard Disk                      :         40 GB.

Ø Floppy Drive                 :         1.44 Mb.

Ø Monitor                         :         15 VGA Colour.

Ø Mouse                            :         Logitech.

Ø Ram                               :         512 Mb.

SOFTWARE REQUIREMENTS:

Ø Operating system           :         Windows XP/7.

Ø Coding Language :         JAVA/J2EE

Ø IDE                      :         Netbeans 7.4

Ø Database              :         MYSQL

REFERENCE:

Leong Hou U, Hong Jun Zhao, Man Lung Yiu, Yuhong Li, and Zhiguo Gong”Towards Online Shortest Path Computation”IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING,VOL. 26,NO. 4,APRIL 2014.