孫 茜

(上海理工大學(xué) 機(jī)械工程學(xué)院, 上海 200093)

導(dǎo)彈因具有精準(zhǔn)打擊、打擊范圍廣等優(yōu)點(diǎn)[1]，在現(xiàn)代戰(zhàn)爭(zhēng)發(fā)揮著無(wú)可替代的作用。但由于這些特點(diǎn)，導(dǎo)彈部隊(duì)就可能會(huì)成為敵人的首要打擊目標(biāo)。由于每臺(tái)發(fā)射裝置只能裝載一枚導(dǎo)彈，所以在實(shí)施多波次發(fā)射時(shí)，需要先將上一波次發(fā)射任務(wù)的車載發(fā)射裝置機(jī)動(dòng)到裝載區(qū)域(用于將導(dǎo)彈吊裝到發(fā)射裝置的專門區(qū)域)裝彈，然后發(fā)射裝置再機(jī)動(dòng)至下一波次指定的發(fā)射點(diǎn)實(shí)施發(fā)射。因此為了避免敵方對(duì)導(dǎo)彈車的打擊，需計(jì)算導(dǎo)彈出任務(wù)的最短時(shí)間。

Dijkstra算法是由荷蘭計(jì)算機(jī)科學(xué)家狄克斯特拉于1959年提出的，因此又叫狄克斯特拉算法，是現(xiàn)有求最短路徑的一種比較成熟的算法，其基本思想是設(shè)置并逐步擴(kuò)充一個(gè)集合S,存放已求出其最短路徑的頂點(diǎn)，則尚未確定最短路徑的頂點(diǎn)集合是V-S,其中V為網(wǎng)中所有頂點(diǎn)集合。按最短路徑長(zhǎng)度遞增的順序,以V-S中的頂點(diǎn)加到S中，直到S中包含全部頂點(diǎn)，而V-S為空。它解決的是有向圖中的最短路徑問(wèn)題，該算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)位置。

本文為了解決在完成緊急任務(wù)時(shí)車輛導(dǎo)彈部署和機(jī)動(dòng)運(yùn)輸?shù)膯?wèn)題，采用Dijkstra算法為車載導(dǎo)彈的兩次連續(xù)發(fā)射任務(wù)提供具體的發(fā)射點(diǎn)分配和機(jī)動(dòng)路線方案，使兩次發(fā)射任務(wù)的總體曝光時(shí)間最短。

1 導(dǎo)彈位置的布置

問(wèn)題描述：現(xiàn)有車載發(fā)射裝置一共24臺(tái)，依據(jù)發(fā)射裝置的不同大致可以分為A、B、C三類，這三類的數(shù)量分別為6、6、12，執(zhí)行任務(wù)之前平均部署在待機(jī)地域。該部收到實(shí)施兩個(gè)波次的齊射任務(wù)，每波次發(fā)射24枚導(dǎo)彈。規(guī)劃出具體的發(fā)射點(diǎn)位分配及機(jī)動(dòng)路線方案，使得完成兩個(gè)波次發(fā)射任務(wù)的整體暴露時(shí)間最短。暴露時(shí)間是指發(fā)射裝置從待機(jī)區(qū)域出發(fā)時(shí)刻至第二波次發(fā)射時(shí)刻為止的時(shí)間，且發(fā)射裝置位于轉(zhuǎn)載地域內(nèi)的時(shí)間不計(jì)入暴露時(shí)間內(nèi)，暫不考慮發(fā)射裝置在發(fā)射點(diǎn)位必要的技術(shù)準(zhǔn)備時(shí)間和發(fā)射后發(fā)射裝置的撤收時(shí)間。各地域的具體位置如圖1所示，其中D1、D2為待機(jī)區(qū)域，Z01—Z06為轉(zhuǎn)載地域，F(xiàn)01—F60為發(fā)射點(diǎn)位，在本文計(jì)算中以D1、D2表示待機(jī)區(qū)域D1、D2，Z01—Z06表示轉(zhuǎn)載地域Z01—Z06，F(xiàn)01—F60表示發(fā)射點(diǎn)位F01—F60。

圖1 作戰(zhàn)區(qū)域道路示意圖

約束條件：

(1)各轉(zhuǎn)載地域最多容納2臺(tái)發(fā)射裝置，但不能同時(shí)作業(yè)，單臺(tái)轉(zhuǎn)載作業(yè)需10 min；

(2)圖中主干道路(圖中虛線)是雙車道，其他道路均是單車道；

(3)A、B、C發(fā)射裝置在主干道路上的行駛速度分別為70、60、50 km/h，在其他道路上的平均行駛速度分別是45、35、30 km/h。

2 模型的建立和優(yōu)化

2.1 作戰(zhàn)區(qū)域道路的距離求解

若要求得最短的暴露時(shí)間，就必須算出作戰(zhàn)區(qū)域示意圖中各個(gè)相連點(diǎn)之間的距離，若每一小段的兩個(gè)頂點(diǎn)坐標(biāo)為(xi,yi)和(xj,yj)，則這兩個(gè)頂點(diǎn)之間的距離為

(1)

2.2 最短路徑集的求解

