A graph theoretic approach to control the traffic congestion on road network
No Thumbnail Available
Date
2015
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Uva Wellassa University of Sri Lanka
Abstract
Many relations in real world problems can be represented by graph networks, where each node represents data and links
represent the relationship between them. Web graphs, internet graphs, communication networks, biological networks
such as food web are some of the examples of the existing social networks. All of those networks are analyzed to identify
the communities or to find the importance of certain nodes in the networks. Therefore centrality measure plays an
important role in social networks analysis. Since massive financial and man-hour loss due to traffic congestion, it becomes
a major issue for all of cites in the world to analyze the traffic networks. In order to control traffic congestion, it is essential
to understand the development of traffic flows. Therefore, finding a way to control traffic is needed. Most authors analyze
road networks from the viewpoints of shortest path, cost minimization etc. Recently, a model for determining traffic
assignment and optimizing signal timings in road networks were presented (Yang,et al.,1995) and way of the speed of
the dynamics are affected by the underling network structure were studied (Holme,et al.,2003).Network representation
was used to analyze the patterns in a street (Masucci,et al.,2009). An efficient algorithm to find the shortest route between
two nodes of a large scale, time-dependent graph were developed on road network (Nannicini,et al.,2008). Cut-set of a
graph were used to find optimal control of the traffic system (Baruah,et al.,2012).In this research, the centrality measures
to analyze the congestion in the road network is used.
Methodology
Considering main and alternative paths from Thorana Junction to Kiribathgoda in Colombo-Kandy main road, a road
network is constructed as a weighted,undirected,labeled graph, where each node represents an intersection, junction, or a
special place and each edge represents a road segment between those intersections. Weights of edges are taken as the
distances between nodes. Due to the complexity of the networks, 118 nodes initially have selected to construct this
network. All centrality measures(Degree,Closeness,Betweenness, Eigenvector) and network criticality for all nodes in
this road network are calculated. Besides that clustering coefficients are also calculated. All simulations are carried out
using Mathematica and MATLAB programs.
Result and Discussion
For each node in the road network, all centrality measures are shown in the Figure 1. Figure 1(a) shows that the nodes
around the Kiribathgoda Hospital represent traffic. Closeness centrality values are obtained in the analysis carried out
range from 0.2985 to 0.62.Figure 1(b) shows that node 71 (Junction of New Hunupitiya road) has the highest closeness
centrality and it is the most accessible node from the source node. Looking at Figure 1(c), Furthermore nodes 73,71 and
72(3 nodes from New Hunupitiya junction to Kiribathgoda junction) have the highest betweenness centralities. This
shows that the road segments from New Hunupitiya road junction to Kiribathgoda junction is an important part in this
network and also nodes belongs to this segment, are crucial to maintain node connections. Figure 1(e) shows that the
nodes 100,102,97 (nodes around the hospital) have high eigenvector centralities. The graph implies that these nodes are
around Kiribathgoda hospital. That means the intersections around the hospital are well connected.
Description
Keywords
Networks, Computer Science, Technology, System, Science and Technology, s