章胤　李瑞敏　郝茂林　王嘉瑜　孫鵬越　高琪

摘 要：由于衛(wèi)星在軍事領(lǐng)域的應(yīng)用，衛(wèi)星偵察下的軍事運(yùn)輸路線選擇得到廣泛關(guān)注。本文通過分析衛(wèi)星在其星下點(diǎn)的軌跡，并生成道路緩沖區(qū)，借助地理信息系統(tǒng)（GIS）和改進(jìn)的Dijkstra算法，為衛(wèi)星偵察下的最優(yōu)路徑選擇提供了更優(yōu)途徑。將該方法應(yīng)用于實(shí)際問題中，程序運(yùn)行所用時(shí)間為7.44秒，而經(jīng)典Dijkstra算法運(yùn)行時(shí)間為16.83秒，改進(jìn)后的Dijkstra算法相比經(jīng)典算法節(jié)約了近10秒，一定程度上能使相關(guān)最優(yōu)選擇問題的效率得到提高。

關(guān)鍵詞：衛(wèi)星運(yùn)動(dòng)；公路運(yùn)輸；路線選擇；GIS；Dijkstra算法

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言（Introduction）

隨著空間軍事化的高速發(fā)展，衛(wèi)星偵察因其可以獲得全天候、大范圍、近實(shí)時(shí)的戰(zhàn)場(chǎng)信息，被認(rèn)為是從外層空間采集地理信息的強(qiáng)有力的手段。為了保護(hù)國(guó)家機(jī)密，在軍事運(yùn)輸過程中必須要躲避航天衛(wèi)星的偵察并要在規(guī)定時(shí)間內(nèi)盡快到達(dá)目的地。因此，快速生成安全的最短運(yùn)輸路線，躲避衛(wèi)星偵查，實(shí)現(xiàn)安全運(yùn)輸顯得尤為重要。

國(guó)內(nèi)外對(duì)軍事運(yùn)輸路線選擇的研討處于發(fā)展完善階段。Rui Neves-Silva等人提出利用擴(kuò)展的Dijkstra算法計(jì)算災(zāi)害中撤離人員的替代路線[1]。Akshay Kumar Guruji等人利用在碰撞階段之前確定啟發(fā)式函數(shù)的值來代替初始化的一種路徑規(guī)劃算法，以尋找機(jī)器人工作時(shí)的無碰撞路徑，該算法減少了問題處理時(shí)間[2]。Xiu Li Gao等人研究改進(jìn)的Dijkstra算法解決動(dòng)態(tài)路徑選擇問題[3]。在國(guó)內(nèi)，王輝等人提出利用Dijkstra算法和改進(jìn)的蟻群算法解決泊車系統(tǒng)的路徑規(guī)劃問題[4]。沈睿等人使用GIS數(shù)據(jù)模型和改進(jìn)的Dijkstra算法，縮短了智能交通系統(tǒng)尋求最短路徑的搜索時(shí)間[5]。姚志敏提出了將Dijkstra算法總計(jì)算步數(shù)由原來的步減少為不到步的方法[6]。

本文結(jié)合衛(wèi)星的運(yùn)行軌跡和覆蓋范圍，以經(jīng)典Dijkstra算法為基礎(chǔ)，對(duì)算法進(jìn)行一定的改進(jìn)，提高了在衛(wèi)星影響下躲避衛(wèi)星偵察的最優(yōu)公路運(yùn)輸路線選擇的效率和準(zhǔn)確性，并借助GIS系統(tǒng)進(jìn)行模擬。

2 基于Dijkstra算法的路徑選擇模型（The path

selection model based on Dijkstra algorithm）

2.1 地理信息系統(tǒng)

