A Fastest Route Planning for LBS based on Traffic Prediction

YONG-BIN KANG, SUNG-SOO KIM

Telematics·USN Research Division
Electronics and Telecommunications Research Institute
161 Gajeong-dong, Yuseong-gu, Daejeon.
REPUBLIC OF KOREA
{ybkang, sungsoo}@etri.re.kr

Abstract: This paper proposes a new route plan on the basis of traffic prediction for finding a fastest route to a given
destination in traffic network. So far, lots of traffic prediction systems were introduced to help drivers. Previous
works were done mainly on providing restricted route services which depend on only cumulative traffic velocities.
For this reason, we consider both real-time and cumulative traffic information together to obtain more accurate
future traffic information. In location-based services, the traffic network is needed to solve certain constrains,
such as turns problems and provide method for avoiding traffic congestions. To guide a fastest route service in
such a complicated network, we first construct a linear dual graph from a traffic network. Then, we propose main
algorithmic approaches which are developed by Kalman Filter and cumulative traffic patterns to predict a much
better quality of future traffic information by combining real-time with cumulative traffic conditions. Finally,
we adopt Dijkstra’s shortest path algorithm to minimize the travel time with generating a fastest cost function.
Experimental results show that this approach is highly efficient in route plan than previously used ways by only
cumulative approaches. This approach is supposed to proceed convenience for drivers and develop a quality of
navigation service in telematics.

Key-Words: Fastest Route Planning, Traffic Prediction, Kalman Filter, Cumulative Traffic Patterns, Linear Dual
Graph, LBS

1 Introduction static information that, in general, is heavily weighted

1.1 Motivation by the only cumulative velocities. Unfortunately, as
Recently, location-based service(LBS) have been in- many drivers in traffic areas are aware, this cost model
creasingly providing a variety of services to our real- cannot entirely be appropriate for determining fastest
life, along with developments in the areas of location route, because real-time condition of routes such as
positioning, wireless communication and automotive the severity of congestion should be play an important
technologies. Also, LBS are considered to be a highly role. For this reason, it is required to provide an effec-
essential technologies in telematics services, which are tive fastest route service of truly valuable future traffic
heavily dependent on the vehicle’s location informa- information reflecting on real-time traffic conditions.
tion. In particular, navigation service in LBS must be
capable of facilitating driver’s convenience and safety
by providing more accurate traffic information of near 1.2 Related Works
future in traffic network. In addition, this service The analysis of traffic network is one of the many ap-
should continuously find and notify all the current and plication areas where the computation of shortest paths
future traffic conditions to conduct a fastest route for is one of the most fundamental problems. The route
drivers with avoiding congested areas. selection problem in traffic network involves finding
In traffic network, where the travel time changes an optimal route from a starting point to a destina-
dynamically, the correctness of the fastest route plan tion on a road map[10]. Even those traffic condi-
very much depends upon the correctness of the cost tions, such as the distribution of congestion, change
model of the route. Typical route cost model based on during driving, the route should be reevaluated before
the car reaches the next intersection. Since no “best” Real Time Traffic

algorithm exists for every kind of transportation prob- Measurement

lem on traffic network, research in this field has re- Correction for
cently moved to the design and the implementation of Missing Edges
on Traffic Network

“heuristic” shortest path algorithm[1]. Much of the fo-

cus has been on the choice and implementation of ef- Check a Variation
between Real time and Cumulative
Traffic Data
Cumulative Traffic Condition.
ficient data structures[6].
There is one more interesting related work by Chon
No
et al.[3]. Chon et al. presents a time-dependent short- Unexpected
Situations ?
Yes

est path algorithm that the trajectory of moving ob-

jects are determined by monitoring the real-time net- Traffic Prediction on the basis of
Cumulative Traffic Patterns
Traffic Prediction on the basis of
Kalman Filter
work conditions. In the study of Chon et al., they show
that the average travel time of moving objects has been Define Cost Function

markedly reduced by considering dynamically chang- Combining with Traffic Prediction

and Road Topology

ing information of moving object with variation of

