Optimally Locating Facilities with Variable Characteristics

Facility location problems aim at optimally locating facilities like plants, warehouses, convenience stores, shopping malls etc. They can have different objectives such as maximizing the profit 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 firm 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 profit. We can classify these problems into two groups: those with non-reactive competition and those with reactive competition. Three different types of competitive facility location models are proposed in order to determine the locations and attractiveness levels of the new facilities to maximize the profit in this thesis. The first one belongs to the former class, where the last two models fall into the latter one.

We formulate the first 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 efficient 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 profit. 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 firm 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 profit of the new entrant firm, whereas the competitor's profit 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 different 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 efficient solution procedure.

Finally, we consider a different facility location problem which takes the customer preferences into account. The facilities are not necessarily identical and customers visit different 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 efficient one. However, a statistical analysis on the quality of the solutions states that there is no significant difference between the three solution procedures.