Optimally locating facilities with variable characteristics

Abstract

Facility location problems aim at optimally locating facilities like plants, warehouses, convenience stores, shopping malls etc. They can have di erent objectives such as maximizing the pro t gained from the customers or minimizing the costs of locating facilities and serving the customers. In this thesis, we mainly focus on competitive facility location problems which constitute a special family. In a competitive facility location problem, a rm or franchise is concerned with installing new facilities to serve customers in a market where existing facilities with known locations and attractiveness levels compete for increasing their market share and pro t. We can classify these problems into two groups: those with non-reactive competition and those with reactive competition. Three di erent types of competitive facility location models are proposed in order to determine the locations and attractiveness levels of the new facilities to maximize the pro t in this thesis. The rst one belongs to the former class, where the last two models fall into the latter one. We formulate the rst one as a mixed-integer nonlinear programming problem and propose three methods for its solution: a Lagrangean heuristic, a branch-and-bound method with Lagrangean relaxation, and a branch-and-bound method with nonlinear programming relaxation. The computational results obtained on a set of problem instances show that the branch-and-bound method using nonlinear programming relaxation is the most e cient and accurate solution method in order to solve the proposed problem. We consider next an extension of this model by relaxing the assumption that the competitor in the market does not react to the opening of new facilities. In other words, the competitor can react by adjusting the attractiveness levels of its existing facilities with the objective of maximizing its own pro t. To this end, a bilevel mixed-integer nonlinear programming model is formulated. We transform this bilevel model into an equivalent one-level mixed-integer nonlinear program and solve it by a global optimization method. For this problem, we also consider a scenario in which the new entrant rm ignores the reaction of the competitor. The experimental results indicate that anticipating the competitor's reaction by including this into his optimization problem increases the pro t of the new entrant rm, whereas the competitor's pro t is decreased. The last competitive facility location model relaxes the limitation about the competitor's reaction: now the competitor can also open new facilities, close existing ones and/or adjust their attractiveness. This also formulates a bilevel mixed-integer nonlinear programming problem which we try to solve by combining tabu search with global optimization algorithms. We develop three di erent tabu search methods and the computational results on a set of problem instances for comparing the performance of the solution methods show that the third tabu search method is the most accurate one, while the second tabu search method is the most e cient solution procedure. Finally, we consider a di erent facility location problem which takes the customer preferences into account. The facilities are not necessarily identical and customers visit di erent types of facilities according to some given probability distribution and the maximum distance which they are willing to travel. We formulate a binary linear programming problem and solve it by three procedures that include a Lagrangean heuristic whose solution is improved further using a local search method. Based on the experimental results carried out on a set of problem instances the third solution method is the most e cient one. However, a statistical analysis on the quality of the solutions states that there is no signi cant di erence between the three solution procedures.