隨機多需求環(huán)境下遠(yuǎn)程中繼保障網(wǎng)絡(luò)設(shè)計優(yōu)化問題建模與求解

楊 培, 肖依永, 王宏宇

(1. 北京航空航天大學(xué)可靠性與系統(tǒng)工程學(xué)院, 北京 100191;2. 中國人民解放軍陸軍航空兵學(xué)院, 北京 101116)

0 引 言

現(xiàn)代信息化戰(zhàn)爭具有作戰(zhàn)強度高、節(jié)奏快、持續(xù)時間短、戰(zhàn)場環(huán)境復(fù)雜多變等特點,面對近岸島嶼聯(lián)合作戰(zhàn)中的保障問題,其保障點既涉及基地級陸地保障點,也涉及中繼級海上保障點,保障網(wǎng)絡(luò)更為復(fù)雜、靈活。面對這樣的保障網(wǎng)絡(luò),中繼保障點的選擇以及保障路線的優(yōu)化對實施及時保障響應(yīng)起到非常重要的作用。國內(nèi)學(xué)者對近岸島嶼聯(lián)合作戰(zhàn)保障問題的研究主要集中在人工島嶼建設(shè)、海域保護戰(zhàn)略、船艇裝備保障力量部署方針、以及島嶼文化安全現(xiàn)狀分析與對策方面。任兆瑞從島上進(jìn)攻裝備保障面臨的難點著手分析,從跨海作戰(zhàn)、裝備物資供應(yīng)困難、裝備力量易受攻擊了個難點進(jìn)行分析,提出了進(jìn)攻作戰(zhàn)裝備保障的主要對策[1]。段祺麟從文化和安全現(xiàn)狀問題對東海的局勢做了一個概括分析[2]。劉增勇從約束滿足問題的理論方法入手,實現(xiàn)近岸島嶼聯(lián)合作戰(zhàn)中船艇裝備保障力量的部署優(yōu)化[3]。除了上述關(guān)于保障理論問題的研究,以任驥為代表的國內(nèi)學(xué)者研究了戰(zhàn)場不確定環(huán)境下的后勤物資供應(yīng)網(wǎng)絡(luò)設(shè)計優(yōu)化問題,考慮了供應(yīng)和需求的不確定性,建立了優(yōu)化問題的整數(shù)規(guī)劃模型,并開發(fā)了基于拉格朗日松弛的啟發(fā)式求解算法[4]。童聲針對執(zhí)行戰(zhàn)場物資供應(yīng)任務(wù)之前,不確定環(huán)境下的戰(zhàn)場物資供應(yīng)任務(wù)規(guī)劃問題進(jìn)行研究,并建立了相應(yīng)的不確定規(guī)劃模型,引入一種新的啟發(fā)式算法——蜂群算法[5]。國內(nèi)學(xué)者主要是針對一個大范圍的作戰(zhàn)保障問題進(jìn)行整體的規(guī)劃部署。在面對于海上作戰(zhàn)問題的研究,目前有較多的作戰(zhàn)理論方針政策進(jìn)行戰(zhàn)略性指導(dǎo),缺乏一定的數(shù)學(xué)模型作為技術(shù)支撐。針對作戰(zhàn)的后勤保障問題,20世紀(jì)80年代末,以美國為首的西方國家率先提出了以“配送式后勤”為主要標(biāo)志的軍事后勤變革理念[6-8]。1990年開始的海灣戰(zhàn)爭中,美軍就開始實踐配送式后勤保障理論,但受限于當(dāng)時的科學(xué)技術(shù)水平較低,在保障過程中遇到前方部隊后勤保障需求不明、后勤物資配送網(wǎng)絡(luò)不通暢等許多的難題,產(chǎn)生了“資源迷霧”和“需求迷霧”現(xiàn)象,嚴(yán)重影響了配送效果和保障效率。美軍吸取了海灣戰(zhàn)爭配送式后勤保障的經(jīng)驗和教訓(xùn),于1996年提出了“主動配送”的新模式,并將其界定為信息、后勤和運輸技術(shù)的融合。Hanson[9]提出在進(jìn)行保障部署問題時,應(yīng)從社會,經(jīng)濟以及歷史的綜合維度進(jìn)行考慮。當(dāng)前關(guān)于作戰(zhàn)后勤保障部署的理論大多借鑒商業(yè)領(lǐng)域供應(yīng)鏈管理的相關(guān)研究成果,所提出的理論用于指導(dǎo)后勤保障體制、編制以及裝備的變革,在具體落實當(dāng)前關(guān)于這種近岸島嶼聯(lián)合作戰(zhàn)問題保障部署的過程中還需要進(jìn)一步對相關(guān)的模型進(jìn)行改進(jìn),才能使相關(guān)保障部署理論真正在現(xiàn)代近岸島嶼聯(lián)合海上作戰(zhàn)的問題中發(fā)揮作用。

