李珍萍，劉 嶸，陳星藝，徐 冉，邢立寧

(1.北京物資學(xué)院 信息學(xué)院，北京 101149;2.中南林業(yè)科技大學(xué) 物流與交通學(xué)院，湖南 長(zhǎng)沙 410018)

0 引言

隨著航天技術(shù)的日益進(jìn)步，無(wú)人飛行器(簡(jiǎn)稱無(wú)人機(jī))技術(shù)發(fā)展迅速。由于無(wú)人機(jī)具有使用成本低、機(jī)動(dòng)性強(qiáng)、安全風(fēng)險(xiǎn)小等特點(diǎn)，已被大量用于執(zhí)行高危險(xiǎn)、高強(qiáng)度或大范圍的巡檢、搜救等任務(wù)[1]。無(wú)人機(jī)能夠順利到達(dá)目標(biāo)點(diǎn)是成功執(zhí)行任務(wù)的必要前提。無(wú)人機(jī)航跡規(guī)劃是指在給定的工作環(huán)境中，尋找滿足無(wú)人機(jī)性能及飛行條件約束的，從起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)飛行軌跡,使無(wú)人機(jī)的飛行代價(jià)盡可能小，無(wú)人機(jī)航跡規(guī)劃問(wèn)題已成為該領(lǐng)域的研究焦點(diǎn)。

由于不同場(chǎng)景下的無(wú)人機(jī)航跡規(guī)劃問(wèn)題需要考慮的目標(biāo)和約束不同，對(duì)應(yīng)的問(wèn)題難度會(huì)有很大的差別。近年來(lái)，國(guó)內(nèi)外學(xué)者針對(duì)不同場(chǎng)景下的無(wú)人機(jī)航跡規(guī)劃問(wèn)題開(kāi)展了研究?，F(xiàn)有研究考慮的主要目標(biāo)包括：總飛行距離(或完成任務(wù)的時(shí)間)最短[1-2]、總服務(wù)效率最大[3]、保密效能最好[4]，或總飛行成本最低或能耗最小[5]等；現(xiàn)有研究中考慮的約束條件包括無(wú)人機(jī)飛行時(shí)間限制[3]、能耗限制[4]、飛行平衡約束[6]、避開(kāi)障礙物[7-8]或無(wú)人機(jī)之間的協(xié)同約束[9]等。其中很多問(wèn)題可以歸結(jié)為帶約束的最短路問(wèn)題，由于大部分帶約束的最短路問(wèn)題都屬于NP-hard問(wèn)題，精確求解需要的運(yùn)行時(shí)間較長(zhǎng)，現(xiàn)有研究主要集中在設(shè)計(jì)求解問(wèn)題的快速有效算法方面[10-11]。

引導(dǎo)無(wú)人機(jī)沿著規(guī)劃的航線飛行，離不開(kāi)導(dǎo)航系統(tǒng)，目前應(yīng)用最廣泛的是捷聯(lián)慣性導(dǎo)航(strap-down inertial navigation)系統(tǒng)，該系統(tǒng)將陀螺儀和加速度計(jì)等設(shè)備安裝在無(wú)人機(jī)上，將這些儀器測(cè)量的信號(hào)直接變換為導(dǎo)航參數(shù)進(jìn)行導(dǎo)航。由于捷聯(lián)慣性導(dǎo)航系統(tǒng)的核心組件陀螺儀和加速度計(jì)存在漂移誤差，而且部分誤差會(huì)隨著飛行距離增加而不斷累積[12]，當(dāng)累積誤差超出允許的范圍時(shí)會(huì)導(dǎo)致導(dǎo)航失敗。為確保無(wú)人機(jī)沿著正確的航跡飛行，必須結(jié)合其他系統(tǒng)信息對(duì)捷聯(lián)慣導(dǎo)系統(tǒng)產(chǎn)生的累積誤差進(jìn)行校正[13]。通常可以使用GPS(global positioning system)的信息進(jìn)行校正，使無(wú)人機(jī)能夠沿著正確的航跡前進(jìn)[14]。

利用GPS系統(tǒng)信息對(duì)捷聯(lián)慣導(dǎo)系統(tǒng)累積誤差進(jìn)行校正的方法是：在無(wú)人機(jī)飛行區(qū)域內(nèi)，預(yù)先設(shè)置一系列誤差校正點(diǎn)，當(dāng)無(wú)人機(jī)經(jīng)過(guò)這些誤差校正點(diǎn)(或其附近小范圍的區(qū)域)時(shí)，捷聯(lián)慣導(dǎo)系統(tǒng)的累積誤差就可以被誤差校正點(diǎn)成功校正為0。由于每個(gè)誤差校正點(diǎn)通常只能校正一個(gè)方向(水平方向或垂直方向)的累積誤差，且每個(gè)誤差校正點(diǎn)的覆蓋范圍有限，只有當(dāng)無(wú)人機(jī)進(jìn)入誤差校正點(diǎn)覆蓋區(qū)域(即水平方向和垂直方向的累積誤差不超過(guò)誤差校正點(diǎn)要求的閾值)時(shí)，其相應(yīng)方向累積誤差才能被校正。若無(wú)人機(jī)沒(méi)有到達(dá)指定誤差校正點(diǎn)時(shí)對(duì)應(yīng)的水平方向或垂直方向累積誤差超過(guò)了規(guī)定的閾值，則其相應(yīng)方向的累積誤差不能及時(shí)得到校正，這將直接導(dǎo)致其飛行軌跡偏離航線，無(wú)法到達(dá)目標(biāo)點(diǎn)。因此，在對(duì)無(wú)人機(jī)進(jìn)行航跡規(guī)劃的時(shí)候，必須確保飛行過(guò)程中各個(gè)方向的累積誤差及時(shí)得到校正，這是無(wú)人機(jī)順利到達(dá)終點(diǎn)的必要條件。現(xiàn)有的關(guān)于無(wú)人機(jī)航跡規(guī)劃問(wèn)題的研究，很少考慮累積誤差校正約束?；谝陨戏治觯疚臄M在考慮水平方向和垂直方向誤差校正點(diǎn)的前提下，研究無(wú)人機(jī)航跡規(guī)劃問(wèn)題，該問(wèn)題屬于一類(lèi)新的帶約束最短路問(wèn)題。

帶約束的最短路問(wèn)題可以描述為在一個(gè)有向或無(wú)向圖中，尋找一條從起點(diǎn)到終點(diǎn)長(zhǎng)度最短的路徑，且該路徑必須滿足給定的約束條件，如帶容量約束[15-17]、帶時(shí)間窗約束[18-21]、帶必經(jīng)點(diǎn)約束[22]、顧客滿意度約束[23]、時(shí)變網(wǎng)絡(luò)約束[24]等。帶約束的最短路問(wèn)題是無(wú)約束最短路問(wèn)題的推廣，無(wú)約束最短路問(wèn)題屬于P問(wèn)題，當(dāng)所有邊權(quán)均為非負(fù)數(shù)時(shí)，可以利用標(biāo)號(hào)法(即Dijkstra算法)求解，其時(shí)間復(fù)雜度為O(n2)[25]，當(dāng)圖中含有負(fù)的邊權(quán)時(shí)，可以利用Floyd算法求解，其時(shí)間復(fù)雜度為O(n3)[25]。

