ON PLANAR MEDIANOID COMPETITIVE LOCATION PROBLEMS WITH MANHATTAN DISTANCE

A medianoid problem is a competitive location problem that determines the locations of a number of new service facilities that are competing with existing facilities for service to customers. This paper studies the medianoid problem on the plane with Manhattan distance. For the medianoid problem with binary customer preferences, i.e., a case where customers choose the closest facility to satisfy their entire demand, we show that the general problem is NP-hard and present solution methods to solve various special cases in polynomial time. We also show that the problem with partially binary customer preferences can be solved with a similar approach we develop for the model with binary customer preferences.