ISSN ONLINE(2320-9801) PRINT (2320-9798)

TAKE DIVERSION Driving Directions with Taxi Drivers Intelligence

Dr.J.Subashchandra Bose, S.Mohan Raj, Karthikeyan.T, Devaneyan.P, Kannan.M, Dharanikumar.S
  1. Professor and Head, Professional Group of Institutions, Palladam, Tamilnadu, India
  2. Assistant Professor, Professional Group of Institutions, Palladam, Tamilnadu, India
  3. Department of Computer Science Engineering, Professional Group of Institutions, Palladam, Tamilnadu, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Computer and Communication Engineering


This paper presents a smart driving system by using the GPS enabled taxis and auto rixas. The GPS devices will update the vehicles positions with a specific period of time. The samples are taken for 2 - 3 months. We are using a routing algorithm to calculate the shortest and optimized path. The common problem in Indian road system was poor road direction and qualities and PWD works also interrupting the daily users travelling time. Users don't know where the PWD works are going on and when will it finished, we are going to propose a solution for the problem by using the backtrack algorithm. Our application will alert the user if there is any PWD work is going in the user’s destination path. Our backtracking algorithm will provide an optimized route for the user as an alternative path. If the PWD works was done the application will update itself. The PWD work updates were done by the staff at PWD or somebody else. For India this application will provide a smart solution for our worst road system.


Back-Tracking, data mining, GPS, driving directions, driving behavior, PWD.


Finding efficient driving direction has become a daily activity and been implemented as a key feature in many maps in Google map and Bing maps. A fast driving route saves not only the time of a driver but also energy consumption (as most gas is wasted in traffic jams). There- fore, this service is important for both end users and governments aiming to ease traffic problems and protect environment.
Essentially, the time that a driver traverses a route depends on the following three aspects:
1) The physical feature of a route, such as distance, capacity (lanes), and the number of traffic lights as well as direction turns;
2) The time-dependent traffic flow on the route; and
3) A user’s driving behavior. Given the same route, cautious drivers will likely drive relatively slower than those preferring driving very fast and aggressively. Also, users’ driving behaviors usually vary in their progressing driving experiences. For example, traveling on an unfamiliar route, a user has to pay attention to the road signs, hence drive relatively slowly. Thus, a good routing service should consider these three aspects (routes, traffic, and drivers), which are far beyond the scope of the shortest/fastest path computing. Usually, big cities have a large number of taxicabs traversing in urban areas. For efficient taxi dispatching and monitoring, taxis are usually equipped with a GPS sensor, which enables them to report their locations to a server at regular intervals, e.g.,2-3minutes.Thatis,alotofGPS- equipped tax is already exist in major cities, generating a huge number of GPS every day. Intuitively, taxi drivers & auto rixas drivers are experienced drivers who can usually find out the fastest route to send passengers to a destination based on their knowledge (we believe most taxi drivers are honest although a few of them might give passengers around about trip).When selecting driving directions, besides the distance of a route, they also consider other factors, such as the time- variant traffic flows on road surfaces, traffic signals and direction changes contained in a route. These factors can be learned by experienced drivers but are too subtle and difficult to incorporate into existing routing engines. Therefore, these historical taxis, which imply the intelligence of experienced drivers, provide us with a valuable resource to learn practically fast driving directions. The public work or nature disasters may divert the normal direction. But we can avoid them by proper updating from the particular area representatives through corporation help. Here we are going to use BACK TRACKING algorithm to achieve this solution.


In practice, to save energy and communication loads, taxis usually report on their locations in a very low frequency, like 2-5minutes per point. This increases the uncertainty of the routes traversed by a taxi [3],[4].Meanwhile, we cannot guarantee there are sufficient taxis reversing each road segment any time even if we have a large number of taxis. That is, we cannot directly estimate the speed pattern of each road segment based on taxis. In our method, we first partition the GPS log of a taxi into some taxi representing individual trips according to the taxi meter’s transaction records. There is a tag associated. If that taxi’s reporting when the taxi meter is turn on or off, i.e… a passenger get on or off the taxi. Then, we employ our IVMM algorithm [4], which has better performance than existing map-matching algorithms when darling with the low-sampling rate. This algorithm utilizes these partial temporal restrictions to obtain candidate road segments, then considers the mutual influences of the GPS points to calculate static/dynamic score matrix for and perform savoringbased approach among all the candidates. As a result, each taxi is converted to a sequence of road segments. The threshold is used to eliminate the edges seldom traversed by taxis, as the fewer taxis that pass two land- marks, the lower accuracy of the estimated travel time (between the two landmarks)could be. Additionally, we set the Tmax value to remove the landmark edges having a very long travel time. Due to the low-sampling rate problem, sometimes, a taxi may consecutively traverse three land- marks while no point is recorded when passing the middle (second) one. This will result in that the travel time between the first and third land mark is very long. Such kinds of edges would not only increase the space complexity of a landmark graph but also bring in accuracy to the travel time estimation (as a farther distance between landmarks leads to a higher uncertainty of the traversed routes).We use the frequency instead of the support of a landmark edge (to guarantee efficient transitions) because we want to eliminate the effect induced by the scale of the archive.
We observe (from the taxi) that different weekdays (e.g., Tuesday and Wednesday) almost share similar traffic patterns while the week days and weekend shave different patterns. Therefore, we build two different landmark graphs for week days and weekends, respectively. That is, we project all the weekday (from different weeks and months)into one weekday landmark graph, and put all the week end in to the week end landmark graph. We also find that the traffic pattern varies in weather conditions. Therefore, we respectively build different landmark graphs for week day and weekend, and for normal and severe weather conditions, like storm, heavy rain, and for a road segment(r10).This aims to handle the situation that a taxi was stuck in a traffic jam or waiting a at traffic light where multiple points may be recorded on the same road segment(although the taxi driver only traversed the segment once).After the detection of landmarks, we convert each taxi from a sequence of road segments to landmark sequence, and then connect two landmarks with an edge if the transitions between these two landmarks conform to (supposing in this example).

