A Service Facility Location Model with Endogenous Consumer Demands

For those facilities that serve end consumers directly, it is natural that consumer demands are affected by the number and locations of facilities. Vehicle sharing system provide a good illustration, as more users join the system when there are more rental sites. Interestingly, opening a facility not only affects customer demands directly but also changes how other facilities affect consumer demands. For example, for a typical bike sharing system, users often travel from the subway stations to their offices, schools, and home. When there are rental sites at both sides, an additional network effect emerges. In this study, we investigate the problem of a profit maximizing retailer in selecting a set of facilities to build from a given set of locations. We assume that the retailer needs to consider two major types of effects: (1) the stand-alone benefit of a single facility and (2) the network benefit between two facilities. The sum of these two benefits will then be input into a nondecreasing concave function to capture the diminishing marginal benefit property. By considering the overall benefit and total cost of building facilities, the retailer decides where to build facilities to maximize her profit. The problem is then formulated as a nonseparable nonlinear integer program. We first prove that the problem is weakly NP-hard. As one of the most common method to approach NP-hard problems is to develop heuristic algorithms, we propose two algorithms. The first one, which is based on relaxing the integer constraints, is called the approximation-relaxation-sorting algorithm (ARSA). The second one, which is called the naive greedy algorithm (NGA), is a straightforward greedy algorithm. We show that ARSA has different worst-case performance guarantees for some special cases of our general problem. We then study the average performance of the two algorithms in various scenarios through numerical experiments.