Solving Continuous Space Location Problems

摘要

The focus of this research is on location problems where potential facility sites are to be located in continuous space and demand is assumed continuously distributed, and includes the continuous p-center and coverage maximization problems. Relevant discrete location models are reviewed for the purpose of comparative analysis, including the vertex p problem and the maximal covering locational problem.;First, this dissertation explores a simple but effective approach for solving large vertex p problems, the results of which are to be used as a benchmark for its continuous space counterpart. By introducing a neighborhood facility set, the p problem can be reformulated such that many redundant variables and constraints are removed but characteristics, including optimality, of the problem are preserved. The problem size of the reformulated model can be substantially smaller than in the original form. This enables the use of general-purpose optimization software to solve large vertex p instances. Application results are provided and discussed.;The dissertation then studies the continuous space p problem. A Voronoi diagram heuristic has been proposed for solving the p problem in continuous space. However, important assumptions underlie this heuristic and may be problematic for practical applications. These simplifying assumptions include uniformly distributed demand, representing a region as a rectangle, analysis of a simple Voronoi polygon in solving associated one-center problems and no restrictions on potential facility locations. In this dissertation, the complexity of solving the continuous space p problem in location planning is explored. Considering the issue of solution space feasibility, this research presents a spatially restricted version of this problem and proposes methods for solving it heuristically. The performance of the heuristic is evaluated by comparison with the discrete p problem. Theoretical and empirical results are provided.;Finally, this dissertation explores approaches for solving the problem of siting service facilities to maximize regional coverage when both facility sites and regional demand are assumed continuous. Traditionally, coverage maximization has been approached using discrete representations of potential facility sites and service demand locations. However, such discretizations of space can lead to significant measurement and coverage errors. Representing candidate facility sites and service demand locations as continuously distributed is more reasonable in many cases. Research on coverage maximization in this context has been limited to siting a single facility in a region. This dissertation addresses multiple facility siting in continuous space. A Voronoi diagram heuristic is proposed to decompose the multiple facility problem into a set of single facility problems. The developed approach is applied to emergency warning siren siting in a region. The results are compared with those obtained from a discrete approach.