图上的路选址问题与连通p-中心和p-中位问题

发布时间：2017-12-26 22:19

本文关键词：图上的路选址问题与连通p-中心和p-中位问题　出处：《上海大学》2016年博士论文　论文类型：学位论文

【摘要】：选址问题是运筹学中重要的问题之一.设施选址问题的应用十分广泛,从城市,产业带,经济技术开发区到机场,水利设施,销售网点以及仓库都涉及到选址问题,涉及经济,政治,社会,管理,心理及工程地质等多门学科.本文主要研究了一些特殊图上路选址问题,连通p-中心和p-中位选址问题.人们已经证明路选址问题和连通p-中心和p-中位选址问题在一般图上都是NP-困难问题,因此考虑这些问题在某些图类上的多项式算法就成为有意义的问题.本文着重讨论了树(tree),区间图(interval graph),圆弧图(circular-arc graph)和块图(block-graph)等重要图类上的算法设计问题.首先,我们介绍了选址问题的背景和本文涉及的相关记号及术语,并提出了本文研究的主要问题.本文所做的主要研究工作如下：第二章,研究了树上的半厌恶型p-路选址问题.当p=2时,即树上的半厌恶型2-路选址问题,对该问题的MWD模型和WMD模型,分别设计了O(n2)和O(n3)时间算法.对p2时,考虑相交p-路和不相交p-路这两种特殊的情形.树上的半厌恶型相交p-路问题的MWD模型和WMD模型都可以转化为树上的k-子树核心问题,由此可证明该问题可以在多项式时间内求解.对树上的半厌恶型不相交p-路选址问题的MWD模型,我们设计了O(np+1)时间算法；而对于该问题的WMD模型,给出了其最优解得一些性质.第三章,应用鲁棒优化理论研究了带区间权重的树上的鲁棒核心选址问题,其中允许顶点的权重为负数.对绝对鲁棒核心选址问题设计了O(n2)时间算法.对偏差鲁棒核心选址问题,证明了该问题的计算复杂性为O(n3).第四章,讨论区间图和圆弧图上的连通p-中心和p-中位选址问题.在区间图上,证明了连通p-中心问题和连通p-中位问题的计算复杂性都是O(n).在圆弧图上,证明了连通p-中心问题可以在O(n)时间内求解,而连通p-中位问题可以在O(n2)时间内求解.第五章,讨论了块图上的连通p-中心和p-中位选址问题.对连通p-中心问题给出了O(mn logn)时间算法,对连通p-中位问题,证明了该问题线性时间可解.对双目标规划：连通p-中心-中位问题,证明了该问题的计算复杂性为O(n2),并且帕雷托最优解的个数不超过n个.对厌恶型连通p-中心和p-中位问题分别给出了O(mn)时间算法和O(p2mn)的拟多项式时间算法.最后给出了需要进一步研究的问题.
[Abstract]:The location problem is one of the important problems in operational research. The application of the facility location problem is very wide, from the city, industrial zone, economic and Technological Development Zone to the airport, water conservancy facilities, warehouse and sales outlets are related to the location problem, involving economic, political, social, management, psychology and many other disciplines. The main engineering geology study on some special graphs on the site, p- and p- in a connected center location problem. It was proved that the road location problem and connected p- center and p- in a location problem in general graphs is NP- hard problem, so consider these problems in some classes of Graphs of the polynomial algorithm becomes a significant problem. This paper focuses on the tree (tree), interval graph (interval graph), arc (circular-arc graph) and block diagram (block-graph) and other important classes of graphs the algorithm design problems. First, we introduce the location problem. Mark and related background and terminology related to this article, and put forward the main problem in this paper. The main research work is as follows: the second chapter studies the tree semi averse p- road location problem. When p=2, the tree half averse 2- road location problem, MWD model and WMD the model of this problem, we have designed a O (N2) and O (N3) time algorithm. On P2, consider the intersection of p- road and p- Road intersection of the two special cases. MWD model and WMD model of p- Road intersection of half averse tree can be transformed into a tree the k- subtree is the core problem, which can prove that the problem can be solved in polynomial time. MWD model of semi averse tree disjoint p- road location problem, we design a O (np+1) time algorithm; and the WMD model of this problem is given, some properties of the optimal solution is third. Chapter, with robust optimization The theory of robust core with interval weight tree location problem, which allows for the negative weight vertex. The location problem of robust core design of O (N2) time algorithm of robust deviation. The core location, proved that the computational complexity of this problem is O (N3). The fourth chapter discusses connected p- the center and p- interval graphs and circular arc graphs the median location problem. On interval graphs, and proves the complexity of connected p- center problem and connected p- problems are O (n). In the arc, proved that connected p- center problem in O (n) time solution. The connected p- median problem in O (N2) time. The fifth chapter discusses the connected p- center and p- block on the map in a location problem. Given the O of p- Center (Mn logn connectivity) time algorithm on a connected p-, it is proved that the linear time the solution of binocular standards. Row: p- connectivity Center - median problem, proved that the computational complexity of this problem is O (N2), and the number of Pareto optimal solutions of no more than n. The aversion connected p- center and p- are presented respectively in O (MN) and O (p2mn) time algorithm for quasi polynomial time the algorithm is given. The problems that need further study.
【学位授予单位】：上海大学
【学位级别】：博士
【学位授予年份】：2016
【分类号】：O22

【相似文献】