雙會(huì)議服務(wù)器選址問(wèn)題研究

徐 弈, 陳 瑩

(1.西安理工大學(xué) 經(jīng)濟(jì)與管理學(xué)院,陜西 西安 710054; 2.西安交通大學(xué) 管理學(xué)院,陜西 西安 710049)

0 引言

中心選址問(wèn)題(Center problem)[1,2]與中位選址問(wèn)題(Median problem)[3,4]一直是選址問(wèn)題中的研究熱點(diǎn)與難點(diǎn)。中心選址問(wèn)題可以等價(jià)于求解最小最大問(wèn)題,以歐氏距離下的平面點(diǎn)集k中心選址問(wèn)題為例,其選址目標(biāo)為尋找k個(gè)選址設(shè)施的位置,要求點(diǎn)集中每個(gè)點(diǎn)到這k個(gè)選址設(shè)施的最近距離的最大值最小[5,6]。記P為平面上含有n個(gè)點(diǎn){a1,a2,…,an}的點(diǎn)集,d(x,y)為平面上任意兩點(diǎn){x,y}的歐氏距離,所要尋找的k個(gè)選址設(shè)施為S={s1,s2,…,sk},則中心選址問(wèn)題優(yōu)化模型如下:

直觀地,k中心選址問(wèn)題等價(jià)于求解k個(gè)全等的圓覆蓋整個(gè)點(diǎn)集P,并且要求這些圓的半徑最小，而最優(yōu)解對(duì)應(yīng)的k個(gè)圓心即為設(shè)施的選址位置。

而對(duì)中位選址問(wèn)題而言,該問(wèn)題所對(duì)應(yīng)的幾何結(jié)構(gòu)則沒有中心選址問(wèn)題那么直觀。仍舊以歐式距離下的平面點(diǎn)集k中位選址問(wèn)題為例,其選址目標(biāo)為尋找k個(gè)選址設(shè)施的位置,要求點(diǎn)集中每個(gè)點(diǎn)到這k個(gè)選址設(shè)施的最近距離和最小,對(duì)應(yīng)選址問(wèn)題優(yōu)化模型如下:

無(wú)論是k中心選址問(wèn)題還是k中位選址問(wèn)題,都已經(jīng)被證明問(wèn)題是NP難的[7],故很難給出最優(yōu)解,因此學(xué)者往往考慮如下幾個(gè)問(wèn)題:針對(duì)這兩個(gè)問(wèn)題的近似算法或者啟發(fā)式算法[8,9];在某些特殊距離或者特殊網(wǎng)絡(luò)結(jié)構(gòu)下的中心或k中位選址問(wèn)題[10];考慮當(dāng)k的值比較小時(shí)的中心或中位選址問(wèn)題的最優(yōu)算法[11];以及考慮k中心或中位選址問(wèn)題的衍生問(wèn)題,例如要求k個(gè)設(shè)施之間的距離滿足某些關(guān)系,或者k個(gè)設(shè)施的位置帶有一定的約束(限制在某些點(diǎn)處或者某些區(qū)域內(nèi))[12,13]。

本文考慮平面內(nèi)歐氏距離條件下的2中位選址問(wèn)題的衍生問(wèn)題。2中心或中位選址問(wèn)題直到現(xiàn)在還有許多學(xué)者在研究,2017年,Tan給出了2中心選址問(wèn)題的O(nlog2n)時(shí)間算法[14],該算法的復(fù)雜性已經(jīng)非常接近該問(wèn)題的下界O(nlogn),這改進(jìn)了1999年Chan設(shè)計(jì)的并行計(jì)算算法[15]。而最新的與2中心選址問(wèn)題相關(guān)的文獻(xiàn)是由Xu等人提出的最小最大2中心選址問(wèn)題,該問(wèn)題不僅要求兩個(gè)圓的半徑盡可能小,同時(shí)要求兩個(gè)圓心之間的距離也不能超過(guò)兩個(gè)圓的半徑。2019年他們給出該問(wèn)題的混合(兩個(gè)圓心均在點(diǎn)集內(nèi)部)與離散(只要求一個(gè)圓心在點(diǎn)集內(nèi)部)的情況分別可以在O(n2log2n)和O(n2logn)的時(shí)間進(jìn)行求解[16]。針對(duì)連續(xù)的情況(即對(duì)兩個(gè)圓的圓心位置沒有限制),Bhattacharya等人于2022年給出O(n2logn)時(shí)間的最優(yōu)算法[17]。

