Research On The Shortest Path Algorithm For Optimizing Performance Of Underground Pipe Network

As the rapid development of urban construction, original urban underground pipe network can not meet the needs of urban development. The updates of old pipe network, the new design and construction of pipeline networks, the planning of new district network, all of which are based on the accurate status quo of the underground pipe network. However, there are a lot of problems in the old network managed by the traditional drawings and diagrams and other forms. Geographic information system (Geographical Information System, referred to as GIS) is a system which is supported by computer hardware and software and based on the spatial database to provide service for geographical imformation management. The main technologies of Gis include theory of system engineering, information science, and spatial data scientific. With the development of GIS technology, its powerful functions have been used in many applications. The shortest path algorithm, as the basis of best selection in many fields, plays an important role in the underground pipe network system.This paper is starting from the status and actual needs of the underground pipe network management, the expression of the vector map, as well as the construction and extraction of network topology. Thus, taking account of the nature of "one to many" in the shortest-path analysis of the underground pipe network, which have common with multicast routing in network communication, we've developed GIS system based on MapInfo platform for urban underground pipe network management. Our main contributions are as follows:1) Outline GIS, describe the development and application of GIS, and introduce GIS data model, GIS data organization and management; discusse network analysis functions and related algorithms of GIS in detail.Most importmant, we've done in-depth analysis and research on each key technology of the shortest-path analysis. Among them, we focus on technologies such as the expression of the vector map about the underground pipe network, network topology extraction and construction, and so on.2) Considering that shortest-path algorithms used in urban underground pipe network can not meet the needs of accurate management, we introduce the concept of"multicast tree", which is new in urban underground pipe network while common in computer network routing, in order to solve the one-source shortest-path problem. By comparion of two classical shortest-path algorithms Dijststra and Froyd, we prove that KPP multicast routing algorithm is more effient in constructing"multicast tree"for more links being shared.3) Discuss the shortcomings of KPP algorithm, and analysize the relationship of the length and cost of paths in urban underground pipe network, an advanced KPP algorithm is proposed for the management and performance optimization of underground pipe network. Based on MapInfo7.0 platform where real pipe network data is running, using the new shortest-path analysizing module of MapBasic language, we test the performace of the renewed underground pipe network. The results show that the advanced KPP algorithm can save cost about 9%-10% comparing to KPP algorithm, which indicate the efficiency of our proposal.