# Discovering Congested Routes Using Vehicle Trajectories in Road Networks

Authors: Kyoung Soo Bok; He Li; Jong Tae Lim; Jae Soo Yoo
Journal: Advances in Multimedia
 (2015)

---

## Abstract

The popular route recommendation and traffic monitoring over the road networks have become important in the location-based services. The schemes to find out the congested routes were proposed by considering the number of vehicles in a road segment. However, the existing schemes do not consider the features of each road segment such as width, length, and direction in a road network. Furthermore, the existing schemes fail to consider the average moving speed of vehicles. Therefore, they can detect the incorrect density routes. To overcome such problems, we propose a new discovering scheme of congested routes through the analysis of vehicle trajectories in a road network. The proposed scheme divides each road into segments with different width and length in a road network. And then, the congested road segment is detected through the saturation degree of the road segment and the average moving speed of vehicles in the road segment. Finally, we compute the final congested routes by using a clustering scheme. The experimental results have shown that the proposed scheme can efficiently discover the congested routes in the different directions of the roads.


---

## Body

## 1. Introduction

Recently, with the increase of the use of mobile devices, the location-based services are becoming increasingly popular. Since the rapidly increased satellites and GPS (global position system) technologies have developed, it is possible to collect a large amount of trajectory data of moving objects such as the vehicle position data, hurricane track data, and animal movement data [1–4]. The analysis over these trajectory data is becoming important for many applications, such as meteorological observation and forecast, animal habits observation, road traffic situation analysis, and navigation in transportations [5–9]. According to the recorded trajectory data and road networks, the moving pattern, traffic situation, and road recommendation services can be supported [1, 2, 10–12].Recently, with the continuously increasing vehicles, the route recommendation service is becoming more and more important [1, 4, 7, 8, 13–15]. For road network based applications, the mobility of the vehicle is road network constrained. Most of the existing schemes try to monitor and forecast the traffic by using the recorded history trajectory data of vehicles equipped with GPS devices. The index based schemes construct an index by adopting the trajectory data of the vehicles [5, 6]. And then the routes are recommended according to the history trajectory data of the related vehicles. The clustering based schemes generate the density routes of the road networks by analyzing the trajectory data of vehicles [9, 13, 16, 17]. Reference [1] proposed the MPR scheme for discovering the popular route between two locations by observing the traveling behaviors of many previous users. Reference [18] studied the problem of finding reasonable alternative routes in road networks. In NETSCAN scheme [13], the density routes of the road networks are evaluated by considering both the location and time of the vehicles.According to the trajectory data, the number of the vehicles within a specific road segment and time period can be used to identify the density routes of a road. However, the existing schemes are not suitable for real road networks. There are three major problems of the existing schemes: (1) the directions of the roads in the road networks are not considered; (2) the widths and lengths of the road segments are not considered; and (3) the average moving speed of vehicles within a road segment is not considered. In the real road network environments, each road is divided into two directions: positive direction and negative direction. The vehicles in the road toward different directions do not affect each other. Therefore, the congested routes are inaccurate if the directions of the road are not considered. The width and length of each road segment are different in a road network, which will also affect the accuracy of the congested routes. Furthermore, the average moving speed of vehicles within a road segment can identify the congestion of the road.To overcome these problems, we propose a congested routes discovering scheme, in which the directions, width, and length of roads are considered for congested route discovering in real road network environments. The proposed scheme divides the roads into segments with different widths and lengths. And then, the congested road segments are extracted by considering the average moving speed of the vehicles and the saturation degree of each road segment in the road networks. Finally, we perform clustering schemes to compute the final congested routes in the whole road networks.The remainder of the paper is organized as follows. We will discuss related work in Section2. Section 3 presents the details of the proposed scheme. Section 4 contains experimental evaluation that demonstrates the superiority of our proposed scheme. Finally, Section 5 concludes this paper.


## 2. Related Work

