Heuristic Methods in Spatial Analysis

Many problems in spatial analysis involve the search for optimal solutions. For example, it is important to find locations for public health facilities such that the residents in an area can be best served. There are exact methods that can be used to solve these problems. An exact method exhaustively evaluates each possible solution and identifies the best one. A drawback of this type of approach is its complexity. For a large-sized problem, as measured by the number of inputs, the time used by an exact method may exceed the time frame required to solve the problem. The predicament of solving a problem exactly suggests the use of heuristic methods. Different from exact methods, heuristics generally do not guarantee that the optimal solution will be found.

To understand how a heuristic method works, it is helpful to imagine a graph formed by all the solutions to a problem, where each vertex represents a specific solution and a link exists between two vertices if knowing one will lead to the other (see example that follows). Finding the optimal solution in the network requires starting from any vertex and finding the path to the vertex representing the optimal solution. As the graph can be [Page 1424]of a huge size because of the number of vertices (possible solutions) and their connections, it is impractical to exhaustively traverse each path between vertices. A heuristic method often starts from a randomly chosen vertex and tries to go through a particular path by guessing that there is no need to go through other paths. The chosen path, however, does not necessarily lead to the optimal solution, though the literature generally suggests that near-optimal solutions can be found.

Many heuristic methods are developed using a “greedy” mechanism (one that solves problems by finding locally optimum solutions in the search for a global optimum) to improve the initial solution that is typically determined on a random basis. Though different forms of greedy methods exist, they generally follow the same design logic: If a better solution can be found in the neighborhood of the current solution, then the current solution should be replaced by the new one. The process continues until no such replacement can be made. This idea can be illustrated using a solution approach to the p-median problem, where p nodes must be selected in a network of n nodes such that the total distance from each node to its nearest selected node is minimal. An initial solution to the problem can be p random, unique integers ranging between 1 and n. Substituting a selected node with each of the unselected ones results in a neighborhood of the solution. The current solution can be improved if at least one solution in the neighborhood has a smaller total distance. The replacement continues until no solution is better in all the neighborhoods of the p selected nodes.

Greedy heuristic methods are typically designed for specific problems, which makes it difficult for one method to be used to solve other problems. Also, a greedy method is often myopic, meaning that it can be trapped in a local optimal solution. Metaheuristics have been developed with the hope of addressing these issues.

...