假設(shè)待機(jī)點(diǎn)Di到各個(gè)發(fā)射點(diǎn)Fn之間的最短路徑集為L(zhǎng)Dimin，又因?yàn)槊總€(gè)待機(jī)點(diǎn)的車輛是均分的，所以LDimin中的元素均為12個(gè)，設(shè)LDimin={d1,i,d2,i,…,d12,i}。

對(duì)于最短路徑集的問(wèn)題，本文選擇通過(guò)Dijkstra算法[2-3]來(lái)求得最短路徑集，在使用Dijkstra算法計(jì)算最短路徑時(shí)，需要指定起點(diǎn)Di[4]，同時(shí)需要引入變量Si和Ui分別用來(lái)表示已經(jīng)求出的最短路徑的節(jié)點(diǎn)和未求出的最短路徑的節(jié)點(diǎn)[5]。在初始階段，Si中只包含起點(diǎn)Di；而Ui則是包含除起點(diǎn)之外的所有頂點(diǎn)，從Ui中選出距離最短的頂點(diǎn)Ki，同時(shí)將頂點(diǎn)Ki從Ui加入到Si中，更新Ui中各個(gè)頂點(diǎn)到起點(diǎn)Di的距離。之所以更新Ui中頂點(diǎn)的距離，是由于上一步中確定了Ki是求出最短路徑的頂點(diǎn)，從而可以利用Ki來(lái)更新其他頂點(diǎn)的距離，就這樣循環(huán)反復(fù)，直至遍歷完所有的頂點(diǎn)，根據(jù)遍歷完成的所有的點(diǎn)數(shù)，可以得到整個(gè)路徑LDni={d1i,d2i,…,dni}所經(jīng)過(guò)的節(jié)點(diǎn)以及其路徑的長(zhǎng)度lDni={l1i,l2i,…,lni}。

2.3 建立0-1整型規(guī)劃模型

首先建立0-1整形規(guī)劃模型[6-7]求解Di待機(jī)區(qū)域距離最短的24個(gè)發(fā)射點(diǎn)。設(shè)置0-1變量xi(i=1,2,…,15)，表示對(duì)于待機(jī)地域D1是否選擇該點(diǎn)為發(fā)射點(diǎn)，

(2)

當(dāng)上一步得到整個(gè)路徑LD1i之后，從中篩選12條最小路徑集LD1min={d1,1,d2,1,…,d12,1}，再根據(jù)主從干道的權(quán)值集Q={a1,i,a2,i,…,a12,i}，其中amn∈(0.5,0.8)為主從干道集的元素，根據(jù)模型中建立的主次干道速度的大小關(guān)系，假設(shè)經(jīng)過(guò)一次主干道，則其權(quán)值乘以0.8，若經(jīng)過(guò)一次次干道，則其權(quán)值乘以0.5，能夠得出其帶權(quán)的最小路徑集LD1min·Q，然后對(duì)速度集V={v1,v2,v3,v1′,v2′,v3′}進(jìn)行速度賦權(quán)，VQ={q1,q2,…,q24}，其中此處的qi∈(0.5,0.8,1)，該權(quán)值的假設(shè)與amn類似，若為A車，則其權(quán)值乘以1，B車乘以0.8，C車乘以0.5。當(dāng)獲得第一波單車最長(zhǎng)暴露時(shí)間，從而可以得知第一波齊射條件下的最短整體暴露時(shí)間，時(shí)間等于路程除以速度，由此可以得出其目標(biāo)函數(shù)的表達(dá)：

(3)

(4)

由于24輛車在部署時(shí)平均分配在兩個(gè)地方，所以分別對(duì)選擇Di進(jìn)行判斷計(jì)算，約束條件:

(5)

綜上所述，式(3)、(4)、(5)為0-1整型規(guī)劃模型。

2.4 模型的求解

根據(jù)Dijkstra算法建立最短路徑模型，距離D1最近的12個(gè)點(diǎn)為：F43、F58、F57、F42、F41、F38、F37、F39、F40、F34、F35、F54，距離D2最近的12個(gè)點(diǎn)為F24、F25、F47、F46、F44、F45、F26、F03、F02、F01、F50、F28。根據(jù)加權(quán)的速度與時(shí)間的計(jì)算能夠得出到D1點(diǎn)的最短時(shí)間TD1min=180.9 s，到D2點(diǎn)的最短時(shí)間TD2min=143.9 s。由于D2的TD2min值小于D1的TD1min值，所以根據(jù)此條件可得，第一波的整體暴露時(shí)間為180.9 s，而根據(jù)D1的TD1min可以優(yōu)化D2的TD2min，對(duì)D2的TD2min重新進(jìn)行建模，將第二波的裝載時(shí)間提前考慮到第一波的模型中來(lái)。

2.5 步驟一模型的優(yōu)化

根據(jù)D1的TD1min可知，第二波若要完成與第一波相同的齊射條件，那么D2的TD2min等待的時(shí)間會(huì)整體增長(zhǎng)，那么可以讓D1、D2的車一起開，但是D2發(fā)出的車可以開到距離轉(zhuǎn)載地域Zi最近的Fi進(jìn)行第一波齊射，即可增加約束Tmax≤TD1min。D2的目標(biāo)函數(shù)為：