Discovering hot routes or popular routes is a very important technique to support location-based service in road network. Reference [1] studied the discovering scheme of the most popular route (MPR) between two locations by observing the traveling behaviors of many previous users. Reference [1] presented an algorithm to establish the transfer network model for a collection of historical trajectories and utilized the absorbing Markov chain model to derive the transfer probability for transfer nodes. Maximum probability product algorithm is used for discovering the MPR from a transfer network based on the popularity indicators in a breadth-first scheme. Reference [16] defined a hot route which is a general path in the road network containing heavy traffic and studied the discovering scheme of hot routes. Reference [16] proposed a new density-based algorithm called FlowScan. It is a robust algorithm that can handle the complexities in the data and was verified through extensive experiments. Instead of clustering the moving objects, road segments are clustered based on the density of common traffic they share. Reference [15] studied the problem of vehicular traffic density estimation, utilizing the information cues present in the cumulative acoustic signal acquired from a roadside-installed single microphone.Vehicles which are located in a congested area try to move to a noncongested area. Reference [10] proposed a route discovery method for alleviating traffic congestions to provide a driving route whose trip time becomes short. The proposed method does not need global traffic information but regional traffic information for each vehicle. The vehicle calculates a route for a destination where a summation of evaluation values for roadway segments in the route becomes minimal. Given a spatial range and a user preference of depth/breadth specified by a user, [11] processed a pattern-aware trajectory search (PATS) to retrieve the top K trajectories passing through popular ROIs. PATS support trip planning without requiring prior knowledge of ROIs in the specified spatial range. PATS used a user movement graph to capture travel patterns hidden in trajectories and develop an algorithm to determine the attractive scores of the ROIs and proposed an algorithm BTS for efficiently retrieving the top K trajectories.Reference [19] proposed a fast path algorithm of finding the best shortest paths in the road network to solve the path planning problem in route guidance systems in terms of accuracy and speed. Reference [20] proposed an adaptive fastest path algorithm capable of efficiently accounting for important driving and speed patterns mined from a large set of traffic data. Reference [20] presented a routing algorithm which uses the road hierarchy and precomputed areas to limit the search space. This improves trip duration by using upgraded roads whenever beneficial and finds routes that take into consideration both speed and driving patterns.Reference [13] proposed a scheme for discovering dense routes by clustering similar road sections according to both traffic and location in each time period. Reference [13] presented NETSCAN which carries out the clustering of dense sections and incorporates them by forming dense routes. NETSCAN cluster the road sections based upon the network density statistics. This clustering takes into account the orientation of the trajectory. Besides, this method utilizes the network topology to create relevant clusters. To propose a model to assess the evolution for dense route pairs at two consecutive time intervals, DENSITYLINK algorithm is presented. DENSITYLINK allows the characterization of the evolution of the dense road network. Reference [17] proposed a time-based clustering algorithm called Tk-means that adapts the k-means algorithm for trajectory data. Tk-means cluster the objects based on the time intervals of different trajectory’s motions. If an object spans different time intervals, it will eventually belong to different clusters. Tk-means used two approaches, an exact method and an approximate method. The exact method computes the actual clusters visited by the object throughout its life time and the approximate method exactly computes some of the actual visited clusters and, based on those computed clusters along with the clusters generated from the remaining data set, it predicts the future motion pattern of the query object.


## 3. The Proposed Scheme

### 3.1. Data Model

We assume that the road network is represented by a graphG(N,E), where N denotes the node which is the intersection between different road segments and E denotes the edge which is used to connect two adjacent nodes in the road network. The trajectory of a vehicle is represented by Tr. Each node Ni in the road network is represented by a point {xi,yi}. Ei denotes a segment of the road network. “+” and “−” are used to represent the different directions of vehicles in a road network. Moreover, since the length and the number of lane of each road are different, the length and width of each road segment are stored. Therefore, each road segment is represented by Si(±) = {Ni, Nj, length, width}, where length is the length of a road segment and width is the number of traffic lanes. As shown in Figure 1, S2 and S3 are the neighbor segments of S1 in a road network G.Figure 1
The data model of road network.In a road networkG, each road segment Si stores the information of its directly connected road segments. This information is used for the following clustering evaluations. Since the vehicles may move continuously or stay in a position, it is necessary to have the location knowledge of each vehicle according to the timestamps. Suppose that the trajectory Tr of each vehicle is as follows:(1)Trn=S1±,T1,S2±,T2,…,Sk±,Tk,where Si denotes the segment ID and Ti is the timestamp. According to Ti, the location of each vehicle can be retrieved easily.