地理信息系統(tǒng)（Geographic Information System，GIS）是用于不同層次的規(guī)劃、管理與決策所需要的信息粒度與空間信息的圖像表達(dá)（可視化）。GIS起源于專題地圖，但又高于專題制圖。在數(shù)字環(huán)境下，地圖信息成為GIS的基礎(chǔ)信息與專題信息的載體，一方面是為了通過圖形信息壓縮來保證地圖的可讀性，而更重要的是還負(fù)擔(dān)著生成GIS多尺度數(shù)據(jù)庫的新使命。對(duì)于以道路網(wǎng)為代表的人工線狀物體集合，利用賦權(quán)圖原理和結(jié)點(diǎn)度的信息使其結(jié)構(gòu)化，進(jìn)而對(duì)其進(jìn)行全局性評(píng)價(jià)[7]。在地理信息系統(tǒng)中，道路交叉點(diǎn)和道路分別構(gòu)成道路交通網(wǎng)絡(luò)中的點(diǎn)集合和邊集合。其中，通過收集點(diǎn)矢量要素和邊矢量要素的屬性字段，來創(chuàng)建邊和點(diǎn)之間的權(quán)重屬性。如道路的長(zhǎng)度、道路的類型、道路的寬度等都可以轉(zhuǎn)換為道路權(quán)重。該模型以對(duì)道路復(fù)雜性適應(yīng)度高的Dijkstra算法為基礎(chǔ)。

2.2 衛(wèi)星軌道和星下點(diǎn)軌跡

衛(wèi)星軌道是衛(wèi)星在獲得某一初始水平速度后，可以環(huán)繞地球飛行的運(yùn)行軌跡。根據(jù)開普勒第一定律，衛(wèi)星運(yùn)轉(zhuǎn)軌道的平面，是一個(gè)以地心為其中的一個(gè)焦點(diǎn)的橢圓。決定衛(wèi)星運(yùn)行軌道的參數(shù)主要有六種[8]，分別是長(zhǎng)軸a、偏心率e、軌道傾角i、升交點(diǎn)赤經(jīng)、近地點(diǎn)幅角和過近地點(diǎn)時(shí)刻t。衛(wèi)星的星下點(diǎn)是指衛(wèi)星和地心的連線與地面的交點(diǎn)。星下點(diǎn)軌跡是因衛(wèi)星運(yùn)動(dòng)與地球的自轉(zhuǎn)使得星下點(diǎn)在地球表面進(jìn)行移動(dòng)所形成的軌跡。由于地球自轉(zhuǎn)，衛(wèi)星星下點(diǎn)軌跡的前一圈與后一圈一般不重合。當(dāng)考慮地球自轉(zhuǎn)時(shí)，衛(wèi)星的星下點(diǎn)軌跡計(jì)算公式[9]為：

上述公式中：表示地心緯度、表示地心經(jīng)度、表示衛(wèi)星平均角速度、i表示軌道傾角、表示衛(wèi)星升交點(diǎn)相對(duì)經(jīng)度零點(diǎn)的西退速率、表示衛(wèi)星經(jīng)過升交點(diǎn)時(shí)的經(jīng)度、表示衛(wèi)星經(jīng)過升交點(diǎn)以后經(jīng)歷的時(shí)間。

2.3 衛(wèi)星覆蓋范圍

以衛(wèi)星在當(dāng)前時(shí)刻下，在地面上所有能觀察到衛(wèi)星的點(diǎn)的集合，作為衛(wèi)星的地面覆蓋區(qū)域。從理論上來說，如圖1所示，衛(wèi)星到地球表面的兩條切線、之間的部分便是衛(wèi)星的地面覆蓋區(qū)域。但由于最小觀察角的因素，實(shí)際的衛(wèi)星覆蓋規(guī)模會(huì)稍有縮小（即圖1中、以內(nèi)的位置）。同該區(qū)域，也就是以衛(wèi)星 在當(dāng)前時(shí)刻下，所要研究的緩沖區(qū)（對(duì)應(yīng)的星下點(diǎn) 為中心，以所對(duì)應(yīng)弧長(zhǎng)為半徑的地面區(qū)域）。在實(shí)際地理應(yīng)用中，將地球視為圓球，單顆衛(wèi)星的覆蓋范圍視為是以星下點(diǎn)軌跡為中心，寬度為的條形域。

2.4 影響因素簡(jiǎn)化

影響運(yùn)輸因素有很多，例如運(yùn)載工具的種類、道路的交通狀況（如紅綠燈個(gè)數(shù)、堵塞程度）、道路上的障礙（如壕溝、涵洞和橋梁）、部隊(duì)行駛時(shí)的指揮人員和駕駛?cè)藛T的技能，以及當(dāng)時(shí)的氣象條件等都是影響軍事運(yùn)輸?shù)囊蛩?。本文?duì)上述因素不予考慮，僅考慮衛(wèi)星偵察對(duì)道路選擇的影響。僅考慮高速公路、縣道、省道和國(guó)道這四種類型的道路。

