Abstract
Geographical Information Systems are commonly described as systems for the storage, manipulation, analysis, and display of geographically referenced data (Maguire, 1991). With the development of GIS, largely fueled by the need for efficient spatial inventory, urban managers increasingly have at their disposal information systems in which geographic data are more readily accessible, more easily synthesized, and more flexibly modified to address issues of land use planning. However, despite the proliferation of GIS software systems in urban and environmental resource management, the technology is often seen as not yet attaining its full potential for spatial analysis and decision support (Openshaw, 1991; Goodchild, 1990; Tomlinson, 1989). In an effort to move beyond spatial data information systems towards spatial decision support systems, researchers propose integrating powerful decision support and analytical tools, including multi-criteria optimization methods (Cambell et al., 1992; Chuvieco, 1993; Carver, 1991; Janssen & Reitveld, 1990; Eastman et al., 1993), spatial analysis and statistical tools (Anselin et al., 1993; Anselin & Getis, 1992; Goodchild et al., 1992), and simulation techniques (White & Engelen, 1992), into GIS. While developments continue, the computational complexity of processing raster based images, each containing thousands of individual pixels, in optimization models makes integration difficult and in many cases relatively impossible. In this paper we propose an approach to land use planning with GIS that combines a dynamic simulation procedure, cellular automata, with a specialized algorithmic approach to the integer programming allocation problem, to overcome some of the computational complexity involved in determining the best possible allocation of pixels to appropriate land use categories.
With a raster GIS, land use planning decisions involve evaluating locations on a number of relevant criteria, combining these criteria into a single measure of suitability for each land use type, and then allocating each pixel such that the overall suitability of the final zoning decision is optimized. A recent article by Chuvieco (1993) demonstrates the potential of integrating linear programming (LP), as a powerful tool for location/ allocation modelling, with a GIS. His article shows how LP can be used to optimize spatial distributions, generate different planning scenarios, and study the relationships between decision variables and the problem constraints. Because a single image within a raster GIS can contain thousands of individual pixels, each one increasing the size of the integer program exponentially, Chuvieco must limit his analysis to a small, simple land use example. The rapidly increasing problem size, particularly if the allocation decision needs to be integer, is perhaps the largest barrier blocking more rapid integration of optimization techniques with GIS. Solution complexity for problems of this type are often 0(2n) where n is the number of land use pixels to be allocated. Eastman et al., (1993) have developed an algorithmic heuristic that is useful for solving allocation decisions that are very large. While the heuristic does not guarantee an optimal solution, in most cases the suggested allocation is near optimal, and much larger problems can be handled effectively than is possible in the formal integer programming format. However, the solution to the heuristic will not assure a pattern with contiguity or compactness in land allocations to different land use types. Additional constraints guaranteeing contiguity would further exacerbate the computational complexity of the problem (Wright et al., 1983).
An alternative approach is to allow the dynamics of land use change to be simulated by a cellular automata model. Cellular automata is a simulation procedure based on the idea that simple rules of spatial relations and neighborhood influence can result in complex patterns of growth and change (Couclelis, 1985; White & Engelen, 1993). Whereas the allocation heuristic determines a one-time land use zoning decision in a top-down planning manner, the cellular automata uses simple rules of spatial relations to model land use development incrementally over time. In this manner, the evaluation of land use suitability can take into account not only the properties of pixels or locations at a single moment in time, but also the attributes and dynamic land use states of the surrounding pixel locations. As changes in the landscape take place incrementally over time, the relative suitability of pixel locations should reflect on-going developments in the surrounding area. For example, a pixel that rates as highly suitable for agriculture based on its characteristics in time period t, may come to be surrounded by industry in time period t+n, making it more suitable for further industrial development and less desirable for agricultural production. A paper and accompanying software program by White & Engelen (1992) demonstrate the power of incorporating cellular automata into GIS. However, this approach is not without its own drawbacks. Although the cellular automata is useful in simulating growth and land use change, once the transition rules are established and the model is running, it is not easy to guide this self-governing process. Because there are no clear cut stopping rules, the simulation can continue to grow until the entire image is saturated. In order to be effective as a decision support tool, the system requires an objective procedure to determine the optimal termination point and to accept the relevant land use allocation scenario.
In this paper we propose a type of hybrid model combining the spatial simulation power of the cellular automata, as a bottom-up approach to modelling, with the optimizing decision rule of an integer programming model to capture elements of a top-down allocation decision. We use the cellular automata procedure to model the suitability of pixels for each land use type over time and combine the results with a solution algorithm for the related integer programming model to determine how many pixels should make the transition to each land use in each iteration of the model. Because of the spatial memory in cellular automata of the states of surrounding pixels, this procedure offers the promise of yielding land use allocation patterns that have some, and hopefully a suitable level, of contiguity and compactness. The paper demonstrates how these two approaches in combination can address the issue of computational complexity inherent in land use planning and decision making with a GIS.
References
Anselin, L., Dodson, R.F.and Hudak, S. 1993. "Linking GIS and Spatial Data Analysis in Practice", Geographical Systems, 1, 3-23.
Anselin, L. and Getis, A. 1992. "Spatial statistical analysis and geographic information systems", Annals of Regional Science, 26, 19-33.
Cambell, J.C., Radke, J., Gless, J.T. and Whirtshafter, R.M. 1992. "An Application of Linear Programming and Geographic Information Systems: Cropland Allocation in Antigue", Environment and Planning A, 24, 535-549.
Carver, S.J. 1991. "Integrating Multi-Criteria Evaluation with Geographic Information Systems", International Journal of Geographical Information Systems, 5(3), 321-339.
Chuvieco, E. 1993. "Integration of Linear Programming and GIS for Land Use Modeling", International Journal of Geographical Information Systems, 7(1), 71-83.
Couclelis, H. 1985. "Cellular Worlds: A Framework for Modeling Micro - Macro Dynamics", Environment and Planning A, 17, 585-596.
Eastman, J.R., Kyem, P.A.K., Toledano, J. and Jin, W. 1993. GIS and Decision Making. Geneva: UNITAR.
Goodchild, M.F. 1992. "Geographic Information Science", International Journal of Geographical Information Systems, 6(1), 31-45.
Goodchild, M.F., Haining, R. and Wise, S. 1992. "Integrating GIS and SpatialData Analysis: Problems and Possibilities", International Journal of Geographical Information Systems, 6(5), 407-423.
Janssen, R. and Rietveld, P. 1990. "Multicriteria Analysis and Geographic Information Systems: An Application to Agricultural land Use in the Netherlands". Scholten, H.J. and Stillwell, J.C.H, eds, Geographical Information Systems for Urban and Regional Planning, 129-139.
Maguire, D.J. 1991. "An Overview and Definition of GIS". In Maguire, D.J., Goodchild, M.F. and Rhind, R.W., eds, Geographic Information Systems - Vol. 1: Principles, Essex: Longman Scientific and Technical, 9-20.
Openshaw, S. 1991. "Developing Appropriate Spatial Analysis Methods for GIS". In Maguire, D.J., Goodchild, M.F. and Rhind, R.W., eds, Geographical Information Systems - Vol. 1: Principles, Essex: Longman Scientific and Technical, 389-402.
Tomlinson, R.F. 1989. "Presidential Address: Geographic information systems and geographers in the 1990's", The Canadian Geographer, 33(4), 290-298.
White, R. and Engelen, G. 1993. "Cellular Automata and Fractal Urban Form: A Cellular Modeling Approach to the Evolution of Urban Land Use Patterns", Environment and Planning A, 25, 1175-1199.
White, R. and Engelen, G. 1992. "Cellular Dynamics and GIS: Modeling Spatial Complexity", position paper presented at the NCGIA Specialist Meeting on GIS and Spatial Analysis.
Wright, J., ReVelle, C. and Cohon, J. 1983. "A Multiobjective Integer Programming Model for the Land Acquisition Problem", Regional Science and Urban Economics, 13, 31-53.