基于改進Dijkstra算法的運輸機航線生成

戴 英，穆 凱

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

基于改進Dijkstra算法的運輸機航線生成

戴 英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è)計中引入了改進的Dijkstra算法，以保證快速生成的航線能符合運輸機飛行性能和交通管制的要求。實踐證明，通過使用改進后的Dijkstra算法建立數(shù)學(xué)模型，本質(zhì)上是對所有的航段進行過濾，使最后生成的航線滿足需求。

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

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

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

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

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

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

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

3 改進的Dijkstra算法

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

圖1 Dijkstra算法演示圖

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

以下是使用Java實現(xià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é)點成為一個永久性節(jié)點

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++;

}

//當終點為永久節(jié)點時停止運算，得出最短路徑

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算法進行修正，使之符合航線生成的要求。通過最短路徑算法，建立了飛行航線模型，可以解決航線自動生成的問題，替代人工操作，提高航線生成的效率。

[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ò)動態(tài)選路中的應(yīng)用[J]．株洲師范高等?？茖W(xué)校校報,2004,9(5):36-38

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

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

[8] 吳華麗,吳進華,王玲玲,等．幾種最短路徑算法的比較[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。