Prof. M. N. Kulkarni
Civil Engineering Department, IIT Bomaby
J. V. S. S. S. Srikanth
Intelligent Transportation Systems (ITS) have become the basic infrastructure for the development of any country. Vehicle Guidance systems, which are a part of these ITS, play a vital role in efficient transfer of men and goods from origin to destination through shortest path with minimum delays and travel times. In the present scenario Guidance Systems are effectively used for many purposes in various fields. Vehicle Guidance Systems are widely in use in many Departments and Organizations. Rail and Road Transportation departments widely use these guidance systems for fleet management and also for public transport. This system guides the users to their destinations by showing the corresponding paths.
In the present scenario traffic problems are increasing in a rapid way. Especially in India, where the travel demand and the travel density are high, traffic is creating many problems. Traffic problems include traffic congestions, traffic jams, delay in travel time, etc. The main causes for this are: the rapid increase in population, non-awareness of traffic rules by the general public, no strict implementation of rules, etc., which, along with many other causes, lead to traffic problems. Especially when the travel is delayed i.e., when the vehicle or the user is unable to reach the destination within a prescribed time, he becomes frustrated, which in turn leads to an inefficient workforce. This hampers the development of the nation. Delay in travel time also increases the mental disorder in the people traveling (Murkami, 2000). This is again a big problem, as it effects people like a slow poison and hampers their mental ability. Delay in travel time mainly depends on two factors. They are – Internal factors
– External factors Internal factors are the factors, which are governed by the user himself like the maintenance of the vehicle, the mode he is traveling, the speed at which he always travels, the road chosen by the user, etc. External factors are the factors, which affect the user externally, like traffic jams, traffic congestion etc. These two kinds of factors are interdependent on each other and cause a mental effect on the user, which is harmful. If travel times are decreased by some means, it creates a positive work-environment. There are many ways of decreasing travel time like by decreasing traffic congestion, by reducing traffic jams, by reducing accidents, etc.
Even after controlling these factors, accidents and traffic jams are inevitable, resulting in traffic problems. If the traveler is informed about the accident or traffic jam before he gets struck in the jam he will be able to choose another path by which he can reach the destination. For this, if he has a data base map, which shows all possible paths between origin and destination, the accident position and the position of the vehicle, then the user can easily judge the alternate paths by which he can reach his destination easily and happily, without frustration. Also if the shortest path between the origin and destination is displayed, the user can use this shortest path to reach his destination fast (Quiroga 2000).
If any person is new to a place and he doesn’t know the route to his destination, but he knows only the name of the destination, then a guidance system will come to his rescue by showing him all possible paths and also the shortest path. The user can then travel using this map and reaches his destination fast and safely. Also if tracking is provided along with display of all possible paths, then the user can view which path he is traveling and he can easily shift between paths, if he is traveling in the wrong direction. The same guidance system can be used by Tourism Department for tourists. Tourists can be guided to their destinations i.e., tourist spots without any manual help, with such type of guidance systems. This gives the tourists an effective and comfortable traveling experience and also attracts many foreign tourists, thus developing the tourism, resulting in inflow of foreign exchange and increase in financial revenues. A GPS-GIS integrated system is most suitable for such vehicle guidance (Taylor et al., 2000).
Fig. 1: All possible paths between Powai and Airport
Global Positioning System
The Global Positioning System (GPS) is a space-based navigation system, consisting of a constellation of 24 satellites, in six orbital planes with 55° inclination to the equator. The satellites are placed at a height of about 20,200 km with 12 hours orbital period and operated by the United States Department of Defense (DOD) for accurate determination of position, velocity and time. All the GPS satellites are controlled by the system tracking stations, ground antenna, and the master control station.
In each satellite two rubidium and two cesium atomic clocks with stability 1013 to 1014 are used to derive the fundamental frequency fo = 10.23 MHz. The GPS signals are transmitted at two frequencies, designated L1 (154 fo = 1575.42 MHz) and L2 (120 fo =1227.6 MHz), which are derived from the fundamental frequency (fo). Two codes are used, one of which is called C/A (coarse acquisition code, fo/10) and the other is called P (precise, fo) code. As the rate of P code is 10 times the rate of C/A code, its precision is 10 times better than C/A code. The L1 and L2 are modulated by Pseudo Random Noise (PRN) code, (each satellite is identified by this code) and transmitted after biphase modulation with the carrier.
The distance to GPS satellite is estimated by measuring the time a radio signal takes to reach us from the satellite. This is accomplished by cross-correlation of pseudo-random code generated by the satellite and the receiver. The distances from receiver to satellite measured in this way are called code pseudo ranges. Minimum four satellites are required for estimating the coordinates of a point on the Earth’s surface. While the use of the GPS is extensive in defense, navigation and surveying applications, it is also being used in geo-sciences, ionospheric & atmospheric studies, global climate changes, observing polar motion & earth rotation rate, mapping the gravity field, detecting seismo ionospheirc effects, transport and communications, environment management, for accurate time and frequency, etc. (Kulkarni, 2000)
Geographical Inforrmation System
Geographical Information System (GIS) has created a revolution in mapping procedures as it can interact with the features and its attributes effectively (Refer website 3). For the present work TransCAD is used as GIS software. TransCAD is the first and only Geographic Information System (GIS) designed specifically for use by transportation professionals to store, display, manage, and analyze transportation data. TransCAD combines GIS and transportation modeling capabilities in a single integrated platform, providing capabilities that are unmatched by any other package. TransCAD can be used for all modes of transportation, at any scale or level of detail. TransCAD is a state-of-the-art GIS that one can use to create and customize maps, build and maintain geographic data sets, and perform many different types of spatial analysis. TransCAD includes sophisticated GIS features such as polygon overlay, buffering, and geocoding, and has an open system architecture that supports data sharing on local- and wide-area networks. TransCAD extends the traditional GIS data model to include transportation data objects such as:
- Transportation networks
- Routes and route systems
- Linear-referenced data
These extensions make TransCAD the best tool for working with transportation data. One can use the GIS functions to prepare, visualize, analyze, and present ones work, and use the application modules to solve routing, logistics, and other transportation problems with greater ease and efficiency than any other product. (Refer website 5)
Fig. 2: All possible paths highlighting shortest path between Powai and Airport
Vehicle guidance system consists of algorithms that will display all possible paths between specified origin and destination highlighting shortest path. Also it has algorithms for interpolating, discontinuous GPS data. The methodology adapted for Vehicle guidance can be divided into two parts viz. Algorithm preparation and TransCAD work.
Algorithms for vehicle Guidance
The algorithms that are prepared for Vehicle guidance are for display of all possible paths between origin and destination and the Interpolating algorithm. The input for the display algorithm is the network file, which contains the road links with their end point positions (White et al., 2000). The output of the algorithm is the file, which contains all the road links between the specified origin and destination. The procedure adapted for this algorithm is that by plotting a graph using the entire link ids and the end points. This is used as a database for the whole algorithm. This graph contains the information about the connectivity of each node. The nearest neighbors for each endpoint are then identified from the graph. The point ids of the specified origin and destination are taken and the nearest neighbors from the origin are identified and from each neighbor its neighbors are called recursively. If the destination is reached the road ids of the path are written to an output file. In this way all the neighbors are called recursively to find all possible paths between origin and destination. If destination is not reached then the particular road links are ignored (Saab, 2000).
Another algorithm is prepared for interpolation of positional data that is obtained from GPS. This interpolation is necessary because the GPS data which we get is not continuous because of many reasons viz. obstruction because of tall buildings, non uniform velocity of the vehicle, longer locking time for the GPS receivers in case of Geodetic type of receivers, rapid variations in the acceleration of the vehicle, etc. Hence, a break in tracking is inevitable. In order to get complete and continuous tracking from the GPS data, an interpolating algorithm is prepared to interpolate the values between the break points. The methodology adapted for this algorithm is that first the break in the GPS data is to be identified. For that the difference between two points is calculated. If this difference is more than a specified interval then there is break in the data. Then the midpoint between the two points is calculated and again the difference between the newly obtained point and the original point is calculated. If this is again grater than the given interval then it is again interpolated by calculating their mid point. Also the other side of the midpoint is interpolated. This process in continued until the difference is less than the specified interval. The interval depends on the positional accuracy of the receiver. In this way interpolation algorithm gives continuous GPS data without any breaks.
The GIS software used for the work is TransCAD. It has all the modules that conventional GIS software should have and also it has several special modules for the application of transportation engineering. TransCAD also has a developer’s kit called GISDK using which one can create his own custom applications to run along with TransCAD (Manual GISDK). GISDK is used for the present problem. Using GISDK a module called Vehicle Guidance is created. Vehicle Guidance has three buttons called Display, Guide and Exit. If Display button is clicked then a dialog box appears which has a pop down menu consisting of different origins. If a particular origin is clicked, then another dialog box appears, hiding the previous one, which contains a pop down menu consisting of different destinations. If a destination is choosen from the list then all possible paths between the origin and destination are calculated using the algorithm. The algorithm gives all the nodes which connect origin to destination. These nodes list is joined with the view and a comparison between the present nodes to the obtained nodes is done and if the node is present then in another field, which is created, a unique value is written. A theme is created with the newly created field and is displayed on the map. This displays all possible paths between the specified origin and destination. In the destination dialog box there is one button called short, which displays the shortest path between the specified origin and destination. The second button created is Guide, which guides the vehicle to the destination. It runs the interpolation program whenever it encounters a break in GPS data. The whole traverse traveled by the vehicle is also shown on the map. The third button is Exit, which exits the program. Also exit buttons are present in each dialog box for instant exiting of the program.
Fig. 3: The path traversed by the vehicle in pilot experiment, after Interpolation
A pilot experiment is conducted in Mumbai city for testing Vehicle guidance system. Six places in Mumbai city were choosen viz. Powai, Andheri, Airport, Mumbai Central, Chatrapathi Shivaji Terminus (CST) and Gateway of India. These places are taken as Origin and Destination. If any user specifies same origin and destination, then a message is displayed saying that the origin and destination specified are same. If user specifies an origin and destination all possible paths between the two points are calculated and displayed (refer to Fig 1). If the short button is activated, the shortest path between the origin and destination is shown (see Fig 2). Also a vehicle is taken to make a traverse, like a Probe vehicle, with onboard GPS receivers. Three kinds of GPS receivers are used for the purpose viz. Geodetic type TRIMBLE 4000ssi receivers (for details refer website 1) which is of dual frequency type, Mapping type TRIMBLE Pro-XR receivers (for details refer website 1) which is single frequency type, Handheld receivers GPS315 of MAGELLAN (for details refer website 4), which are also of single frequency. Taking all the three receivers on a vehicle, a pilot experiment is conducted by roving on the six places and also on some other places in Mumbai city. A base station was setup before traversing so that the processing mode could be of DGPS mode. After the traverse is completed the data was downloaded from the receivers and as explained earlier, there were breaks between the data collected. This data was then interpolated with the interpolating algorithm and the interpolated co-ordinates are fed to the Vehicle Guidance system. This system then made a line layer using the present data and the line layer was superimposed on the map to get the map of the traversed area (see Fig 3).
From the data that was obtained from the GPS receivers, a comparison was made between the three receivers for their compatibility with the Vehicle Guidance system. It was observed that Geodetic type receivers had more breaks in the data. The probable reason for this is that the locking time for the antenna is 200 sec in the fastest mode i.e., on-the-fly mode. Hence it requires more time for actually collecting data, thus it is not suitable for vehicle guidance system, even if the positional accuracy of the receiver is more. Mapping type receivers gave a considerable good traverse with less number and length of breaks in comparison with the geodetic type receivers. The positional accuracy of these receivers is not as high as compared with the Geodetic type receivers. They give few meter level accuracy, but it is sufficient for vehicle guidance purposes. Hand held receivers also gave a continuous data with less number and length of breaks but their positional accuracy is in tens of meters, so they are not ideally suited for vehicle guidance purposes. Thus, mapping type single frequency receivers are best suited for vehicle guidance purpose.
- Kulkarni, m.n., (ed.) short term course, The GPS and its Applications, Civil Engineering Department, IIT Bombay, 2000
- Murkami, E., D.P Wagner., Can GPS improve trip reporting?, Transportation Research – C, 7C, pp 149 – 165, 2000
- “Manual of GISDK”, Caliper Co operation, U.S.A.
- Quiroga, C.A., and D Bullock., Travel Time studies using GIS and GPS and Integrated methodology, Transportation Research Part C, 6C, pp 101 – 127, 1995
- Saab. S.S., A Map Making Approach for train positioning, Part – I methodology, Part – II Applications and Experimentation, IEEE Transactions on Vehicular Technology, Volume 49, No 2, 2000.
- Taylor, M.A.P., J.E Wolley., and R Zito., Integration of GPS and GIS for Traffic Congestion Studies, Transportation Research – C, 8C, pp 257 – 285, 2000
- White, C.E., David Bernstein, A.L Kornhauser., Some Map making Algorithms for Personal Assistants, Journal Of Transportation, Part – C, 8C, pp 91 – 108, 2000
Web Site References