Generalized Representation for Large Road Networks
This work is submitted as a thesis for my MS by Research in Computer Science degree at IIIT Hyderabad.
Overview
Road Networks are the most preferred and important mode of transportation due to its accessibility and connectivity thereby influencing the social and economic activity patterns. Therefore, understanding road network behaviour is crucial for the economic and social development of the country. Geographical Information System(GIS) is designed to store, analyze and manipulate geographical data. Since road network data forms a major part of geographical data, GIS can be employed in understanding and utilizing road network behaviour for a variety of applications. Due to the rapidly increasing road network information and its complexity, road network data management for GIS applications is becoming increasingly difficult.
Navigation and transportation planning are two most important GIS applications. The challenges in navigation is the processing and storage of large road network data and design of cost metric to be minimized while computing minimum cost path. Sometimes people prefer a path used by most of the travelers rather than the optimal path. In such a case understanding road network behaviour may provide better insights on the travel patterns leading to improved efficiency of nav- igation applications. Traffic flow analysis is one of the important goals of transportation planning. It involves monitoring the entire road network for the collection, storage and processing of traffic data, which may be a huge overhead in case of large road networks. Proper understanding of the road network behaviour leads to efficient traffic flow analysis even in the absence of traffic data while reducing the amount of data to be collected and analyzed. The existing methods in the context of road network management as a standalone might work but may require additional processing when trying to perform some important operations in GIS applications.
In order to understand the road network behaviour and achieve better road network data management, we propose Skeleton Network of a road network extracted using map generalization techniques by exploiting the inherent node/edge characteristics. The Skeleton Network is the most significant and representative network subset capturing the overall connectivity and structure of the road network. In order to understand its significance in terms of capturing road user behaviour the Skeleton Network of Melbourne, Australia is evaluated against the Annual Average Daily Traffic(AADT) data . Observations indicate that the Skeleton Network mimics the traffic volume data thus capturing the road user behaviour.
The utility of Skeleton Network in efficient road network data management is assessed by applying it in the previously mentioned GIS applications namely navigation and transportation planning. In order to assess the applicability of the Skeleton Network in navigation, a model has been proposed that incorporates the Skeleton Network in pgRouting, a SQL based geospatial routing library. The model is tested on road networks of varying size and topology and the observations indicate that significant gains in path computation are achieved. Moreover path computed using the proposed model mimics the natural traveling pattern. In addition to this, the proposed model also resulted in structured storage of the road network in a relational database enabling efficient querying of road network data. Furthermore, the applicability of Skeleton Network in transportation planning is assessed using an interesting approach that generates a well connected hybrid road network subset by integrating the Skeleton Network and the traffic flow(AADT) data. The generated hybrid network being significantly smaller than the original network comprises of all the high traffic roads and the connectivities between them, leading to efficient analysis of traffic flow. For the ease of understanding and appreciating the outcomes of this work, the proposed methods have been applied to three city level networks(Chandigarh, Hyderabad, Melbourne), one state level network(New York) and a country level network(Belgium). Given the availability of appropriate datasets required for the study, the proposed method can easily be applied to much larger road networks.