Approximating solutions to a bilevel capacitated facility location problem with customer's patronization toward a list of preferences

This paper presents a bilevel capacitated facility location problem where customers are allocated to the facilities they patronize based on a predetermined list of preferences. The bilevel problem is composed of an upper level, where a company locates facilities to minimize locating and distributing costs; and a lower level, where customers aim to maximize their preferences by being allocated to the most preferred facilities to get their demands met. The complexity of the lower level problem, which is NP-hard, demands alternatives for obtaining, in general, the follower's rational reaction set. Hence, bilevel attainable solutions are defined for solving the bilevel problem in an efficient manner. Moreover, for obtaining valid bounds, a reformulation of the bilevel problem based on the lower level's linear relaxation is performed. Then, a cross entropy method is implemented for obtaining solutions in the upper level; while the lower level is solved in three different manners: by a greedy randomized adaptive procedure based on preferences, by the same procedure but based on a regret cost, and by an exact method (when possible). The conducted experimentation shows the competitiveness of the proposed algorithms, in terms of solution quality and consumed time, despite the complexity of the problem's components.