帶約束的最短路問(wèn)題大部分是NP-hard問(wèn)題[26]，即使圖中所有邊權(quán)均為正數(shù)，也很難求解?，F(xiàn)有文獻(xiàn)中對(duì)于帶約束最短路問(wèn)題的求解方法大體可以分為精確算法和混合啟發(fā)式算法。其中精確算法有：整數(shù)規(guī)劃方法[18]、雙向標(biāo)記算法[27-28]、拉格朗日松弛法[29]、動(dòng)態(tài)規(guī)劃算法[30]、列生成算法[31-32]等。針對(duì)精確算法求解過(guò)程中由于搜索空間太大導(dǎo)致求解時(shí)間太長(zhǎng)等問(wèn)題，部分學(xué)者提出將多種策略相結(jié)合的混合啟發(fā)式算法，如粒子群算法和變鄰域搜索相結(jié)合[16],標(biāo)號(hào)法和禁忌搜索相結(jié)合[17],基于k-opt移動(dòng)、候選路徑搜索、沖突節(jié)點(diǎn)提升和連接松弛等多種策略的元啟發(fā)式算法[22],超啟發(fā)式遺傳算法[20]，回溯優(yōu)化算法[33]等。

通常情況下，精確算法可以得到問(wèn)題的全局最優(yōu)解，但需要較長(zhǎng)的運(yùn)行時(shí)間；混合啟發(fā)式算法的運(yùn)行時(shí)間大大縮短，但很多混合啟發(fā)式算法無(wú)法保證得到全局最優(yōu)解。

Lozano等[34]于2013年提出了求解帶約束最短路問(wèn)題的脈沖算法，其本質(zhì)是一種分支切割算法，是求解帶約束最短路問(wèn)題的精確算法。該算法將標(biāo)號(hào)法與分支切割法巧妙地結(jié)合在一起，通過(guò)引入3種判斷準(zhǔn)則，有效地縮小了搜索空間，提高了求解效率。該算法在求解帶約束的最短路問(wèn)題上取得了很好的效果。

GPS與捷聯(lián)慣導(dǎo)系統(tǒng)相結(jié)合背景下的無(wú)人機(jī)航跡規(guī)劃問(wèn)題中，為了確保無(wú)人機(jī)能夠順利到達(dá)終點(diǎn)，必須滿足無(wú)人機(jī)飛行途中經(jīng)過(guò)每個(gè)誤差校正點(diǎn)時(shí)，其水平方向和垂直方向的累積誤差不超過(guò)給定的閾值。該約束條件與現(xiàn)有文獻(xiàn)中考慮的約束條件均不相同，因此無(wú)法用文獻(xiàn)中的方法直接求解帶誤差校正點(diǎn)約束的無(wú)人機(jī)航跡規(guī)劃問(wèn)題。

本文針對(duì)該問(wèn)題開(kāi)展研究，在給定的導(dǎo)航區(qū)域內(nèi)，考慮水平方向和垂直方向的誤差校正點(diǎn)，建立使總飛行距離最短的無(wú)人機(jī)航跡規(guī)劃問(wèn)題數(shù)學(xué)模型，基于多維標(biāo)號(hào)算法和脈沖算法設(shè)計(jì)求解模型的快速精確算法，為無(wú)人機(jī)航跡規(guī)劃提供理論依據(jù)。

1 問(wèn)題描述與分析

捷聯(lián)慣性導(dǎo)航系統(tǒng)和輔助誤差校正系統(tǒng)聯(lián)合應(yīng)用場(chǎng)景下，同時(shí)考慮水平誤差和垂直誤差校正點(diǎn)的無(wú)人機(jī)航跡規(guī)劃問(wèn)題可以描述如下：已知無(wú)人機(jī)的飛行起點(diǎn)、終點(diǎn)和飛行區(qū)域內(nèi)預(yù)先設(shè)置的若干個(gè)水平誤差和垂直誤差校正點(diǎn)。假設(shè)無(wú)人機(jī)在飛行過(guò)程中，慣性導(dǎo)航系統(tǒng)在水平方向和垂直方向均會(huì)產(chǎn)生累積誤差，且兩個(gè)方向產(chǎn)生的累積誤差都與飛行距離成正比例。為了對(duì)慣性導(dǎo)航系統(tǒng)產(chǎn)生的累積誤差進(jìn)行校正，輔助誤差校正系統(tǒng)(如GPS)在飛行區(qū)域內(nèi)的特定位置預(yù)先設(shè)置了若干個(gè)水平誤差校正點(diǎn)和垂直誤差校正點(diǎn)。當(dāng)無(wú)人機(jī)到達(dá)某個(gè)水平(垂直)誤差校正點(diǎn)時(shí)，若其水平方向和垂直方向的誤差不超過(guò)給定的閾值，則其水平(垂直)方向的誤差可以被校正為0，垂直(水平)方向的誤差不變；若無(wú)人機(jī)到達(dá)某個(gè)水平(或垂直)誤差校正點(diǎn)時(shí)，其水平誤差或垂直誤差超過(guò)了給定的閾值，則誤差校正失敗，無(wú)人機(jī)將偏離規(guī)劃航跡，無(wú)法到達(dá)終點(diǎn)，此次飛行任務(wù)失敗。為保證無(wú)人機(jī)順利到達(dá)終點(diǎn)，在進(jìn)行航跡規(guī)劃時(shí)，可以包含一定數(shù)量的誤差校正點(diǎn)，問(wèn)題是如何規(guī)劃從起點(diǎn)出發(fā)，依次經(jīng)過(guò)若干個(gè)誤差校正點(diǎn)并成功到達(dá)終點(diǎn)的航跡，才能使無(wú)人機(jī)的總飛行距離最短。

假設(shè)無(wú)人機(jī)在任意兩點(diǎn)之間均可以沿直線飛行，且在誤差校正點(diǎn)可以變換飛行方向。在以上假設(shè)下，一條可行的飛行航跡指由起點(diǎn)出發(fā)，依次通過(guò)若干個(gè)誤差校正點(diǎn)，最后到達(dá)終點(diǎn)的序列，且滿足下列兩個(gè)條件：

(1)無(wú)人機(jī)到達(dá)每個(gè)誤差校正點(diǎn)時(shí)，其水平誤差和垂直誤差均不超過(guò)給定的閾值(誤差校正成功的條件)。

(2)無(wú)人機(jī)到達(dá)終點(diǎn)時(shí)水平誤差和垂直誤差不超過(guò)給定的閾值(順利到達(dá)終點(diǎn)的條件)。