2.5 經(jīng)典Dijkstra算法的主要原理

經(jīng)典Dijkstra算法是一種通過比較再添加的模型，也稱雙標(biāo)記法[10]。并且該算法只適用于邊權(quán)重均非負(fù)的賦權(quán)圖。對(duì)于圖，其中V表示頂點(diǎn)集，E表示邊集，W表示權(quán)集。對(duì)圖G中的每一點(diǎn)進(jìn)行標(biāo)號(hào)，其中是從源點(diǎn)s開始到第i個(gè)節(jié)點(diǎn)的最短路徑長(zhǎng)度，是第i個(gè)節(jié)點(diǎn)的直接前趨。其基本思路如下：

（1）對(duì)參數(shù)進(jìn)行初始化。令，并標(biāo)記s點(diǎn)。其他為，均為空。

（2）對(duì)于任意未標(biāo)記的節(jié)點(diǎn)j，求。其中表示已標(biāo)記的節(jié)點(diǎn)k到源點(diǎn)s的距離，表示從節(jié)點(diǎn)k到節(jié)點(diǎn)j的距離。

（3）標(biāo)記i節(jié)點(diǎn)，使得，并取。

（4）重復(fù)（2）（3）步，直到所有點(diǎn)的已標(biāo)記，算法運(yùn)行完畢。

2.6 Dijkstra算法理解與改進(jìn)

從2.3中的算法過程中可以看出，每個(gè)節(jié)點(diǎn)要標(biāo)記，需要比較其所連接的所有邊的最小值，并且最終要標(biāo)記所有的節(jié)點(diǎn)，算法才可以結(jié)束。也就是說，對(duì)于一張圖來說，圖中的節(jié)點(diǎn)越多，運(yùn)行算法的時(shí)間越長(zhǎng)。而對(duì)于實(shí)際道路中，因地理因素的影響，兩地之間的最短距離，往往不包括以兩點(diǎn)距離為直徑的圓以外的點(diǎn)，并且對(duì)于圖中邊的權(quán)值與實(shí)際道路長(zhǎng)度成正相關(guān)，即對(duì)于所考慮節(jié)點(diǎn)距離較遠(yuǎn)的節(jié)點(diǎn)，顯然沒必要考慮。所以對(duì)于算法遍歷的點(diǎn)的數(shù)量，可以選擇性遍歷，在以源點(diǎn)與所求節(jié)點(diǎn)歐氏距離為直徑的圓內(nèi)遍歷，可進(jìn)一步減少了循環(huán)比較的次數(shù)，從而提高算法的運(yùn)行效率。

在Dijkstra算法運(yùn)行步驟（2）中，對(duì)于遍歷所有未標(biāo)記的節(jié)點(diǎn)，傳統(tǒng)的Dijkstra算法關(guān)于節(jié)點(diǎn)的遍歷是無序的。我們知道算法要對(duì)所有點(diǎn)遍歷是不可避免的，但如果圖中節(jié)點(diǎn)有些權(quán)值明顯大于其他權(quán)值而又要先遍歷，到某個(gè)節(jié)點(diǎn)的最短路徑加經(jīng)過該節(jié)點(diǎn)邊的直接距離之和中取最小值，在進(jìn)行最小值判斷的時(shí)候，權(quán)值較大的邊會(huì)在循環(huán)中比較多次，這會(huì)制約算法的效率。如果在計(jì)算機(jī)運(yùn)行前得到權(quán)值的排序，利用這樣的排序可以將權(quán)值較小的優(yōu)先比較，那么在與其他邊比較的過程中，可以直接舍去一些權(quán)值較大的邊，從而可以提高算法效率。

引入順序數(shù)組，對(duì)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)加入篩選屬性scr，改進(jìn)的Dijkstra算法的主要思路如下：

（1）初始化源點(diǎn)數(shù)據(jù)，記scr值為0。對(duì)所有邊的權(quán)重匯總升序編號(hào)存入數(shù)組中。

（2）在以出發(fā)點(diǎn)到匯點(diǎn)為直徑的圓，將覆蓋到的點(diǎn)。

（3）對(duì)圓中未標(biāo)記的節(jié)點(diǎn)j，依數(shù)組D的次序，求。其中表示已標(biāo)記的節(jié)點(diǎn)k到源點(diǎn)s的距離，表示從節(jié)點(diǎn)k到節(jié)點(diǎn)j的距離。