由于高新技術(shù)在現(xiàn)代海上局部戰(zhàn)爭中的廣泛應(yīng)用, 作戰(zhàn)方式發(fā)生了深刻變化, 實行全方位、多層次、連續(xù)不斷的后勤支援保障顯得越來越重要。其中受保障資源約束下,中繼保障點的優(yōu)化選址以及保障任務(wù)執(zhí)行路線的優(yōu)化,對保障的快速響應(yīng)起到十分重要的作用。

本文面對海上保障點進(jìn)行中繼浮島保障點的連續(xù)選址研究,其中連續(xù)選址問題的研究也經(jīng)過了不少學(xué)者的探討。Dinler[10]針對單個選址和多個選址問題建立了兩個模型,對于單個選址問題,歸因于一個二階錐規(guī)劃問題,可以在多項式時間內(nèi)進(jìn)行求解,對于多個選址問題,歸因于一個多項式復(fù)雜程度的非確定性問題(non-deterministic polynomial, NP),難以在多項式時間內(nèi)求解,因此采取了3種啟發(fā)式算法進(jìn)行比較,并在需求區(qū)域為矩形區(qū)域時,提出一種特殊的啟發(fā)式算法以提高求解速率。Meira通過創(chuàng)建ε-近似中心集進(jìn)行聚類來解決連續(xù)選址問題[11]。

在連續(xù)選址的各種方法[12-13]中,以給定一個初始位置選址,然后不斷迭代尋找更好的選址為主要思路。學(xué)者通過對模擬退化算法、遺傳算法的應(yīng)用來找到較優(yōu)的選址位置。本文試圖在Xie[14]、Yang[15]研究的基礎(chǔ)上將連續(xù)選址問題轉(zhuǎn)化為線性規(guī)劃問題,通過調(diào)用CPLEX求解器進(jìn)行求解,使得求解過程較為簡單。

由于在本文的研究中,除了進(jìn)行中繼保障點的選址外,還要研究最短支援路線的選擇,總的來說本文研究的問題是在帶有中繼點選址的網(wǎng)絡(luò)設(shè)計(network design problem with relays,NDPR)問題下進(jìn)行的。中繼點在不同的應(yīng)用場景下具有不同的應(yīng)用特征。在運輸網(wǎng)絡(luò)中,選擇中繼點交換駕駛員或改變運輸方式。在綠色出行中,優(yōu)化加油/充電的中繼站選址從而減少能源消耗。在電信網(wǎng)絡(luò)中,中繼器是擴展光信號范圍的再生器。

