The maximum capture problem with heterogeneous customers

A product is sold in a geographical market and it is provided by different companies. Small unmeasurable differences exist between the products sold by different companies and customers have heterogeneous tastes. A newcomer wishes to enter the market locating p new facilities, in order to gain the maximum number of customers. It is assumed that he is not able to specify the exact behavior of every customer, so he models the consumers' decision making by a random utility function. Under some more technical assumptions, a closed formula for the probability of patronizing a given facility is obtained. By this way, a formulation of the maximum capture problem can be obtained. The computational features of the problem are considered and two branch-and-bound methods are developed. The first method exploits the Lagrangian relaxation of the problem, the second uses the submodularity of the objective function. Data sets are generated according to different competitive scenarios and problems of up to 100 nodes are solved within a few seconds. (C) 1999 Elsevier Science Ltd. All rights reserved.