Providing a Classification of Dual Graph Types to Improve the Routing Analysis

Management of transportation is one of the most important GIS applications. In this filed the network capabilities of GIS such as shortest path computation is very useful. Graph theories play an important role in GIS network analysis. Various theories such as the algorithms of computing shortest path have ever been used in different cases of graph problems. But for some important cases, there is not a good solution in primal graph. For using of dual spaces, at first the problem will be sent to a proper dual space and then after solving, the answers will come back to the primal space. In this paper, different types of dual graphs used in different sciences such as GIS, have been explained by authors. The dual graph concept for two particular problems in route specification: modeling the different costs of turns in crosses and shortest path finding between non-point origin and destination, have been used. As known, the travel time on crosses in right turning is less than left turning. In this paper it is propounded that linear dual graph can be used for modeling the left turn and right turn in a city network. A solution for finding the shortest path between non-point origin and destination was proposed. In many cases the destination or origin of the trip is not a specific point. It was shown that by changing the structure of the primal graph and its adjacent matrix, the linear or polygonal destination could be converted to a specific point. The proposed approach was implemented on the street map of a municipal district in City of Tehran. The developed application illustrated the usefulness and positive effect of discussed approach in transportation network routing.