[發明專利]一種帶通行限制的國際航線航路規劃方法

在審

• 申請號: 202210697154.5
• 申請日: 2022-06-20
• 公開（公告）號: CN115204466A
• 公開（公告）日: 2022-10-18
• 發明（設計）人: 陳創希;伍翔;許南;常先英;吳東岳;張苗苗;曾力舜;謝靜娜;羅德貴;蔣祿妹;柳亞昆;瞿也豐;李翰林;高嘉許
• 申請（專利權）人: 中國南方航空股份有限公司
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q50/30;G06F16/29
• 代理公司: 廣州知友專利商標代理有限公司 44104
• 代理人: 李海波;高修華

1.一種帶通行限制的國際航線航路規劃方法，其特征在于，包括以下步驟：

1)加載全網航路數據，生成航線網絡圖；

2)根據設定的起飛機場和降落機場對航線網絡圖進行裁剪，并對航線網絡圖進行壓縮，得到用于優化的有向圖G＝{V,E}，其中V為有向圖G中所有節點的集合，E為有向圖G中所有航路邊的集合；

3)用Dijkstra算法，計算不帶限制的情況下起點到所有節點的最短距離并建立一個最短路徑字典MINDict_D，計算不帶限制的情況下所有節點到終點的最短距離并建立一個最短路徑字典MINDict_A，用于估算航路邊的權重及用于后續A*算法估算當前點到終點的預估距離；

4)根據設定的優化目標及包括風溫、風速及航向角的數據，計算每一條航路邊各高度層的邊權重；

5)選擇每條航路邊所有高度層的邊權重的平均值作為該航路邊的預估權重；

6)利用所述A*算法確定滿足航路限制的水平航路；

7)根據得到的水平航路確定垂直航路；

8)輸出優化結果；

將航路限制規則分類為：(1)Not available-不可經過；(2)Compulsory-必須經過，

所述A^*算法的估值函數為：

f(n)＝g(n)+h(n)；其中f(n)是每個可能節點的成本估值，它由兩部分組成，其中g(n)為起點到當前節點的實際成本，h(n)為當前節點到終點的成本估值，以MINDict_A中預先計算的不帶限制的情況下每個航路節點到目的機場的最短距離作為h(n)，每個節點保留多條擴展路徑，并在有航路相關限制時調整h(n)為過所有必經節點的最短路徑。

2.根據權利要求1所述的帶通行限制的國際航線航路規劃方法，其特征在于：所述步驟6)中，所述滿足航路限制的水平航路的確定過程如下：

(1)建立一個open list，一個close list,均初始化為空，將所有節點狀態初始化為open；

(2)初始化兩個規則集合R_na和R_cmp，R_na為優化范圍內涉及的第(1)類Not available類型規則，R_cmp為優化范圍內涉及的第(2)類Compulsory類型規則；

(3)將起點S加入到openlist，用一個五維標簽表示節點{pre-node，cost，weight，time，C_n}，分別代表前序節點、成本估值、飛機經過該點后的重量，時間及必經節點集合，其中pre-node、C_n初始化為空，cost初始化為MINDict_A中對應的不帶限制的最短距離，weight初始化為飛機起飛重量，時間初始化為航班起飛時間，若open list為空，或者已經找到K條起點至終點的最短路徑，則程序終止；

(4)若openlist不為空，則從openlist中找到成本最小，即f(n)值最小的節點n進行路徑擴展；

(5)將節點n從open list中刪除，若close list中節點n的狀態為close，則跳過該節點，選取下一個節點，否則，對相應路徑進行規則檢查，若不違反規則，則將該節點的路徑加入closelist，若放入節點n后，closelist中其個數達到K個，則將該節點狀態修改為close，若節點n為終點，則找到一條從起點到終點的路徑；

(6)遍歷節點n有出邊的節點m，若m不為close則計算其成本f(m)，由于到達每條邊起點的飛機重量對該邊的油耗、成本和時間影響較大，擴展邊時根據到達該邊時飛機的實際重量重新從起點正向計算待擴展邊的權重，更新MINDict_D并記錄經過該邊后飛機的重量，對于當前擴展節點，檢查是否觸發R_cmp中的條件，若是，檢查必經節點集合中是否已有限制所規定的必經節點，如有，則忽略，否則更新必經集合C_m，若必經集合C_m為空，h(m)＝當前節點到目標點的不帶限制的最短路距離，否則h(m)為當前點經過必經點至終點的最短路徑，即當前節點到必經集合中起點的不帶限制的最短路距離+必經集合中點與點之間的不帶限制的最短路距離+必經集合結束點與目標點的不帶限制的最短路距離，更新當前擴展節點的成本f(m)并將其加入openlist；

每條航路邊的權重由反向根據到終點的不帶限制的最短路徑的估算權重和正向根據由起點到該點的帶限制的最短路徑共同確定，因此稱為雙向動態估算權重；

(7)重復步驟(4)至步驟(6)，直至獲得目標點的最短路徑或者openlist為空。