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

楊 培, 肖依永, 王宏宇

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

0 引 言

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

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

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

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

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S:機(jī)場(chǎng)節(jié)點(diǎn)的集合。

H:飛機(jī)機(jī)型集合。

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

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

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

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

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

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

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

e:島礁保障點(diǎn)的個(gè)數(shù)。

f:浮島保障點(diǎn)的個(gè)數(shù)。

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

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

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

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

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

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

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

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

M:一個(gè)大數(shù)。

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

2 模型求解

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

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

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

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

(25)

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

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

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

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

(26)

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

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

(27)

整理得θ和n的計(jì)算公式為

(28)

(29)

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

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

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

(30)

AMPL模型代碼如下。

定義集合set:

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

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

定義參數(shù)param:

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

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

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

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

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

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

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

paramM(cita、nn)。

定義變量var:

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

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

距離、累計(jì)飛行距離

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é)點(diǎn)的出入平衡,路徑的單向性

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

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

#固定機(jī)場(chǎng):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;

…

#浮島為動(dòng)態(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)動(dòng)態(tài)計(jì)算)

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 模擬實(shí)驗(yàn)驗(yàn)證

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

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

3.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

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

中繼級(jí)島礁保障點(diǎn)選擇:

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

中繼級(jí)浮島保障點(diǎn)選擇:

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

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

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

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

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

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

事發(fā)點(diǎn)2(節(jié)點(diǎn)26)需要支援:3架機(jī)型A從基地級(jí)保障點(diǎn)D出發(fā)到事發(fā)點(diǎn)2實(shí)施支援(機(jī)型:1, 出發(fā):4, 到達(dá):26),同時(shí)3架機(jī)型B從基地級(jí)保障點(diǎn)B出發(fā)到事發(fā)點(diǎn)2進(jìn)行支援(機(jī)型: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)化求解,實(shí)施遠(yuǎn)程救援的路線與安排為:

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

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

中繼級(jí)島礁保障點(diǎn)選擇:

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

中繼級(jí)浮島保障點(diǎn)選擇:

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

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

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

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

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

事發(fā)點(diǎn)1(節(jié)點(diǎn)25)需要支援:3架機(jī)型A從基地級(jí)保障點(diǎn)C出發(fā)到事發(fā)點(diǎn)1實(shí)施支援(機(jī)型:1, 出發(fā):3, 到達(dá):25),同時(shí)3架機(jī)型B從基地級(jí)保障點(diǎn)A出發(fā)到事發(fā)點(diǎn)1進(jìn)行支援(機(jī)型: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)化求解實(shí)施遠(yuǎn)程救援的路線與安排為:

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

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

中繼級(jí)島礁保障點(diǎn)選擇:

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

中繼級(jí)浮島保障點(diǎn)選擇:

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

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

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

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

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

4 結(jié)論與展望

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

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

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

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