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
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=758736
• 关键词: 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中心问题。这项工作也可能导致有用的应用程序在供应链的设计。另一个研究领域将推进NSERC支持的先前工作，即解决全局和组合优化问题的近似方法（算法），重点是位置模型。一个具体的重点将是提高我们的理解的拓扑结构（或景观）的解决方案空间产生的不同的本地搜索运营商和不同的质量开始解决方案。我们打算对一些经典问题进行实证研究，这将使我们能够经验地评估局部最优解之间的相对距离。这将为各种元启发式算法的参数值设置提供见解，例如可变邻域搜索（VNS）中的“摇动”参数。我正在与欧洲的同事合作的一个相关领域涉及到“少即是多”的哲学，该哲学追求简单的设计，而不是目前文献中日益复杂的设计。另一个有趣的现象涉及局部搜索方法的收敛速度。我们的初步结果表明，通过改变在解空间中行进的路径，减慢速度可以得到质量更好的解。另一个研究领域涉及网络上枢纽的位置，它有许多重要的应用。在这里，我与另一个来自欧洲的同事团队合作，应用VNS来解决这个问题的一些经典版本，所有这些都假设三角不等式成立。这个强假设导致沿着连接源节点到目的节点的任何路径最多有两个中间集线器沿着。我们最近提出了一个新的“流”模型，消除了这种限制，并打算工作更有效的配方这种类型。