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.

翻译：在本文中,我们提出了中位树位置问题(OMT)。OMT是一个单位设施位置问题,P设施必须放在非方向树连接的网络上。目标是尽量减少订购加权平均分配费用的总和,加上连接树上设施的费用总和。我们根据树上最小覆盖问题和定序中位优化的特性,为OMT提出了不同的MILP配方。鉴于定置中位中心位置问题相当难以解决,我们通过在有效的重整中引入变量并开发两个预处理阶段以减少这种配方的规模,改进了OMT解决方案的性能。此外,我们建议采用Benders分解算法接近OMT。我们对这些新配方进行实验性比较,我们还提供改进,加上适当的配方,能够解决普通随机图中的中等规模实例。