Solving Location Problems by Heuristics and Exact Algorithms

通过启发式和精确算法解决定位问题

• 批准号: RGPIN-2014-04868
• 负责人: Brimberg, Jack
• 金额: $ 1.75万
• 依托单位: Royal Military College of Canada
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2017
• 资助国家: 加拿大
• 起止时间: 2017-01-01 至 2018-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=636784
• 关键词: Solving; Location; Problems; Heuristics; Exact

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.

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