杨晓兵，王 勤

(中国计量大学 理学院，浙江 杭州 310018)

圈图上的两类组合优化问题

杨晓兵，王 勤

(中国计量大学 理学院，浙江 杭州 310018)

在圈图上研究了两类组合优化问题.第一类问题主要研究在要求图中各边的最大调整费用不能超过给定预算时，如何对各边权进行调整，使得其他各顶点到给定顶点的距离之和最大，得到了线性时间算法；第二类问题主要研究在要求圈图上的所有边的调整费用之和不超过给定预算时，如何对各边权进行调整，使得某一固定顶点到给定顶点的距离尽可能的大，得到了求解该问题的多项式时间算法.

圈图；组合优化问题；多项式时间算法

组合优化是运筹学和理论计算机科学的重要分支. 在对组合优化问题的研究中，我们希望找到问题的多项式时间算法. 但是当一个组合优化问题是NP-困难问题时，我们则致力于寻找该问题在特殊情形下的多项式时间算法，比如说在树图、圈图、星图、二分图等特殊网络结构中对问题进行研究.

本文研究了圈图上的两类组合优化问题. 圈图是一类特殊的网络结构,被国内外学者广泛研究,并在实际生活中得到应用.例如城市规划中的选址问题,要在城市中选择一些地点作为医院、学校、图书馆、消防站等，或者作为机场、垃圾站、燃气厂、发电厂等. 前者称为非厌恶型选址问题，后者为厌恶型选址问题. 在一些情况下，如果设施已经存在，我们就需要在一定的预算下调整网络参数，使得调整后的网络尽可能的满足要求[1]. 以上问题都可以转化为圈图上的最优化问题.

文献[2]研究了在中欧铁路货运集拼方案的设想基础上,通过构建混合整数规划模型,研究社会福利最大化时的铁路货运集拼中心的最优选址与顾客选择.文献[3]研究了需求和供给不确定的物流网络选址问题.在假设随机变量服从正态分布的前提下，给出一个确定型模型，并用拉格朗日松弛算法的改进算法进行求解，其结果证明了算法的有效性.文献[4]针对垃圾中转站选址问题进行了研究，构建了多目标情形下的基于逆向物流网络的中转站选址模型,并采用基于遗传算法的多目标进化算法对模型进行了求解.最后通过实际算例对模型及算法进行了验证.文献[5]用改进蚁群算法对应急物流中心选址问题进行了研究.文献[6]研究了特殊圈上的逆1-maxian问题，给出了一个多项式时间算法并得到了任意预算下的最优解.文献[7]研究了在时间限制条件下，面向节点成本的物流中心选址问题.通过分析问题的求解模型，证明了该问题是NP-困难的，并给出了一个近似比为ln(n)的随机近似算法.文献[8]用分支切割算法研究了厌恶型p-median选址问题，并通过求解其0-1规划模型证明了该算法的有效性.文献[9]研究了电力系统设施选址优化问题，该问题是NP-困难的.文献[9]用改进的遗传算法与局部搜索算法解决了该问题并为企业提供了切实可行的方案.文献[10]研究了危险废弃物回收中心选址问题,将风险最小化和风险公平性最大化这两个目标函数结合起来,构造出模型，并用改进重心法进行了求解.

以下是本文各节的主要内容.在第一节中，我们给出圈图上的第一类组合优化问题的具体描述和求解该问题的线性时间算法；在第二节中，我们研究了圈图上的第二类组合优化问题，即如何在现有的费用预算下调整网络的参数，使得网络中的一个固定顶点到给定顶点的距离尽可能的大.我们得到了求解该问题的多项式时间算法.在第三节中，我们给出了一些下一步可以继续研究的问题.

1 第一类优化问题及其算法

我们将证明如果该问题的最优解集X≠∅，那么存在x∈X满足0≤xi≤bi,i=1,…,n.我们有以下定理:

如果在权w下，圈图上的顶点vj,j∈{1,…,n-1}满足

则称顶点vj为在权向量w下的圈图的中心点.我们可得到以下算法1.

算法1:

第3步 最优权调整向量即为x*，最优目标函数值为

定理2 算法1可以正确求解圈图上的第一类组合优化问题，其时间复杂性为O(n).

此时目标函数值

在第1步中，对每条边做增量需要进行一次除法和一次比较操作，所以共需要O(n)时间.求出圈图的中心点需要每次进行一次加法和一次与m的比较操作，因此也需要O(n)时间.计算D*也可以在O(n)时间内完成.因此，算法1的时间复杂性为O(n).

2 第二类优化问题及其算法

本节主要研究圈图上的第二类组合优化问题.这里我们要研究的圈图和其中的参数与第一节中相同.但在该问题中，我们给出一个固定顶点vs,s∈{1,…,n-1}.我们要求当所有边的调整费用之和不超过费用预算B时，如何调整边上的权值，使得vs到v0的距离尽可能的大.与定理1的证明方法类似可知，我们可以只考虑圈图上每条边的权值不能减少的第二类组合优化问题.因此，该问题可以描述为如下的数学规划问题:

算法2:

