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

Discrete versions of the medianoid and the centroid problems are considered under different assumptions concerning customers bahaviour. All assumptions rely on logit theory, i.e. that choices are probabilistic rather than deterministic. It is proved that both problems are NP-hard, as are their deterministic versions. As corollary, the NP-hardness of two nonlinear integer programming problems is also obtained. A tabu-search heuristic is developed and tested on a set of random problems. The computational results suggest that it can produce good quality solutions.