### 3.2. Congested Road Segment

The initial road information and trajectory data can be used to determine the existence of vehicles in each road segment of different directions. The complexity value of each road segment is evaluated. The road segment is considered as congested region if the evaluated complexity value is higher than the predefined threshold value. The clustering algorithm is performed among congested road segments. The road segments with low moving speed and high number of vehicles are determined as congested road segments. Figure2 shows the procedure of computing congested routes.Figure 2
The procedure of computing congested routes.In this paper, the congested road segments are computed according to the different directions of the roads. The location and direction of each vehicle can be retrieved from the recorded trajectory data. The complexity value of each road segment is computed by considering the average speed of the vehicles in the road segment and the saturation degree of the road segment. The fast moving speed indicates that the congestion of the road segment is low. In contrast, the low moving speed indicates that the congestion of the road segment is high. The saturation degree is computed based on the number of the vehicles within a road segment and the length and width of a road segment, which are indicated in Figure3. We define that the congested road segments within a road network are the road segments with high complexity values.Figure 3
The road segment between nodesN1 and N2 in a road network.The average moving speed(Av) of the vehicles in a road segment according to different directions is computed by the following equation (2), where V(Obi) denotes the moving speed of a vehicle Obi. The saturation (Sat) according to the width (Swidth) and length (Slength) of a road segment is computed in (3), where Obn denotes the number of the vehicles in a road segment. As a result, the complexity value of a road segment is computed by (4) which combines (2) and (3); α denotes the weight value between the average moving speed of vehicles and the saturation of a road segment. Consider(2)Avi±=∑i=1nVObiObn±×Vmax,(3)Sati±=1-Obn±Swidth×Slength,(4)Rii±=α×Avi±+1-α×Sati±.


### 3.3. Congested Routes Detection

In this section, we present the algorithm of congested routes detection. The algorithm operates in two phases. In the first phase, the complexity value of each road segment in the road network according to different directions is computed. In the second phase, the congested routes of a road network are evaluated by clustering the congested road segments with each time interval. When the complexity value of a road segment is larger than the predefined threshold value, the road segment is considered as a congested road segment. Finally, the congested road segments with same direction are clustered together. Algorithm1 shows the congested routes detection algorithm.Algorithm 1:The algorithm of the proposed scheme.
Congested routes detection algorithm
Input:
Set of road segment listS={S1,S2,…,Sn+1}
Set of trajectoryTr⁡={Tr⁡1,Tr⁡2,…,Tr⁡n}
Set of time intervalT={T1,T2,…,Tn}
Thresholdβ—trajectory velocity and road weight
Output:
Thresholdα—road density
Set of cluster groups CH = {CH1, CH2,…, CHn}
CH← Initialization
for every time intervalt
while there exist Tr in segment listS
for each satisfiedα in S
segmentS = create candidate c
end for
if exist neighbor segmentN in candidate c
create CH← extend from c to N
else if
create CH← candidate c
end if
end while
end forSince the complexity values of road segments are changed according to different timestamps, they have to be computed periodically. The congested routes of a road network are computed according to the complexity values. Figure4 shows the congested routes (the dotted areas) of a road network in different timestamp T. According to the recorded trajectory data of vehicles at time T=0, the congested routes of the road network of different directions are generated, such as S2(+) and S5(-) in Figure 4(a). As shown in Figure 4(b), when time T=1, S1(+), S5(-), and S6(-)  are evaluated as congested road segments. Since S5(-) and S6(-) are neighbor road segments and have the same direction in the road network, they are clustered together.Figure 4
The clusters according to different timestamps.
(a)
T
=
0
(b)
T
=
1