Adel[16]在電信和配電網(wǎng)有關(guān)的研究背景下提出了一個混合下降法來解決帶有中繼站點且兩邊不相交的網(wǎng)絡(luò)設(shè)計問題。Chen[17]提出了一個帶中繼的隨機最優(yōu)路徑問題,目標(biāo)是在保持合理到達(dá)概率的同時便一般預(yù)期成本最小化，研究在給定的一對節(jié)點間尋找出駕駛范圍有限的車輛的最優(yōu)路徑問題。如果節(jié)點對之間的最小距離超過范圍限制,則必須在指定的站點為車輛加油。由于一條可行路徑可能由多個中繼組成,因此該問題被稱為具有中繼的最優(yōu)路徑問題(optimal path problem with relays, OPPR)。研究有中繼站的最小成本路徑問題的目的在于確定權(quán)值約束下的最小成本路徑和中繼站的位置選擇。Markus[18]研究了有向-中繼的網(wǎng)絡(luò)設(shè)計問題(directed NDPR, DNDPR),其目的是構(gòu)造一個最小成本網(wǎng)絡(luò),使給定的一組起始點-目的地能夠進(jìn)行通信,研究分支-切割算法并考慮有效的不等式,以加強得到的對偶界并加快收斂速度。Zhou[19]考慮了在固定的預(yù)算下,如何獲得最少中繼節(jié)點數(shù),以設(shè)計一個在固定預(yù)算約束下具有“最大連通性”網(wǎng)絡(luò)的問題。無人機(unmanned aerial vehicle, UAV)作為一種半雙工解碼轉(zhuǎn)發(fā)(decode and forward, DF)中繼設(shè)備,在緊急情況下為室內(nèi)用戶和室外基站建立了可靠的鏈路。Cui[20]設(shè)計了一個按功率分配以及帶寬分配的公平位置優(yōu)化算法,通過合理的功率和帶寬分配,可以快速確定無人機的最佳位置,并使中斷概率最小。該算法最大限度地保證了用戶的公平性,中繼鏈路間的中斷概率差距在1%以內(nèi)。Lu[21]分析了兩個利用幾何關(guān)系構(gòu)造中繼網(wǎng)絡(luò)的直觀解決方案,提出基于預(yù)測的動態(tài)中繼模型,然后證明其相對于靜態(tài)部署解決方案的優(yōu)勢; 其次,基于動態(tài)中繼模型,提出了一種中繼網(wǎng)絡(luò)部署算法。單向電動汽車共享系統(tǒng)有望成為未來交通系統(tǒng)的一個組成部分,在減少交通擁堵和碳排放方面發(fā)揮重要作用。Zhang[22]建立了電動汽車的分配模型并考慮了中繼車輛的影響,使用戶能夠通過順序乘坐兩輛車來完成更長的行程。Li[23]提出了一種基于禁忌搜索的迭代元啟發(fā)式算法,在兩個步驟內(nèi)迭代求解帶有中繼點的網(wǎng)絡(luò)設(shè)計問題:首先生成路徑,然后確定與這些路徑相關(guān)聯(lián)的最優(yōu)中繼分配。Ma[24]研究了通過選擇額外的中繼節(jié)點來構(gòu)建具有網(wǎng)絡(luò)可重構(gòu)性的無線傳感器網(wǎng)絡(luò)問題。針對此問題,提出了一個包括覆蓋階段和連接階段的工作框架。Ilhan[25]針對使用解碼轉(zhuǎn)發(fā)中繼的基于下行鏈路正交頻分多址的用戶中繼輔助蜂窩網(wǎng)絡(luò),提出了能源效率最大化問題。針對建立的混合整數(shù)非線性規(guī)劃模型,提出了一種實用的兩階段解決方案。Khaled[26]在考慮兩種干擾情況的同時將移動中繼節(jié)點用于“室外”(外部)小區(qū)邊緣以改善其連通性。Khan[27]設(shè)計了基于預(yù)測的移動性的可獲利的中繼選擇算法,用于協(xié)作通信。Xiao[28]基于高效運送商品的背景提出了一種基于可變鄰域搜索的混合方法。可變鄰域算法搜索每種商品的路線,并用隱式枚舉算法確定給定路線集的最佳中繼位置。Konak[29]指出,通過解決集合覆蓋問題,可以為給定路徑集優(yōu)化確定中繼位置,并開發(fā)了一種混合遺傳算法完成路徑搜索,通過解決集合覆蓋問題來確定中繼位置。隨后,Konak[30]應(yīng)用相同的原理解決了兩個邊緣不相交的NDPR,其中中繼位置由拉格朗日啟發(fā)式算法確定。Kabadurmus[31]也通過考慮邊容量來研究兩個邊不相交的NDPR問題,并基于問題的數(shù)學(xué)表達(dá)式提出了一個三階段啟發(fā)式算法。

基于以上的研究,本文在近岸島嶼聯(lián)合海上作戰(zhàn)提供保障支援的應(yīng)用背景下,研究了帶有中繼點的保障網(wǎng)絡(luò)設(shè)計問題,針對海上區(qū)域往往需要陸地上的基地級保障點提供遠(yuǎn)程支援,而海上保障點除一些可以通過離散選址得到的岸基保障點外,還需要通過連續(xù)選址得到的浮島、保障船等作為中繼保障設(shè)施,受到保障資源約束,提出了連續(xù)離散相結(jié)合選址下的中繼點的選擇,同時進(jìn)行最低成本路徑選擇,以使得支援路徑成本最小,保障資源消耗最低,并且能達(dá)到最快響應(yīng)的目的。

1 遠(yuǎn)程中繼保障網(wǎng)絡(luò)模型

1.1 問題描述

假設(shè)在遠(yuǎn)海海域的多個目標(biāo)區(qū)域內(nèi)具有發(fā)生安全事件的概率。一旦發(fā)生安全事件,則需要從大陸保障基地派遣飛機進(jìn)行緊急支援和救援。每個事發(fā)點根據(jù)事發(fā)嚴(yán)重程度不同,需求的支援機隊的數(shù)量也不同。由于支援機隊的航程半徑約束,途中需要降落至中繼節(jié)點,在完成加油保障之后繼續(xù)飛往救援區(qū)域,受中繼保障點的保障資源約束,中繼節(jié)點(包括島礁和浮島中繼保障點)的數(shù)量也受到一定的限制。為了加快支援的響應(yīng)速度,節(jié)省支援路徑成本,節(jié)省設(shè)立中繼保障點的資源,本文旨在優(yōu)化選擇近海岸位置、海面海島或島礁，從而建立合適的中繼節(jié)點,并且優(yōu)化保障支援路徑,使救援活動能夠得到保障,使在滿足保障需求的同時運用更少的資源,能夠達(dá)到最低期望救援成本的目的。