基于以上分析，無(wú)人機(jī)航跡規(guī)劃問(wèn)題可以表示為帶誤差校正約束的最短路問(wèn)題，即求一條滿足多個(gè)約束條件的總飛行里程最短的航跡。該問(wèn)題的約束條件包括：①無(wú)人機(jī)到達(dá)路徑中的每個(gè)中間點(diǎn)(誤差校正點(diǎn))時(shí)，必須滿足該點(diǎn)對(duì)應(yīng)的誤差校正條件；②無(wú)人機(jī)到達(dá)終點(diǎn)時(shí)，水平誤差和垂直誤差必須滿足條件。

圖1描述了一條經(jīng)過(guò)10個(gè)誤差校正點(diǎn)的可行飛行路徑。路徑中包含了5個(gè)水平誤差校正點(diǎn)和5個(gè)垂直誤差校正點(diǎn)。

2 無(wú)人機(jī)航跡規(guī)劃問(wèn)題的混合整數(shù)規(guī)劃模型

2.1 符號(hào)說(shuō)明

為了建立無(wú)人機(jī)航跡規(guī)劃問(wèn)題的數(shù)學(xué)模型，首先定義如下符號(hào)：

垂直誤差校正點(diǎn)的抵達(dá)條件：垂直誤差不超過(guò)α1，水平誤差不超過(guò)α2;

水平誤差校正點(diǎn)的抵達(dá)條件：垂直誤差不超過(guò)β1，水平誤差不超過(guò)β2;

δ為無(wú)人機(jī)每飛行單位距離，水平誤差和垂直誤差各增加δ;

θ為無(wú)人機(jī)抵達(dá)終點(diǎn)時(shí)，水平誤差和垂直誤差均不大于θ，才能保證安全降落;

1為起點(diǎn)序號(hào);

n為終點(diǎn)序號(hào);

V=V1∪V2={2,3，…,n-1}，為誤差校正點(diǎn)集合，其中：V1表示水平誤差校正點(diǎn)集合，V2表示垂直誤差校正點(diǎn)集合；

i,j,k為點(diǎn)的索引(i,j,k∈{1,2,…,n});

dij為點(diǎn)i到點(diǎn)j的直線距離。

2.2 決策變量

定義如下決策變量：

lj為無(wú)人機(jī)沿最優(yōu)路徑飛行，到達(dá)點(diǎn)j時(shí)的累計(jì)飛行距離；

gj為無(wú)人機(jī)沿最優(yōu)路徑飛行，到達(dá)點(diǎn)j時(shí)的水平誤差；

hj為無(wú)人機(jī)沿最優(yōu)路徑飛行，到達(dá)點(diǎn)j時(shí)的垂直誤差；

Sj為無(wú)人機(jī)沿最優(yōu)路徑飛行，離開(kāi)點(diǎn)j時(shí)的水平誤差；

Tj為無(wú)人機(jī)沿最優(yōu)路徑飛行，離開(kāi)點(diǎn)j時(shí)的垂直誤差。

2.3 模型建立

考慮水平誤差和垂直誤差校正點(diǎn)的無(wú)人機(jī)航跡規(guī)劃問(wèn)題可以表示成如下混合整數(shù)規(guī)劃模型：

minln。

(1)

s.t.

(2)

(3)

(4)

(5)

lj≥li+dij·xij-M·(1-xij),

i∈{1}∪V,j∈V∪{n};

(6)

gj≥Si+δ·dij·xij-M·(1-xij),

i∈{1}∪V,j∈V∪{n};

(7)

hj≥Ti+δ·dij·xij-M·(1-xij),

i∈{1}∪V,j∈V∪{n};

(8)

gj≤α2+M·(1-yj),j∈V2;

(9)

hj≤α1+M·(1-yj),j∈V2;

(10)

Sj=gj,j∈V2;

(11)

Tj=hj(1-yj),j∈V2;

(12)

gj≤β2+M·(1-yj),j∈V1;

(13)

hj≤β1+M·(1-yj),j∈V1;

(14)

Sj=gj(1-yj),j∈V1;

(15)

Tj=hj,j∈V1;

(16)

gn≤θ;

(17)

hn≤θ;

(18)

S1=0;

(19)

T1=0;

(20)

l1=0;

(21)

lj≥0,gj≥0,hj≥0,Sj≥0,Tj≥0,

j∈V∪{n};

(22)

xij∈{0,1}i∈{1}∪V,j∈V∪{n};

(23)

yj∈{0,1},j∈V∪{1}∪{n}。

(24)

目標(biāo)函數(shù)(1)表示無(wú)人機(jī)到達(dá)終點(diǎn)時(shí)總飛行路徑長(zhǎng)度最短。約束條件(2)表示最優(yōu)路徑的起點(diǎn)為1；約束條件(3)表示最優(yōu)路徑的終點(diǎn)為n；約束條件(4)和(5)表示最優(yōu)路徑經(jīng)過(guò)的每一個(gè)中間點(diǎn)只有一條邊進(jìn)入，一條邊離開(kāi)；約束條件(6)表示無(wú)人機(jī)從起點(diǎn)出發(fā)沿著最優(yōu)路徑到達(dá)相鄰兩點(diǎn)的飛行距離之間的關(guān)系；約束條件(7)和(8)分別表示無(wú)人機(jī)沿著最優(yōu)路徑到達(dá)相鄰兩點(diǎn)的水平誤差和垂直誤差之間的關(guān)系;約束條件(9)和(10)表示無(wú)人機(jī)沿著最優(yōu)路徑到達(dá)垂直誤差校正點(diǎn)時(shí)，其水平誤差和垂直誤差分別不能超過(guò)給定的閾值(垂直誤差校正點(diǎn)約束)；約束條件(11)和(12)分別表示無(wú)人機(jī)離開(kāi)垂直誤差校正點(diǎn)時(shí)，其水平誤差和垂直誤差的取值，其中水平誤差不變，垂直誤差校正為零;約束條件(13)～(16)的含義與約束條件(9)～(12)類(lèi)似，分別表示無(wú)人機(jī)到達(dá)和離開(kāi)水平誤差校正點(diǎn)時(shí)的水平和垂直誤差取值；約束條件(17)和(18)表示無(wú)人機(jī)到達(dá)終點(diǎn)時(shí)水平誤差和垂直誤差不超過(guò)給定的閾值(成功到達(dá)終點(diǎn)的約束);約束條件(19)～(21)表示無(wú)人機(jī)從起點(diǎn)出發(fā)時(shí)，其飛行距離、水平誤差、垂直誤差均為0；約束條件(22)～(24)表示變量取值約束。

