| GISdevelopment.net ---> Technology---> Mobile Mapping |
Implementation of a GPS-based AVL System for Mazandaran Province
M.R.Mosavi and A.Ghadiri
Department of Electrical Engineering,
Behshahr University of Science and Technology,
Behshahr 48518-78413, Iran
Tel.: 0152-1525242001, Fax.: 0152-1525242004
Email: M_Mosavi@iust.ac.ir, Ghadiri@iust.ac.ir
Abstract:
Implementation of a GPS-based Automatic Vehicle Location (AVL) system for Mazandaran province, a northern province of Iran, has been presented in this paper. This system is composed of three main parts: computer-aided dispatch software, mobile data terminals and digital communications. A fuzzy map matching method was implemented for software, which uses a digital road map to correct the GPS position error. The proposed algorithm is easy to calculate. It requires little computation time without need to extra sensors and can find the mobile exact position which moves on the road. Mobile data terminals are composed of low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the implemented algorithm for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm. The software was equipped with many capabilities which can be classified in two main categories. The first category was implemented as a Graphic User Interface (GUI). Instantaneous position of mobile vehicle on the map with zooming capability and the momentary geographical position of mobile vehicle can be viewed graphically. Moreover, contents of message103 such as date and time, velocity, error factors and channels status of GPS receiver can be extracted for each mobile vehicle. Other category of software capabilities is searching and path-finding. The best path for a mobile vehicle to a desired destination can be found instantaneously based on determined criteria. The implemented AVL system is used in some cities of Mazandaran province.
I. Introduction
Automatic Vehicle Location (AVL) is a computer-based vehicle tracking system. For transit, the actual real-time position of each vehicle is determined and relayed to a control center. Actual position determination and relay techniques vary, depending on the needs of the transit system and the technologies employed. Simple AVL systems include: computer-aided dispatch software, mobile data terminals, emergency alarms, and digital communications. The dominant AVL technology deployed today is GPS. The mobile determined positions using GPS receivers could be displayed in electronic map. However, because of errors exist in GPS and also in digital maps, it is not possible to ensure that mobile positions register properly on a digital map. To avoid this problem, map matching method can be used to improve mobile position display precision over an electronic map [1].
A map matching method using a digital road map is a useful approach to correct these errors. There are a lot of map matching methods based on the geometric approaches. These methods find the road which is close to the mobile trajectory. In these algorithms, it is difficult to calculate the nearest road and it requires hard calculations, which leads to a time consuming. Another map matching algorithm is to use conditional probability. This algorithm is more robust than geometric method and it can cover from false positioning quickly. However, it requires more computation time and more memory to store the mobile trajectory [2,3].
In this paper, a new fuzzy map matching algorithm is proposed for reducing of GPS position error in AVL application. It is easy to implement and requires little computation. Also, this method can find the mobile exact position on the road. Implemented software of the GPS-based AVL system exploits this method for precise map matching. The effectiveness and applicability of the proposed algorithm is verified by the real road experiments.
This paper is organized as follow. Section II explains proposed fuzzy map matching algorithm. Section III explains computer-aided dispatch center and path finding approaches will be discussed in section IV. Finally conclusions are explained in section V.
II. Proposed Fuzzy Map Matching Algorithm Design
The block diagram of proposed fuzzy system is shown in Fig.1. (error between the mobile measured position and the desired route) and (the mobile measured position distance to the desired route) are used as input fuzzy variables to this fuzzy system. is fuzzy system output and is defined as rotation angle of trajectory vector for mapping. , , and are divided into five segments for partition the rule space. The membership functions are defined as Fig.2, where LN, SN, ZE, SP and LP express Large Negative, Small Negative, Zero, Small Positive and Large Positive, respectively. Seventeen rules in the rule base are defined as Table1.
Fig.1. The block diagram of proposed fuzzy system
Fig.2. Membership functions for q, q', and d
Table1. Seventeen rules in the rule base of fuzzy system of Fig.1
The Mamdani-Style method with is used for the inference process and the center of area method is employed for the defuzzification [4,5,6].
III. Computer-Aided Dispatch Center
Vector-scan maps were used in computer-aided dispatch center. In order to generate a map the following process applied. At first, precise paper map was prepared for each city since digital maps were not accessible while this project was being done. Prepared maps were scanned, resized and modified for each city of Mazandaran province. To modify scanned maps Macromedia software along with Flash software was used. Then a new layer was added to map file and the lines of main layer were redrawn in new layer based on scanned map. After deleting the main layer, new layer was saved as SWF file and used by software.
Since WGS84 geographical system used for GPS is 3-D systems and our maps are 2-D, and usual mapping approaches such as UTM have computational overload, we used proportional approach to map received data of GPS. Neglecting partial effect of earth curvature we can use following relations to compute and coordinate on the map:
where Longmin, Longmax, Latmin and Latmax are minimum longitude, maximum longitude, minimum latitude and maximum latitude on the map respectively.
The software was equipped with many capabilities which can be classified in two main categories. The first category was implemented as a Graphic User Interface (GUI). Instantaneous position of mobile vehicle on the map with zooming capability and the momentary geographical position of mobile vehicle can be viewed graphically. Moreover, contents of message103 such as date and time, velocity, error factors and channels status of GPS receiver can be extracted for each mobile vehicle. Other category of software capabilities is searching and path-finding. The best path for a mobile vehicle to a desired destination can be found instantaneously based on determined criteria.
Fig.3 shows the main page of implemented GUI. User can find a location in a city by entering the location and city names. Related information of the desired location and the adjacent node will be displayed on the message and results window. Nodes will be explained later. Connecting and disconnecting time of mobile vehicle are of other information which is shown in this window. Information section displays important data of a connected mobile vehicle such as mobile position based on WGS-84 coordination system. Map matching implemented on right section of the main page. City map along with other information such as its population and geographical position will be demonstrated on right section by choosing the name of a city. For easy mobile tracking and effective implementation of path finding algorithm, each city of Mazandaran province will be determined by some nodes. Fig.4 shows the map of part of Behshahr city, eastern city of Mazandaran province, along with nodes used for map matching.
Fig.3. Main page of implemented GUI
Fig.4. Map of part of Behshahr city, eastern city of Mazandaran province
GPS menu of software has some options for monitoring of mobile vehicles. Connect option of GPS is used for connection of different mobile vehicles. A message error will be shown if connection to a mobile GPS encounters with any problem, and ask the user to modify setting. With successful connection, new mobile vehicle is added to mobile GPS list along with connection time. User can view classified status of a mobile GPS by choosing message103 option. Information such as date and time, coordinates, velocity, error factors and channel status can be viewed and modified on a window. Fig.5 shows different parts of message103 window.
Fig.5. Different parts of message103 window
Report menu has two options: Start auto save and Get report. By choosing Start auto save option, automatic saving of mobile vehicles status such as their position and velocity in user-determined intervals will be activated. Get report option is used for reporting saved data collected from mobile vehicles. Mobile position and velocity saved in data base at different times can be reviewed by user. All recorded data will be displayed by choosing show all record option. Moreover user can select special records by setting desired date and time intervals, geographical longitude or latitude, or velocity. Information related to maximum and minimum values of geographical longitude or latitude, velocity and average velocity is demonstrated for operator in report window. Records can be saved as QRP format, used by this software, or as html format. Fig.6 shows Get report form and reported information of a mobile vehicle.
Fig.6. Get report form and reported information of a mobile vehicle
Tools menu has two options: Find path and Options. Fig.7 shows the Find path form. To find path between two nodes in a city, node list will be displayed for operator. By choosing source and destination nodes, path between two nodes along with intermediate nodes will be arranged. Fig.8 shows path finding between two nodes in Behshahr city.
Fig.7. Find path form
Fig.8. Path finding between two nodes in Behshahr city
Options form helps to set serial ports of mobile vehicle transmitter along with reporting interval. Baud rate, data bits, stop bits, parity and flow control can be modified as shown in Fig.9. Refresh interval can be 5, 10, 20, or 30 seconds.
Fig.9. Options and Setup forms
IV. Path finding
Scanned or digital map file can not be used for precise tracking of a mobile vehicle. To be able to use SWF file obtained from scanned file for path finding, we should consider map as a graph. To extract a graph from scanned map, each fraction on the road was considered as a node. Therefore it is possible to have several nodes for a street and each street was divided to several lines. Each node was labeled and the distance between two nodes was considered as graph weight. The graph was saved as neighborhood matrix. A 2-D matrix , in which is the number of nodes, was generated. is the length of line between node and . It is obvious that is zero. If there is not any path between two nodes, a maximum value more than sum of all lines of the graph is considered as path length. To find the shortest path between two nodes the following problem should be solved [7].
Problem: Consider graph in which each line has a positive value and source node is obvious. Find the shortest path between source node and every other node in in such way that the total path length was summation of other length.
Solution: To solve the problem Dijkstra's algorithm is used. This algorithm holds a set of nodes which have minimum distance from source node. For initial time, includes source node only. In each repeat a node of with minimum distance to source node is added to . Assuming that nodes of have positive cost, we can find the shortest path from source node to which pass from nodes of . This path is called "Special Path". In each repeat, array is used to record the shortest distance. When includes all nodes, all related paths will be "Special Path". Therefore contains the shortest distance from source node to each other nodes. An example of this algorithm is shown in Fig.10 and Table2. To find the shortest path between all couples of nodes, Floyd algorithm was used. Consider we have neighborhood matrix for all nodes with the name . Now repeats will be applied on . After repeats, has the shortest distance from node to which does not pass from other node with number larger than . In other words, nodes and can be every node but the number of each intermediate node should be equal or lower than . To calculate in repeat the following relation is used:
Fig.10. An example of graph for testing of Dijkstra's algorithm
Table2. Output of Dijkstra's algorithm for above example
An example of Floyd algorithm is shown in Fig.11 and Table3 and Table4.
Fig.11. An example of graph for testing of Floyd algorithm
Table3. Calculate in repeat for above example
Table4. Output of Floyd algorithm for above examples
V. Conclusions
In this paper, implementation of a GPS-based AVL system for Mazandaran province, a northern province of Iran, has been presented. A fuzzy map matching method was implemented for software, which uses a digital road map to correct the GPS position error. Software was developed with a GUI to report instantaneous position of mobile vehicle on the map and record contents of message103. Moreover, software has searching and path-finding capabilities. For experiments, a car navigation system was developed with a small number of sensors, such as a low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the implemented algorithms for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm.
References:
M.R.Mosavi and A.Ghadiri
Department of Electrical Engineering,
Behshahr University of Science and Technology,
Behshahr 48518-78413, Iran
Tel.: 0152-1525242001, Fax.: 0152-1525242004
Email: M_Mosavi@iust.ac.ir, Ghadiri@iust.ac.ir
Abstract:
Implementation of a GPS-based Automatic Vehicle Location (AVL) system for Mazandaran province, a northern province of Iran, has been presented in this paper. This system is composed of three main parts: computer-aided dispatch software, mobile data terminals and digital communications. A fuzzy map matching method was implemented for software, which uses a digital road map to correct the GPS position error. The proposed algorithm is easy to calculate. It requires little computation time without need to extra sensors and can find the mobile exact position which moves on the road. Mobile data terminals are composed of low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the implemented algorithm for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm. The software was equipped with many capabilities which can be classified in two main categories. The first category was implemented as a Graphic User Interface (GUI). Instantaneous position of mobile vehicle on the map with zooming capability and the momentary geographical position of mobile vehicle can be viewed graphically. Moreover, contents of message103 such as date and time, velocity, error factors and channels status of GPS receiver can be extracted for each mobile vehicle. Other category of software capabilities is searching and path-finding. The best path for a mobile vehicle to a desired destination can be found instantaneously based on determined criteria. The implemented AVL system is used in some cities of Mazandaran province.
I. Introduction
Automatic Vehicle Location (AVL) is a computer-based vehicle tracking system. For transit, the actual real-time position of each vehicle is determined and relayed to a control center. Actual position determination and relay techniques vary, depending on the needs of the transit system and the technologies employed. Simple AVL systems include: computer-aided dispatch software, mobile data terminals, emergency alarms, and digital communications. The dominant AVL technology deployed today is GPS. The mobile determined positions using GPS receivers could be displayed in electronic map. However, because of errors exist in GPS and also in digital maps, it is not possible to ensure that mobile positions register properly on a digital map. To avoid this problem, map matching method can be used to improve mobile position display precision over an electronic map [1].
A map matching method using a digital road map is a useful approach to correct these errors. There are a lot of map matching methods based on the geometric approaches. These methods find the road which is close to the mobile trajectory. In these algorithms, it is difficult to calculate the nearest road and it requires hard calculations, which leads to a time consuming. Another map matching algorithm is to use conditional probability. This algorithm is more robust than geometric method and it can cover from false positioning quickly. However, it requires more computation time and more memory to store the mobile trajectory [2,3].
In this paper, a new fuzzy map matching algorithm is proposed for reducing of GPS position error in AVL application. It is easy to implement and requires little computation. Also, this method can find the mobile exact position on the road. Implemented software of the GPS-based AVL system exploits this method for precise map matching. The effectiveness and applicability of the proposed algorithm is verified by the real road experiments.
This paper is organized as follow. Section II explains proposed fuzzy map matching algorithm. Section III explains computer-aided dispatch center and path finding approaches will be discussed in section IV. Finally conclusions are explained in section V.
II. Proposed Fuzzy Map Matching Algorithm Design
The block diagram of proposed fuzzy system is shown in Fig.1. (error between the mobile measured position and the desired route) and (the mobile measured position distance to the desired route) are used as input fuzzy variables to this fuzzy system. is fuzzy system output and is defined as rotation angle of trajectory vector for mapping. , , and are divided into five segments for partition the rule space. The membership functions are defined as Fig.2, where LN, SN, ZE, SP and LP express Large Negative, Small Negative, Zero, Small Positive and Large Positive, respectively. Seventeen rules in the rule base are defined as Table1.
Fig.1. The block diagram of proposed fuzzy system
Fig.2. Membership functions for q, q', and d
The Mamdani-Style method with is used for the inference process and the center of area method is employed for the defuzzification [4,5,6].
III. Computer-Aided Dispatch Center
Vector-scan maps were used in computer-aided dispatch center. In order to generate a map the following process applied. At first, precise paper map was prepared for each city since digital maps were not accessible while this project was being done. Prepared maps were scanned, resized and modified for each city of Mazandaran province. To modify scanned maps Macromedia software along with Flash software was used. Then a new layer was added to map file and the lines of main layer were redrawn in new layer based on scanned map. After deleting the main layer, new layer was saved as SWF file and used by software.
Since WGS84 geographical system used for GPS is 3-D systems and our maps are 2-D, and usual mapping approaches such as UTM have computational overload, we used proportional approach to map received data of GPS. Neglecting partial effect of earth curvature we can use following relations to compute and coordinate on the map:
where Longmin, Longmax, Latmin and Latmax are minimum longitude, maximum longitude, minimum latitude and maximum latitude on the map respectively.
The software was equipped with many capabilities which can be classified in two main categories. The first category was implemented as a Graphic User Interface (GUI). Instantaneous position of mobile vehicle on the map with zooming capability and the momentary geographical position of mobile vehicle can be viewed graphically. Moreover, contents of message103 such as date and time, velocity, error factors and channels status of GPS receiver can be extracted for each mobile vehicle. Other category of software capabilities is searching and path-finding. The best path for a mobile vehicle to a desired destination can be found instantaneously based on determined criteria.
Fig.3 shows the main page of implemented GUI. User can find a location in a city by entering the location and city names. Related information of the desired location and the adjacent node will be displayed on the message and results window. Nodes will be explained later. Connecting and disconnecting time of mobile vehicle are of other information which is shown in this window. Information section displays important data of a connected mobile vehicle such as mobile position based on WGS-84 coordination system. Map matching implemented on right section of the main page. City map along with other information such as its population and geographical position will be demonstrated on right section by choosing the name of a city. For easy mobile tracking and effective implementation of path finding algorithm, each city of Mazandaran province will be determined by some nodes. Fig.4 shows the map of part of Behshahr city, eastern city of Mazandaran province, along with nodes used for map matching.
Fig.3. Main page of implemented GUI
Fig.4. Map of part of Behshahr city, eastern city of Mazandaran province
GPS menu of software has some options for monitoring of mobile vehicles. Connect option of GPS is used for connection of different mobile vehicles. A message error will be shown if connection to a mobile GPS encounters with any problem, and ask the user to modify setting. With successful connection, new mobile vehicle is added to mobile GPS list along with connection time. User can view classified status of a mobile GPS by choosing message103 option. Information such as date and time, coordinates, velocity, error factors and channel status can be viewed and modified on a window. Fig.5 shows different parts of message103 window.
Fig.5. Different parts of message103 window
Report menu has two options: Start auto save and Get report. By choosing Start auto save option, automatic saving of mobile vehicles status such as their position and velocity in user-determined intervals will be activated. Get report option is used for reporting saved data collected from mobile vehicles. Mobile position and velocity saved in data base at different times can be reviewed by user. All recorded data will be displayed by choosing show all record option. Moreover user can select special records by setting desired date and time intervals, geographical longitude or latitude, or velocity. Information related to maximum and minimum values of geographical longitude or latitude, velocity and average velocity is demonstrated for operator in report window. Records can be saved as QRP format, used by this software, or as html format. Fig.6 shows Get report form and reported information of a mobile vehicle.
Fig.6. Get report form and reported information of a mobile vehicle
Tools menu has two options: Find path and Options. Fig.7 shows the Find path form. To find path between two nodes in a city, node list will be displayed for operator. By choosing source and destination nodes, path between two nodes along with intermediate nodes will be arranged. Fig.8 shows path finding between two nodes in Behshahr city.
Fig.7. Find path form
Fig.8. Path finding between two nodes in Behshahr city
Options form helps to set serial ports of mobile vehicle transmitter along with reporting interval. Baud rate, data bits, stop bits, parity and flow control can be modified as shown in Fig.9. Refresh interval can be 5, 10, 20, or 30 seconds.
Fig.9. Options and Setup forms
IV. Path finding
Scanned or digital map file can not be used for precise tracking of a mobile vehicle. To be able to use SWF file obtained from scanned file for path finding, we should consider map as a graph. To extract a graph from scanned map, each fraction on the road was considered as a node. Therefore it is possible to have several nodes for a street and each street was divided to several lines. Each node was labeled and the distance between two nodes was considered as graph weight. The graph was saved as neighborhood matrix. A 2-D matrix , in which is the number of nodes, was generated. is the length of line between node and . It is obvious that is zero. If there is not any path between two nodes, a maximum value more than sum of all lines of the graph is considered as path length. To find the shortest path between two nodes the following problem should be solved [7].
Problem: Consider graph in which each line has a positive value and source node is obvious. Find the shortest path between source node and every other node in in such way that the total path length was summation of other length.
Solution: To solve the problem Dijkstra's algorithm is used. This algorithm holds a set of nodes which have minimum distance from source node. For initial time, includes source node only. In each repeat a node of with minimum distance to source node is added to . Assuming that nodes of have positive cost, we can find the shortest path from source node to which pass from nodes of . This path is called "Special Path". In each repeat, array is used to record the shortest distance. When includes all nodes, all related paths will be "Special Path". Therefore contains the shortest distance from source node to each other nodes. An example of this algorithm is shown in Fig.10 and Table2. To find the shortest path between all couples of nodes, Floyd algorithm was used. Consider we have neighborhood matrix for all nodes with the name . Now repeats will be applied on . After repeats, has the shortest distance from node to which does not pass from other node with number larger than . In other words, nodes and can be every node but the number of each intermediate node should be equal or lower than . To calculate in repeat the following relation is used:
Fig.10. An example of graph for testing of Dijkstra's algorithm
| Repeat Number | S | W | D[2] | D[3] | D[4] | D[5] |
| Initial state | {1} | - | 10 | ∞ | 30 | 100 |
| 1 | {1,2} | 2 | 10 | 60 | 30 | 100 |
| 2 | {1,2,4} | 4 | 10 | 50 | 30 | 90 |
| 3 | {1,2,4,3} | 3 | 10 | 50 | 30 | 60 |
| 4 | {1,2,3,4,5} | 5 | 10 | 50 | 30 | 60 |
An example of Floyd algorithm is shown in Fig.11 and Table3 and Table4.
Fig.11. An example of graph for testing of Floyd algorithm
| Node | 1 | 2 | 3 |
| 1 | 0 | 3 | 0 |
| 2 | 0 | 0 | 1 |
| 3 | 2 | 0 | 0 |
V. Conclusions
In this paper, implementation of a GPS-based AVL system for Mazandaran province, a northern province of Iran, has been presented. A fuzzy map matching method was implemented for software, which uses a digital road map to correct the GPS position error. Software was developed with a GUI to report instantaneous position of mobile vehicle on the map and record contents of message103. Moreover, software has searching and path-finding capabilities. For experiments, a car navigation system was developed with a small number of sensors, such as a low cost GPS receiver and a microcontroller chip. The real road experiments demonstrate the effectiveness and applicability of the implemented algorithms for accurate navigation with low cost GPS receivers. The results show that real-time positioning error reduces from 25m to less than 1.5m using proposed fuzzy map matching algorithm.
References:
- Fenglin Guo, Yuesheng Ji, and Guorong Hu, "Methods for Improving the Accuracy and Reliability of Vehicle-borne GPS Intelligence Navigation", GIS Development Magazine, November 2002.
- Sinn Kim and Jong-Hwan Kim, "Q-factor Map Matching Method using Adaptive Fuzzy Network", IEEE Conference on Fuzzy Systems, Vol.2, August 1999, pp.628-633.
- Sinn Kim and Jong-Hwan Kim, "Adaptive Fuzzy-Network-Based C-Measure Map-Matching Algorithm for Car Navigation System", IEEE Transactions on Industrial Electronics, Vol.48, No.2, April 2001, pp.432-441.
- K.-Y. Tu, F.-R. Chang, L.-S. Wang, and G.-S. Song, "Navigation and Control of Unmanned Boat via GPS", ION Technical Meeting, January 1997, pp.617-621.
- M.R.Mosavi, "Fuzzy Point Averaging of the GPS Position Components", Map Asia Conference 2004, 26-29 August, 2004, Beijing, China.
- M.R.Mosavi, "A Real-Time Precise Fuzzy Algorithm for Map Matching via GPS", Map Middle East 2005 Conference, 23-25 April, Dubai.
- Anany V.Levitin, "Introduction to the Design and Analysis of Algorithm", Addison-Wesley, 2002.