該問題可抽象為一個無向圖G(V,E)來描述,其中V表示頂點的集合,E表示邊的集合。頂點位置坐標(biāo)表示為(Xi,Yi),邊的長度表示為dij,其在i∈V,j∈V, (i,j)∈E。令集合S和T分別表示救援活動的出發(fā)節(jié)點和目標(biāo)節(jié)點,且有S?V和T?V。再令飛機類型的集合為H,以L表示救援線路集合。對于每一支救援路線 (h,s,t)∈L,其中h∈H,s∈S,t∈T,均需要從s節(jié)點出發(fā),途徑經(jīng)停圖G的部分頂點后,到達(dá)目標(biāo)節(jié)點t,并滿足飛機的航程約束。

此問題的特殊性體現(xiàn)在如下幾個方面。

(1) 多任務(wù)不確定環(huán)境

由于現(xiàn)場環(huán)境復(fù)雜多變,接收到的任務(wù)需求也在時刻變化,并且可能同時存在兩個或兩個以上的保障任務(wù)需求,保障支援路徑需要根據(jù)目標(biāo)點的分布,結(jié)合提供遠(yuǎn)程中繼保障的基地級保障點的位置,進(jìn)行中繼保障點的最優(yōu)選址,從而能夠通過優(yōu)化后的中繼保障點的選址,針對不同的保障任務(wù)選擇響應(yīng)最快的保障路徑。此外還考慮不同事發(fā)點的事發(fā)頻率作為需求的權(quán)重。

(2) 多種飛機機型及性能約束

由于保障任務(wù)需求的多樣化,需調(diào)派不同類型的支援機以響應(yīng)對應(yīng)的保障任務(wù)。每種機型的飛機性能,尤其以飛行半徑為主要性能代表，對中繼保障點的位置選取具有較大的影響。因此問題中考慮中繼保障點位置選址時,還要綜合考慮多種支援機的飛機性能。

(3) 離散與連續(xù)選址混合

對于中繼保障點的選址,在海岸沿線可以預(yù)選一些合適的地點作為中繼保障點的預(yù)選址,在此類固定預(yù)選點的岸基保障點中進(jìn)行選址屬于離散選址。此外,考慮事發(fā)地點處于遠(yuǎn)離岸基的海洋上,僅僅設(shè)定岸基或離海岸線較近的島嶼保障點不能完全滿足保障的較快響應(yīng),因此需要設(shè)定海上浮島或保障船保障點,以更快滿足保障需求。而海上浮島保障點的選址范圍較大,較難應(yīng)用離散選址問題進(jìn)行求解,因此采用在限定范圍內(nèi)進(jìn)行連續(xù)選址的方法進(jìn)去求解,本文中還將對連續(xù)選址的求解方法進(jìn)行進(jìn)一步的探討。

(4) 混合整數(shù)規(guī)劃模型

由于本問題中,涉及離散和連續(xù)選址問題相結(jié)合,既涉及到整數(shù)變量,也涉及到了連續(xù)變量。設(shè)計的數(shù)學(xué)模型為混合整數(shù)規(guī)劃數(shù)學(xué)模型,其約束中涉及了非線性約束,下文將針對此類NP-hard問題的求解進(jìn)行較為詳細(xì)的解釋,并通過將線性約束轉(zhuǎn)化為非線性約束的方法,求解此混合整數(shù)規(guī)劃模型。其中非線性約束轉(zhuǎn)化為線性約束通過幾何近似來實現(xiàn)。

面對如上問題描述,在實際進(jìn)行保障支援時首先開展區(qū)域保障需求分析,確定目標(biāo)保障區(qū)域的范圍界定和保障需求估算,行程保障區(qū)域的特征參數(shù)。同時,分析保障方的保障能力,分析各種可能的保障點建設(shè)方案(岸基保障點、島礁保障點、浮島/保障船),分析各種保障方案的保障能力和容量約束,獲得各類保障方案的能力特征參數(shù)。然后,建立局域保障配置優(yōu)化數(shù)學(xué)規(guī)劃模型,研究模型的最優(yōu)化求解方案和開展仿真實驗驗證與分析。此模型的主要輸入和輸出如圖1所示。

圖1 模型輸入輸出框架圖Fig.1 Frame diagram of input and output of model

1.2 參數(shù)符號及混合整數(shù)規(guī)劃模型

T:保障目標(biāo)的集合。

S:機場節(jié)點的集合。

H:飛機機型集合。

L:支援路線方案集合L(H,S,T)。

W(h,s,t):從S起飛到達(dá)T,需求飛機數(shù)量。

Rh:不同飛機類型的最大飛行距離,h∈H。

Pt:某地發(fā)生戰(zhàn)事的可能性概率,t∈T。

N:路線節(jié)點集合。

ai:節(jié)點的類型,ai=1表示基地級保障點;ai=2表示中繼點(島礁);ai=3表示中繼點(浮島);ai=4表示保障目標(biāo)。

