基于改進(jìn)Dijkstra算法的運(yùn)輸機(jī)航線生成

戴 英，穆 凱

（1.新疆維吾爾自治區(qū)第二測繪院，新疆 烏魯木齊830001；2.新疆農(nóng)業(yè)大學(xué) 草業(yè)與環(huán)境科學(xué)學(xué)院，新疆 烏魯木齊830001；3.中亞地理信息開發(fā)利用國家測繪地理信息局工程技術(shù)研究中心，新疆 烏魯木齊830002；4.新疆維吾爾自治區(qū)測繪科學(xué)研究院，新疆 烏魯木齊830002）

基于改進(jìn)Dijkstra算法的運(yùn)輸機(jī)航線生成

戴 英1,2，穆 凱1,3,4

（1.新疆維吾爾自治區(qū)第二測繪院，新疆 烏魯木齊830001；2.新疆農(nóng)業(yè)大學(xué) 草業(yè)與環(huán)境科學(xué)學(xué)院，新疆 烏魯木齊830001；3.中亞地理信息開發(fā)利用國家測繪地理信息局工程技術(shù)研究中心，新疆 烏魯木齊830002；4.新疆維吾爾自治區(qū)測繪科學(xué)研究院，新疆 烏魯木齊830002）

比較幾種常見的航線算法，在航線設(shè)計(jì)中引入了改進(jìn)的Dijkstra算法，以保證快速生成的航線能符合運(yùn)輸機(jī)飛行性能和交通管制的要求。實(shí)踐證明，通過使用改進(jìn)后的Dijkstra算法建立數(shù)學(xué)模型，本質(zhì)上是對所有的航段進(jìn)行過濾，使最后生成的航線滿足需求。

運(yùn)輸機(jī)；航線生成；Dijkstra算法；航線規(guī)則

1 現(xiàn)階段航線生成方法及主要解決辦法

在航線生成方面，當(dāng)前的領(lǐng)航業(yè)務(wù)基本由手工制作。工作人員必須依據(jù)正確的情況先進(jìn)行人工判斷，然后根據(jù)自身的經(jīng)驗(yàn)來選擇正確的飛行航線。這種決策方式必須先通過實(shí)踐經(jīng)驗(yàn)豐富的工作人員找出大量的領(lǐng)航數(shù)據(jù)進(jìn)行計(jì)算，易受工作人員自身經(jīng)驗(yàn)、知識(shí)和思維模式的限制，在需要指揮部門下達(dá)緊急任務(wù)時(shí)很難及時(shí)作出正確的反應(yīng)，致使效率低下[1]。

對運(yùn)輸機(jī)來說，整條航線的飛行或者是中途降落、加油，然后繼續(xù)飛行所要生成的最優(yōu)航線，都要做好計(jì)劃。航線的選擇有許多限制因素，其中包括飛機(jī)路線的最短選擇、航段回旋角的角度限制等因素[2-4]。在充分考慮影響因素的前提下，采用改進(jìn)后的Dijkstra算法與人工干預(yù)相結(jié)合，用以快速獲取合理的飛行航線，避免了人為干預(yù)過程中的誤差，保證了航線設(shè)計(jì)的正確性及合理性[5-8]。

2 傳統(tǒng)的Dijkstra算法

Dijkstra算法是計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)最短路徑的算法，是以一個(gè)起點(diǎn)為中心向其他節(jié)點(diǎn)范圍擴(kuò)散，基本原理是每擴(kuò)展一個(gè)新距離就會(huì)出現(xiàn)一個(gè)最短距離的點(diǎn)，同時(shí)更新它周邊的那些點(diǎn)的距離。這就是Dijkstra 算法中最具代表性的最短路徑路算法，這種算法是基于Dijkstra算法實(shí)現(xiàn)最短距離為出發(fā)點(diǎn)的。