無(wú)人機(jī)航跡規(guī)劃問(wèn)題可以表示為混合整數(shù)規(guī)劃模型，對(duì)于小規(guī)模問(wèn)題，可以直接用求解器(如Gurobi等)進(jìn)行求解；對(duì)于大規(guī)模問(wèn)題，由于模型的約束條件和變量較多，求解器很難在可接受的時(shí)間內(nèi)得到問(wèn)題的全局最優(yōu)解。

由于一方面實(shí)際問(wèn)題的規(guī)模都較大，另一方面實(shí)際中往往需要在短時(shí)間內(nèi)對(duì)無(wú)人機(jī)的航跡作出規(guī)劃，設(shè)計(jì)求解模型的快速有效算法是解決這類(lèi)問(wèn)題的關(guān)鍵。接下來(lái)將結(jié)合帶誤差校正點(diǎn)約束的無(wú)人機(jī)航跡規(guī)劃問(wèn)題混合整數(shù)規(guī)劃模型結(jié)構(gòu)，設(shè)計(jì)求解模型的兩階段算法。

3 兩階段算法設(shè)計(jì)與分析

無(wú)人機(jī)航跡規(guī)劃問(wèn)題可以歸結(jié)為帶誤差校正點(diǎn)約束的最短路問(wèn)題。求解無(wú)約束最短路徑問(wèn)題常用的標(biāo)號(hào)算法本質(zhì)上屬于動(dòng)態(tài)規(guī)劃算法，由于無(wú)約束最短路問(wèn)題的最優(yōu)解滿足最優(yōu)性條件，即最優(yōu)路徑中的部分路徑也一定是最優(yōu)的?；谧顑?yōu)性原理設(shè)計(jì)的求解無(wú)約束最短路徑問(wèn)題的標(biāo)號(hào)法為多項(xiàng)式時(shí)間算法。本文研究的無(wú)人機(jī)航跡規(guī)劃問(wèn)題中，由于存在誤差校正點(diǎn)，無(wú)人機(jī)飛行中的累積誤差在經(jīng)過(guò)校正點(diǎn)前后的取值不滿足線性關(guān)系，由此導(dǎo)致帶誤差校正約束的最短路問(wèn)題的最優(yōu)解不滿足最優(yōu)性條件，即從起點(diǎn)到終點(diǎn)滿足誤差校正約束的最短路徑中的部分路徑不一定是連接兩點(diǎn)且滿足誤差校正約束的最短路徑。下面用一個(gè)二維空間中的示例加以說(shuō)明。

例1已知無(wú)人機(jī)飛行區(qū)域內(nèi)的5個(gè)點(diǎn)，如圖2所示，1為出發(fā)點(diǎn)，5為目標(biāo)點(diǎn)，2、4為水平誤差校正點(diǎn)，3為垂直誤差校正點(diǎn)。兩點(diǎn)之間的連邊表示無(wú)人機(jī)可以飛行的航線，邊權(quán)表示飛行距離。假設(shè)無(wú)人機(jī)從1點(diǎn)出發(fā)時(shí)水平誤差和垂直誤差均為0,無(wú)人機(jī)飛行單位距離在水平方向和垂直方向產(chǎn)生的累積誤差均為0.1。當(dāng)無(wú)人機(jī)經(jīng)過(guò)某個(gè)水平(或垂直)誤差校正點(diǎn)時(shí)，若其水平誤差和垂直誤差均不超過(guò)0.3，則其水平(或垂直)誤差將被校正為0，垂直(或水平)誤差不變。無(wú)人機(jī)成功到達(dá)目標(biāo)點(diǎn)的條件是水平誤差和垂直誤差均不超過(guò)0.3。如何規(guī)劃無(wú)人機(jī)的航跡，才能使總飛行距離最短？

由于該問(wèn)題規(guī)模很小，直接利用Gurobi 8.0編程求解混合整數(shù)規(guī)劃模型可以得到無(wú)人機(jī)的最優(yōu)航跡為1-2-3-5，對(duì)應(yīng)的最短飛行距離為4.5，到達(dá)目標(biāo)點(diǎn)5時(shí)水平方向累積誤差為0.25，垂直方向累積誤差為0.2。

容易驗(yàn)證，無(wú)人機(jī)最優(yōu)飛行航跡中的部分路徑1-2-3并不是從1到3的最優(yōu)路徑。實(shí)際上，從1到3的最優(yōu)路徑為1-3，沿著該路徑到達(dá)3時(shí)，總飛行距離為2，水平誤差和垂直誤差均為0.2。如果無(wú)人機(jī)沿著最優(yōu)航跡1-2-3-5中的部分路徑1-2-3飛行，到達(dá)3點(diǎn)的總飛行距離為2.5，水平誤差為0.05，垂直誤差為0.25。顯然，最優(yōu)路徑中的子路徑1-2-3對(duì)應(yīng)的飛行距離大于路徑1-3對(duì)應(yīng)的距離，這說(shuō)明帶誤差校正點(diǎn)約束的最短路問(wèn)題不滿足最優(yōu)性條件。因此，經(jīng)典的標(biāo)號(hào)算法無(wú)法直接用來(lái)求解帶誤差校正約束的最短路問(wèn)題。

為了求出帶誤差校正約束的無(wú)人機(jī)航跡規(guī)劃問(wèn)題全局最優(yōu)解，需要將從起點(diǎn)到中間點(diǎn)的所有可行子路徑信息保存下來(lái)。由于求解無(wú)約束最短路徑問(wèn)題的Dijkstra標(biāo)號(hào)算法只保留了從起點(diǎn)到中間點(diǎn)的最優(yōu)路徑，因此，經(jīng)典標(biāo)號(hào)算法可能會(huì)漏掉那些本來(lái)應(yīng)該出現(xiàn)在最優(yōu)解中的非最優(yōu)子路徑(如例1中的子路徑1-2-3)，從而導(dǎo)致無(wú)法找到問(wèn)題的最優(yōu)解。為了避免漏掉可能包含在最優(yōu)解中的非最優(yōu)子路徑，一種可行的方法是，保留從起點(diǎn)到每個(gè)中間點(diǎn)的所有可行子路徑，這樣做會(huì)使搜索空間變大，求解時(shí)間延長(zhǎng)。如果能夠借助一定的策略提前識(shí)別出那些不可能包含在最優(yōu)解中的可行子路徑，則可以通過(guò)剪枝縮小搜索空間，有效降低計(jì)算復(fù)雜度，提高求解效率。因此，提高算法性能的關(guān)鍵是快速準(zhǔn)確地識(shí)別出哪些是不可能包含在最優(yōu)解中的可行子路徑，哪些是可能擴(kuò)展成最優(yōu)解的可行子路徑[36]。

