  We study the maximum capture problem in facility location under random
utility models, i.e., the problem of seeking to locate new facilities in a
competitive market such that the captured user demand is maximized, assuming
that each customer chooses among all available facilities according to a random
utility maximization model. We employ the generalized extreme value (GEV)
family of discrete choice models and show that the objective function in this
context is monotonic and submodular. This finding implies that a simple greed
heuristic can always guarantee an (1-1/e) approximation solution. We further
develop a new algorithm combining a greedy heuristic, a gradient-based local
search and an exchanging procedure to efficiently solve the problem. We conduct
experiments using instances of difference sizes and under different discrete
choice models, and we show that our approach significantly outperforms prior
approaches in terms of both returned objective value and CPU time. Our
algorithm and theoretical findings can be applied to the maximum capture
problems under various random utility models in the literature, including the
popular multinomial logit, nested logit, cross nested logit, and the mixed
logit models.