Dijkstra算法中參與計(jì)算的節(jié)點(diǎn)，包括永久性、未標(biāo)記和臨時(shí)標(biāo)記的節(jié)點(diǎn)，對這些節(jié)點(diǎn)進(jìn)行初始化，先設(shè)定好自動(dòng)搜索，再進(jìn)行循環(huán)計(jì)算，最終得出永久節(jié)點(diǎn)標(biāo)記。在臨時(shí)標(biāo)記節(jié)點(diǎn)中，離開始節(jié)點(diǎn)的路徑長度最短的節(jié)點(diǎn)應(yīng)標(biāo)記為永久標(biāo)記節(jié)點(diǎn)，再不斷循環(huán)，找到設(shè)定的目標(biāo)節(jié)點(diǎn)或所有節(jié)點(diǎn)都成為永久標(biāo)記節(jié)點(diǎn)，最終結(jié)束算法。

3 改進(jìn)的Dijkstra算法

在求解最短路徑時(shí)，傳統(tǒng)的Dijkstra算法會(huì)產(chǎn)生負(fù)權(quán)邊，循環(huán)加入新的節(jié)點(diǎn)進(jìn)行計(jì)算時(shí)，延伸到負(fù)權(quán)邊會(huì)有更短的距離產(chǎn)生，導(dǎo)致新參與計(jì)算的點(diǎn)距離不會(huì)改變。由于Dijkstra算法過程有大量的節(jié)點(diǎn)參與計(jì)算，雖然最終可以得出最短路徑，但效率低下。Dijkstra算法如圖1所示，各對應(yīng)路徑的距離如表1所示。

圖1 Dijkstra算法演示圖

若起點(diǎn)A至終點(diǎn)G之間的最短距離為70，最短路徑則是ABFCDG。首先從A點(diǎn)開始對區(qū)域內(nèi)各點(diǎn)進(jìn)行距離比較，得出A到B點(diǎn)的距離最近，把B點(diǎn)作為臨時(shí)標(biāo)記節(jié)點(diǎn)，與A沒有發(fā)生距離關(guān)系的C、E、F、H點(diǎn)作為未標(biāo)記節(jié)點(diǎn)，A點(diǎn)本身作為永久標(biāo)記節(jié)點(diǎn)。其次由臨時(shí)標(biāo)記節(jié)點(diǎn)B開始對區(qū)域內(nèi)除A外的各點(diǎn)作比較得出B到F的距離最近，那么F點(diǎn)就是臨時(shí)標(biāo)記節(jié)點(diǎn)，不能和B發(fā)生距離關(guān)系的C、E、H就是為未標(biāo)記節(jié)點(diǎn)。把B改為永久標(biāo)記節(jié)點(diǎn)，由臨時(shí)節(jié)點(diǎn)F開始對區(qū)域內(nèi)除A、B外的單個(gè)點(diǎn)作距離比較，若C點(diǎn)是距離F最近的點(diǎn)，將其設(shè)成臨時(shí)標(biāo)記節(jié)點(diǎn)，沒有和F點(diǎn)發(fā)生距離關(guān)系的點(diǎn)E、H設(shè)為未標(biāo)記節(jié)點(diǎn)。同理，再對各點(diǎn)進(jìn)行比較，同時(shí)對臨時(shí)標(biāo)記節(jié)點(diǎn)、未標(biāo)記節(jié)點(diǎn)及永久標(biāo)記節(jié)點(diǎn)進(jìn)行轉(zhuǎn)換，直到終點(diǎn)G點(diǎn)成為臨時(shí)標(biāo)記節(jié)點(diǎn)時(shí)算出最短距離為70，最短路徑是ABFCDG。

以下是使用Java實(shí)現(xiàn)的改進(jìn)Dijkstra算法的核心代碼：

表1 對應(yīng)路徑的距離

