Using Linear Integer Programming for Multi-Site Land-Use Allocation
Aerts, Jeroen C. J. H., Eisinger, Erwin, Heuvelink, Gerard B. M., Stewart, Theodor J., Geographical Analysis
Research in the area of spatial decision support (SDS) and resource allocation has recently generated increased attention for integrating optimization techniques with GIS. In this paper we address the use of spatial optimization techniques for solving multi-site land-use allocation (MLUA) problems, where MLUA refers to the optimal allocation of multiple sites of different land uses to an area. We solve an MLUA problem using four different integer programs (IP), of which three are linear integer programs. The IPs are formulated for a raster-based GIS environment and are designed to minimize development costs and to maximize compactness of the allocated land use. The preference for either minimizing costs or maximizing compactness has been made operational by including a weighting factor. The IPs are evaluated on their speed and their efficacy for handling large databases. All four IPs yielded the optimal solution within a reasonable amount of time, for an area of 8 x 8 cells. The fastest model was successfully applied to a case study involving an area of 30 x 30 cells. The case study demonstrates the practical use of linear IFs for spatial decision support issues.
Recently, much attention has been paid to solving resource allocation problems with multi-criteria decision-making (MCDM) techniques in a geographic information system (GIS) environment. For resource allocation, this area is often referred to as spatial decision support (SDS). There are two basic MGDM techniques suitable for implementation in a GIS. The first is multi-criteria analysis (MCA), which involves the evaluation of a relatively small set of allocation alternatives (Nijkamp, Rietveld, and Voogd 1990; Janssen 1991; Herwijnen et al. 1997; Fulong 1998; Herwijnen 1999; Malczewski 1999). These alternatives, usually about three to five and rarely more than ten, are defined beforehand and are simply evaluated against each other. MCA is therefore termed an evaluation technique. MCA is certainly useful when the alternatives are available. However, in many cases a set of allocation alternatives is not available, or difficult to define. Hence, research in the field of SDS and resource allocation has changed foc using to techniques that generate an optimal allocation alternative using optimization techniques (e.g., Barber 1976; Chuvieco 1993, 1997; Guariso, Hitz, and Werther 1996; Arthur and Nalle 1997; Dutta, Gupta, and Ramnaron 1998; Grabaum and Meyer 1998; Maniezzo, Mendes, and Paruccini 1998; Ridgley and Heil 1998; Fedra and Haurie 1999; Purao, Jan, and Nazareth 1999; Aerts 2001; Aerts and Heuvelink 2002). These so-called design techniques form the second branch of basic MCDM techniques.
In this paper we examine the use of linear optimization techniques for multi-site land-use allocation problems (MLUA). Multi-site refers to the problem of allocating multiple sites of different land uses to an area. It is explored whether linear optimization methods are suitable for practical use in a decision environment. A crucial element in the analysis is how to introduce a spatial compactness objective in the optimization model. Four different integer programming (IP) models, three linear IPs and one non-linear IP, are considered that all solve the same basic problem and are evaluated against two criteria: (1) their efficacy to encourage spatial compactness within a reasonable solution time for small and large data sets (preferably more than 50 x 50 cells), and (2) their ability to yield a mathematically optimal allocation alternative. It is finally illustrated how IP models can be used in a decision environment by demonstrating the use of the models to a case study in Spain. The main problem of the cas e study is to restore a former open mining area with new land use.
2.1. The Basic MLUA Model
An MLUA problem can be formalized as a pair (S, f), where the solution space S denotes the set of all possible solutions and f denotes a cost function. …