  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.
