Intelligent In-Car Navigation SystemVehicle Speed GPS velocity is calculated based on the frequency shift (or Doppler shift) in the carrier band. Accuracy of the velocity depends on the effect of multi-path, city sky-scrappers, DOP etc. The comparison of Speed data from GPS and Speedometer or Tachometer has been studied detailed by many researchers. The GPS speed is accurate than speed from speedometer/tachometer. Witte et al, has studied that the speed determined by the GPS receiver was within 0.2 ms(-1) of the true speed measured for 45% of the values with a further 19% lying within 0.4 ms(-1). Hence, it can be interpreted that there isn’t much difference in the speed rendered by GPS and the Speedometer. However, the preference could be given to GPS speed data. In addition, the implementation methods given in this paper does not depend on the accuracy of the speed data. Optimum route analysis Path finding algorithms fall into one of two main categories, matrix algorithms and tree-building algorithms, of which the latter is the one mostly used in Geospatial. Tree-building algorithms find the shortest path from an origin node to all other nodes, producing a tree of shortest paths with branches emanating from the origin (Lombard and Church 1993). The most commonly used tree-building procedure was developed by Djikstra (1959), of which to date many modifications and improvements have been made for specific applications. The working of the Djikstra’s shortest path algorithm is briefed by an example of five nodes (Figure1-a) that are all connected by a road and contains a weight represented by travel time in minutes. The source node or starting location of the shortest path to each node is “A”. The arrows represent the direction of travel between the edges. The numbers near the arrows represent the weight (travel time). Figure1-b shows the algorithm pointing to red nodes with the total weight from node “A”. As the red nodes are found not to have any other edges coming into them such as node “B”, they are coded orange. The orange indicates that the lowest cumulative weight has been assigned to that node. Searches continue for other nodes (“C”, “D”, “E”, and “F”) until the algorithm establishes that all nodes have been assigned the shortest cumulative weight (Figure1-c). Figure1-d shows the final result and the shortest time between all nodes (Ravi. B, et al, 2005).  Figure1. Working of Djikstra’s algorithm We have seen about the general approach of the Djikstra’s algorithm for optimum route analysis. This algorithm could be implemented in network analysis (roads, pipelines, transmission lines etc), which has the nodes and arcs with constraints. The constraint could be length, distance, time, travel time or the combinations of any assumed cost. Map Database – Road Network Data In this section, we will discuss the road network and its attributes other than the geometry. The common attribute information in the road network data and attributes which are used for optimum route analysis are described in the following table 1 & 2. The number of fields would depend on the map data vendor. The format of the map data would never be addressed in this paper. This paper tends to provide general approach for dynamic speed storage and its usage. Table 1:
Table 2:
The “weight” used in the sample Djikstra’s implementation (as described in the above section) could be replaced with the “length of the road” or “travel time” for optimum route analysis as given in the above table. |