time. Run Dijkstra's
Shortest Path Method.
In this paper, we do not attempt to solve or pro-
pose yet another variation of the shortest path prob-
lems. The major contribution of this work is to present Fig. 1: Overview of our proposed traffic prediction
system.
a new route plan is that based on the traffic prediction
reflecting on dynamic changing of real-time and pat-
terns of cumulative traffic information.
2 Route Planning using Linear Dual
1.3 Overview of Route Planning Graph
Major procedure for our determination of fastest route In most of traffic networks, the route planning for car
planning is as follows (see also Fig.1). navigation or public transport should consider no-left-
Step 1: Construction of a linear dual graph turn, P-turn, U-Turn and other turn problems to find
Construct a linear dual graph DT [4][9] from a minimal travel time cost. In particular, in urban en-
a given data of traffic network GT , which is vironment, turning left is often forbidden in order to
represented by schema of node and edge. DT is minimize congestions and, when allowed, traffic lights
a fundamental structure for determining fastest and counter flow cause an extra travel cost itinerary be-
route in our approach. tween two nodes.
The common approaches to handle these prob-
Step 2: Prediction of future traffic velocity lems are node expansion[8] and linear dual graph
Predict the future traffic velocity VP (t+d) , which method[4]. The node expansion approach builds up
is evaluated by real-time velocity VR(t) and the expanded network, Ge , which is obtained by high-
cumulative traffic patterns VC(t−d) at time lighting each movement in the intersections by means
t, where d denote an interval index of given of dummy nodes and edges, where the costs of the
periods of time. dummy edges are the penalties. The major disadvan-
tage of this approach is that the resulting network Ge
Step 3: Cost definition for fastest routing service
is significantly larger than the original graph G.
A cost function ω(ek ) of each edge ek in DT
Generally, a directed graph G is consists of a set of
is formed by using VP (t+d) and traffic topology
nodes N and a set of edges E connecting the nodes,
TG .
G(N, E). Given a graph G(N, E), the linear dual
Step 4: Performance of fastest route service graph D =L(G) has node set N (D) = E(G) and
Dijkstra’s shortest method is performed to edge set E(D) = {ab : a, b ∈ N (D), the head of a
guarantee the fastest route plan using ω(ek ). coincides with the tail of b}. The detail definition of a
linear dual graph is described in[8](see also Fig.2): properly calculate ω(ek ) from DT . This ω(ek ) is de-
termined with results of VC(t−d) and TG .
3 23 34

3.1 Real-Time Measurement and Correction