脈沖算法將分支定界思想和動(dòng)態(tài)規(guī)劃方法相結(jié)合，在求解帶約束的最短路徑問(wèn)題中取得了較好的效果。脈沖算法在求解帶約束最短路徑問(wèn)題時(shí)，以當(dāng)前最好的可行解對(duì)應(yīng)的路徑總長(zhǎng)度作為最優(yōu)目標(biāo)函數(shù)值的上界，對(duì)于每一個(gè)待擴(kuò)展的路徑點(diǎn)，利用目標(biāo)函數(shù)值上界判斷從起點(diǎn)到該點(diǎn)的可行子路徑有沒(méi)有可能擴(kuò)展為從起點(diǎn)到終點(diǎn)的最優(yōu)路徑。對(duì)于一條可行子路徑，若能夠證明由該子路徑擴(kuò)展得到的從起點(diǎn)到終點(diǎn)的可行路徑長(zhǎng)度的下界大于目前已知的上界，則說(shuō)明該可行子路徑一定不會(huì)出現(xiàn)在最優(yōu)路徑中，此時(shí)可以停止這一條可行子路徑的擴(kuò)展。利用該策略可以有效縮小搜索空間，提高求解效率，縮短求解時(shí)間。

基于以上分析，本章將利用改進(jìn)的多維標(biāo)號(hào)算法(或改進(jìn)的Dijkstra算法)和脈沖算法設(shè)計(jì)求解無(wú)人機(jī)航跡規(guī)劃問(wèn)題的兩階段算法：

第一階段：利用改進(jìn)的多維標(biāo)號(hào)算法求一條從起點(diǎn)到終點(diǎn)的可行路徑(初始可行解)；

第二階段：利用脈沖算法求最優(yōu)路徑(全局最優(yōu)解)。

3.1 第一階段：利用改進(jìn)的多維標(biāo)號(hào)算法求初始可行解

為每個(gè)點(diǎn)i定義一個(gè)多維標(biāo)號(hào)，Lebali=[lengthi,horizoni,verticali,fatheri],其中4個(gè)分量分別表示無(wú)人機(jī)從起點(diǎn)到點(diǎn)i的可行路徑長(zhǎng)度、累積水平誤差、累積垂直誤差、點(diǎn)i的前續(xù)節(jié)點(diǎn)序號(hào)。

首先給每個(gè)節(jié)點(diǎn)標(biāo)注臨時(shí)標(biāo)號(hào)，然后從起點(diǎn)S開(kāi)始，依次檢查各個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào)，當(dāng)找到一條從起到當(dāng)前點(diǎn)的可行路徑時(shí)，將當(dāng)前點(diǎn)的臨時(shí)標(biāo)號(hào)修改為永久標(biāo)號(hào)，直到終點(diǎn)T得到永久標(biāo)號(hào)。

步驟1給起點(diǎn)S標(biāo)注臨時(shí)標(biāo)號(hào)[0,0,0,-1]，其余各點(diǎn)賦予臨時(shí)標(biāo)號(hào)[∞,0,0,-1]。

步驟2從所有臨時(shí)標(biāo)號(hào)點(diǎn)中尋找對(duì)應(yīng)路徑長(zhǎng)度最短的標(biāo)號(hào)點(diǎn)，記為Nodei，把該點(diǎn)的臨時(shí)標(biāo)號(hào)改為永久標(biāo)號(hào)，根據(jù)節(jié)點(diǎn)Nodei對(duì)應(yīng)的誤差校正類(lèi)型計(jì)算飛行器離開(kāi)節(jié)點(diǎn)i時(shí)的水平和垂直誤差；

(1)如果節(jié)點(diǎn)i為水平誤差校正點(diǎn)(i∈V1)，則

(2)如果節(jié)點(diǎn)i為垂直誤差校正點(diǎn)(i∈V2)，則

步驟3判斷與Nodei相鄰的每個(gè)節(jié)點(diǎn)Nodej的臨時(shí)標(biāo)號(hào)是否滿足下列更新條件，對(duì)滿足條件的節(jié)點(diǎn)更新臨時(shí)標(biāo)號(hào)：

(1)如果節(jié)點(diǎn)Nodej為水平誤差校正點(diǎn)(j∈V1)，且滿足

lengthi+dij

則更新節(jié)點(diǎn)Nodej的臨時(shí)標(biāo)號(hào)。

(2)如果節(jié)點(diǎn)Nodej為垂直誤差校正點(diǎn)(j∈V2)，且滿足

lengthi+dij

則更新節(jié)點(diǎn)Nodej的臨時(shí)標(biāo)號(hào)。

(3)如果節(jié)點(diǎn)Nodej為終點(diǎn)(j=T)，且滿足

lengthi+dij

則更新節(jié)點(diǎn)Nodej的臨時(shí)標(biāo)號(hào)。

更新以后節(jié)點(diǎn)Nodej的臨時(shí)標(biāo)號(hào)為：

lengthj←lengthi+dij,

fatherj←Nodei。

步驟4檢查終點(diǎn)T是否被賦予永久標(biāo)號(hào)，若是，則算法結(jié)束，按照終點(diǎn)T的永久標(biāo)號(hào)倒向追蹤找出完整的可行路徑。否則，返回步驟2。

顯然，根據(jù)以上算法找到的從起點(diǎn)到終點(diǎn)的路徑一定滿足模型的所有約束條件，因此是無(wú)人機(jī)航跡規(guī)劃問(wèn)題的可行解。由于無(wú)人機(jī)飛行過(guò)程中，水平方向和垂直方向均會(huì)產(chǎn)生累積誤差，而每個(gè)誤差校正點(diǎn)只能校正一個(gè)方向的累積誤差，為避免另一方向的累積誤差過(guò)大，導(dǎo)致路徑無(wú)法延伸至終點(diǎn)，算法中引入了比例系數(shù)λ，對(duì)非校正方向的累積誤差閾值進(jìn)行修正(λ可以取0.5～1之間的數(shù))，即當(dāng)無(wú)人機(jī)經(jīng)過(guò)水平誤差校正點(diǎn)時(shí)，其垂直誤差不能超過(guò)給定閾值的λ倍，當(dāng)無(wú)人機(jī)經(jīng)過(guò)垂直誤差校正點(diǎn)時(shí)，其水平方向的累積誤差不能超過(guò)誤差閾值的λ倍。這樣做可以避免改進(jìn)的多維標(biāo)號(hào)法求解過(guò)程中出現(xiàn)路徑走偏，無(wú)法到達(dá)終點(diǎn)的情況。

由于帶誤差校正點(diǎn)約束的無(wú)人機(jī)航跡規(guī)劃問(wèn)題不滿足最優(yōu)性條件，改進(jìn)的多維標(biāo)號(hào)算法結(jié)束時(shí)得到的可行解不一定是問(wèn)題全局最優(yōu)解。

3.2 第二階段：利用脈沖算法求出全局最優(yōu)解

將第一階段標(biāo)號(hào)算法得到的初始可行解作為當(dāng)前的最好解，其目標(biāo)函數(shù)值作為最優(yōu)目標(biāo)函數(shù)值的上界，借助于該上界，設(shè)計(jì)脈沖算法求出問(wèn)題的全局最優(yōu)解。

