圈圖上的兩類組合優(yōu)化問題

楊曉兵，王 勤

(中國(guó)計(jì)量大學(xué) 理學(xué)院，浙江 杭州 310018)

圈圖上的兩類組合優(yōu)化問題

楊曉兵，王 勤

(中國(guó)計(jì)量大學(xué) 理學(xué)院，浙江 杭州 310018)

在圈圖上研究了兩類組合優(yōu)化問題.第一類問題主要研究在要求圖中各邊的最大調(diào)整費(fèi)用不能超過給定預(yù)算時(shí)，如何對(duì)各邊權(quán)進(jìn)行調(diào)整，使得其他各頂點(diǎn)到給定頂點(diǎn)的距離之和最大，得到了線性時(shí)間算法；第二類問題主要研究在要求圈圖上的所有邊的調(diào)整費(fèi)用之和不超過給定預(yù)算時(shí)，如何對(duì)各邊權(quán)進(jìn)行調(diào)整，使得某一固定頂點(diǎn)到給定頂點(diǎn)的距離盡可能的大，得到了求解該問題的多項(xiàng)式時(shí)間算法.

圈圖；組合優(yōu)化問題；多項(xiàng)式時(shí)間算法

組合優(yōu)化是運(yùn)籌學(xué)和理論計(jì)算機(jī)科學(xué)的重要分支. 在對(duì)組合優(yōu)化問題的研究中，我們希望找到問題的多項(xiàng)式時(shí)間算法. 但是當(dāng)一個(gè)組合優(yōu)化問題是NP-困難問題時(shí)，我們則致力于尋找該問題在特殊情形下的多項(xiàng)式時(shí)間算法，比如說在樹圖、圈圖、星圖、二分圖等特殊網(wǎng)絡(luò)結(jié)構(gòu)中對(duì)問題進(jìn)行研究.

本文研究了圈圖上的兩類組合優(yōu)化問題. 圈圖是一類特殊的網(wǎng)絡(luò)結(jié)構(gòu),被國(guó)內(nèi)外學(xué)者廣泛研究,并在實(shí)際生活中得到應(yīng)用.例如城市規(guī)劃中的選址問題,要在城市中選擇一些地點(diǎn)作為醫(yī)院、學(xué)校、圖書館、消防站等，或者作為機(jī)場(chǎng)、垃圾站、燃?xì)鈴S、發(fā)電廠等. 前者稱為非厭惡型選址問題，后者為厭惡型選址問題. 在一些情況下，如果設(shè)施已經(jīng)存在，我們就需要在一定的預(yù)算下調(diào)整網(wǎng)絡(luò)參數(shù)，使得調(diào)整后的網(wǎng)絡(luò)盡可能的滿足要求[1]. 以上問題都可以轉(zhuǎn)化為圈圖上的最優(yōu)化問題.

文獻(xiàn)[2]研究了在中歐鐵路貨運(yùn)集拼方案的設(shè)想基礎(chǔ)上,通過構(gòu)建混合整數(shù)規(guī)劃模型,研究社會(huì)福利最大化時(shí)的鐵路貨運(yùn)集拼中心的最優(yōu)選址與顧客選擇.文獻(xiàn)[3]研究了需求和供給不確定的物流網(wǎng)絡(luò)選址問題.在假設(shè)隨機(jī)變量服從正態(tài)分布的前提下，給出一個(gè)確定型模型，并用拉格朗日松弛算法的改進(jìn)算法進(jìn)行求解，其結(jié)果證明了算法的有效性.文獻(xiàn)[4]針對(duì)垃圾中轉(zhuǎn)站選址問題進(jìn)行了研究，構(gòu)建了多目標(biāo)情形下的基于逆向物流網(wǎng)絡(luò)的中轉(zhuǎn)站選址模型,并采用基于遺傳算法的多目標(biāo)進(jìn)化算法對(duì)模型進(jìn)行了求解.最后通過實(shí)際算例對(duì)模型及算法進(jìn)行了驗(yàn)證.文獻(xiàn)[5]用改進(jìn)蟻群算法對(duì)應(yīng)急物流中心選址問題進(jìn)行了研究.文獻(xiàn)[6]研究了特殊圈上的逆1-maxian問題，給出了一個(gè)多項(xiàng)式時(shí)間算法并得到了任意預(yù)算下的最優(yōu)解.文獻(xiàn)[7]研究了在時(shí)間限制條件下，面向節(jié)點(diǎn)成本的物流中心選址問題.通過分析問題的求解模型，證明了該問題是NP-困難的，并給出了一個(gè)近似比為ln(n)的隨機(jī)近似算法.文獻(xiàn)[8]用分支切割算法研究了厭惡型p-median選址問題，并通過求解其0-1規(guī)劃模型證明了該算法的有效性.文獻(xiàn)[9]研究了電力系統(tǒng)設(shè)施選址優(yōu)化問題，該問題是NP-困難的.文獻(xiàn)[9]用改進(jìn)的遺傳算法與局部搜索算法解決了該問題并為企業(yè)提供了切實(shí)可行的方案.文獻(xiàn)[10]研究了危險(xiǎn)廢棄物回收中心選址問題,將風(fēng)險(xiǎn)最小化和風(fēng)險(xiǎn)公平性最大化這兩個(gè)目標(biāo)函數(shù)結(jié)合起來,構(gòu)造出模型，并用改進(jìn)重心法進(jìn)行了求解.