在第2步中，我们对v0到vs长度较小的路上的边权进行调整.每一条边权的增量受到费用、调整量的上界和v0到vs两条路长度差Δd的限制.若达到了费用限制或所有边调整到上界的费用之和不超过费用限制，且所有边调整量上界之和不超过Δd，则停止，已找到最优解.若达到了Δd的限制，则此时vs是新的边权向量下圈图的中心点，在保持vs是中心点的情况下，我们继续进行后面的运算.若达到了边上调整量上界的限制，我们继续对下一条单位费用最小的边进行调整.

当vs成为中心点时，我们进行第3步.在这一步，我们每次分别考虑一条E1和E2中的单位调整费用最小的边，在这两条边的调整量的上界和费用的限制下，对这两条边作相同的增量，若达到了费用限制，则停止，此时已找到最优解.若达到了某条边调整量的上界，则继续考虑下一条单位调整费用最小的边.若有某一条路上的边已不能再作调整，则此时也得到最优解.因此，我们有以下的定理3.

定理3 算法2可以正确求解圈图上的第二类组合优化问题，其时间复杂性为O(nlogn).

证明:算法2的正确性可由以上分析得出.在第1步，我们分别对两部分边的费用作递增排序，这需要O(nlogn)的时间.在第2步和第3步中，我们依次对边权作增量，这需要O(n)时间.所以，算法2的时间复杂性为O(nlogn).

3 结 语

本文研究了圈图上的两类组合优化问题，分别得到了求解问题的线性时间算法和多项式时间算法.下一步，我们可以继续考虑这两类问题在其他范数下的模型求解，也可以继续对其他网络结构中的问题模型进行研究.

[1] ZHANG J Z, LIU Z H, MA Z F.Some reverse location problems[J]. European Journal of Operational Research,2000,124(1):77-88.

[2] 蒋雪莹,王晓蕾,朱道立.“一带一路”战略下的物流基础设施选址问题研究[J].上海管理科学,2015,37(5):1-6. JIANG X Y, WANG X L, ZHU D L. Research on the problem of site selection of logistics infrastructure under the “one belt one road” development strategy [J]. Shanghai Management Science,2015,37(5):1-6.

[3] 何方国.随机条件下一个网络选址问题的模型及算法[J].武汉理工大学学报(信息与管理工程版)，2015,37(3):274-277. HE F G. A model and algorithm on logistics location under uncertainty [J]. Journal of WUT(Information & Management Engineering),2015，37(3):274-277.

[4] 陈燕升.基于遗传算法的城市生活垃圾中转站选址问题研究[J].物流技术,2014,33(8):275-277,329. CHEN Y S. Study on location problem of urban domestic trash transfer station based on genetic algorithm[J]. Logistics Technology,2014,33(8):275-277,329.

[5] 韦晓,常相全.基于改进蚁群算法的应急物流中心选址问题研究[J].价值工程,2014,33(17):26-27. WEI X, CHANG X Q. Emergency logistics center location issue based on improved ant colony algorithm[J]. Value Engineering,2014,33(17):26-27.

[6] 朱芳，王勤.特殊圈上的逆1-maxian问题[J].中国计量学院学报,2014,25(4):439-442. ZHU F, WANG Q. Inverse 1-maxian problem on special cycles[J]. Journal of China University of Metrology,2014,25(4):439-442.

[7] 孙玉芳,王守强.应急物流中心选址问题算法研究[J].新型工业化，2014,4(6):37-42. SUN Y F, WANG S Q. Algorithm for emergency logistics center location[J]. The Journal New Industrialization,2014,4(6):37-42.

[8] PIETRO B, MARTINE L, FRANCESCO M. A branch-and-cut method for the obnoxious p-median problem[J]. 4OR-A Quarterly Journal of Operations Research,2007,5(4):299-314.

[9] 莫汉培,陈秋良,张子臻.遗传算法求解电力设施选址问题[J].计算机技术与发展,2016,26(3):197-201. MO H P, CHEN Q L, ZHANG Z Z. Solving grid system facility location problem based on improved genetic algorithm[J].Computer Technology and Development,2016,26(3):197-201.

[10] 程珩,牟瑞芳.基于改进重心法的危险废弃物回收中心选址问题研究[J].交通运输工程与信息学报,2014,12(4):109-113. CHENG Y, MOU R F.Location research of hazardous waste recycling center based on improved gravity method[J]. Journal of Transportation Engineering and Information,2014,12(4):109-113.

Two combinatorial optimization problems on cycles

YANG Xiaobing, WANG Qin

(College of Sciences, China Jiliang University, Hangzhou 310018, China)

Two combinatorial optimization problems were studied on cycle graphs. One was how to adjust the weight of each edge to avoid the cost of each edge exceeding the given budget, to adjust the sum of distances from all the other vertices to the maximum. A linear-time algorithm was proposed. The other problem was to adjust the edge weights to avoid the cost of each edge exceeding the given budget, and to adjust the distance from a fixed vertex to the given vertex to the maximum. A polynomial-time algorithm was also presented in this case.

cycle graph; combinatorial optimization problem; polynomial-time algorithm

2096-2835(2017)02-0247-05

10.3969/j.issn.2096-2835.2017.02.018

2017-01-21 《中国计量大学学报》网址：zgjl.cbpt.cnki.net

国家自然科学基金资助项目(No. 11171316).

杨晓兵(1989-)，男，山西省忻州人，硕士研究生，主要研究方向为网络优化.E-mail: yangxiaobing467977@163.com 通信联系人：王勤，女，教授. E-mail: wq@cjlu.edu.cn

TP301；O221

A