Chj:島礁/浮島的容量(可駐停飛機最大數(shù)量,正對不同類型)。

e:島礁保障點的個數(shù)。

f:浮島保障點的個數(shù)。

i:路線節(jié)點,i∈N。

j:路線節(jié)點,j∈N。

(Xmax,Ymax):保障點的選址范圍(最大X、Y坐標(biāo))。

(Xmin,Ymin):保障點的選址范圍(最小X、Y坐標(biāo))。

Dij:節(jié)點之間的距離。

ri:是否可以經(jīng)停(即:是否建造島礁/浮島)。

X(h,s,t)ij:飛機路徑選擇變量。

Pθ:歐式距離精度表示。

M:一個大數(shù)。

d(h,s,t)ij:保障區(qū)域與浮島保障點的歐式距離, 如果不是服務(wù)關(guān)系則為0。

ri:是否可以經(jīng)停(即:是否建造島礁/浮島),1-是;0-否。

目標(biāo)函數(shù):

min Total_Weighted_Dis=

(1)

約束條件:

(2)

(3)

?{(h,s,t)∈L,?i∈N|i≠s∩i≠s}

(4)

(5)

(6)

(7)

(8)

x(h,s,t)ij≤ri

?{i∈N,j∈N,(h,s,t)∈L|i≠j,ai≥2}

(9)

(10)

(11)

(12)

(13)

(14)

(15)

d(h,s,t)ij=x(h,s,t)ijDij

?{i∈N,j∈N,(h,s,t)∈L|ai≠3∩aj≠3}

(16)

?{i∈N,j∈N,(h,s,t)∈L|ai=3∪aj=3}

(17)

?{i∈N,j∈N,(h,s,t)∈L|ai=3∪aj=3}

(18)

?{i∈N,j∈N,(h,s,t)∈L|ai=3∪aj=3}

(19)

?{i∈N,j∈N,(h,s,t)∈L|ai=3∪aj=3}

(20)

?{i∈N,j∈N,(h,s,t)∈L|ai=3∪aj=3}

(21)

?{i∈N,j∈N,t∈T|ai≠1∩aj≠4}

(22)

d(h,s,t)ij≤Rh

?{i∈N,j∈N,(h,s,t)∈L|i≠j∩aj≠4}

(23)

d(h,s,t)ij≤0.4Rh

?{i∈N,j∈N,(h,s,t)∈L|i≠j∩aj=4}

(24)

上述目標(biāo)函數(shù),其目標(biāo)是使保障距離最短,能以較快的響應(yīng)速度為保障需求點提供保障。式(2)～式(4)設(shè)置節(jié)點的出入平衡。式(2)表示為在每個保障路徑中,只能從出發(fā)點出發(fā)一次;式(3)表示在每條保障路徑中,只能到達(dá)目標(biāo)點一次;式(4)表示每條保障路徑中,每個節(jié)點的進(jìn)入次數(shù)和輸出次數(shù)相同;式(5)表示基地級機場在每條保障路徑中都是被選中的路徑節(jié)點;式(6)和式(7)表示島礁和浮島作為保障中繼站點的數(shù)量限制;式(8)表示保障路徑中保障目標(biāo)節(jié)點不可?？恐г畽C;式(9)限制了沒有建立保障點的島礁和浮島無法提供服務(wù);式(10)和式(11)表示除了浮島外的保障路徑節(jié)點的固定坐標(biāo);式(12)～式(15)表示浮島保障點在一定范圍區(qū)域內(nèi)設(shè)定;式(16)表示保障路徑節(jié)點(除浮島外)之間的固定距離;式(17)～式(21)是保障路徑中其他節(jié)點與浮島節(jié)點相連接的歐式距離線性化表示;式(22)表示滿足島礁或浮島的容量限制;式(23)表示支援機隊到達(dá)保障目標(biāo)前,保障路徑每兩節(jié)點之間的距離需滿足支援機的作戰(zhàn)半徑要求;式(24)表示支援機隊從鄰保障目標(biāo)節(jié)點最終到達(dá)保障目標(biāo)的距離需要保證支援機隊可以從保障目標(biāo)返回鄰保障目標(biāo)節(jié)點。上述模型以較為貼近現(xiàn)實的約束條件,實現(xiàn)區(qū)域保障點的模型優(yōu)化。

2 模型求解

此問題中,通過AMPL進(jìn)行數(shù)學(xué)模型的轉(zhuǎn)化。將數(shù)學(xué)模型進(jìn)行求解,AMPL語言是一種建模語言,由于AMPL語言采用極為類似自然代數(shù)的語法規(guī)則和變量符號,即使是極其復(fù)雜的模型也可以用簡潔的陳述來闡釋清楚。因此本模型采用AMPL語言來描述混合整數(shù)規(guī)劃問題。

