The Maximum Coverage Location Problem

Abstract

Abstract. In this paper we define and discuss the following problem which we call the maximum coverage location problem. A transportation network is given together with the locations of customers and facilities. Thus, for each customer i, a radius ri is known such that customer i can currently be served by a facility which is located within a distance of r, from the location of customer i. We consider the problem from the point of view of a new company which is interested in establishing new facilities on the network so as to maximize the company's "share of the market. " Specifically, assume that the company gains an amount of wi in case customer i decides to switch over to one of the new facilities. Moreover, we assume that the decision to switch over is based on proximity only, i.e., customer i switches over to a new facility only if the latter is located at a distance less than ri from i. The problem is to locate p new facilities so as to maximize the total gain. The maximum coverage problem is a relatively complicated one even on tree-networks. This is because one aspect of the problem is the selection of the subset of customers to be taken over. Nevertheless, we present an O(nZp) algorithm for this problem on a tree. Our approach can be applied to other similar problems which are discussed in the paper. 1. Introduction. We