Fr 16 August 2019 | -- (permalink)
As part of the SciGRID_gas project, we need to construct a network from OSM gas network data and combine it with data from other sources. However, OSM gas network data is incomplete for most parts of the Europe, which we will discuss in a more comprehensive manner within a paper, but basically underground pipelines are hard to map.
Hence, we have created an environment to test several algorithms for network creation. In addition, none-OSM data can be used to improve the outcome. This is required as network components, such as compressors, storages or LNG terminals are mostly missing in the OSM data set. The overall result will be a coherent gas network. Such networks can be used to construct a more comprehensive gas network model.
In this video we present one of our first model runs to create a network for the region of France. In the following, a description of most essential algorithms and underlying data is presented. The image series in the description below belongs to a very similar run (compared to the video).
Step 0: Original Input Data:
We have 1681 identified pipelines from the OSM data set with a total length of 11,332 km. On average, each OSM pipeline consists of 34 nodes and 33 edges. This leads to a total of 56,426 nodes and 54,789 edges. In the image below the high density data makes it impossible for the naked eye to differentiate between nodes and edges. The data has not yet been added to the network.
Step 1: Preparation of OSM Data:
Each route of the OSM pipelines consists of several georeferenced points. To reduce the computational time of further alogrithms, the density of the OSM data is reduced by a “sequencing” algorithm. This is realized by preparing the initial data in a manner, that each route has only one start point, one end point and intermediate points every 25 km. Subsequently, each route is added to the network. At this stage 3,330 nodes and 1,681 edges are added to the network.
Step 2: "Load Compressors" from none OSM data:
As mentioned above, we can use none-OSM data to reduce potential data gaps. Here, 32 compressors are added to the network as special network nodes (green dots). This process is also required as we do not have identified special network components (e.g. compressors stations) within the original OSM data set. This additional geographic information of the added compressors can also improve the overall network structure.
Step 3: “Merge”:
Currently, there are more than 3,362 nodes and 1,681 edges in our French network. To improve computational speed of future model applications, a smaller node count is preferred. Hence, we are clustering the network by merging nodes that are closer than ~20 km into a single node (father), starting with the nodes with shortest distances. All links of a child node are then passed over to the father node. This process reduces the number of nodes to a total of 173 and number of edges to total of 128.
Step 4: "Connect" or "Spanning Tree:"
So far, we still have some unconnected components in our network. The task is to connect those to a coherent single network. This can be realized by constructing a (minimal) spanning tree under the preservation of existing pipeline routes.
As a result 56 links are added to the network. In contrast to the video, we have color coded the links for explanation purposes. The blue edges are part of the spanning tree and consist of preserved links and the 64 newly added links. The red ones are the preserved links, which are not a part of the spanning tree. The final total number for nodes is 173, respectively 184 for edges.
“A spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.”(Wikipedia)