论文标题
有序中位树位置问题的扩展版本，包括附录和详细的计算结果
An extended version of the Ordered Median Tree Location Problem including appendices and detailed computational results
论文作者
论文摘要
在本文中，我们提出了有序的中位树位置问题（OMT）。 OMT是一个单位分配设施位置问题，必须将P设施放置在由非导向树连接的网络上。目的是最大程度地减少有序加权平均分配成本的总和，以及连接树上设施的成本的总和。我们根据最小跨越树问题的特性和有序的中值优化提供了OMT的不同MILP公式。鉴于有序的中间集线器位置问题很难解决，我们通过在有效的重新印度中引入覆盖变量，并开发两个预处理阶段以减少该配方的大小，从而提高了OMT解决方案性能。此外，我们建议弯曲器分解算法接近OMT。我们在这些新配方之间建立了经验比较，还提供了增强功能，并与适当的配方一起允许在一般随机图上求解中等大小实例。
In this paper, we propose the Ordered Median Tree Location Problem (OMT). The OMT is a single-allocation facility location problem where p facilities must be placed on a network connected by a non-directed tree. The objective is to minimize the sum of the ordered weighted averaged allocation costs plus the sum of the costs of connecting the facilities in the tree. We present different MILP formulations for the OMT based on properties of the minimum spanning tree problem and the ordered median optimization. Given that ordered median hub location problems are rather difficult to solve we have improved the OMT solution performance by introducing covering variables in a valid reformulation plus developing two pre-processing phases to reduce the size of this formulations. In addition, we propose a Benders decomposition algorithm to approach the OMT. We establish an empirical comparison between these new formulations and we also provide enhancements that together with a proper formulation allow to solve medium size instances on general random graphs.
