On Transforming a Road Network Database to a Graph for Localization Purpose

On Transforming a Road Network Database to a Graph for Localization Purpose

Xiangli Meng (School of Technology and Business Studies, Dalarna University, Falun, Sweden & School of Statistics, Shandong University of Finance and Economics, Jinan, China) and Pascal Rebreyend (School of Technology and Business Studies, Dalarna University, Falun, Sweden)
Copyright: © 2016 |Pages: 10
DOI: 10.4018/IJWSR.2016040103


The problems of finding best facility locations require complete and accurate road networks with the corresponding population data in a specific area. However the data obtained from road network databases usually do not fit in this usage. In this paper the authors propose a procedure of converting the road network database to a road graph which could be used for localization problems. Several challenging problems exist in the transformation process which are commonly met also in other data bases. The procedure of dealing with those challenges are proposed. The data come from the National road data base in Sweden. The graph derived is cleaned, and reduced to a suitable level for localization problems. The residential points are also processed in ordered to match the graph. The reduction of the graph is done maintaining the accuracy of distance measures in the network.
Article Preview

1. Introduction

Consider the common location-allocation model (the p-median problem) which allocate P facilities to a population geographically distributed in Q demand points such that the population’s average or total distance to its nearest service facility is minimized. Solving such problems is based on computing the distance between candidate locations and all or a subset of points representing the habitat of people. The candidate locations should be connected in a graph and the corresponding distance matrix should be suitable for further calculations. A popular approach is to avoid the trouble caused by transforming the original data into a connected road network and instead use the Euclidian distance between the candidate locations and residential points. Thus, all points are assumed to be connected pairwise via straight lines. However, the Euclidian distance may be inaccurate, especially if two points are not directly connected and require detours, in which case the Euclidian distance would underestimate the real distance. Thus the quality of the distance is deteriorated, particularly in a area with a lot natural barriers. Consequently, the usage of Euclidian distance would lead to poor locations of the model.

Han & al (2013) shows that using the road network to compute distances instead gives a good treatment of the problem. The road network distance gives accurate estimate of distance between 2 points. It reflects the road connections and natural barriers. In their analysis, although the complexity of the problem leads to sub-optimal solutions, the road network distance solutions still outperforms those of Euclidian ones.

However, even though the usage of the road network distance is essential in solving the models, the original network data sets researchers obtained usually do not fit and are unable to be used directly. Those data sets need to be cleaned and transformed to a connected road network graph before being used for finding best locations of facilities. Many challenging problems could pop out in this process such as incomplete information or isolated sub graph. Dealing with these problems inappropriately would produce inaccurate graph and then lead to bad solutions. For data sets in a large scale, the necessity of giving proper treatment of the problems in the data set and the transformation process is even more crucial.

Despite the nontrivial role an accurate road network graph plays in solving the location models, few research papers give proper illustrations on how to deal with the troubles in the process of deriving it. Especially for data at a large scale for the p-median models, there is no research investigation on how to deal with the challenges in the transformation process, which is the focus of this paper. In our case, we are interested in locating public facilities such as hospitals, public services at the scale of the country Sweden. The objective function we want to minimize is the average distance between residence’s habitants and the closest facilities nationwide. The scale of the problem is very large, making the quality for graph and distance matrix vital. The original data we get is from the National road data base (NVDB), provided by the National Swedish Road Agency (Trafikverket). It is a very detailed data set consisting of over 34 million data points with auxiliary information like speed limits and direction. Many commonly met challenges appear in the transformation process. Proper methods need to be used for handling those challenges before getting the graph for solving the p-median models. The main challenges we encountered are as follows.

  • A.

    Filling in the missing crossing and connectivity information properly.

  • B.

    Reducing a super large graph to a manageable scale and keep the distance information as accurate as possible.

  • C.

    Calculating the distance between different nodes in an affordable time.

Complete Article List

Search this Journal:
Open Access Articles
Volume 16: 4 Issues (2019): 1 Released, 3 Forthcoming
Volume 15: 4 Issues (2018)
Volume 14: 4 Issues (2017)
Volume 13: 4 Issues (2016)
Volume 12: 4 Issues (2015)
Volume 11: 4 Issues (2014)
Volume 10: 4 Issues (2013)
Volume 9: 4 Issues (2012)
Volume 8: 4 Issues (2011)
Volume 7: 4 Issues (2010)
Volume 6: 4 Issues (2009)
Volume 5: 4 Issues (2008)
Volume 4: 4 Issues (2007)
Volume 3: 4 Issues (2006)
Volume 2: 4 Issues (2005)
Volume 1: 4 Issues (2004)
View Complete Journal Contents Listing