Link

Shivani (@Shivani-15)

Design your own Google Map Pathfinder

Table of Contents

  1. Introduction
  2. Stored Data
  3. Preprocessing
  4. Computing Quickest/Shortest Path
  5. Efficiency and Feasibility
  6. References
  7. Conclusion

Introduction

Maps and other informations are provided by various private firms and government organisations. Data abstracted from them is stored in graph database management system. The maps are stored in the form of vector graphics. GPS gives the real time traffic conditions. Real time information achieved from various sources (google maps users, satellites etc.) is combined to give the best results. Some features are tried to cover in this design.

Stored Data

Maps are stored in the form of Vector Tiles which are small chunks of map. The are woven together and displayed. Since all the roads, landmarks or places can be displayed as lines, curves or some sorts of shapes, real images need not to be stored. This saves a lot of space.

- Native Graph Database Management System is used to store data of surface across the globe. It’s perhaps the best way to store complex and dynamic relationships in connected data. New routes/roads develop over time, so it will be easy to update the database. Moreover, it will be easy to store information about roads as the properties of edges.

  1. Nodes - Nodes have the location (latitude, longitude) of the place. Roads are either curvy or straight. Curvy roads are divided into ver small parts so that they almost become straight lines. The end points of each straight road are made a node with no label. Other public places are made nodes with labels. It has properties in the form of (name/value pairs).
    • Name: Name of the place.
    • Address: Address of the place.
  2. Labels - Labels store the information about places which are helpful in categorizing them. User can easily get results for particular searches (e.g. hospitals, petrol pumps, water body, etc.) on his/her way. For junctions, a label ‘junction’ is added.
  3. Relations - Relations hold the information about the road between two nodes, i.e., Number of Lanes and Quality factor.

Demonstartion (Random):

image

DATA TYPES :

  1. Location: Set where values are decimal.
  2. Name, Address and Label: Characters.
  3. Lane : Integer.
  4. Quality factor: Decimal.

** Data for RAILWAY ROUTE/BUS ROUTE is stored in Tables consisting of rows and columns.**

Columns Data Types

  1. Location (Latitude/Longitude) of starting point and destination.— Set of decimal values.
  2. Time of departure and arrival at stations.— Time.
  3. Name of train/bus (if any).— Character.
  4. Train number or bus number (if any).— Character.
  5. Non-functioning days (if any).— Character.
  6. Platform number (in case of trains).— Character.

Preprocessing

For finding the quickest/shortest path, we do not need all the nodes stored. So we need to filter the data stored. All the nodes with label ‘junction’ are chosen between the starting and final locations and also of limited surrounding areas. Weight of the edges is calculated with the help of formula discussed in the next section. If the user wishes to locate any nearest public place, nodes with that label will also be chosen.

Computing Quickest/Shortest Path

In some situations, minimum time taking route is preferred while shortest distance route in other cases.

For shortest distance:

The algorithm being used is A* algorithm . At every node, we calculate two parameters for all the connected nodes, g and h, where g is the distance between the starting point and the current node and h is the heuristic distance between current node and the final node.

		f = g+h Node with the least value of f is chosen at every step. To calculate h, we use euclidean distance since the roads can be leading towards any direction.

	Euclidean distance (h)= ((xf – x)2 + (yf – y)2)1/2
				where (x , y) – (latitude , longitude) of current node
					(xf , yf) – (latitude , longitude) of final node

Minimum time taking route:

For minimum time taking route, h can not solely depend on distance. It involves other factors like quality of road, less number of turns and traffic at that time. But, even g cannot be accurate for time. More or less, it will also be an estimate. So, djikstra algorithm is used to calculate the minimum time taking route. Factors taken into consideration to calculate the weight of each node.

Traffic factor- Traffic factor is assigned according to the traffic conditions. 0 for clear roads, 0.5 for moderate traffic and 1 for heavy traffic. Time taken by the chosen vehicle to cross the unit traffic area is added.

Road quality factor- Roads are assigned a quality factor ranging from 0 to 1 by which the time taken to travel through it is increased due to its poor quality. For each vehicle, a threshold quality factor qo is there, below which the road is not safe for that vehicle. If the quality factor is less than it, that node is discarded .

Acceleration and deacceleration time- For taking a turn, vehicles have to accelerate and decelerate which takes time. So for each turn, twice of deceleration time of that vehicle is added.

	h = (d- u – v - w)/(s*q1) + w/(s*q2) + u*th + v*tm  + n*2*td where h is the weight of node\  d is the distance between nodes\  u is the distance which has heavy traffic\  v is the distance which has moderate traffic\  w is the distance of clear road which has quality factor q2, , while the remaining clear road has quality factor q1 .\  n is the number of turns\  td is the deacceleration time\

Traffic

Deceleration

Then, Djikstra’s algorithm is applied. For moderate and heavy traffic areas, quality factor is not taken into consideration because it does not has much effect. It is still an estimate because factors like tolls and traffic lights are not taken into consideration.

Computation time:

Though Djikstra’s algorithm is time consuming but it will give accurate results. For a* algorithm, predicting the time for different routes will be difficult at any junction (node) since factors like traffic will depend on the edge we choose later. Or since the route is not known, it will be difficult to predict time. (I couldn’t think of a way to make an estimate).

Time/ Accuracy trade off:

For finding shortest route, we can also use djikstra’s algorithm which will be more accurate than A* algorithm but will increase the computing time by a big factor. We can attain more accuracy for finding quickest path if the time expected gets updated with the change in speed of the vehicle (which can be obtained through gps) thus increasing the computation time.

Rerouting:

If a wrong turn is taken, the new position will be made the source node and the calculations will be made again but it will be time consuming.

Efficiency and Feasibility

  • It has been tried to keep a balance between accuracy and time but djikstra’s algorithm is not that effecient and will consume much time though we have reduced the nodes/junctions covered.
  • Most probably, it will work on the scale of globe but it will not be that effecient for long routes , it will take much time.

References

[1].(55) How does Google Map work and gather data? - Quora [3].Graph Databases for Beginners: Why Graph Technology Is the Future [4].Global Practices on Road Traffic Signal Control: Fixed-Time Control at … - Keshuang Tang, Manfred Boltze, Hideki Nakamura, Zong Tian - Google Books - A study of time taken by vehicles to deccelerate and cross heavy traffic areas. [5].https://www.geeksforgeeks.org/a-search-algorithm/ [6].https://en.wikipedia.org/wiki/Vector_tiles