×

Tabu search algorithms for the \((r| X_p)\)-medianoid and \((r| p)\)-centroid problems. (English) Zbl 0917.90222

Summary: The \((r| X_p)\)-medianoid and \((r| p)\)-centroid problems are two well-known competitive location problems on networks. In the medianoid problem, a player locates \(r\) facilities in a network in order to maximize its market share, given that \(p\) facilities are already located. In the centroid problem, two players in turn locate \(p\) and \(r\) facilities at the vertices of a network in order to maximize their market share. The problem is for the first player to find a set of locations that will minimize the second player’s maximal market share. These problems are both NP-hard. They are solved by means of tabu search heuristics. Computational results confirm the value of the proposed approach.

MSC:

90B80 Discrete location and assignment
PDFBibTeX XMLCite