以下是本文各節(jié)的主要內(nèi)容.在第一節(jié)中，我們給出圈圖上的第一類組合優(yōu)化問題的具體描述和求解該問題的線性時(shí)間算法；在第二節(jié)中，我們研究了圈圖上的第二類組合優(yōu)化問題，即如何在現(xiàn)有的費(fèi)用預(yù)算下調(diào)整網(wǎng)絡(luò)的參數(shù)，使得網(wǎng)絡(luò)中的一個(gè)固定頂點(diǎn)到給定頂點(diǎn)的距離盡可能的大.我們得到了求解該問題的多項(xiàng)式時(shí)間算法.在第三節(jié)中，我們給出了一些下一步可以繼續(xù)研究的問題.

1 第一類優(yōu)化問題及其算法

我們將證明如果該問題的最優(yōu)解集X≠?，那么存在x∈X滿足0≤xi≤bi,i=1,…,n.我們有以下定理:

如果在權(quán)w下，圈圖上的頂點(diǎn)vj,j∈{1,…,n-1}滿足

則稱頂點(diǎn)vj為在權(quán)向量w下的圈圖的中心點(diǎn).我們可得到以下算法1.

算法1:

第3步 最優(yōu)權(quán)調(diào)整向量即為x*，最優(yōu)目標(biāo)函數(shù)值為

定理2 算法1可以正確求解圈圖上的第一類組合優(yōu)化問題，其時(shí)間復(fù)雜性為O(n).

此時(shí)目標(biāo)函數(shù)值

在第1步中，對(duì)每條邊做增量需要進(jìn)行一次除法和一次比較操作，所以共需要O(n)時(shí)間.求出圈圖的中心點(diǎn)需要每次進(jìn)行一次加法和一次與m的比較操作，因此也需要O(n)時(shí)間.計(jì)算D*也可以在O(n)時(shí)間內(nèi)完成.因此，算法1的時(shí)間復(fù)雜性為O(n).

2 第二類優(yōu)化問題及其算法

本節(jié)主要研究圈圖上的第二類組合優(yōu)化問題.這里我們要研究的圈圖和其中的參數(shù)與第一節(jié)中相同.但在該問題中，我們給出一個(gè)固定頂點(diǎn)vs,s∈{1,…,n-1}.我們要求當(dāng)所有邊的調(diào)整費(fèi)用之和不超過費(fèi)用預(yù)算B時(shí)，如何調(diào)整邊上的權(quán)值，使得vs到v0的距離盡可能的大.與定理1的證明方法類似可知，我們可以只考慮圈圖上每條邊的權(quán)值不能減少的第二類組合優(yōu)化問題.因此，該問題可以描述為如下的數(shù)學(xué)規(guī)劃問題:

算法2:

