Maximum Capture Location Problem with Random Utilities and Overflow Penalties

This paper extends the maximum capture location problem with random utilities by incorporating the facility capacity and introducing penalties for overflows into the objective function. We propose a method that combines the key features of two state-of-the-art approaches for the uncapacitated case, which are adapted to solve the problem at hand. The first approach is a linear reformulation that extends the best-known linearization in the literature, which is based on variable substitution. The second approach is a reformulation that incorporates outer-approximation cuts and enhanced submodular cuts, solving the problem via a branch-and-cut approach. We tested the performance of the three approaches on several instances and show that the combined method outperforms each of the preceding techniques. The optimal location patterns of the model are also analysed, and it is found that considering the overflow and overflow penalties in the objective function affects the location decisions. The resulting optimal locations align more closely with practical scenarios. © 2025 Elsevier Ltd