A modified genetic algorithm for the capacitated competitive facility location problem with the partial demand satisfaction

Competitive facility location problem is a typical optimization problem which is also associated with the game theory. The very first assumption of this problem is the competitive nature of the market. In essence, the problem is composed of two competitors (a leader and a follower) who seek to attract customers by establishing new facilities and consequently to maximize their own profit. In this research, the capacitated competitive facility location problem is introduced. The limited capacity of facilities is more compatible with real world situations. The possibility of not satisfying some of the customers' demands increases the complexity of the problem. In the first proposed problem, the facility establishment is affected by the attractiveness of facilities, which is directly in relation with their proximity to the customers. In addition, customers may be rejected by a facility because of capacity constraints which is also a novel point. In order to consider a more realistic environment, we present a second problem which enables the follower to partially (due to the capacity limitation of the facilities) satisfy the demand of a customer that is supposed to be met by the leader. To find a near optimal solution for the two proposed problems, we develop two algorithms (GA and PSO), which solve an IP (MIP) model for evaluation of the fitness function. The effectiveness of the algorithm is validated by applying it to semi-benchmark problems and comparing the results with those obtained from an exact method which is a combination of complete enumeration and mathematical model. Computational results show a very small deviation among the results of the proposed GA and the exact method (3% in average) for the small-size instances, also the proposed GA outperforms the PSO algorithm for the medium- and large-size instances. Moreover, a quasi-real case is studied which deals with locating competitive after-sale service facilities in a metropolis. The results show that (i) ignoring the competition will result in 122% and 236% decrease in the value of profit for the leader and the follower companies, respectively, and (ii) the option of follower to partially satisfy the demand of a customer will result in a better equilibrium such that 10% and 12% increase in the value of profit will occur for the leader and the follower companies, respectively.