Determination of optimal route for GIS based road network

Abstract

Dhaka, the capital of Bangladesh, has a population of about 9.6 million and extending over an area of about 360 square kilometer. In 2016 population would be greater than 15.5 million. The city has been turned into one of the densely populated cities of the world with an annual growth rate of population of about 8%. Existing road network of Dhaka city is considered to be inadequate and in poor condition to provide a minimum standard of traveling level of service in comparison to other mega cities of the world. Inadequate development of road network, rapid increase of population and vehicles have created adverse effect on traffic movements, road safety, noise pollution, air pollution and socio-economic conditions. The situation is more severe when movement of emergency services such as fire and ambulance services are compared. No priority measures are available for rapid movement of such services. A broad range of diverse technologies, known as Intelligent Transport Systems (ITS), holds the answer to many of these transport problems. A route planner to provide advance traveller information, in this regard, is considered to help a traveler to make the desired trip effectively and efficiently. Geographic Information Systems (GIS) has been effectively using in the Advanced Traveler Information Systems (ATIS) in several countries like India, Japan, Korea, USA, etc. Although, shortest route analysis can be performed using built in tools of GIS and non-GIS packages considering only a single impedance factor as a network weight such as route length or travel time, they are unable to consider all impedance factors at once. For a given origin and destination, one is always tempted to use the shortest distance route. But this need not always is the best (optimal) route, especially in emergency situations, wherein shortest travel time is to be preferred over shortest distance. A shorter route does not always translate to shorter travel time, because it may be narrow in width or it may have higher volume of traffic, or more numbers of signals and turns and so on. Weighted graphs, which are a pervasive data structure in computer science and algorithms for working with them are fundamental for the problems of computing optimal routes between nodes when each edge has an associated length or “weight’ to represent the road and traffic condition. An optimal path/route algorithm can be describe as a (directed) graph G=(N,E,C) consists of a node set N, a cost set C, and an edge set E. The edge is a subset of the cross product N*N. Each element (u,v) in E is an edge that joins node u to node v. Each edge (u,v) is associated with a cost C (u,v). Cost C (u,v) takes values from the set of real numbers. A node v is a neighbor of node u if edge (u,v) is in E. An optimal path from node u to node v is the path with the smallest cost. However, optimal path algorithms are very rarely available in literature, which explains only the conceptual framework. Furthermore, literature reveals that most route selection techniques are based on shortest path on the basis of distance or travel time not considering road type, road geometry, land use, intersection queue length, signal timing, flow restriction, etc. Also most of them need to install specific GIS software in the computer for their visual display. The present study thus intends to develop a methodology/technique in the form of an ATIS to determine optimal route based on shortest travel time (lowest impedance or cost) considering all impedance factors at once between a selected pair of origin and destination for a GIS based road network. In this regard, road network of Dhaka City Corporation has been used to demonstrate the application of the system. A total of 588 edges (E) and 400 nodes (N) were developed using ArcInfo and ArcView GIS software through digitization, editing, georeferencing, projection and building topology. Travel times, the cost set (C), were generated through analysis traffic data, capacity of road network, capacity of intersection and signal settings. Travel time is the summation of link travel time and intersection delay (signalized, unsignalized, roundabout and level crossing) delay. To estimate link travel time temporal data for the spatial network (such as: AADT, capacity of links) were obtained from the Strategic Transport plan (STP) of Dhaka city and the free flow speeds on links were collected through traffic survey conducted for the research. Bureau of Public Roads (BPR) function was used to estimate link travel time. Values of calibration parameters (α, β) have been calculated according to road class and journey period for road network of Dhaka city. To calculate signalized intersection delay, the HCM 2000 delay calculation formula was efficiently used with proper inclusion of control delay and incremental delay coefficient. Due to the mixed mode traffic instead of lane based traffic flow, the uniform control delay (d1) was increased by 20% and incremental delay (d2) was reduced by 70%. Akcelik delay estimation model for roundabout delay has been used estimate roundabout delay. Entry and circulating flows for each approach were the volumes of interest for roundabout capacity analysis, rather than turning movement volumes. Detail traffic survey were conducted at roundabouts to collect approach flow and circulating flow. Adams’s formula was used to calculate delay at the minor roads on un-signalized intersection with different critical lag (t) as suggested in the research . Stop delay survey was conducted to determine level crossing delay. A detail traffic survey was conducted to determine number of blockage per hour (n), arrival rate of vehicle, queue dissipation rate (μ) and average blockage time (r) as well as level crossing delay (D). An edge matrix was generated to represent transportation links and simultaneously, a turn matrix was generated to define turn of each individual intersection. An algorithm to determine ranked optimal path considering users preferred travel node for a turn-based directed graph G=(V,E,C) is developed using C++ environment. The algorithm consists of two parts: the first part is responsible for splitting intersection nodes other than origin, destination and fringe area nodes to ensure turn conditions, which needs a time complexity of O(E); where E is the edge set. The second part is responsible for compute ranked optimal path for the entire nodes, which has a time complexity of O(ElgV); where V is the edge set and E is the edge set. Thus the resultant time complexity for 3-ranked path is O(V2ElgV). Finally, a graphical interface was developed to display the three ranked optimal paths based on users selected origin, destination and preferred travel node.