## 3.1. Data Model

We assume that the road network is represented by a graphG(N,E), where N denotes the node which is the intersection between different road segments and E denotes the edge which is used to connect two adjacent nodes in the road network. The trajectory of a vehicle is represented by Tr. Each node Ni in the road network is represented by a point {xi,yi}. Ei denotes a segment of the road network. “+” and “−” are used to represent the different directions of vehicles in a road network. Moreover, since the length and the number of lane of each road are different, the length and width of each road segment are stored. Therefore, each road segment is represented by Si(±) = {Ni, Nj, length, width}, where length is the length of a road segment and width is the number of traffic lanes. As shown in Figure 1, S2 and S3 are the neighbor segments of S1 in a road network G.Figure 1
The data model of road network.In a road networkG, each road segment Si stores the information of its directly connected road segments. This information is used for the following clustering evaluations. Since the vehicles may move continuously or stay in a position, it is necessary to have the location knowledge of each vehicle according to the timestamps. Suppose that the trajectory Tr of each vehicle is as follows:(1)Trn=S1±,T1,S2±,T2,…,Sk±,Tk,where Si denotes the segment ID and Ti is the timestamp. According to Ti, the location of each vehicle can be retrieved easily.


## 3.2. Congested Road Segment

The initial road information and trajectory data can be used to determine the existence of vehicles in each road segment of different directions. The complexity value of each road segment is evaluated. The road segment is considered as congested region if the evaluated complexity value is higher than the predefined threshold value. The clustering algorithm is performed among congested road segments. The road segments with low moving speed and high number of vehicles are determined as congested road segments. Figure2 shows the procedure of computing congested routes.Figure 2
The procedure of computing congested routes.In this paper, the congested road segments are computed according to the different directions of the roads. The location and direction of each vehicle can be retrieved from the recorded trajectory data. The complexity value of each road segment is computed by considering the average speed of the vehicles in the road segment and the saturation degree of the road segment. The fast moving speed indicates that the congestion of the road segment is low. In contrast, the low moving speed indicates that the congestion of the road segment is high. The saturation degree is computed based on the number of the vehicles within a road segment and the length and width of a road segment, which are indicated in Figure3. We define that the congested road segments within a road network are the road segments with high complexity values.Figure 3
The road segment between nodesN1 and N2 in a road network.The average moving speed(Av) of the vehicles in a road segment according to different directions is computed by the following equation (2), where V(Obi) denotes the moving speed of a vehicle Obi. The saturation (Sat) according to the width (Swidth) and length (Slength) of a road segment is computed in (3), where Obn denotes the number of the vehicles in a road segment. As a result, the complexity value of a road segment is computed by (4) which combines (2) and (3); α denotes the weight value between the average moving speed of vehicles and the saturation of a road segment. Consider(2)Avi±=∑i=1nVObiObn±×Vmax,(3)Sati±=1-Obn±Swidth×Slength,(4)Rii±=α×Avi±+1-α×Sati±.


## 3.3. Congested Routes Detection

In this section, we present the algorithm of congested routes detection. The algorithm operates in two phases. In the first phase, the complexity value of each road segment in the road network according to different directions is computed. In the second phase, the congested routes of a road network are evaluated by clustering the congested road segments with each time interval. When the complexity value of a road segment is larger than the predefined threshold value, the road segment is considered as a congested road segment. Finally, the congested road segments with same direction are clustered together. Algorithm1 shows the congested routes detection algorithm.Algorithm 1:The algorithm of the proposed scheme.
Congested routes detection algorithm
Input:
Set of road segment listS={S1,S2,…,Sn+1}
Set of trajectoryTr⁡={Tr⁡1,Tr⁡2,…,Tr⁡n}
Set of time intervalT={T1,T2,…,Tn}
Thresholdβ—trajectory velocity and road weight
Output:
Thresholdα—road density
Set of cluster groups CH = {CH1, CH2,…, CHn}
CH← Initialization
for every time intervalt
while there exist Tr in segment listS
for each satisfiedα in S
segmentS = create candidate c
end for
if exist neighbor segmentN in candidate c
create CH← extend from c to N
else if
create CH← candidate c
end if
end while
end forSince the complexity values of road segments are changed according to different timestamps, they have to be computed periodically. The congested routes of a road network are computed according to the complexity values. Figure4 shows the congested routes (the dotted areas) of a road network in different timestamp T. According to the recorded trajectory data of vehicles at time T=0, the congested routes of the road network of different directions are generated, such as S2(+) and S5(-) in Figure 4(a). As shown in Figure 4(b), when time T=1, S1(+), S5(-), and S6(-)  are evaluated as congested road segments. Since S5(-) and S6(-) are neighbor road segments and have the same direction in the road network, they are clustered together.Figure 4
The clusters according to different timestamps.
(a)
T
=
0
(b)
T
=
1