（4）標(biāo)記i節(jié)點(diǎn)，使得，并取。

（5）重復(fù)（2）（3）（4）步，直到全部點(diǎn)的已標(biāo)記，算法運(yùn)行完畢。

對(duì)于增加的衛(wèi)星過頂因素，以衛(wèi)星過頂時(shí)的緩沖區(qū)為參考，一方面減少了所遍歷的點(diǎn)的個(gè)數(shù)，但另一方面會(huì)阻礙原始最短路徑的選擇，并且緩沖區(qū)會(huì)隨著時(shí)間規(guī)律性移動(dòng)。

為了解決這些問題，將衛(wèi)星過頂?shù)木彌_區(qū)等效為車輛沿原始最短路行駛下的緩沖區(qū)，將經(jīng)過緩沖區(qū)以后的路段進(jìn)行二次處理。以重新進(jìn)入緩沖區(qū)的節(jié)點(diǎn)作為新的源點(diǎn)，重新尋找最短路徑，每找到一個(gè)中間點(diǎn)，將該點(diǎn)作為新的源點(diǎn)，再次重新尋找最短路徑，直到離開衛(wèi)星緩沖區(qū)。

3 應(yīng)用與實(shí)現(xiàn)（Application and implementation）

在Arcgis 10.2，Orbitron 3.71等軟件中對(duì)算法進(jìn)行實(shí)現(xiàn)。利用Orbitron 3.71獲取衛(wèi)星信息，利用Arcgis 10.2獲取地理地圖并對(duì)其數(shù)據(jù)庫進(jìn)行處理，利用Arcgis 10.2中自帶的Python 2.7腳本實(shí)現(xiàn)算法。

3.1 衛(wèi)星過頂軌跡

選擇恰當(dāng)?shù)男l(wèi)星，使其星下點(diǎn)軌跡經(jīng)過所研究的道路。由于衛(wèi)星不斷運(yùn)動(dòng)，故設(shè)置每1分鐘更新一次衛(wèi)星位置，如圖3所示。通過衛(wèi)星各項(xiàng)參數(shù)，計(jì)算出衛(wèi)星掃描范圍，生成緩沖區(qū)。

3.2 最短路徑生成

考慮所選衛(wèi)星經(jīng)過的地理區(qū)域進(jìn)行試驗(yàn)，利用Arcgis 10.2繪制河北省秦皇島市—唐山市地圖，地籍?dāng)?shù)據(jù)采集1：10000；經(jīng)過計(jì)算，共得到4597個(gè)道路交叉點(diǎn)。假設(shè)高速公路行駛時(shí)速為勻速100公里/小時(shí)，普通公路行駛時(shí)速為勻速50公里/小時(shí)，不考慮行駛過程中的加、減速時(shí)間；假設(shè)衛(wèi)星的覆蓋面帶是以星下點(diǎn)軌跡為中心，寬度為固定值的條帶；假設(shè)A地和B地之間有多條路相連，在運(yùn)輸過程中如果按未考慮衛(wèi)星影響因素生成的最短路徑在衛(wèi)星的覆蓋范圍內(nèi)，那么依據(jù)衛(wèi)星所在位置和覆蓋范圍在衛(wèi)星覆蓋區(qū)域外尋找路徑或者原地等待。如果經(jīng)過區(qū)域沒有被衛(wèi)星覆蓋，那么依照原路行駛；不考慮車隊(duì)長(zhǎng)度對(duì)避開衛(wèi)星的影響。

若采用經(jīng)典Dijkstra算法腳本運(yùn)行，因經(jīng)過緩沖區(qū)以后，緩沖區(qū)之內(nèi)的點(diǎn)再次加入，節(jié)點(diǎn)最短路徑得到更新，所以最終得到的路徑并不是在緩沖區(qū)影響下的最短路徑。采用改進(jìn)的方法，所生成的道路并不是起點(diǎn)到終點(diǎn)的最短路，而是最短路的近似。其原因在于緩沖區(qū)是動(dòng)態(tài)移動(dòng)的，如按原始選擇的道路行駛將會(huì)與緩沖區(qū)相遇。于是選擇更換道路，在衛(wèi)星無法偵察到的其余道路中選擇最短路。

