New models and solution approaches in continuous and discrete facility location

连续和离散设施位置的新模型和解决方案

• 批准号: RGPIN-2020-04846
• 负责人: Brimberg, Jack
• 金额: $ 1.89万
• 依托单位: Royal Military College of Canada
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2021
• 资助国家: 加拿大
• 起止时间: 2021-01-01 至 2022-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=740254
• 关键词: New; models; solution; approaches; continuous

A main objective of the proposed research is to construct and study generalized versions of some classical location problems in the literature that may extend their usefulness in practice. An example is the "distributed p-median problem", which generalizes the classical p-median and was recently proposed by myself and two co-authors in a recent paper (JORS 2019). This new model imposes a distribution rule that allows flows to be directed to new facilities that are not necessarily the closest to the demand points (as in the classical model). We have formulated various discrete and continuous versions of the problem and derived interesting structural properties. For example, it is well known that facility locations for the classical (closest facility) problem may be restricted to the nodes of a network. However we have shown that this is not true for the general problem. We are now working on a network formulation, and developing special cases where the finite dominating set of generalized median points has a manageable size, and hence is more amenable to solution. We also plan to extend the study to other problem classes such as the p-centre problem for locating emergency facilities. This work may also lead to useful applications in the design of supply chains. Another area of research will advance previous work supported by NSERC on approximate methods (heuristics) for solving global and combinatorial optimization problems with an emphasis on location models. A specific focus will be on improving our understanding of the topology (or landscape) of the solution space generated by different local search operators and different qualities of starting solutions. We intend to conduct empirical studies on some classical problems that will enable us to empirically evaluate the relative distances between local optima. This will provide insights on setting parameter values for various meta-heuristics, such as the 'shaking' parameter in variable neighborhood search (VNS). A related area I am working on with colleagues in Europe involves a "less is more" philosophy, which strives for simple designs instead of the current trend in the literature of increasing complexity of heuristics. Another interesting phenomenon relates to the convergence rate of local search methods. Preliminary results we have show that slowing the rate can lead to better quality solutions by altering the path traveled in the solution space.  Another area of research deals with the location of hubs on a network, which has many important applications. Here I am working with another team of colleagues from Europe on applying VNS to solve some classical versions of this problem, all of which assume that the triangle inequality holds. This strong assumption results in at most two intermediary hubs along any path connecting source to destination nodes. We recently proposed a new "flow" model that eliminates this restriction, and intend to work on more efficient formulations of this type.

本研究的主要目的是构建和研究文献中一些经典定位问题的广义版本，以扩展其在实践中的应用。一个例子是“分布式p中位数问题”，它概括了经典的p中位数，最近由我和两位合著者在最近的一篇论文（JORS 2019）中提出。这个新模型施加了一个分配规则，允许流被引导到不一定最接近需求点的新设施（就像在经典模型中一样）。我们已经公式化了这个问题的各种离散和连续版本，并推导出了有趣的结构性质。例如，众所周知，经典（最近的设施）问题的设施位置可能被限制为网络的节点。然而，我们已经证明，对于一般问题，这是不成立的。我们现在正在研究一个网络公式，并开发特殊情况，其中广义中值点的有限支配集具有可管理的大小，因此更易于解决。我们还计划将研究扩展到其他问题类别，例如定位应急设施的p-centre问题。这项工作也可能导致供应链设计的有用应用。另一个研究领域将推进NSERC支持的关于解决全局和组合优化问题的近似方法（启发式）的先前工作，重点是位置模型。一个特别的重点将是提高我们对由不同的局部搜索操作符和不同质量的起始解生成的解空间的拓扑（或景观）的理解。我们打算对一些经典问题进行实证研究，使我们能够经验地评估局部最优之间的相对距离。这将为设置各种元启发式的参数值提供见解，例如可变邻域搜索（VNS）中的“摇动”参数。我和欧洲的同事正在研究的一个相关领域涉及“少即是多”的哲学，它致力于简单的设计，而不是当前文献中不断增加的启发式复杂性的趋势。另一个有趣的现象与局部搜索方法的收敛速度有关。我们的初步结果表明，通过改变在解空间中行进的路径，减慢速率可以得到质量更好的解。另一个研究领域涉及网络中集线器的位置，这有许多重要的应用。在这里，我正在与另一个来自欧洲的同事团队合作，应用VNS来解决这个问题的一些经典版本，所有这些都假设三角形不等式成立。这个强假设导致在连接源节点到目标节点的任何路径上最多有两个中间集线器。我们最近提出了一种新的“流”模型，消除了这种限制，并打算研究这种类型的更有效的公式。