1 研究動(dòng)機(jī)與問(wèn)題

1.1 研究動(dòng)機(jī)

在網(wǎng)絡(luò)中,雙會(huì)議服務(wù)器選址問(wèn)題的實(shí)際背景可以看成在平面點(diǎn)集結(jié)構(gòu)中,尋找兩個(gè)服務(wù)器,要求其他終端均連接這兩個(gè)服務(wù)器中的一個(gè),最終形成一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)(樹結(jié)構(gòu)),而尋找目的是使得這個(gè)網(wǎng)絡(luò)的花費(fèi)最小。此時(shí)網(wǎng)絡(luò)的花費(fèi)為網(wǎng)絡(luò)中所有兩點(diǎn)的網(wǎng)絡(luò)距離和(不包含兩服務(wù)器)。雙會(huì)議服務(wù)器選址問(wèn)題不僅需要考慮如何尋找兩個(gè)服務(wù)器位置,同時(shí)還需要考慮如何將點(diǎn)集中的點(diǎn)與這兩個(gè)服務(wù)器相連接。如果不限制這兩個(gè)服務(wù)器的位置,那么該問(wèn)題與Weber問(wèn)題一樣[18],只能通過(guò)設(shè)計(jì)啟發(fā)式算法或者近似算法進(jìn)行求解,不存在最優(yōu)算法。類似地,如果要求這兩個(gè)服務(wù)器在點(diǎn)集內(nèi)部,則可以證明該問(wèn)題是多項(xiàng)式時(shí)間內(nèi)可解的。本文的主要工作就是對(duì)這種情況,通過(guò)討論其幾何結(jié)構(gòu),給出多項(xiàng)式時(shí)間的算法。

1.2 問(wèn)題描述

首先介紹只針對(duì)一個(gè)服務(wù)器(單服務(wù)器)進(jìn)行選址的情況。記P為平面上含有n個(gè)點(diǎn){a1,a2,…,an}的點(diǎn)集,每點(diǎn)的平面坐標(biāo)對(duì)應(yīng)記為(aix,aiy)(i=1,2,…,n),單會(huì)議服務(wù)器選址目標(biāo)為p,其平面坐標(biāo)對(duì)應(yīng)記為(px,py),則單會(huì)議服務(wù)器選址問(wèn)題定義如下:

問(wèn)題1單會(huì)議服務(wù)器選址問(wèn)題指最小化點(diǎn)集張成的一星樹上所有葉子之間的距離和。其中點(diǎn)集的一星樹是指由這n個(gè)點(diǎn)生成的一棵樹,并且滿足這n個(gè)點(diǎn)僅連接某一個(gè)點(diǎn)(不一定屬于P)。

如果要求p?P,該問(wèn)題等價(jià)于著名的Weber問(wèn)題并且可以證明該問(wèn)題無(wú)法求得最優(yōu)解[18]。如果要求p∈P,則可以通過(guò)遍歷的方法求解,其時(shí)間復(fù)雜性為O(n2)。