選擇以河北省秦皇島市（119.714°E，39.946°N）為起點(diǎn)，以唐山市（118.172°E，39.615°N）為終點(diǎn)，經(jīng)過G1高速，楊柏路，再到唐古路，最終到達(dá)目的地，途中紅色標(biāo)線即為躲避衛(wèi)星偵察的最短路徑。通過對(duì)比發(fā)現(xiàn)，利用改進(jìn)后的算法，根據(jù)衛(wèi)星進(jìn)入的時(shí)刻，重新記錄新起點(diǎn)，程序運(yùn)行所用時(shí)間為7.44秒，而經(jīng)典算法所運(yùn)行時(shí)間為16.83秒，相比經(jīng)典算法節(jié)約了近10秒，一定程度上縮短了路徑選擇時(shí)間。

4 結(jié)論（Conclusion）

本文基于衛(wèi)星星下點(diǎn)軌跡、衛(wèi)星覆蓋范圍和Dijkstra算法的特點(diǎn)，并借助地理信息系統(tǒng)，建立了基于改進(jìn)的Dijkstra算法躲避衛(wèi)星偵察的路線選擇模型，并通過軟件進(jìn)行了實(shí)現(xiàn)，滿足了軍事運(yùn)輸過程中對(duì)隱蔽性和快速性的要求。但本文在對(duì)道路進(jìn)行選擇時(shí)，僅考慮了常見的道路類型。算法效率雖然得到提高，但也減少了道路選擇，使得所求得的距離與實(shí)際最短路仍有差距。同時(shí)，由于道路限制等其他復(fù)雜原因，無法求得真正意義上的最短路徑，只能最大程度的接近，也是接下來進(jìn)一步研究的重點(diǎn)。

參考文獻(xiàn)（References）

[1] Rui Neves-Silva，George A.Tshirintzis，Vladimir Uskov，et al.An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation[J].Frontiers in Artificial Intelligence and Applications，2014：262.

[2] Akshay Kumar Guruji，Himansh Agarwal，D.K.Parsediya.Time-efficient A*Algorithm for Robot Path Planning[J].Procedia Technology，2016：23.

[3] Xiu Li Gao，Tian Jun Hu，Jia Zheng.Research on Dynamic Path Selection Improved Dijkstra Algorithm[J].Advanced Materials Research，2014（1006）：3382.

[4] 王輝，朱龍彪，王景良，等.基于Dijkstra-蟻群算法的泊車系統(tǒng)路徑規(guī)劃研究[J].工程設(shè)計(jì)學(xué)報(bào)，2016，23（05）：489-496.

[5] 沈睿，朱學(xué)君.基于GIS的最優(yōu)路徑選擇的設(shè)計(jì)與實(shí)現(xiàn)[J].工業(yè)儀表與自動(dòng)化裝置，2016（02）：102-105.

[6] 姚志敏.最短路徑問題Dijkstra算法的改進(jìn)[J].數(shù)字技術(shù)與應(yīng)用，2016（11）：133.

[7] 任偉建，左方晨，黃麗杰.基于GIS的Dijkstra算法改進(jìn)研究[J].控制工程，2018，25（02）：188-191.

[8] 韓建昌.我國(guó)通用航空文化建設(shè)研究[D].西北工業(yè)大學(xué)，2016.

[9] 張三彬，張永生，近圓.軌逍遙感衛(wèi)星星下點(diǎn)軌跡的計(jì)算[J].測(cè)繪學(xué)院學(xué)報(bào)，2001，18（4）：257-259.

[10] 王樹西，李安渝.Dijkstra算法中的多鄰接點(diǎn)與多條最短路徑問題[J].計(jì)算機(jī)科學(xué)，2014，41（06）：217-224.

作者簡(jiǎn)介：

章 胤（1978-），男，碩士，講師.研究領(lǐng)域：微分方程數(shù)值解，數(shù)學(xué)建模.

李瑞敏（1996-），女，本科生.研究領(lǐng)域：統(tǒng)計(jì)學(xué).

郝茂林（1995-），男，本科生.研究領(lǐng)域：信息與計(jì)算科學(xué).

王嘉瑜（1996-），女，本科生.研究領(lǐng)域：統(tǒng)計(jì)學(xué).

孫鵬越（1998-），男，本科生.研究領(lǐng)域：統(tǒng)計(jì)學(xué).

高 琪（1997-），女，本科生.研究領(lǐng)域：會(huì)計(jì).