Solving Location Problems by Heuristics and Exact Algorithms

设施选址理论研究相对于一组现有设施的新设施的布置。在文献中研究得最好的几个问题中，最流行的可能是经典的p-中值问题。这里的目标是定位给定数量p的新设施，以便最小化到现有设施的加权距离之和。例如，新设施可以代表仓库、现有设施--客户(或市场区域)，以及重量--预期需求或商品或服务流向每个客户。客户和他们“最近的”新设施之间的加权距离之和将是满足客户要求的总成本的一个有用的业绩衡量标准。P中心问题的目标是最大限度地减少客户与其最近设施之间的最大距离，这将是另一个可能与紧急设施的位置更相关的业绩衡量标准的例子。新的设施可能局限于产生离散(或网络)模型的候选地点，或者它们可能位于连续空间的任何地方。 无论解空间的类型如何，大多数设施选址模型，包括上面提到的两个，都是很难求解的。尽管存在精确的算法，但这些算法通常仅限于较小的问题实例。需要启发式(或近似)解决方法来解决实际问题中可能出现的较大实例，其中客户数量数以千计，并且需要几个设施。选址问题也不仅仅局限于物理设施。例如，在聚类分析、回归分析和数据挖掘领域，可能会遇到在数百万个数据点中编号的超大规模问题，这也可能被归类为选址问题。 这项研究将开发和研究新的启发式算法来解决连续选址问题，如p-Medium问题。我们希望研究的一个新想法是在求解方法中使用连续模型的离散近似。也就是说，任何连续模型可以由网络来近似，其中指定的节点被标识为新设施的候选站点，并且任何节点对(例如，客户-设施对)之间的距离通过指定的距离函数来测量。通过这种方式，我们可以将离散模型的算法(精确或近似)与用于连续空间的算法相结合。然而，为了有效地做到这一点，我们需要更好地理解这两种类型的模型之间的关系。这本身就提出了一个有趣的研究领域，在文献中几乎没有涉及到。在这个过程中，我们将不得不调查几个基本问题。例如，我们如何选择一组合适的候选站点来表示连续模型？我们能为离散近似得到的解的质量提供良好的界吗？将搜索的离散部分和连续部分结合在一起的最佳方式是什么？ 其他想法和问题也将被调查。例如，我们目前正在研究生成“好的”开始解决方案的新方法，以及它们对最终解决方案质量的影响。还将研究具有不同邻域结构的基于分解的方法。另一个目标是将我们开发的新的本地搜索纳入更高级别的算法。这些不同的想法有望提高我们对连续区位模型结构的理解。对于从业者来说，我们希望开发出更高效的解决方案，能够在合理的计算时间内找到更高质量的解决方案。

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.