12 45
1 2 4
To predict the accurate traffic condition, we first mea-
5 54
sure VR(t) in GT . This measurement can be possible
25
by AVI(Automatic Vehicle Identification) systems or
G D the diffusion of car navigation devices. In the results
of these measurement, however, it may contain miss-
Fig. 2: A digraph G and its linear dual graph D =L(G) ing edges in GT which were not measured correctly.
Two kinds of missing edges can be measured accord-
In determining the performance of the approaches, ing to the extent of these edges - (a) one specific miss-
it is useful to summarize their storage requirements. ing edge and (b) all missing edges can be found in a
The node expansion method requires δmax |NG | nodes specific region.
for the primal graph G since any node n expands into Under these cases, appropriate correction processes
δ(n) nodes (where, δmax denotes maximum degree are required to be done to obtain the more suitable
of node). This method also requires the number of measurements. Correction of missing edges are made
edges in G, |EG |, plus the number of path of length by deriving the average velocity of adjacent edges ex-
2, δmax
2 |EG |[7]. The boundary node is a node which cept edges which permit U-turn for the case of (a). In
has a single-source and single-target in G. The linear the case of (b), VC(t) of all adjacent edges in a spe-
dual graph (D) method requires the number of nodes cific region are treated as the correction velocity, be-
which |EG | adds to the number of boundary nodes in cause all edges in this region are missing edges. As
G, |NG0 |. The storage requirement for the edges in D already noted, VC(t) means the cumulative traffic pat-
is the number of edges which δmax 0
2 |EG | plus |NG | (see terns, which represent a cumulative average traffic ve-
Table 1). locity at current time (t).
Fig.3 shows an example of the case of (a) that the
Method |N | |E|
δmax correction process can be applied when a missing edge
Node δmax |NG | (1 + 2 )|EG | −−−→
expansion (Ge ) obtained. Let v (a, b) be a velocity of two adjacent
Dual 0
|EG | + |NG | δmax 0 node from a toward b.
2 |EG | + 2|NG |
graph (D)
Table 1: Estimation of upper limits for node expansion and
0
linear dual graph. (NG denotes boundary nodes of a primal f
graph G and δmax denotes maximum degree of node) c
Missing Edge
a b e
Based on these facts, we adopt the linear dual graph
d
technique as a conceptual model for our route specifi-
cation on GT .
Fig. 3: An example of a missing edge and its cor-
3 Traffic Prediction rection process.
To predict VP (t+d) , we measure not only VC(t−d) sim-
ply, but through VR(t) and VC(t−d) . If VR(t) is similar It is seen from Fig.3 that the average velocity of
−−−→ −−−→ −−−→ −−−→
to that of the of regular cases then, the result of VP (t+d) those edges v (c, a), v (d, a), v (b, f ), v (b, e) is treated
will be obtained by the difference between VR(t) and −−−→
as correction velocity for v (a, b).
VC(t−d) . Otherwise, we apply a method on the basis of
Kalman Filter for finding a practically useful conver- 3.2 Detection of Unexpected Situations
gence by combining updates with VR(t) and VC(t−d) . Particularly, it should be taken notice of that unex-
To find a minimal travel time cost, it is important to pected situations(e.g., traffic congestion, road con-
struction, traffic accident) are found to accurately pro- feedback in the form of (noisy) measurements[2].
vide these situations to drivers. To find out such edges, The input to the system consists of a sequence
a comparison method between VR(t) and VC(t) was re- of unknown K-dimensional real-valued input column
quired. vectors uj (j = 1, 2, ...). A sequence of hidden N -
Let VR(t) (ek ) be VR(t) and VC(t) (ek ) be VC(t) , where dimensional real-valued state vectors xj (j = 1, 2, ...)
a connected edge ek in GT . Then, unexpected situa- are meant to represent the internal dynamics of the sys-
tions for all ek can be detected by the following ex- tem. Input vector uj and state vector xj combine lin-
pression, early to produce the next state vector:

| VR(t) (ek ) − VC(t) (ek ) | > δ , where xj+1 = Aj xm + Bj uj

sP
n 2
d=1 (VC(t) (ek ) − VC(t−d) (ek )) with a measurement z ∈ <M that is
δ =α∗
n
zj = Hxj + vj
where δ is adjusting threshold which is believed as
boundary of unexpected traffic situations and constant Aj is the N × N state transition matrix at time j and
α represent average velocity deviation within a given Bj is an N × K matrix that maps the input into the
total periods of time n. state space.
In this present work, there are two possible traffic In our research case, element values of matrix A are
prediction models will be defined differently, in the velocity values of GT . The input vectors may also be
case of when these unexpected situations appeared or interpreted as state transition noise vectors. The input
not. vector can be decomposed as Bj uj + ωj , where ωj is
possible noise. We simply exploit initial matrix A by
3.3 Traffic Prediction based on Cumulative initializing the VC(t) . The matrix M × N matrix H in
Traffic Patterns the measurement equation relates the state to the mea-
In this section, we describe the method that predict the surement zj . In practice H might change with each
future traffic condition, which is applied when a devi- time step or measurement so we adopt the average
ation between VR(t) and VC(t) can be regarded as per- value of the cumulative velocities for each road link.
mitable small. Fig.4 shows the prediction process by using Kalman
Based on the facts that have been observed so far,
traffic patterns which were classified by the same pe- Predict Future Velocity
riods of days and times have been shown quite similar
aspect. Therefore, we attempt to define the prediction
velocity on each ek at prediction time (t+d) as a future Real-Time Measurement Kalman Filter Processing Prediction Traffic Velocity
value by using the following equation,