脈沖算法的基本思想是：通過(guò)深度優(yōu)先搜索遍歷所有可能的路徑，從中選出最短的一條，即為最優(yōu)路徑。本文采用3種判斷準(zhǔn)則識(shí)別不可能出現(xiàn)在最優(yōu)解中的子路徑，并提前進(jìn)行剪枝處理，從而減少計(jì)算量。

3種判斷準(zhǔn)則分別是可行性判斷、支配性判斷、界的判斷。下面分別舉例說(shuō)明在路徑擴(kuò)充過(guò)程中，如何使用3種準(zhǔn)則。

如圖3所示，已知S是起點(diǎn)，T是終點(diǎn)，r,g是任意兩個(gè)中間點(diǎn)(誤差校正點(diǎn))。假設(shè)S→r的可行子路徑已探明(即該子路徑有可能出現(xiàn)在最優(yōu)路徑中)，現(xiàn)在需要判斷子路徑S→r擴(kuò)展到g點(diǎn)形成的子路徑S→r→g是否滿足約束條件，以及是否可能出現(xiàn)在最優(yōu)路徑中。

(1)可行性判斷

根據(jù)問(wèn)題的約束條件來(lái)判斷點(diǎn)g能否加入到可行子路徑中。若無(wú)人機(jī)從點(diǎn)r到點(diǎn)g時(shí)產(chǎn)生的累計(jì)誤差超出了點(diǎn)g要求的累積誤差范圍，則點(diǎn)g無(wú)法加入到子路徑中，即子路徑S→r→g不滿足約束條件，因此子路徑S→r→g不可能出現(xiàn)在最優(yōu)路徑中，可以直接在搜索樹(shù)中對(duì)其進(jìn)行剪枝。從深度優(yōu)先搜索的角度來(lái)講，這一部分子樹(shù)無(wú)需再繼續(xù)向后搜索。

可行性判斷的算法流程如Functionfeasible_check：

Function feasible_check

input：當(dāng)前已探明子路徑path，下一個(gè)擬加入路徑的點(diǎn)node

if：加入node后的水平誤差和垂直誤差都不超過(guò)給定的閾值

then：return False

else：return True

End if

其中，F(xiàn)alse表示加入新點(diǎn)之后形成的子路徑滿足可行性約束，True表示不滿足可行性約束。

(2)支配性判斷

支配性準(zhǔn)則用于判斷某個(gè)中間點(diǎn)對(duì)應(yīng)的兩個(gè)不同標(biāo)號(hào)的優(yōu)劣(即從起點(diǎn)到中間點(diǎn)的兩條可行路徑的優(yōu)劣)。由于使用多維標(biāo)號(hào)，每個(gè)標(biāo)號(hào)中同時(shí)包含距離、水平誤差、垂直誤差等信息。如果標(biāo)號(hào)A對(duì)應(yīng)的三個(gè)指標(biāo)均小于標(biāo)號(hào)B的同類(lèi)指標(biāo)，則標(biāo)號(hào)A嚴(yán)格優(yōu)于標(biāo)號(hào)B。此時(shí)標(biāo)號(hào)B對(duì)應(yīng)的子路徑不可能出現(xiàn)在最優(yōu)子路徑中，因此標(biāo)號(hào)B可以舍去。

支配性判斷的算法流程如Functiondominate_check：

Function dominate_check

input：當(dāng)前已探明子路徑path，下一個(gè)擬加入路徑的點(diǎn)node

計(jì)算在path后面接入node之后的路徑長(zhǎng)度，記為length_new；

計(jì)算在path后面接入node之后的累積水平誤差，記為horizon_new；

計(jì)算在path后面接入node之后的累積垂直誤差，記為vertical_new；

if：node本身的length標(biāo)號(hào)不大于length_new，并且node本身的horizon標(biāo)號(hào)不大于horizon_new，并且node本身的vertical標(biāo)號(hào)不大于vertical_new

then：return True

else：return False

End if

其中True表示加入node點(diǎn)形成的可行路徑不如node點(diǎn)原標(biāo)號(hào)對(duì)應(yīng)的可行路徑，即該子路徑不可能出現(xiàn)在最優(yōu)路徑中。

(3)界的判斷

界的判斷用于識(shí)別那些不可能出現(xiàn)在最優(yōu)解中的可行子路徑，以便提前剪枝。

如圖3所示，假設(shè)點(diǎn)g加入路徑S→r之后形成可行子路徑S→r→g，要判斷該子路徑有沒(méi)有可能出現(xiàn)在最優(yōu)路徑中，只需要計(jì)算包含S→r→g的完整路徑長(zhǎng)度的下界，并與當(dāng)前最好可行解的目標(biāo)函數(shù)值(最優(yōu)值的上界)進(jìn)行對(duì)比，即可得出結(jié)論。若包含S→r→g的完整路徑長(zhǎng)度下界大于當(dāng)前可行解的目標(biāo)函數(shù)值，則可行子路徑S→r→g不可能擴(kuò)展成最優(yōu)路徑，因此可以直接舍去(剪枝)。

本文采用直觀方式計(jì)算包含S→r→g的完整路徑長(zhǎng)度下界。該下界等于S→r→g的長(zhǎng)度加上g→T的直線距離。由于g→T的完整可行路徑必須滿足各種約束條件，任意一條g→T的可行路徑長(zhǎng)度都不可能小于g→T的最短距離。

界的判斷算法流程如Functionbound_check：

Function bound_check

input：當(dāng)前已探明子路徑path，下一個(gè)擬加入路徑的點(diǎn)node，點(diǎn)node到終點(diǎn)T的無(wú)約束最短路長(zhǎng)度Dnode，當(dāng)前最好解對(duì)應(yīng)的路徑長(zhǎng)度primal_bound

if：path的長(zhǎng)度+Dnode≥primal_bound

then：return True

else：return False

End if

其中True表示加入node點(diǎn)之后的子路徑不可能出現(xiàn)在最優(yōu)路徑中。

采用上述3種準(zhǔn)則，可以識(shí)別出不可行子路徑和不可能出現(xiàn)在最優(yōu)解中的子路徑，以便提前剪枝，從而縮小搜索空間，降低計(jì)算量。

基于以上3種準(zhǔn)則設(shè)計(jì)的脈沖算法，本質(zhì)上可以遍歷所有可行路徑，因此當(dāng)算法停止時(shí)，得到的必然是全局最優(yōu)解。

脈沖算法的主程序如Functionpulse：

Function pulse

input：當(dāng)前已探明的子路徑path(每一條子路徑對(duì)應(yīng)一個(gè)永久標(biāo)號(hào))，下一個(gè)擬加入路徑的點(diǎn)的集合NodetoAdd(所有臨時(shí)標(biāo)號(hào)的集合)

fornode in NodetoAdd

if：feasible_check(path,node)==False或dominate_check(path,node)==False或bound_check(path,node)==False

