In this paper an extension of the (r|Xp)-medianoid on networks introduced by Hakimi is studied. In this extension the customer considers not only the distance but some characteristics of the facilities such as store size, quality of service and parking space. A new firm wants to establish r new facilities which have to compete with the p facilities that already exist in the market. The entry firm wants to find their locations and characteristics to maximize profits. Three different customer choice rules (binary, partially binary and proportional preferences) are considered. Some discretization results are obtained and a resolution procedure is proposed. The problem is solved combining a global search algorithm based on a branch and bound procedure with some combinatorial heuristics (greedy, interchange, and tabu search). Some computational experiences are presented.