2.1Travel Time Generation

In this step, we aim to automatically partition time of a day into several slots (for different landmark edges) according to the traffic conditions reflected by the raw samples pertaining to a land mark edge. Then, west in ate the travel time distribution of each time slot for each landmark edge.

2.2Route Generation

Besides the traffic condition of a road, the travel time of a route also depends on drivers. Sometimes, different drivers take different amounts of time to traverse the same rout eat the same time slot. The reasons lie in a driver’s driving habit, skills and familiarity of routes. For example, people familiar with a route can usually pass the route faster than a new comer. Also, even on the same path, cautious people will likely drive relatively slower than those preferring to drive very fast and aggressively.


The cloud sends the computed driving routes along with the travel time distributions of the landmark edges contained in the driving route to the phone. Later, the mobile phone logs the user’s driving path with a GPS data, which will be used for recalculate the user’s custom factor. The more a driver uses this system, the deeper this system under stands the driver;
Hence, a better driving direction services can be provided

3.1 Route Calculation

For evaluating the effectiveness of the routes suggested by different methods (say methods A and B), we use the following two criteria: FastRate1 (FR1) andFastRate2 (FR2) Number A’s travel time <B0s travel time
Landmark graph to estimate the travel time of a route by mapping the users’ to the landmark graph (detailed in[1]).driving routes recorded in GPS . Here, their custom factors gradually stabilize after the mobile client processed10times of the same route for them .Meanwhile, the error of travel time, measured by MAPE, shows a downward trend with the increasing number of routes processed until reaching10.Clearly, the two users have different custom factors tuned indifferent ways.


Public Work Department is the one of the impartment department in India. It take cares the road transportation and underground cabling, drainage system implementation and maintenance. Indian roads are basically very poor because of often other works in road. The roads are drilled and not proper maintenance. So that the passengers are affected by this in rainy season more rather than other season. TAKE DIVERSION is the very familiar word for traffic police and passengers. Always we miss our punctuation because of this, workers get delay by and students miss their valuable class. According Sensex 47% of late happen by this.
We have suggestion to solve this problem by algorithm called BACKTRACKING which is used to solve problems software field most of the problems.


Backtracking is a general algorithm for finding all (or some) solutions to some computational problem that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

4.2 Pseudo code

In order to apply backtracking to a specific class of problems, one must provide the data P for the particular instance of the problem that is to be solved, and six procedural parameters, root, reject, accept, first, next, and output. These procedures should take the instance data P as a parameter and should do the following:
root(P): return the partial candidate at the root of the search tree.
reject(P,c): return true only if the partial candidate c is not worth completing.
accept(P,c): return true if c is a solution of P, and false otherwise.
first(P,c): generate the first extension of candidate c.
next(P,s): generate the next alternative extension of a candidate, after the extension s.
output(P,c): use the solution c of P, as appropriate to the application.
The backtracking algorithm reduces then to the call bt(root(P)), where bt is the following recursive procedure:
ifreject(P,c) thenreturn
ifaccept(P,c) thenoutput(P,c)
s ← first(P,c)
whiles ≠ Λ do
s ← next(P,s)


This paper describes a system to find out the practically fastest route for a particular user a taxi given departure time. Specifically, the system mines the intelligence of experienced drivers from a large number of taxis, auto rixas and provides the end user with a smart route, which incorporates the physical feature of a route, the time-dependent traffic flow as well as the users’ driving behaviors. This paper saves the people’s valuable time and money.


[1] J.Yuan, Y. Zheng C .Zhang, W. Xie, G. Sun, H.Yan, and X. Xie , “T-Drive: Driving Directions Based on Taxi ,”Proc.18th SIGSPATIALInt’l Conf. Advances in Geographic Information Systems(GIS),2010.

[2] T. Hunter, R. Herring, P. Abbeel , and A.Bayen,“Path and Travel Time Inference from GPS Probe Vehicle Data,” Proc. Neural Information Processing Systems(NIPS),2009.

[3] Y. Lou, C. Zhang, Y. Zheng, X. Xie, W. Wang, and Y.“Map-Matching for Low-Sampling-Rate GPS ,” Pros .Int’l Conf. Advances in Geographic Information Systems (GIS),2009.

[4] J. Yuan, Y. Zheng , C. Zhang ,and X. Xie,“An Interactive Voting Based Map Matching Algorithm,” Proc. Int’l Conf. Mobile Data Management (MDM), 2010.

[5] E. Kanoulas, Y. Du, T. Xia, and D. Zhang , “Finding Fastest Paths on a Road Network with Speed Patterns,” Proc. Int ’l Conf. Data Eng.(ICDE),2006.

[6] A. OrdaandR. Rom, “Shortest-Path and Minimum-Delay Algorithms in Networks with Time-Dependent Edge-Length,” J.ACM,vol.37,no.3,pp. 607-625,1990.

[7] N. Leibowitz, B. Baum, G. Enden, and A. Karniel, “ The Exponential Learning Equation as a Function of Successful Trials Results in Sigmoid Performance,” J.Math. Psychology,vol.54, no.3,pp.338-340,2010.