min(lF2i-lZi)=V·VQ·T·xi,

根據(jù)上述算法可以判斷出新選擇出來(lái)的D2的路徑集中使得min(lF2i-lZi)成立的點(diǎn)為F11、F26、F29、F30、F32、F33、F47、F48、F49、F50、F51、F52，同時(shí)將距離D1最近的12個(gè)點(diǎn)根據(jù)時(shí)間約束改為F20、F34、F35、F36、F37、F38、F40、F41、F42、F43、F54、F57。

綜上所述：第一波次的機(jī)動(dòng)方案如表1所示，節(jié)點(diǎn)分配如圖2所示。

表1 第一波次機(jī)動(dòng)方案分配表

圖2 第一波次節(jié)點(diǎn)分配圖

2.6 步驟二模型的建立

根據(jù)步驟一求得各個(gè)坐標(biāo)節(jié)點(diǎn)，由于各個(gè)節(jié)點(diǎn)是確定的，所以需要先通過(guò)步驟一的原始模型，再增加約束條件：距離每個(gè)Zi周圍最近的地方Fi必須被第一波完成，以達(dá)到第二波的轉(zhuǎn)載速度最快。其次，在第一波齊射的頂點(diǎn)必須被刪除，其數(shù)學(xué)表達(dá)式為

(6)

同時(shí)，將上述Fi點(diǎn)確認(rèn)了之后，通過(guò)Dijkstra算法可以得到距離Zi最近的Fi的最短路徑集LFimin={f1i,f2i,…,fni}，接著分配在此處轉(zhuǎn)載的車輛在最快裝載完成之后開往距離LFimin中篩選出來(lái)的n個(gè)點(diǎn)中的最遠(yuǎn)的距離，用以獲得單車最長(zhǎng)暴露時(shí)間，從而可以得知第二波齊射條件下的最短整體暴露時(shí)間。

由于此時(shí)沒(méi)有從Di點(diǎn)出發(fā)，而是從各個(gè)Zi點(diǎn)出發(fā)，所以可以抽象為通過(guò)從6個(gè)Zi點(diǎn)尋找其最短距離。所以0-1整型規(guī)劃模型的約束條件改為：

(7)

而且每個(gè)點(diǎn)尋找的第二波發(fā)射點(diǎn)Fi需要根據(jù)其距離的加權(quán)集合LFimin·Q和速度的加權(quán)集合V·(VQ·TQ)進(jìn)行計(jì)算,以獲得到達(dá)第二波發(fā)射點(diǎn)的最短時(shí)間，所以，其目標(biāo)函數(shù)為

2.7 問(wèn)題的求解

根據(jù)上述模型的建立以及第一波的求解所得到的各個(gè)點(diǎn)，可求得LFimin={f1i,f2i,…,fni},然后根據(jù)各個(gè)賦權(quán)值之后，可以求得發(fā)車順序，從而計(jì)算得出使得單車第二波暴露時(shí)間最長(zhǎng)的路線和各個(gè)節(jié)點(diǎn)與車型的分配。第二波次的機(jī)動(dòng)方案見表2，節(jié)點(diǎn)分配圖如圖3所示。

綜合表1和表2可以得知：兩波齊射的最大暴露時(shí)間為

T總 (8)

續(xù)表

圖3 第二波次節(jié)點(diǎn)分配圖

3 結(jié) 論

本文通過(guò)對(duì)兩波齊射問(wèn)題的分解，將兩波齊射問(wèn)題分解為步驟一和步驟二，步驟一主要解決第一波齊射后所需要的單車最長(zhǎng)暴露時(shí)間，同時(shí)通過(guò)模型一選出Di中時(shí)間較長(zhǎng)的，從而通過(guò)時(shí)間反饋對(duì)模型再一次進(jìn)行優(yōu)化，為第二波齊射做準(zhǔn)備，并且將第一波在Di處等待時(shí)間較長(zhǎng)的發(fā)射點(diǎn)Fi進(jìn)行優(yōu)化。通過(guò)步驟一的反饋優(yōu)化，可以大大提高時(shí)間的利用率并且為第二波齊射做充分的準(zhǔn)備。

步驟二的模型是建立在第二波齊射關(guān)于第一波齊射的一定耦合度上的局部最優(yōu)解的基礎(chǔ)上進(jìn)行的，第二波齊射任務(wù)在考慮了時(shí)間權(quán)重的基礎(chǔ)上求解，可以減少發(fā)車順序錯(cuò)亂而導(dǎo)致的單車暴露時(shí)間過(guò)長(zhǎng)的問(wèn)題，同時(shí)求解LFimin可以得出距離最近的點(diǎn)，從而獲得單車暴露最短時(shí)間。

文章中所提出的模型是在距離、速度以及真實(shí)情況下所建立出來(lái)的模型。在此模型下，通過(guò)多次反饋、賦權(quán)來(lái)計(jì)算整體暴露時(shí)間的最小值，該方法能夠有效地解決一些常規(guī)的導(dǎo)彈任務(wù)分配問(wèn)題。