A graph theoretic approach to control the traffic congestion on road network

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.