VP (t+d) (ek ) = VR(t) (ek ) ± f (ek ), where

sP Cumulative Traffic Pattern
m 2 2
d=0 (VR(t) (ek )) − (VC(t−d) (ek ))
f (ek ) = β ∗
m Fig. 4: The process of prediction by using Kalman
filter’s iterative solution.
where β is average velocity deviation within a given
total period of time m. The result of this evaluation filter. The detailed prediction procedures are beyond
turned out to be proceed smoothly and provide desired the scope of this paper. So, we will not cover detail
prediction velocity. two steps of the Kalman filter.

3.4 Traffic Prediction based on Kalman Filter

In this section, we derive the Kalman filter as the op-
4 Fastest Route Planning
timal velocity predictor in DT for a discrete time- The route service is a network-accessible service that
varying system. The Kalman filter estimates a process determines travel routes and navigation information
by using a form of feedback control: the filter esti- between two or more points. The OpenLS route de-
mates the process state at some time and then obtains termination service is one of the OpenLS service spec-
ification for route service[5]. In this specification, the a real-time velocities and predicted in every 5 min-
route preferences are defined as follows: utes and the length of prediction time were 3 peak
(1) “Fastest” - Minimize the travel time hours(08:05 ∼ 11:05). The experimental results are ob-
tained through investigating for 4 weeks at the 95%
(2) “Shortest” - Minimize the travel distance
confidence interval.
(3) “Easiest” - Minimize the driving difficulty
AVERAGE DEVIATION OF ERROR ε(t): 5 KM
(4) “Pedestrian” - Best route by foot
M ETHOD A : 85.3%
(5) “PublicTransportation” - Best route by public M ETHOD B : 86.2%
transportation. M ETHOD C : 89.2%
In this work, we only describe “Fastest” prefer-
ence case. To provide this routing service, the weight
cost of between two adjacent nodes to be calculated. On the “Method C”, Kalman filter was applied when
The cost function was defined by using VP (t+d) (ek ), ε(t) > 10km and more accurate results are obtained
which indicates predication traffic velocity of (ek ), comparing with “Method A” and “Method B” as can be
road classes ck and the number of traffic-lane m. seen the above results. Fig.5 shows the corresponding
Thus, the cost function of (ek ) can be expressed by results of our experiments, which illustrates the rates
the following expression, of edges(0 ∼ 25%) in the average deviation of errors
ω(ek ) = ck · λ, where between the actual and the prediction velocities(1km
1 ∼ 20km).
λ= ,0 < λ ≤ 1
VP (t+d) (ek ) · m 25

Method using cumulative traffic data

Method using real-time and cumulative traffic data 20

After then, Dijkstra algorithm is conducted to search
The number of edges/Total number of edges(%)

Method using real-time and cumulative traffic data(with

fastest path on DT .
Kalman filter applied)

15

5 Experiment
In order to evaluate the accuracy of the proposed ap-
10

proach, we performed a comparative analysis on an ac-

tual traffic network, Kang-Nam area where consists of 5

about 10,000 nodes in Seoul, Korea. In this experi-

ment, accumulated data which include cumulative traf- 0

fic velocities were prepared for six months. The three 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

The average deviation of errors between the actual and the prediction velocities
19 20

prediction method was evaluated for comparative anal- (km)

