Path Location, Connected P-Center And P-Median Problems On Graphs

Facility location problem is one of the important problems in operational re-search. Facility location problem has very wide application, from the city, industry area, economic and technological development zone to the airport, water conser-vancy facilities, sales network and warehouse, involves different subjects such as the economic, political, social, management, psychology and engineering geology, all these problems related to the location theory. This article mainly studied the path location and the connected p-center and p-median location problems in some spe-cial graphs. It has been proved that the path location and the connected p-center and p-median location problems are NP-hard in general graphs, so it is meaningful to consider these problems in special graphs, to see if there is a polynomial time algorithm. This article focuses on the algorithm design of problems in tree graphs, interval graphs, circular-arc graphs and block graphs.First of all, we briefly describe the background of the facility location problem, introduce the involved symbols and terminologies, then represent the problems to study in this paper.In Chapter 2, we analysis the p-path location problem in trees with positive or negative weights. When p=2, for the MWD model and WMD model, we design an O(n2) and O(n3) time algorithm, respectively. When p>2, we consider two special cases:the intersection p-path and disjoint p-path. The MWD model and WMD model of the intersection p-path problem can be reduced to the k-subtree problem, therefore, two models of the problem can be solved in polynomial time. For the MWD model of the disjoint p-path problem, we design an O(np+1) time algorithm, for the WMD model of this problem, we get some optimal properties.In Chapter 3, we apply the robust optimization theory to study the robust path median problem on trees with interval weight, in which the vertex weights may be negative. For the absolute robust path median problem, we formulate an O(n2) time algorithm. The deviation robust path median problem can be solved in O(n3) time.In Chapter 4, we discuss the connected p-center and p-median location problem on interval graph and circular-arc graph. We show that the connected p-center problem and the connected p-median problem on interval graph can be solved in linear time. On circular-arc graph, the connected p-center problem can be solved in O(n) time and the connected p-median problem can be solved in O(n2) time.In Chapter 5, we give an O(mn log n) time algorithm for the connected p-center problem and show that the connected p-median problem can be solved in linear time. For the bi-objective problem:the connected p-centdian problem, there are at most n Pareto optimal solution which can be found in O(n2). Later, an O(mn) time and an O(p2mn) pseudo-polynomial time algorithm were illustrated for the obnoxious connected p-center and p-median problem, respectively.In the end, we prospect the future research work.