Published on Sep 03, 2023
This paper presents a smart driving direction system leveraging the intelligence of experienced drivers. In this system, GPS-equipped taxis are employed as mobile sensors probing the traffic rhythm of a city and taxi drivers’ intelligence in choosing driving directions in the physical world. We propose a time-dependent landmark graph to model the dynamic traffic pattern as well as the intelligence of experienced drivers so as to provide a user with the practically fastest route to a given destination at a given departure time.
Then, a Variance- Entropy-Based Clustering approach is devised to estimate the distribution of travel time between two landmarks in different time slots. Based on this graph, we design a two-stage routing algorithm to compute the practically fastest and customized route for end users. We build our system based on a real-world trajectory data set generated by over 33,000 taxis in a period of three months, and evaluate the system by conducting both synthetic experiments and in-the-field evaluations. As a result, 60-70 percent of the routes suggested by our method are faster than the competing methods, and 20 percent of the routes share the same results. On average, 50 percent of our routes are at least 20 percent faster than the competing approaches.
The efficient driving directions has become a daily activity and been implemented as a key feature in many map services like Google 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). Therefore, 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 taxi cabs traversing in urban areas.
· That is, we cannot answer user queries by directly mining trajectory patterns from the data. Therefore, how to model taxi drivers’ intelligence that can answer a variety of queries is a challenge
· We cannot guarantee there are sufficient taxis traversing on each road segment even if we have a large number of taxis.
· That is, we cannot accurately estimate the speed pattern of each road segment
The preprocessed taxi trajectories, we detect the top-k frequently traversed road segments, which are termed as landmarks. The reason why we use “landmark” to model the taxi drivers’ intelligence is that: first, the sparseness and low-sampling rate of the taxi trajectories do not support us to directly calculate the travel time for each road segment while we can estimate the traveling time between two landmarks (which have been frequently traversed by taxis).Second, the notion of landmarks follows the natural thinking pattern of people.
The threshold is used to eliminate the edges seldom traversed by taxis, as the fewer taxis that pass two landmarks, 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 landmark is very long. Such kinds of edges would not only increase the space complexity of a landmark graph but also bring inaccuracy to the travel time estimation.
· The almost share similar traffic patterns while the weekdays and week end shave different patterns. Therefore, we build two different landmark graphs for weekdays and weekends, respectively.
· The travel times of transitions pertaining to a land mark edge clearly gather around some values (like a set of clusters) rather than a single value or a typical Gaussian distribution, as many people expected.
· This aims to handle the situation that a taxi was stuck in a traffic jam or waiting at a traffic light where multiple points may be recorded on the same road segment
1. Intelligence modeling
2. Low Sampling Rate Problem
3. The Landmark Graph
4. Route Generation
5. Path logging
6. Route Computing
A user can select any place as a source or destination, there would be no taxi trajectory exactly passing the query points. That is, we cannot answer user queries by directly mining trajectory patterns from the data. Therefore, how to model taxi drivers’ intelligence that can answer a variety of queries is a challenge.
To save energy and communication loads, taxis usually report on their locations in a very low frequency, like 2-5 minutes per point. This increases the uncertainty of the routes traversed by a taxi. As shown in there could exists four possible routes.
To save energy and communication loads, taxis usually report on their locations in a very low frequency, like 2-5 minutes per point. This increases the uncertainty of the routes traversed by a taxi. Meanwhile, we cannot guarantee there are sufficient taxis traversing on each road segment anytime even if we have a large number of taxis. That is, we cannot directly estimate the speed pattern of each road segment based on taxi trajectories.
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 route at 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 trajectory, 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.
According to the departure time, start and destination point, the cloud chooses a proper land mark graph considering the weather information and whether it’s a holiday or a workday. Based on the landmark graph, a two-stage routing algorithm is performed to obtain a time-dependent fastest route
System : Pentium IV 2.4 GHz.
Hard Disk : 40 GB.
Monitor : 15 VGA Colour.
Mouse : Logitech.
Ram : 512 Mb.
Mobile : Android Mobile
Operating system : Windows XP.
Coding Language : Java 1.6
Tool Kit : Android 2.2
IDE : Eclipse
