New models and solution approaches in continuous and discrete facility location

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

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.