類似的同樣可以定義點(diǎn)集的二星樹,二星樹是指由這n個(gè)點(diǎn)生成的一棵樹,同時(shí)滿足這n個(gè)點(diǎn)僅連接某兩個(gè)點(diǎn){p,q}中的一個(gè),并且這兩個(gè)點(diǎn){p,q}之間相互連接。其中這棵樹上任意兩葉子之間的距離可以寫成f(ai,aj)=d(ai,p)+d(p,q)+d(p,aj),如果{ai,aj}同時(shí)連接p或者q,這時(shí)上式可以看成點(diǎn)p與點(diǎn)q重合,即d(p,q)=0。若要求{p,q}∈P,此時(shí)可以定義雙會(huì)議服務(wù)器選址問(wèn)題如下:

問(wèn)題2雙會(huì)議服務(wù)器選址問(wèn)題指最小化點(diǎn)集二星樹上所有兩點(diǎn)之間的距離和。

與雙會(huì)議服務(wù)器選址問(wèn)題強(qiáng)相關(guān)的是2中心選址問(wèn)題與最小直徑樹問(wèn)題[19～21]。其中2中心選址問(wèn)題用兩個(gè)圓覆蓋某個(gè)平面點(diǎn)集,并且要求兩個(gè)圓的半徑都盡可能小; 而最小直徑樹問(wèn)題是指求解給定點(diǎn)集的一個(gè)生成樹,使得該樹的直徑最小,其中樹的直徑是指這棵樹上最遠(yuǎn)兩點(diǎn)之間的距離。對(duì)于該問(wèn)題曾證明,一定存在一棵一星樹或者二星樹是該點(diǎn)集的最小直徑樹[19]。而雙會(huì)議服務(wù)器選址問(wèn)題可以看成是二星最小直徑樹的衍生,它不僅僅要求這棵樹最遠(yuǎn)兩點(diǎn)之間的距離最小,同時(shí)要求這棵樹所有葉子之間的距離總和最小。

本文結(jié)構(gòu)如下,第2節(jié)給出最優(yōu)解所對(duì)應(yīng)的幾何結(jié)構(gòu),以及該幾何結(jié)構(gòu)的構(gòu)造思路,第3節(jié)給出最優(yōu)解的求解算法并分析其算法復(fù)雜性,第4節(jié)給出結(jié)論與展望。

2 幾何結(jié)構(gòu)

d(q2,q)+…+d(pk1,p)+d(p,q)+d(q1,q)+d(pk1,p)+d(p,q)+d(q2,q)+…+

d(pk1,p)+d(p,q)+d(pk2,q)

這時(shí)考慮作{p,q}兩點(diǎn)連線的垂直平分線,得到兩個(gè)半平面,記包含點(diǎn)p的半平面內(nèi)所包含的點(diǎn)為集合S1={u1,u2,…,uh1},其點(diǎn)的個(gè)數(shù)為h1,記包含點(diǎn)q的半平面H2內(nèi)所包含的點(diǎn)為集合S2={v1,v2,…,vh2},個(gè)數(shù)為h2。此時(shí)分兩種情況考慮:點(diǎn)集P中沒有點(diǎn)在{p,q}連線的垂直平分線上和至少有一個(gè)點(diǎn)在{p,q}連線的垂直平分線上。

情況1沒有點(diǎn)在{p,q}連線的垂直平分線上。

情況1.1h2

此時(shí)有k1k2>h1h2,對(duì)給定k1,k2,以得到如下引理:

情況1.2k1≥h1≥h2≥k2或k2≥h1≥h2≥k1。

這時(shí)k1k2≤h1h2,為了計(jì)算最優(yōu)解,需要以下引理。不失一般性,考慮k2≤h2≤h1≤k1的情況:

引理2如果k2≤h2≤h1≤k1,此時(shí)最優(yōu)解結(jié)構(gòu)一定滿足:如果K1中有x′個(gè)點(diǎn)屬于S1,K2中有y′個(gè)點(diǎn)屬于S2,則一定有k1-x′≥k2-y′。

證明由于k1-h1=h2-k2,由假設(shè)K1中有x′個(gè)點(diǎn)屬于S1,K2中有y′個(gè)點(diǎn)屬于S2,則K1中剩余點(diǎn)一定屬于S2,K2中剩余點(diǎn)一定屬于S1,即h2-y′=k1-x′=k2-y′。假設(shè)k1-x′