## 4. Performance Evaluation

In this section, we introduce the performance evaluation by comparing the proposed scheme with the existing scheme NETSCAN [13]. The vehicles are generated by the network-based generator [21]. The complexity values and clusters are generated according to the number of vehicles in each time interval. All of the experiments are coded in Java and the experiments are performed in Intel i3 3.0 GHz CPU and 4 G memory. Table 1 summarizes the parameters for this performance evaluation.Table 1
The values of parameters.
Parameter
Value
Road network
Oldenburg city
The number of segments
7,035
The number of nodes
6,105
The number of vehicles
10,000~100,000
Velocity
0~120In the first experiment, we show the congested routes road networks of Oldenburg city by using our proposed scheme. In this experiment, the total number of vehicles in the road network is set to 50,000 and the saturation of the road is set to 30%. As shown in Figure5, the results indicated that the congested routes of the road network are different according to the different directions of the road networks. The blue and red regions represent the congested routes of the road networks in positive direction and negative direction, respectively.Figure 5
The congested route of Oldenburg city.In Figure6, we compare the NETSCAN scheme with our proposed scheme. The number of the congested routes of NETSCAN and the proposed scheme are evaluated according to the number of the vehicles. For the proposed scheme, the congested routes are evaluated in different directions (positive direction and negative direction) and same direction, respectively. PROPOSED (Positive) and PROPOSED (Negative) mean the number of congested routes of each direction of road segments, and PROPOSED (Whole) means the number of congested routes of bidirectional road segments according to the number of vehicles. The results show that the number of the congested routes is increased when the number of the vehicles increases. The number of the congested routes of the proposed scheme is similar when the number of the vehicles is between 20,000 and 30,000. This is because the saturation of each road segment is considered in the proposed scheme. When the width and length of a road segment are large, 20,000 and 30,000 vehicles are not large for the road. Therefore, most of the road segments are not identified as congested routes at first. For NETSCAN scheme, the number of congested routes is increased proportionally with the increase of the number of vehicles.Figure 6
The number of congested routes according to the number of vehicles.Figure7 shows the number of congested routes according to the various timestamps when the time interval is set to 1 hour. The congested routes are evaluated in different directions (positive direction and negative direction) and same direction, respectively. Cluster (Positive) and Cluster (Negative) mean the number of congested routes of each direction of road segments according to the different timestamps. We can see that the number of the congested routes of the positive direction is larger than that of the negative direction. And the number of the congested routes of the proposed scheme that does not consider the direction of the road segment is larger than that of the congested routes of the proposed scheme considering the direction of the road segment.Figure 7
The number of congested routes according to the different timestamps.


## 5. Conclusion

In this paper, we have proposed a congested routes discovering scheme in real road networks. The proposed scheme divides the road into segments with different widths and lengths. It extracts the congested road segments based on the average speed of the vehicles and the saturation degree of a road segment. The final congested routes are computed by performing clustering scheme. The experimental results have shown that the proposed scheme can discover the congested routes in different directions over the existing schemes. In the future, we will show the superiority of our approach by using the real trajectory data of vehicles.



---

*Source: 420689-2015-08-03.xml*