public int[] getShortestPath(int id1, int id2){

Set neighbor[] = new Set[map_data.nodes.length];

Set connected = new TreeSet();

Set solved = new TreeSet();

//初始化讓最短邊的節(jié)點(diǎn)成為一個(gè)永久性節(jié)點(diǎn)

double[] distance = new double[map_data.nodes. length];

int[] prev = new int[map_data.nodes.length];

for (int i = 0; i ＜ map_data.nodes.length; i++){

prev[i] = id1;

distance[i] = Double.POSITIVE_INFINITY;

neighbor[i] = new TreeSet();

}//對每一條邊作比較

for (int i = 0; i ＜ map_data.edges.length; i++){

int ida = map_data.edges[i].id1;

int idb = map_data.edges[i].id2;

neighbor[ida].add(new Integer(idb));

neighbor[idb].add(new Integer(ida));

if (ida == id1 && idb != id1){

connected.add(new Integer(idb));

distance[idb] = getLength(ida, idb);

}

else if (idb == id1 && ida != id1){

connected.add(new Integer(ida));

distance[ida] = getLength(ida, idb);

}

}

solved.add(new Integer(id1));

distance[id1] = 0;

for (Integer id2_obj = new Integer(id2); !solved. contains(id2_obj); ){

Integer sel = null;

for (Iterator i = connected.iterator(); i.hasNext(); ){

Integer val = (Integer)i.next();

if (sel == null || distance[val.intValue()] ＜ distance[sel. intValue()]){

sel = val;

}

}

solved.add(sel);

connected.remove(sel);

for (Iterator i = neighbor[sel.intValue()].iterator(); i.hasNext(); ){

Integer val = (Integer)i.next();

if (!solved.contains(val)){

connected.add(val);

double dtmp = distance[sel.intValue()]

+ getLength(sel.intValue(), val.intValue());

if (dtmp ＜ distance[val.intValue()]){

distance[val.intValue()] = dtmp;

prev[val.intValue()] = sel.intValue();

}

}

}

}

int size = 1;

for (int i = id2; i != id1; i = prev[i]){

size++;

}

//當(dāng)終點(diǎn)為永久節(jié)點(diǎn)時(shí)停止運(yùn)算，得出最短路徑

int[] answer = new int[size];

for (int i = id2; i != id1; i = prev[i]){

size--;

answer[size] = i;

}

answer[0] = id1;

return answer;

}

}

4 結(jié) 語

以經(jīng)典的Dijkstra算法解決復(fù)雜的航線生成問題，并根據(jù)具體限制條件對Dijkstra算法進(jìn)行修正，使之符合航線生成的要求。通過最短路徑算法，建立了飛行航線模型，可以解決航線自動(dòng)生成的問題，替代人工操作，提高航線生成的效率。

[1] 田方．中國民航國內(nèi)航空資料匯編適應(yīng)新形勢需要[J]．空中交通管理，2006(12):19-21

[2] Baldwin J F,Guild M C．Comparison of Fuzzy Sets on the Same Decision Space [J]．Fuzzy Sets and Systems,1979,2(2):213-231

[3] Adamo J M．Fuzzy Decision Trees [J]．Fuzzy Sets and Systems，1980,4(3):207-220

[4] Baas S M，Kwakernaak H．Rating and Ranking of Multiple Aspect Alternative Using FuzzySets[J]．Automatica,1977,13(1):47-58

[5] 陳皓．遺傳算法在網(wǎng)絡(luò)動(dòng)態(tài)選路中的應(yīng)用[J]．株洲師范高等?？茖W(xué)校校報(bào),2004,9(5):36-38

[6] 何迪,嚴(yán)余送,郭守儆,等．基于矩陣分析的公共交通網(wǎng)絡(luò)最優(yōu)路徑算法[J]．西南交通大學(xué)學(xué)報(bào),2007,42(7):315-319

[7] 陳江,扈志峰．Dijkstra最短路徑算法實(shí)現(xiàn)[J]．科技經(jīng)濟(jì)市場, 2011(9):10-11

[8] 吳華麗,吳進(jìn)華,王玲玲,等．幾種最短路徑算法的比較[J]．計(jì)算機(jī)科學(xué), 2010,37(7):196-197

P208

B

672-4623（2016）02-0034-02

10.3969/j.issn.1672-4623.2016.02.012

戴英，主要從事測繪生產(chǎn)內(nèi)業(yè)工作。

2014-05-29。