then：path′={path,node}，給node標(biāo)注一個(gè)永久標(biāo)號(hào)；

更新NodetoAdd為node的后繼節(jié)點(diǎn)集合，記為NodetoAdd′；

執(zhí)行pulse(path′,NodetoAdd′)；

End if

End for

4 模擬計(jì)算與結(jié)果分析

為了驗(yàn)證模型的正確性和算法的有效性，本章在[0,100 000]×[0,100 000]×[0,100 000]范圍內(nèi)隨機(jī)生成12個(gè)不同規(guī)模的算例進(jìn)行模擬計(jì)算，各個(gè)算例的參數(shù)如表1所示。其中第1列為算例編號(hào)，第2列為飛行區(qū)域內(nèi)設(shè)置的總點(diǎn)數(shù)(包括起點(diǎn)、終點(diǎn)和兩類(lèi)誤差校正點(diǎn))，第3、4列分別為水平誤差校正點(diǎn)和垂直誤差校正點(diǎn)的個(gè)數(shù)，第5～10列為模型中的各個(gè)參數(shù)的取值。

表1 算例參數(shù)

表1中算例1～6是小規(guī)模算例，主要用于驗(yàn)證模型的正確性。對(duì)每一個(gè)小規(guī)模算例，通過(guò)直接求解混合整數(shù)規(guī)劃模型得到問(wèn)題的精確最優(yōu)解，并使用兩階段算法求解，對(duì)比兩種方法的求解結(jié)果，驗(yàn)證模型的正確性，同時(shí)分析兩階段算法的求解時(shí)間優(yōu)勢(shì)。

算例7～12是較大規(guī)模算例，用于驗(yàn)證兩階段算法的快速有效性。6個(gè)較大規(guī)模算例可以分為兩組，其中算例7～9使用一組相同的節(jié)點(diǎn)坐標(biāo)，誤差校正參數(shù)分別設(shè)置為較緊、適中、較松3種；算例10～12使用另一組相同的節(jié)點(diǎn)坐標(biāo)，誤差校正參數(shù)分別設(shè)置為較緊、適中、較松3種。對(duì)于每個(gè)大規(guī)模算例，分別使用兩階段算法與文獻(xiàn)中常用的方法如脈沖算法、動(dòng)態(tài)規(guī)劃方法[37]進(jìn)行求解，通過(guò)對(duì)比分析，展示兩階段算法的求解速度優(yōu)勢(shì)。

本章所有模擬計(jì)算均在一臺(tái)Intel Core i7-6700HQ 2.6 GHz的PC上進(jìn)行，為了驗(yàn)證模型正確性，直接使用Gurobi 8.0編寫(xiě)程序求解混合整數(shù)規(guī)劃模型；對(duì)于兩階段算法和動(dòng)態(tài)規(guī)劃算法則使用Python 3.6.8編程實(shí)現(xiàn)。

表2列出了分別利用兩種方法求解小規(guī)模算例的結(jié)果。其中第2、3列為利用Gurobi求解整數(shù)規(guī)劃模型的運(yùn)算時(shí)間和得到的最優(yōu)值，第4、5列為利用兩階段算法求解的運(yùn)算時(shí)間和得到的目標(biāo)函數(shù)值，最后一列分析了兩階段方法是否找到問(wèn)題的最優(yōu)解。通過(guò)表2可以看出，對(duì)于每一個(gè)小規(guī)模算例，利用Gurobi求解混合整數(shù)規(guī)劃模型均可得到最優(yōu)解，因此本文建立的混合整數(shù)規(guī)劃模型是正確的；利用兩階段算法求解得到的結(jié)果與求解整數(shù)規(guī)劃模得到的最優(yōu)解完全相同，這說(shuō)明本文設(shè)計(jì)的兩階段算法在各個(gè)算例上均找到了精確最優(yōu)解。通過(guò)對(duì)比兩種方法的求解時(shí)間可以發(fā)現(xiàn)，對(duì)于每個(gè)算例，兩階段算法的求解時(shí)間均不超過(guò)0.1 s，而Gurobi求解整數(shù)規(guī)劃模型的運(yùn)算時(shí)間均超過(guò)了兩階段算法的運(yùn)算時(shí)間。隨著問(wèn)題規(guī)模的增大，兩階段算法的求解速度優(yōu)勢(shì)越來(lái)越明顯。對(duì)于包含38個(gè)點(diǎn)的算例6，利用Gurobi求解整數(shù)規(guī)劃模型的運(yùn)算時(shí)間為439.59 s，而兩階段算法的運(yùn)行時(shí)間只有0.084 s。

表2 小規(guī)模算例的模擬計(jì)算結(jié)果

續(xù)表2

對(duì)于包含327個(gè)點(diǎn)的中等規(guī)模算例7，利用Gurobi求解混合整數(shù)規(guī)劃模型的運(yùn)算時(shí)間已經(jīng)超過(guò)2小時(shí)，因此中等規(guī)模以上的算例無(wú)法直接利用Gurobi求解混合整數(shù)規(guī)劃模型得到最優(yōu)解。對(duì)于中大規(guī)模的帶約束最短路徑問(wèn)題，文獻(xiàn)中常用的精確算法有脈沖算法和動(dòng)態(tài)規(guī)劃算法。由于本文研究的帶誤差校正點(diǎn)約束的最短路問(wèn)題與文獻(xiàn)中考慮的約束條件不同，本章結(jié)合誤差校正點(diǎn)約束條件的特點(diǎn)，基于求解一般約束最短路問(wèn)題的動(dòng)態(tài)規(guī)劃算法[37]設(shè)計(jì)了求解無(wú)人機(jī)航跡規(guī)劃問(wèn)題的動(dòng)態(tài)規(guī)劃算法，算法的偽代碼如DP Algorithm所示。

DP Algorithm

Γs←{([0,…,s],0,0,0,0)}

for all i∈V(〗s} do

Γi←?

end for

E←{s}

repeat

Select i∈E

lj←Extend(li,j)

Γj←EFF(Γj,lj)

E←E∪{j}

end if

end for

end for

E←E(〗i}

until E=?

為了分析本文設(shè)計(jì)的兩階段算法求解效果，并與文獻(xiàn)中使用的脈沖算法和動(dòng)態(tài)規(guī)劃算法進(jìn)行對(duì)比。對(duì)于表1中的中、大規(guī)模算例，分別使用兩階段算法、脈沖算法和動(dòng)態(tài)規(guī)劃算法進(jìn)行求解，記錄各種算法的求解結(jié)果和運(yùn)算時(shí)間。結(jié)果顯示，3種算法均可以得到精確最優(yōu)解，但3種算法的運(yùn)算時(shí)間有顯著差異，表3列出了3種算法求解各個(gè)算例的運(yùn)算時(shí)間,其中包括兩階段算法第一階段的運(yùn)算時(shí)間(T1)、第二階段運(yùn)算時(shí)間(T2)的和總運(yùn)算時(shí)間(T)。

