Insights into the computational complexity of the single-source capacitated facility location problem with customer preferences

Abstract Single-source capacitated facility location problems are well studied in the operations research literature, yet classic problems often lack practicability by disregarding the customers’ perspective: An authority that assigns customers to open facilities deprives customers from choosing facilities according to their individual preferences. In reality, this can render solutions infeasible, as customers may deviate to their most preferred open facility, thereby breaking capacities of facilities serving more customers than originally planned. Preference constraints aim to prevent this by ensuring that each customer is served at their most preferred open facility. The corresponding problem is called single-source capacitated facility location problem with customer preferences ( CFLP-CP ) and is known to be strongly NP-hard. In this paper, we provide a deeper understanding of the transition from polynomially solvable cases to strongly NP-hard cases of the CFLP-CP. In particular, we show that the effect of preference constraints on the theoretical complexity can go both ways: Some problems become harder, while others become easier. This is because preference constraints simplify the assignment of customers to facilities, while simultaneously increasing the complexity of locating facilities. We show that the type of customer preferences, e.g., strict preferences or geographically closest assignments, has a vital impact on the complexity. Notably, strict preferences, i.e., customers cannot be indifferent, allow to compute feasible solutions of the CFLP-CP in polynomial time.