AMPL自身并非一個用于求解的程序,其作用是讀取一個問題的模型文件和數(shù)據(jù)文件,再調(diào)用一個外部求解器進(jìn)行求解。本技術(shù)模型中選用的外部求解器為CPLEX12.0求解器。進(jìn)行求解之前必須遵循AMPL的語法規(guī)則和CPLEX求解器的使用限制建立AMPL語言模型,保存在后綴名為.mod的模型文件中,同時將數(shù)據(jù)文件也整理為符合AMPL的語法規(guī)則,保存在后綴名為.data的數(shù)據(jù)文件中。AMPL語言求解時可以調(diào)用預(yù)先編寫好的腳本文件(.sh),從而連續(xù)處理多條指令。本技術(shù)進(jìn)行的求解計算調(diào)用CPLEX12.0學(xué)術(shù)版來求解,建模和編程均在實驗室電腦上完成,電腦的處理器型號為Intel Core i3-4160 CPU @3.60 GHz,已安裝的內(nèi)存為12.0 GB,操作系統(tǒng)為64位Windows 10專業(yè)版。

針對本技術(shù)的混合整數(shù)規(guī)劃模型,由于涉及到兩點之間的歐式距離計算,而歐式距離屬于非線性約束條件,無法被CPLEX求解器直接使用,須將其轉(zhuǎn)化為線性約束條件。

歐氏距離公式是最常用的距離公式,指在m維空間內(nèi)兩個點間的真實距離。二維平面中的歐氏距離公式為

(25)

同樣,式中根式也屬于非線性約束條件,無法被CPLEX求解器直接使用,須將其轉(zhuǎn)化為線性約束條件。

如圖2所示,點A與點B間的歐氏距離為以點A和點B軸向距離為兩直角邊的直角三角形斜邊的長度?，F(xiàn)將此直角三角形的直角由n條射線等分為n個大小為θ的單位角，有nθ=π/2。過A,B兩點分別做到這些射線的垂線段,以到所有射線的兩段垂線段的長度之和(AOk1+AOk2)的最大值，作為A,B兩點歐氏距離的近似值。

圖2 歐式距離幾何線性化Fig.2 Geometric linearization of Euclidean distance

d≥|x1-x2|cos(kθ)+|y1-y2|sin(kθ)k∈N*,k≤n

(26)

可知,n的值越大,此近似值越接近于真實值,當(dāng)n趨近于無窮時,此近似值無限接近于真實值。

圖3 歐式距離線性化計算Fig.3 Linearization calculation of Euclidean distance

(27)

整理得θ和n的計算公式為

(28)

(29)

由此計算得ε、θ與n的部分關(guān)系數(shù)據(jù)如表1所示。

表1 ε、θ與n的關(guān)系表

在一般問題中,選定θ值為0.087 3,n值為18,可控制誤差ε在0.10%以內(nèi),滿足實際問題的要求。建立歐氏距離的線性約束條件為

(30)

AMPL模型代碼如下。

定義集合set:

保障目標(biāo)、所有的節(jié)點、機場節(jié)點、飛機機型集合、支援路線方案

setT(N、S、H、Lwithin {H,S,T})。

定義參數(shù)param:

路徑選擇、最大飛行距離、發(fā)生戰(zhàn)事的可能性概率

paramw{L}(R{H}、P{T});

節(jié)點的經(jīng)緯度、節(jié)點的類型、島礁/浮島的容量

paramN_X{N}(N_Y{N}、delta{N}、C{N});

島礁浮島的數(shù)量、節(jié)點之間的距離、連續(xù)選址區(qū)域限制

parame(f、D{N,N}、X_max、X_min、Y_max、Y_min);

無限大數(shù)、歐式距離精度

paramM(cita、nn)。

定義變量var:

節(jié)點位置、島礁/浮島的建立、路徑的選擇

var (n_x{N}，n_y{N}，r{N}，x{L,N,N}) binary

距離、累計飛行距離

vardx{L,N,N}(dy{L,N,N}，d{L,N,N}，

accD{H,N})>=0

目標(biāo)函數(shù):加權(quán)保障總距離最短化

minimize

Total_Weighted_Dis sum{(h,s,t) inL,iinN,jinN:i<>j}d[h,s,t,i,j]P[t]w[h,s,t];

約束條件:

#路徑設(shè)定路徑的方向性;

#節(jié)點的出入平衡,路徑的單向性

subject to InOut_sta{(h,s,t) inL}

sum{jinN:j<>s}x[h,s,t,s,j]=1;

#固定機場:r[i]=1

subject to Con1a{iinN: delta[i]=1}:r[i]=1;

#島礁中繼:上限數(shù)量e

subject to Con1b: sum{iinN: delta[i]=2}r[i]=e;

#浮島中繼:上限數(shù)量f

