Finding minimal cost paths in Raster geographic information system map representations, genetic algorithms, simulated annealing and tabu search.

摘要

The importance of heuristic search methods is based on the inability of exact methods to solve some large combinatorial optimization problems within a reasonable time. Heuristic search methods provide a method of searching for an optimum in these types of problems. These methods are not exact and may not find the actual optimum. In practice they have successfully found near optimum solutions for many classes of problems. This dissertation investigated the use of three heuristic search methods to identify minimal cost paths in a raster encoded Geographic Information System (GIS). In a raster GIS model, a cost factor can be associated with the feature(s) defined in an overlay(s). By combining the overlay information a cost surface can be developed. The three heuristic search methods that were studied are Genetic Algorithms, Simulated Annealing and Tabu Search. Currently, network based methods, such as Dijkstra's Algorithm and related algorithms, are utilized to find the minimum cost paths in GIS data layers. While these algorithms are guaranteed to find a minimum cost path for the specified network, they are currently implemented on sparse networks connecting only adjacent cells in the raster encoded GIS's. This dissertation investigated the utility of using heuristic search methods to find minimum cost paths on the large, dense networks that can be defined by connecting each cell in a raster encoded GIS data layer to every other cell in the GIS data layer. Overall, the heuristic algorithms find lower cost paths than network based algorithms using a sparse network that connects adjacent cells (8-way). The heuristic methods do not perform quite as well as the network-based methods when a denser network connecting each cell with 16 near by cells is used (16-way). The performance of the heuristic algorithms as compared to the network algorithms was found to depend on the terrain type. Some suggestions for choices between the approaches are given.