ysis as follows:
(1) “Method A” - by the only cumulative traffic data Fig. 5: Comparison results of the three prediction method.
(2) “Method B” - by the real-time and the cumulative traffic
data As you can see in this graph, the rates for “Method
C” were always at higher level(about 12%, 23%, 17%)
(3) “Method C” - by the real-time and the cumulative traffic
data(with Kalman filtering) than the others, “Method B”(about 8%, 23%, 12%) and
To analyze the accuracy of these cases, the average “Method A”(about 4%, 18%, 16%) between 1km to 3km,
deviation errors on all the edges are given by the fol- during the lowest scope of errors, while nearly the
lowing expression, same for the rest of scope of errors(4km ∼ 20km).
Pn These indicate that the rate of edges for “Method C”
| VR(t) (ek ) − VP (t) (ek ) |
ε(t) = k=1 gives us minimal deviation error between the actual
n
and prediction velocities and can provide higher trust-
, which denotes a average value of the difference be- worthy prediction model than the two others, “Method
tween the actual and the prediction velocity at time t. A” and “Method B”. Fig.6 shows a snapshot from nav-
We measured a traffic network in every 5 min- igation device, providing traffic prediction service that
utes intervals during hours(08:00 ∼ 09:00) to obtain was proposed by our approach. The traffic prediction
service flow is that firstly, a user selects traffic predic- vices of LBS solution and telematics.
tion service menu during the navigation and then a user
sets desirous future time for traffic prediction service, References:
finally, the user can preview the result of predicted traf- [1] Chang Wook Ahn, R. S. Ramakrishna, A Ge-
fic information as texts or on the map. netic Algorithm for Shortest Path Routing Prob-
lem and the Sizing of Populations, IEEE Trans-
preview
on action on Evolutionary Computation, pp. 566-
map
579, Vol. 6, No. 6., 2002.
D

[2] Greg Welch et al., An Introduction of the

Kalman Filter, The SIGGRAPH 2001 Course
A
begin
navigation
C set
E preview
on
Note 8, 2001.
service prediction
time text

select traffic
prediction
[3] H. D. Chon, D. Agrawal and A. E. Abbadi, FAT-
service
EST:Finding A Time dependent Shortest Path,
B Proceedings of the 4th International Confer-
ence on Mobile Data Management, 2003.
[4] J. Anez, T. de la Barra, B. Perez, Dual
Fig. 6: A snapshot of navigation device simulated Graph Representation of Transport Networks,
with our approach. In Transportation Research, Vol. 30, No. 3, pp.
209-216. 1996.
From these experimental results, we expect that
our proposed method could be efficient for future traf- [5] OpenLS Initiative, OpenLS Route Determina-
fic prediction and can be integrated with conventional tion Service Specification, OpenGIS Interoper-
method. ability Program Report (OGC 02-090), Open
GIS Consortium Inc., 11 November 2002.

6 Conclusion [6] Stefano Pallottino, Maria Grazia Scutella,

In this paper, we propose a new route plan to guide Shortest Path Algorithms in Transportation
a fastest route from a given destination, which based Models: Classical and Innovative Aspects,
on future traffic prediction. The data structure of lin- Technical Report, Univ. of Pisa, 1998.
ear dual graph is our primal graph that permit to min- [7] Stephan Winter, Weighting the Path Continua-
imize travel time cost and solve the turn problem that tion in Route Planning, In Proceedings of 9th
may be occurred at the intersection area. To predict ACM International Symposium on Advances in
the future traffic condition, we first measured real-time Geographic Information Systems, pp. 173-176,
traffic condition for reflecting on dynamic changing of 2001.
current traffic flows. The traffic prediction model on
the basis of real-time and cumulative traffic patterns [8] Stephan Winter, Route Specifications with a
was proposed to provide more realistic and accurate Linear Dual Graph, In Proceedings of Advances
traffic information to drivers. If the measured real- in Spatial Data Handling, pp.329-338, 2002.
time velocity was permitted within satisfiable thresh-
[9] Stephan Winter, Modeling Costs of Turns in
old, traffic prediction was determined by adopting the
Route Planning, GeoInformatica, Vol. 6, No. 4,
cumulative traffic patterns. Otherwise, Kalman filter-
pp. 345-360, 2002.
ing method was adopted in case of the traffic conges-
tion or unexpected circumstances. The results of our [10] T. Nakamura et al., Head Start Route Select-
works are supposed to provide driver with truly valu- ing Algorithm for Reducing Driver’s Waiting
able traffic information of near future. Furthermore, Time, The Second World Congress on Intelli-
this work may also be extended to the fields in the ser- gent Transport System, pp.2031-2036, 1995.