Study And Realization Of GIS-based Optimal Path Algorithms

Optimal path planning is one of the elementary scientific toptics in network optimization, which has produced a considerable amount of research results of the corresponding fields. However, new situations appearing in many burgeoning fields such as computer network and communication system, intelligent transportation systems based on GIS, mobile robot and military command system, bring forward new tasks and demands for the research of the optimal path problem. Mainly, to meet the demand of the scientific research project of army industry and based on the interrelated research, the follow problems are emphatically researched in this dissertation: optimal path problems of single-task and multitask under some computing conditions under the antagonism condition; high-efficiency algorithms in the shortest path problem; multi-constraint optimal path problem and the optimal path problem in time-dependent network.Main contributions of the dissertation include:(1) A topological structure of road network, which is based on the line-like elements file of digital map, is constructed for optimal path algorithm analysis.(2) An aid decision-making system under the antagonism condition is designed and realized for shortest and fastest path computation of single-task and multitask. Considering the conflict in multitask path optimization, this paper proposes two kinds of resolving schemes: synchronization algorithm and asynchronism algorithm. Experiment on prototype system shows that aforementioned algorithms are reasonable and feasible.(3) Algorithmic efficiency of the shortest path searching is problem which has brought wide attention and need to be resolved urgently in war paramilitary decision-making system, contingency succor system, etc. In this paper, two improved shortest path algorithms are proposed to adapt for asymmetry and abnormity of the road network of the item GIS platform: the restricted rectangle searching area algorithm with variational ratio coefficient r and the beeline optimizing A~* algorithm with heuristic gene. The two algorithms are all of high stability and achieve significantly higher computational performance in searching scope, computational efficiency and EMS memory over the classical Dijkstra's algorithm.(4) Aimmed at the optimal path problem of the network which provided with multiple constraints on each link, a multi-constraint optimal path (MCOP) algorithm is proposed. Furthermore, by introducing heuristic idea into the research of MCOP problem, an exact A*_MCOP algorithm is designed. Experiments show the validity of the two algorithms and the superiority of A~*_MCOP algorithm.(5) Theories of least time path algorithm in FIFO and non-FIFO network are studied and proved systematically. Thereinto, the research about non-FIFO network provides a new approach for least time path problem in non-FIFO network. The "forward" and "backward" least time path algorithms under various waiting constraints are designed and summarized also in this paper.Based on the analysis and summarization of existing algorithms, this paper proposes a series of new optimal path algorithm ideas and algorithm theories with practicability as the goal. The algorithms for path optimization are experimentslly proved accurate and effective.