subject to Con1c: sum{iinN: delta[i]=3}r[i]=f;

…

#浮島為動態(tài)坐標(biāo),受到區(qū)域的約束

subject to ConPos_f{iinN: delta[i]=3}:

n_x[i]>=X_min;

subject to ConPos_1f{iinN: delta[i]=3}:

n_x[i]<=X_max;

…

#飛行距離(跟浮島相關(guān)的弧段,距離通過坐標(biāo)動態(tài)計算)

subject to ConDisFlexA{(h,s,t) inL,iinN,jinN:delta[i]=3 or delta[j]=3}:

dx[h,s,t,i,j]>=(n_x[i]-n_x[j])-M(1-x[h,s,t,i,j]);

subject to ConDisFlexB{(h,s,t) inL,iinN,jinN:delta[i]=3 or delta[j]=3}:

dx[h,s,t,i,j]>=(n_x[j]-n_x[i])-M(1-x[h,s,t,i,j]);

…

#容量約束

#subject to ConCapacity{jinN: delta[j]<>4}:

sum{(h,s,t) inL,iinN:i<>j}x[h,s,t,i,j]w[h,s,t]<=C[j];

#航程半徑距離約束1(單程)

subject to ConLenLimitA{(h,s,t) inL,iinN,jinN:i<>jand delta[j]<>4}:

d[h,s,t,i,j]<=R[h];

3 模擬實驗驗證

3.1 數(shù)據(jù)集和參數(shù)分析

表2 模擬算例數(shù)據(jù)

3.2 實驗結(jié)果分析

算例驗證在Linux PC服務(wù)器上進(jìn)行了兩個2.30 GHz Intel Xeon(R)CPU和128 GB RAM的計算實驗。在Linux PC服務(wù)器上使用MILP解算器AMPL/CPLEX(版本12.6.0.1)。求解結(jié)果若顯示:solve_result=solved,則證明可以在限制約束條件下完成此種保障任務(wù)。

(1) 仿真任務(wù)A

事發(fā)點3、事發(fā)點4(節(jié)點27、節(jié)點28)需要支援:6架機型A從基地級保障點C出發(fā)到事發(fā)點3實施支援(機型:1, 出發(fā):3, 到達(dá):27),同時4架機型B從基地級保障點A出發(fā)到事發(fā)點4進(jìn)行支援(機型:2, 出發(fā):1, 到達(dá):28)。

經(jīng)過模型的優(yōu)化求解,目標(biāo)函數(shù)Total_Weighted_Dis=508.043;求解結(jié)果solve_result=solved,證明存在最優(yōu)解。實施遠(yuǎn)程救援的路線以及中繼岸基保障點與浮島保障點的選址如下:

節(jié)點3→節(jié)點16→節(jié)點30→節(jié)點27；

節(jié)點1→節(jié)點3→節(jié)點29→節(jié)點28。

中繼級島礁保障點選擇:

節(jié)點16(x=49.59,y=64.02)。

中繼級浮島保障點選擇:

節(jié)點29(x=70.58,y=38.73)；

節(jié)點30(x=57.24,y=20.00)。

其救援路線示意圖如圖4所示。在此次任務(wù)支援中,通過離散選址得到了16號(49.59,64.02)中繼島礁保障點,通過連續(xù)選址得到了29號(70.58, 38.73)和30號(57.24, 20.00)2個中繼浮島保障點。圖4中顯示了兩條救援路線,支援路線經(jīng)由了選擇的16、29、30中繼保障點。

圖4 仿真任務(wù)AFig.4 Simulation task A

圖4中共有兩條支援路線,支援路線旁邊的數(shù)字對應(yīng)表1中的相應(yīng)節(jié)點。

(2) 仿真任務(wù)B

事發(fā)點2(節(jié)點26)需要支援:3架機型A從基地級保障點D出發(fā)到事發(fā)點2實施支援(機型:1, 出發(fā):4, 到達(dá):26),同時3架機型B從基地級保障點B出發(fā)到事發(fā)點2進(jìn)行支援(機型:2, 出發(fā):2, 到達(dá):26)。

經(jīng)過模型的優(yōu)化求解,目標(biāo)函數(shù)Total_Weighted_Dis=372.084;求解結(jié)果solve_result=solved,證明存在最優(yōu)解。經(jīng)過模型的優(yōu)化求解,實施遠(yuǎn)程救援的路線與安排為:

節(jié)點4→節(jié)點29→節(jié)點30→節(jié)點26；

節(jié)點2→節(jié)點20→節(jié)點30→節(jié)點26。

中繼級島礁保障點選擇:

節(jié)點20(x=43.46,y=67.93)。

中繼級浮島保障點選擇:

節(jié)點29(x=55.72,y=60.00);

節(jié)點30(x=25.28,y=21.12)。

