The 1-median Location Problem With Center Constraint

The center and median location problems are classical location models which have significant foundations in the research field of location theory.In this paper,we consider the combination of these two classic problems and develop three new location models based on the need of location problems for fresh supermarkets in actual application.These three models are the 1-median location problem with center constraint on trees,the 1-center location problem with median constraint on trees,the max+sum location problem on trees.For each problem,we consider two classes subproblems including vertex type and absolute type subproblems.A vertex type location problem means that the location can be only chose on the set of vertices in a graph.An absolute type location problem means that the location can be chose both on the set of vertices and on any point of an edge in a graph.In Chapter 2,we consider the 1-median location problem with center constraint on trees.For the vertex type subproblem,we solve it by the weighted distance matrix of the tree,and present an algorithm with time complexity O(n2),where n is the number of nodes in the tree.For the absolute type subproblem,it is necessary to further determine the properties of the feasible solution and the optimal solution.The global optimal solution can be obtained by comparing local optimal solution in the feasible region.We also propose an algorithm with time complexity O(n2).In Chapter 3,we consider the 1-center location problem with median constraint on trees.For the vertex type subproblem,we devise a binary search algorithm,in each iteration,we solve a vertex-type 1-median location problem with center constraint on trees.Hence,the time complexity is O(n2 log n).For the absolute type subproblem,after finding the feasible region for the subproblem defined on an edge,we transform the problem into a 1-center location problem on trees.The time complexity of the algorithm is O(n2)time.In Chapter 4,we consider the max+sum location problem on trees For the vertex type sub-problem,we solve it directly by using the traversal algorithm,and the time complexity is O(n2).For the absolute type subproblem,we first solve the local optimal value for the subproblem defined on an edge,which can be turned into a 1-center location problem with a new weights defined on the tree.Then we prove that the optimal solution must be obtained at some turning point.Therefore,the problem can be solved in O(n2logn)time.