Modeling Width in Spatial Optimization in Raster Space

Sammanfattning: Given a grid of cells, each of which is assigned a numerical value quantifying its utility (or cost) for a certain use, a popular type of problem in geographic information science is raster-based spatial optimization. Such problems commonly seek to find a set of cells that maximizes (or minimizes) that utility (or cost) while adhering to a given set of constraints. If the problem concerns the selection of a region, i.e., a connected set of cells, it is particularly useful in a range of planning fields that rely on geographic information science. With the increasing availability of high-resolution data on the Earth’s surface, it may no longer be sufficient to exclusively model such raster-based optimization problems on a cell-by-cell basis. Instead, the explicit consideration of width and subsequent modeling of spatial optimization problems may be considered.The overall objective of this thesis is to integrate the “neighborhood” approach to modeling for width in raster grids into pertinent spatial optimization problems. The studies presented in this thesis focus on two common raster-based spatial optimization problems, the maximum value region problem and the least-cost path problem. Each study then models variations of those problems which incorporate a width larger than a cell, and designs, implements, and tests solution methods as follows. The raster-based maximum value region problem involves the selection a region with a specified size that maximizes (or minimizes) the sum of all their values. This task can be cast as a combinatorial optimization problem, and exact and heuristic methods exist for its solution. While solutions generated by these methods are guaranteed to be feasible (if not optimal), they may not be desirable for practical use if they contain too narrow segments (which can be as narrow as the width of a single cell). A new variation of the maximum value region problem—referred to here as the maximum value wide region problem—is presented that requires a region to be at least as wide as a specified width. A heuristic method for its solution is introduced and its performance is tested through computational experiments with randomly generated artificial landscape data. Results demonstrate that the method generates good feasible solutions in terms of all of connectedness, size, width, and value, but requires more computing time—which, in theory, grows linearly with grid size and quadratically with region size and region width—than other methods for maximum value regions without a minimum width requirement.The raster-based least-cost path problem involves the selection of a region that connects two specified cells, a source and destination, and that minimizes the sum of all their values. It is one of the most widely studied problems in geographic information science, and itself is a variation of the optimal routing problem. In relation to width, optimal routing of a path with a constant width, i.e., a corridor, in a two-dimensional (2D) grid of cost-weighted square cells is a recent extension of the least-cost path problem, and models and solutions are available and ready to be integrated into raster-based geographic information systems (GIS). However, these solutions are reliant on the cost surface on which they are modeled, which have limitations in certain situations, including 1) a reliance on the assumption that the cost (per unit length) is measured on a quantitative scale, 2) a measured distortion when the cost-surface is constant, and 3) they are limited to optimal routing of paths in 2D.In relation to the first limitation, one additional model is proposed that characterizes a least-cost corridor on an ordinal-scaled raster cost surface—or a least ordinal-scaled cost corridor for short—and shows that it can be transformed into an instance of a multiobjective optimization problem known as the preferred path problem with a lexicographic preference relation and solved accordingly. The model is tested through computational experiments with randomly generated artificial landscape data as well as real-world data. Results show that least ordinal-scaled cost corridors are guaranteed to contain smaller areas of higher cost than conventional least-cost corridors at the expense of more elongated and winding forms. The least ordinal-scaled cost corridor problem has a computational complexity of O(n2.5) in the worst case, resulting in a longer computational time than least-cost corridors. However, this difference is smaller in practice.In relation to the second limitation, as is the case with conventional raster-based least-cost paths, the incremental orientations are limited to a fixed number of (typically eight cardinal) directions, and therefore, regardless of the grid resolution, least-cost corridors tend to deviate from those conceivable on the Euclidean plane. A method is proposed for solving the raster-based least-cost corridor problem with reduced distortion by adapting a distortion reduction technique originally designed for least-cost paths and applying it to an efficient but distortion-prone least-cost corridor algorithm. The proposed method is, in theory, guaranteed to generate no less accurate solutions than the existing one in polynomial time and, in practice, expected to generate more accurate solutions, as demonstrated experimentally using synthetic and real-world data.In relation to the 2D limitation, with the increased availability of 3D data, one could consider yet another spatial optimization problem in a three-dimensional grid of cost-weighted cubic cells or voxels, which is to find a tubular region of voxels with a constant width, referred to here as “3D corridor,” connecting two termini while accumulating the least amount of cost. A 3D corridor is modeled as a sequence of sets of voxels, called “neighborhoods,” that are arranged in a 26-hedral form, a heuristic method is designed to find a sequence of such neighborhoods that sweeps the minimum cost-weighted volume, and its performance is tested with computer-generated random data. Results show that the method finds a low-cost, if not least-cost, corridor with a specified width in a three-dimensional cost grid and has a reasonable efficiency as its complexity is O(n2) where n is the number of voxels in the input cost grid and is independent of corridor width. A major drawback is that the corridor found may self-intersect, which is often not only an undesirable quality but makes the estimation of its cost-weighted volume inaccurate.