Study Of Dynamic Path Optimum Algorithm's Problem Under GIS

This paper studies the key techniques of the shortest path by using dynamic path optimum algorithm under GIS. The shortest path problem is a basic problem in network analysis; it is not only a basic but also an important problem as selecting the best value in many fields, it has an especially important use in traffic inducement system. This paper analyses some characters of dynamic path optimum algorithm, studies and verifies the key techniques of the optimum path of city road network under GIS.The material jobs are three directions. Firstly, it research the data structure which was figured by road network and the key technique of extracting road network structure focusing in data model, organic and management form of data after analyzing the road network topology. Secondly, it put forward an improved GA algorithm based on not equation long code and designs the cross and mutating arithmetic operator; this method can guarantee the correct of making path, decrease the searching scope; so enhance the searching efficiency. Thirdly, it probe the strategy of searching region limited to solve the shortest path after considering the increase of the size of city road network and complex degree by making use of the characteristics of GIS in reality; the strategy decrease the searching time very greatly.After the base of above research, this paper design CMap class of extracting and building road network, realize CIndividual class, CPopulation class and CShortestWay class of improved GA algorithm by making using of programming language C++ under Visual C++ 6.0 IDE and MapInfo platform, then build the prototype system. The experiment indicate the improved GA algorithm and searching region limited that this paper put forward to have better efficiency on solving path optimum problem.