表3 利用3種算法求解中、大規(guī)模算例的運(yùn)算時(shí)間

從表3可以看出，對(duì)于每個(gè)算例，兩階段算法的運(yùn)算時(shí)間均遠(yuǎn)遠(yuǎn)小于脈沖算法和動(dòng)態(tài)規(guī)劃算法。3種算法的求解效率由高到低排列順序?yàn)椋簝呻A段算法>脈沖算法>動(dòng)態(tài)規(guī)劃。需要特別說(shuō)明的是，不論是兩階段算法還是脈沖算法，本質(zhì)上都使用了動(dòng)態(tài)規(guī)劃的思想，可以看成是動(dòng)態(tài)規(guī)劃算法和分支定界算法的結(jié)合。由于兩階段算法第一階段找到的可行解具有更小的上界，因此使用兩階段算法比直接使用脈沖算法求解效率更高。從表3中還可以看出，對(duì)于點(diǎn)坐標(biāo)完全相同的算例，誤差約束越緊求解時(shí)間越短，誤差約束越松求解時(shí)間越長(zhǎng)，這一點(diǎn)從兩組算例7～9和10～12的組內(nèi)對(duì)比可以看出。如算例7～9使用的點(diǎn)坐標(biāo)一樣，隨著誤差約束的逐步放松，求解時(shí)長(zhǎng)逐步增大。這是因?yàn)楫?dāng)放松誤差約束時(shí)，可行解個(gè)數(shù)增多，兩階段算法第二階段的搜索空間變大，因此需要的搜索時(shí)間變長(zhǎng)。

通過(guò)模擬計(jì)算還發(fā)現(xiàn)，對(duì)于誤差約束較緊的算例，第一階段多維標(biāo)號(hào)算法中的比例系數(shù)λ取0.5～1之間的任意值均可以得到可行解；當(dāng)誤差約束放松時(shí)，第一階段多維標(biāo)號(hào)算法中的比例系數(shù)λ的取值應(yīng)該適當(dāng)減小。如表1中的算例9和算例12，當(dāng)λ取1時(shí)，第一階段多維標(biāo)號(hào)算法沒(méi)有找到可行解；當(dāng)λ取0.5時(shí)，所有算例均可以找到可行解。實(shí)際計(jì)算時(shí)，為了保證第一階段找到可行解，可以直接取λ=0.5。

通過(guò)觀察兩階段算法第一階段和第二階段的運(yùn)行時(shí)間可以發(fā)現(xiàn)，對(duì)所有的算例，第一階段找初始可行解的運(yùn)算時(shí)間均不超過(guò)2 s；基于第一階段初始可行解提供的上界，算法第二階段的求解時(shí)間均不超過(guò)2 s。且總求解時(shí)間均小于4.2 s。

由以上分析可以看出，兩階段算法在求解帶誤差校正點(diǎn)約束的無(wú)人機(jī)航跡規(guī)劃問(wèn)題上表現(xiàn)出非常優(yōu)越的性能，隨著問(wèn)題規(guī)模的增大，其求解速度的優(yōu)勢(shì)越來(lái)越明顯。因此，兩階段算法可以作為無(wú)人機(jī)實(shí)時(shí)路徑規(guī)劃系統(tǒng)的核心算法。

6 結(jié)束語(yǔ)

無(wú)人機(jī)航跡規(guī)劃問(wèn)題是導(dǎo)航系統(tǒng)設(shè)計(jì)中的關(guān)鍵問(wèn)題，本文針對(duì)同時(shí)考慮水平誤差和垂直誤差校正的無(wú)人機(jī)航跡規(guī)劃問(wèn)題開(kāi)展研究，將該問(wèn)題轉(zhuǎn)化為帶誤差校正點(diǎn)約束的最短路徑問(wèn)題，建立了混合整數(shù)規(guī)劃模型，并設(shè)計(jì)了求解模型的兩階段算法。第一階段利用改進(jìn)的多維標(biāo)號(hào)法求得問(wèn)題的初始可行解，并將初始可行解的目標(biāo)函數(shù)值作為最優(yōu)值的上界；第二階段，利用第一階段得到的目標(biāo)函數(shù)值上界，基于3種準(zhǔn)則設(shè)計(jì)改進(jìn)的脈沖算法，求得問(wèn)題的全局最優(yōu)解。最后，分別利用小規(guī)模和大規(guī)模算例，驗(yàn)證了整數(shù)規(guī)劃模型的正確性和兩階段算法的快速有效性。

本文的主要貢獻(xiàn)包括：

(1)將考慮誤差校正點(diǎn)的無(wú)人機(jī)航跡規(guī)劃問(wèn)題轉(zhuǎn)化為帶誤差校正約束的最短路徑問(wèn)題，建立了混合整數(shù)規(guī)劃模型，擴(kuò)展了帶約束最短路徑問(wèn)題的應(yīng)用范圍。

(2)在分析了問(wèn)題困難性的基礎(chǔ)上，將改進(jìn)多維標(biāo)號(hào)法與改進(jìn)的脈沖算法相結(jié)合設(shè)計(jì)了求解模型的兩階段精確算法。一方面，利用脈沖算法通過(guò)深度優(yōu)先搜索潛在遍歷了所有可行解，保證最終求得全局最優(yōu)解；另一方面，利用改進(jìn)多維標(biāo)號(hào)算法得到的高質(zhì)量初始可行解作為最優(yōu)值的上界，大大縮小了脈沖算法的搜索空間，提高了求解效率。

本文設(shè)計(jì)的兩階段算法，比單獨(dú)使用動(dòng)態(tài)規(guī)劃或脈沖算法求最優(yōu)解的速度更快，綜合性能具有明顯優(yōu)勢(shì)。該算法思想可以推廣到其他類(lèi)型的帶約束最短路徑問(wèn)題中，具有良好的擴(kuò)展性。

本文研究無(wú)人機(jī)航跡規(guī)劃問(wèn)題時(shí)，假設(shè)無(wú)人機(jī)到達(dá)某個(gè)誤差校正點(diǎn)后，其相應(yīng)方向的誤差均可以得到成功校正，沒(méi)有考慮誤差校正失敗的情況。實(shí)際中，由于信號(hào)傳輸中斷或GPS系統(tǒng)的誤差等原因，可能導(dǎo)致在某些校正點(diǎn)誤差校正失敗的情況。后續(xù)研究中，筆者將針對(duì)可能存在誤差校正失敗的情況，研究無(wú)人機(jī)航跡規(guī)劃問(wèn)題，建立數(shù)學(xué)模型并設(shè)計(jì)求解模型的算法，為實(shí)際中無(wú)人機(jī)等飛行器的導(dǎo)航系統(tǒng)設(shè)計(jì)提供理論依據(jù)和算法支持。