Research On Mathematical Models And Optimization Algorithms For Facility Location Problems

This thesis studies mathematical models and optimization algorithms for facility location problems. First, the main progress of location problems, especially the competitive facility location is reviewed. Several classic models and algorithms are discussed. Then we mainly present the following four research results:1. With the background of Ad Hoc network an optimization model for district partition and node location is proposed based on the Voronoi diagram. When the district is a simple connected domain, topological properties of its solution are proved. Then a new evaluating indicator is defined for the network connectivity. What's more, survivability is discussed by minimum spanning tree. When the district is a complex connected domain, a reduced model is obtained by penalty function method and using Monte Carto simulation, we get a satisfactory solution.2. A two-stage location-pricing game model with stochastic customer behavior on a network is investigated. We provide definitions for its solution and a sufficient condition for the existence of equilibrium prices in the subgame. The existence and uniqueness of the pure strategy Nash equilibrium price with a specified utility function is proved. A mixed heuristic based on tabu search is developed to find the optimal location-price solution of the model. In addition, we conduct sensitivity analysis of numerical examples and some interesting managerial insights are proposed.3. Framework for location-pricing problem is proposed using biform game theory. Location strategy is investigated in Stage 1 noncooperatively, while pricing strategy is decided in Stage 2 cooperatively. Finally, procedures for the algorithm and some further ideas are presented.4. An optimization model with time and capacity constraints is proposed for road planning and vehicle scheduling problem in logistics. We analyze the travelling salesman problem(VRP) by breaking the travelling circle. An improved ant colony algorithm is developed using penalty function method, in which the circuitry information is fed back to the objective function. Results show the algorithm is efficient and it could be applied to problems with different types of objective and complex constraints.