Solving Location Problems by Heuristics and Exact Algorithms

设施选址理论研究新设施相对于一组现有设施的位置。在文献中被充分研究的几个问题中，最受欢迎的可能是经典的p中值问题。这里的目标是找到给定数量的新设施p，以便最小化到现有设施的加权距离总和。例如，新设施可以代表仓库，现有设施-客户（或市场区域），以及重量-预计需求或货物或服务流向每个客户。客户和他们“最近”的新设施之间的加权距离的总和将是满足客户需求的总成本的一个有用的性能度量。p中心问题的目标是尽量减少顾客与其最近的设施之间的最大距离，这是另一种绩效衡量标准的一个例子，这种衡量标准可能与应急设施的位置更相关。新的设施可能被限制在产生离散（或网络）模型的候选地点，或者它们可能位于连续空间的任何地方。

Facility location theory studies the placement of new facilities relative to a set of existing facilities. Of the several well-studied problems in the literature, the most popular one is probably the classical p-median problem. The objective here is to locate a given number, p, of new facilites in order to minimize a sum of weighted distances to the existing facilities. The new facilities could represent, for example, warehouses, the existing facilities - customers (or market areas), and the weights - anticipated demand or flow of goods or services to each customer. The sum of weighted distances between the customers and their "closest" new facility would be a useful performance measure for the total cost of satisfying the requirements of the customers. The p-centre problem, where the objective would be to minimize the maximum distance between the customers and their closest facilities would be an example of another performance measure that might be more pertinent to, say, the location of emergency facilities. The new facilities may be restricted to candidate sites giving rise to discrete (or network) models, or they may be located anywhere in continuous space. Irrespective of the type of solution space, most facility location models, including the two mentionned above, are very difficult to solve. Although exact algorithms exist, these are generally restricted to smaller problem instances. Heuristic (or approximate) solution methods are needed to solve larger instances that may arise in real-life problems where customers number in the thousands and several facilities are required. Location problems are not restricted to physical facilities either. In the areas of cluster analysis, regression analysis and data mining, for example, very large scale problems numbering in the millions of data points may be encountered, which may also be classified as location problems. The proposed research will develop and study new heuristics for solving continuous location problems such as the p-median problem. One new idea we wish to investigate will use discrete approximations of the continuous model within the solution approach. That is, any continuous model may be approximated by a network where specified nodes are identified as candidate sites for the new facilities and the distance between any pair of nodes (e.g., customer- facility pair) is measured by the specified distance function. In this way we may combine algorithms (exact or approximate) for discrete models with those used in the continuous space. However, to do this effectively, we need to better understand the relation between the two types of models. This in itself raises an interesting area of research that has hardly been touched in the literature. In the process we will have to investigate several basic questions. For example, how do we select an appropriate set of candidate sites to represent the continuous model? Can we provide good bounds on the solution quality obtained from a discrete approximation? What is the best way of combining the discrete and continuous components of the search? Other ideas and questions will also be investigated. For example, we are currently studying new ways of generating "good" starting solutions, and their impact on the quality of the final solution. Decomposition-based approaches with different neighbourhood structures will also be investigated. Another objective will be to incorporate the new local searches that we develop into higher-level algorithms. These various ideas will hopefully improve our understanding of the structure of continuous location models. For practitioners, we hope to develop more efficient solution approaches that will be capable of finding higher-quality solutions in reasonable computing time.