其救援路線示意圖如圖5所示。在此次任務(wù)支援中,通過離散選址得到了20號(43.46, 67.93)中繼島礁保障點,通過連續(xù)選址得到了29號(55.72, 60.00)和30號(25.28, 21.12)兩個中繼浮島保障點。圖5中顯示了兩條救援路線,支援路線經(jīng)由了選擇的20、29、30中繼保障點。

圖5 仿真任務(wù)BFig.5 Simulation task B

(3) 仿真任務(wù)C

事發(fā)點1(節(jié)點25)需要支援:3架機型A從基地級保障點C出發(fā)到事發(fā)點1實施支援(機型:1, 出發(fā):3, 到達(dá):25),同時3架機型B從基地級保障點A出發(fā)到事發(fā)點1進(jìn)行支援(機型:2, 出發(fā):1, 到達(dá):25)。

經(jīng)過模型的優(yōu)化求解,目標(biāo)函數(shù)Total_Weighted_Dis=491.065;求解結(jié)果solve_result=solved,證明存在最優(yōu)解。經(jīng)過模型的優(yōu)化求解實施遠(yuǎn)程救援的路線與安排為:

節(jié)點3→節(jié)點29→節(jié)點30→節(jié)點25；

節(jié)點1→節(jié)點15→節(jié)點30→節(jié)點25。

中繼級島礁保障點選擇:

節(jié)點15(x=41.33,y=67.10)。

中繼級浮島保障點選擇:

節(jié)點29(x=47.71,y=51.70)；

節(jié)點30(x=51.70,y=20.0)。

其救援路線示意圖如圖6所示。在此次任務(wù)支援中,通過離散選址得到了15號(41.33, 67.10)中繼島礁保障點,通過連續(xù)選址得到了29號(47.71, 51.70)和30號(51.70, 20.0)兩個中繼浮島保障點。圖6中顯示了兩條救援路線,支援路線經(jīng)由了選擇的15、29、30中繼保障點。

圖6 仿真任務(wù)CFig.6 Simulation task C

圖4～圖6中的支援路徑和中繼保障點的選址都有效保障了支援機隊的航程半徑。由支援路徑的形狀來看也都接近于從出發(fā)點到事發(fā)點的直線連接。

4 結(jié)論與展望

本文構(gòu)建了綜合考慮選址—路徑的聯(lián)合優(yōu)化保障網(wǎng)絡(luò)系統(tǒng)。通過仿真任務(wù)來看,模型能較為準(zhǔn)確地幫助保障點選址做決策。此仿真任務(wù)可根據(jù)海軍后勤保障的實際能力來擬定,具有較強的適應(yīng)性, 可滿足海上作戰(zhàn)原則和保障方式發(fā)展的需要;未來海戰(zhàn)戰(zhàn)場復(fù)雜多變, 難以預(yù)料,此模型中根據(jù)預(yù)案的不同調(diào)整模型的輸入,具有靈活的彈性。

遵循基于實際需求的建模原則,本文假定遠(yuǎn)程保障支援的基地級保障點位于陸地,中繼級保障點位于岸基島嶼以及海上保障船,并且可以將幾個區(qū)域發(fā)生戰(zhàn)事的可能性大小作為設(shè)計保障網(wǎng)絡(luò)所考慮的因素,以此設(shè)定保障需求的權(quán)重。

在求解模型的過程中,采用連續(xù)選址與離散選址混合的優(yōu)化方案。不同于以往的單一選址問題,連續(xù)選址與離散選址相結(jié)合的選址問題更貼合實際應(yīng)用場景的需要。本模型中,現(xiàn)有的島礁可以作為預(yù)選中繼保障點,然而某些遠(yuǎn)離岸基的海上區(qū)域無法被現(xiàn)有的島礁保障,為了提高響應(yīng)速度,提升實際應(yīng)用場景中的應(yīng)用效率,本文考慮增設(shè)浮島,即引入了連續(xù)選址問題,同時設(shè)定連續(xù)型選址區(qū)域限制,從而利用線性模型高效解決了實際應(yīng)用場景的復(fù)雜要求。采用精確式優(yōu)化方法,根據(jù)問題背景建立線性模型,可以直接求解最優(yōu)解。綜上所述,本模型綜合考慮諸多實際因素,具有實際應(yīng)用的價值。

根據(jù)仿真初步的計算,結(jié)合實際場景的應(yīng)用,模型計算出最短的保障支援路徑并同時得出最優(yōu)中繼保障點的選址。充分驗證了模型的合理性和正確性，未來對中規(guī)?；蜉^大規(guī)模的優(yōu)化問題需要進(jìn)一步設(shè)計啟發(fā)式規(guī)則和啟發(fā)式算法,以滿足超大規(guī)模的保障任務(wù)的需求。