×

NP-hardness of some competitive location models with probabilistic choice rules. (English) Zbl 0973.90040

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.

MSC:

90B80 Discrete location and assignment
PDFBibTeX XMLCite