Optimization Strategy Based On The Hierarchical Path Of The Genetic Algorithm And Path Query System Design

Along with the development of transportation and tourist industry,A good planning is very important in traveling day by day.The shortest path is commonly invovled in path planning.Because the different factors are considered,such as time,cost and capacity of roads,problem of the shortest path can be treated as problem of the fastest or least cost.Whichever standard chosen,path planning is in order to attain the most optimal path.So the most optimal path planning is regard as the problem of searching for roads which have the least cost in a road net.Studying on problem of the shortest path is always a hotspot,the classical algorithms are Dijkstra,Ford,A,A~*,Dynamic Planning and so on.In order to have a good efficiency of search, many scholars have made improvement on Dijkstra algorithm.Because time complexity of Dijkstra algorithm is O(n~2),so its efficiency will be lower when there are a lot of road nodes.In order to overcome this problem and narrow area,some scholars lead into the idea of restricted searching area, such as restrict to ellipse and restrict to rectangle.Genetic algorithm is intelligent search method based on survival of the fittest,natural selection and law of biological inheritance of theory of biological evolution.Genetic algorithm has strong search capability of overall situation,robust, parallelism and heuristic and random search features.Genetic algorithm maintains a number of viable solutions and reorganizes them in order to change their mobile trajectories or trends in multi-dimensional space,then,has an optimal solution.Genetic algorithm overcomes the drawback what the traditional optimization methods are vulnerable to local optimum.Because of this reason, genetic algorithm only encodes some paths and evolves through operations of evolution.As a result, the approximate optimum or most optimum paths can be attained.In fact,when solution space is enough large,genetic algorithm is very hard to have the satisfactory solutions.Because searching of genetic algorithm is blindness and randomness in some cases.In this paper,the solution space is divided into two or more sub-space,the solution will be searched by hierarchical scenario.As a result,quality of solutions and efficiency of genetic algorithm can be improved.Compare to the simply genetic algorithm,the hierarchical algorithm prefers high layer paths to low layer paths.A hierarchical algorithm is fit in with the decision-making psychology of travelersa and makes the choice of paths more rational.The work is mainly composed of two parts.The first part is research of algorithms,here is mainly research of genetic algorithm.The efficiency of modified genetic algorithm is improved by hierarchical scenario in optimal routing.Finally,validity of the algorithm is proved by experiment. The second part is design of system which includes functional modules,workflow and interface of system.At last,a path searching system is designed and implemented by Visual Studio 2005 and MapXtreme 2005 based on Oracle 9i database.This system achieves the functions of path finding and geographic information processing.