The capacitated facility location problem with customer preferences

Facility location problems (FLPs) play an essential role in operations research literature due to their applicability to many real world problems. In their basic version, FLPs consist in choosing sites for opening facilities to provide some service for customers, and assigning these customers to open facilities. The aim is to minimise the total opening and assignment costs in order to maximise the society’s accumulated benefit. The individual needs of customers, however, are neglected by this objective: Customers, are treated as passive participants who will gladly follow their determined assignment. This is acceptable if customers correspond to inanimate objects yet might lack realism if customers are actual people. In this work, we study a variation of the basic FLP in which we are given a preference ranking of all facilities for each customer. Furthermore, we associate each customer with a demand, and each facility with a capacity for serving customer demands. In addition to the basic objective, each customer now has to be served at exactly one of their most-preferred open facilities and the capacity at each open facility has to be respected. This problem is known as the single-source capacitated facility location problem with customer preferences (CFLP-CP). We analyse combinatorial structures and develop exact methods for the CFLP-CP. While the problem’s strong NP-completeness is expected, we observe that the structure of the customer preferences has an important impact on the problem’s complexity. If each customer has a strict preference order, the problem’s feasibility can be determined in polynomial time (Theorem 3), which is in contrast to the capacitated facility location problem without preferences. If preferences are defined by assignment costs, the problem can be solved in polynomial time if assignment costs are defined on a path (Theorem 12). While preference constraints can ease the complexity of assigning customers, we observe that they increase the complexity of locating facilities (Theorem 6). In addition to a detailed analysis of the problem’s computational complexity, we also contribute to practical algorithms for solving the CFLP-CP. We introduce novel preprocessing methods and valid inequalities for integer programs by utilising combinatorial structures implied by customer preferences (Chapter 5). In a computational study, we observe that our preprocessing improves the performance of state-of-the-art solvers and our inequalities successfully reduce the integrality gap. We furthermore propose a solver-free combinatorial branch-and-bound (B&B) algorithm for the CFLP-CP with strict customer preferences, which utilises insights from our analysis of the problem’s combinatorial structures (Chapter 6). In a second computational study, we observe that our B&B algorithm finds better primal solutions for more instances than a state-of-the-art solver and, if slowly, makes progress on solving instances with 1000 customers and 1000 facilities for which a state-of-the-art solver fails.