在第2步中，我們對(duì)v0到vs長(zhǎng)度較小的路上的邊權(quán)進(jìn)行調(diào)整.每一條邊權(quán)的增量受到費(fèi)用、調(diào)整量的上界和v0到vs兩條路長(zhǎng)度差Δd的限制.若達(dá)到了費(fèi)用限制或所有邊調(diào)整到上界的費(fèi)用之和不超過費(fèi)用限制，且所有邊調(diào)整量上界之和不超過Δd，則停止，已找到最優(yōu)解.若達(dá)到了Δd的限制，則此時(shí)vs是新的邊權(quán)向量下圈圖的中心點(diǎn)，在保持vs是中心點(diǎn)的情況下，我們繼續(xù)進(jìn)行后面的運(yùn)算.若達(dá)到了邊上調(diào)整量上界的限制，我們繼續(xù)對(duì)下一條單位費(fèi)用最小的邊進(jìn)行調(diào)整.

當(dāng)vs成為中心點(diǎn)時(shí)，我們進(jìn)行第3步.在這一步，我們每次分別考慮一條E1和E2中的單位調(diào)整費(fèi)用最小的邊，在這兩條邊的調(diào)整量的上界和費(fèi)用的限制下，對(duì)這兩條邊作相同的增量，若達(dá)到了費(fèi)用限制，則停止，此時(shí)已找到最優(yōu)解.若達(dá)到了某條邊調(diào)整量的上界，則繼續(xù)考慮下一條單位調(diào)整費(fèi)用最小的邊.若有某一條路上的邊已不能再作調(diào)整，則此時(shí)也得到最優(yōu)解.因此，我們有以下的定理3.

定理3 算法2可以正確求解圈圖上的第二類組合優(yōu)化問題，其時(shí)間復(fù)雜性為O(nlogn).

證明:算法2的正確性可由以上分析得出.在第1步，我們分別對(duì)兩部分邊的費(fèi)用作遞增排序，這需要O(nlogn)的時(shí)間.在第2步和第3步中，我們依次對(duì)邊權(quán)作增量，這需要O(n)時(shí)間.所以，算法2的時(shí)間復(fù)雜性為O(nlogn).

3 結(jié) 語

本文研究了圈圖上的兩類組合優(yōu)化問題，分別得到了求解問題的線性時(shí)間算法和多項(xiàng)式時(shí)間算法.下一步，我們可以繼續(xù)考慮這兩類問題在其他范數(shù)下的模型求解，也可以繼續(xù)對(duì)其他網(wǎng)絡(luò)結(jié)構(gòu)中的問題模型進(jìn)行研究.

[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] 蔣雪瑩,王曉蕾,朱道立.“一帶一路”戰(zhàn)略下的物流基礎(chǔ)設(shè)施選址問題研究[J].上海管理科學(xué),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] 何方國(guó).隨機(jī)條件下一個(gè)網(wǎng)絡(luò)選址問題的模型及算法[J].武漢理工大學(xué)學(xué)報(bào)(信息與管理工程版)，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] 陳燕升.基于遺傳算法的城市生活垃圾中轉(zhuǎn)站選址問題研究[J].物流技術(shù),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ìn)蟻群算法的應(yīng)急物流中心選址問題研究[J].價(jià)值工程,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].中國(guó)計(jì)量學(xué)院學(xué)報(bào),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] 孫玉芳,王守強(qiáng).應(yīng)急物流中心選址問題算法研究[J].新型工業(yè)化，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] 莫漢培,陳秋良,張子臻.遺傳算法求解電力設(shè)施選址問題[J].計(jì)算機(jī)技術(shù)與發(fā)展,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ìn)重心法的危險(xiǎn)廢棄物回收中心選址問題研究[J].交通運(yùn)輸工程與信息學(xué)報(bào),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 《中國(guó)計(jì)量大學(xué)學(xué)報(bào)》網(wǎng)址：zgjl.cbpt.cnki.net

國(guó)家自然科學(xué)基金資助項(xiàng)目(No. 11171316).

楊曉兵(1989-)，男，山西省忻州人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化.E-mail: yangxiaobing467977@163.com 通信聯(lián)系人：王勤，女，教授. E-mail: wq@cjlu.edu.cn

TP301；O221

A