Solving Location Problems by Heuristics and Exact Algorithms

设施选址理论研究新设施相对于一组现有设施的位置。在文献中被充分研究的几个问题中，最受欢迎的可能是经典的p中值问题。这里的目标是找到给定数量的新设施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.