Article Preview
Top1. 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.