NP-hardness of some competitive location models with probabilistic choice rules (Q2708116)

The paper considers competitive location problems on a network under probabilistic choice rules for customers. NP-completeness of the \((r/X_p)\)-medianoid and the \((r/p)\)-centroid problem under three such rules (logit, nested logit, and hierachical logit) is proved by reduction from the dominating set and vertex cover problems, respectively. A tabu search algorithm for the \((r/X_p)\)-medianoid problem is also given and numerical results are presented.