綜上，得到最優(yōu)解結(jié)構(gòu)如下:

其中wi∈S2(i=1,2,…,h2-k2),并且這些點(diǎn)是S2中距離p最近的h2-k2個(gè)點(diǎn)。

證明由k1+k2=h1+h2,可以得到下式:

其中pi∈S2(i=1,2,…,k1-x′),qj∈S1(j=1,2,…,k2-y′)。對(duì)i=1,2,…,k-x′,j=1,2,…,k2-y′,由于d(pi,p)>d(pi,q),pi∈S2,d(qj,q)>d(qj,p),qj∈S1,有

圖1 連接圖例

同理,對(duì)于k1≤h2≤h1≤k2的情況,同樣可以得到:

推論如果k1≤h2≤h1≤k2,有:

其中wi∈S1,i=1,2,…,h2-k1是S1中距離q最近的h2-k1個(gè)點(diǎn)。

情況2P中至少有一個(gè)點(diǎn)在{p,q}連線的垂直平分線上。

F2=k1k2(d(p,q))

與引理1類似地,可以得到:

引理4若h2

(h1+j)h2(d(p,q))

定理1令P為平面上包含n個(gè)點(diǎn)的點(diǎn)集,對(duì)P中固定的兩點(diǎn){p,q}并給定兩個(gè)常數(shù)k1和k2,如果k2≤h2

k1k2(d(p,q))

其中wi∈S2(i={1,2,…,h2-k2})是S2中距離p最近的h2-k2個(gè)點(diǎn)。

如果k1≤h2

k1k2(d(p,q))

其中wi∈S2(i={1,2,…,h2-k1})是S1中距離q最近的h2-k1個(gè)點(diǎn)(見圖2和圖3示例,圖2中h1=5,h2=3,j=2,k1=8,k2=2,圖3中h1=5,h2=3,j=2,k1=2,k2=8)。

圖2 h1=5,h2=3,j=2,k1=8,k2=2時(shí)的最優(yōu)解

圖3 h1=5,h2=3,j=2,k1=2,k2=8時(shí)的最優(yōu)解

3 算法設(shè)計(jì)

定理2對(duì)給定包含n個(gè)點(diǎn)的點(diǎn)集P,雙會(huì)議服務(wù)器選址問(wèn)題可以在O(n3logn)的時(shí)間內(nèi)求解。

4 結(jié)論與展望

本文考慮平面點(diǎn)集選址問(wèn)題中的雙會(huì)議服務(wù)器選址問(wèn)題,即尋找由該點(diǎn)集構(gòu)成的一棵二星樹,使得這棵樹上所有葉子之間的距離和最小。本文給出求解該問(wèn)題的關(guān)鍵幾何結(jié)構(gòu)和最優(yōu)解算法設(shè)計(jì),并給出時(shí)間復(fù)雜性為O(n3logn)的最優(yōu)時(shí)間算法。雙會(huì)議服務(wù)器選址問(wèn)題以看成是2中位問(wèn)題的衍生問(wèn)題。目前,雙會(huì)議服務(wù)器選址問(wèn)題和最小直徑樹問(wèn)題還沒有學(xué)者給出時(shí)間復(fù)雜性小于O(n3)的最優(yōu)時(shí)間算法,尋找這兩個(gè)問(wèn)題更深入的最優(yōu)幾何結(jié)構(gòu)和性質(zhì)將是改進(jìn)這兩問(wèn)題算法復(fù)雜性的研究重點(diǎn)。

Algorithm 1 雙會(huì)議服務(wù)器選址問(wèn)題算法設(shè)計(jì)1:Initialization e=∞,c=?,c?,A=?B=?,a=?,b=?;2.for each p∈P do3. for each q∈Pp do4. for each si∈Pp,q do5. if d(si,p)