航空路線圖分析與最佳化策略

– 10 分鐘閱讀

運用 TigerGraph 的圖資料科學函式庫分析航空路線，可以深入瞭解機場間的連通性和重要性。首先，利用經緯度和 Haversine 公式計算航線實際距離，再使用接近中心性和介於中心性兩種演算法找出樞紐機場，例如法蘭克福、巴黎戴高樂等高接近中心性機場，以及扮演中轉角色的機場，如巴拿馬運河。接著，利用最短路徑演算法，計算出轉機次數最少或飛行里程最短的航線，並透過修改 GSQL 演算法，加入城市名稱和限制路徑長度，使結果更易讀。最後，使用強連通分量演算法進行社群檢測，識別出航線密集區域，並修改演算法，過濾掉過小或過大的社群，以便分析。

航空路線分析：中央性演算法與社群檢測的應用

在現代航空運輸網路中，理解機場之間的連線性和重要性對於營運商、旅客以及相關決策者至關重要。本章節將探討如何利用圖資料科學（Graph Data Science, GDS）函式庫中的中央性演算法（Centrality Algorithms）和社群檢測演算法（Community Detection Algorithms）來分析全球航空路線網路。

路線長度計算

在進行深入分析之前，首先需要計算各個航線的長度。TigerGraph 提供了一個名為 calculate_route_length 的查詢，用於計算每個航線的里程。該查詢利用機場的經緯度坐標，透過 haversine 公式計算出考慮地球曲率的弧長，並將結果儲存在每個航線的 miles 屬性中。

RUN QUERY calculate_route_length("flight_to", True)
[
  {
    "@@dontChangeList": [],
    "@@numChanged": 37606
  }
]

RUN QUERY calculate_route_length("flight_route", True)
[
  {
    "@@dontChangeList": [],
    "@@numChanged": 38535
  }
]

內容解密：

  • calculate_route_length 查詢用於計算航線長度，引數分別為邊型別和是否重新計算的布林值。
  • 查詢結果顯示了受影響的邊數量，表明計算已成功執行。
  • 透過使用 haversine 公式，查詢能夠準確計算出兩個機場之間的距離。

中央性分析

中央性（Centrality）是衡量一個頂點在網路中的重要性的指標。本文將介紹兩種中央性演算法：接近中心性（Closeness Centrality）和介於中心性（Betweenness Centrality）。

接近中心性

接近中心性衡量一個頂點到其他所有頂點的最短路徑距離的倒數。對於一個機場來說，高接近中心性意味著它有大量的直飛或一站式航班到達其他機場。

RUN QUERY tg_closeness_cent(
  v_type = "Airport", 
  e_type = "flight_to", 
  rev_e_type = "reverse_flight_to"
)

內容解密：

  • tg_closeness_cent 查詢用於計算接近中心性，引數包括頂點型別、邊型別和反向邊型別。
  • 結果顯示了全球前十大機場分別為法蘭克福（FRA）、巴黎戴高樂（CDG）、倫敦希思羅（LHR）、杜拜（DXB）、阿姆斯特丹（AMS）、洛杉磯（LAX）、紐約甘迺迪（JFK）、多倫多（YYZ）、伊斯坦堡（IST）和芝加哥奧黑爾（ORD）。
  • 這些機場被公認為全球最繁忙和最重要的樞紐機場，結果符合預期。

介於中心性

介於中心性衡量一個頂點在所有最短路徑中被經過的次數。巴拿馬運河是一個典型的例子，它對於連線大西洋和太平洋的航線具有很高的介於中心性。

RUN QUERY tg_betweenness_cent(
  v_type = "Airport", 
  e_type = "flight_to", 
  rev_e_type = "reverse_flight_to"
)

內容解密：

  • tg_betweenness_cent 查詢用於計算介於中心性，引數與接近中心性相同。
  • 由於介於中心性需要考慮所有頂點之間的最短路徑，因此計算時間較長。
  • 介於中心性高的機場通常是重要的中轉樞紐，如巴拿馬運河對於跨洋航線的重要性。

社群檢測

社群檢測演算法用於識別網路中的群組結構。在航空路線網路中，社群代表了具有密集連線的機場群。

RUN QUERY strongly_connected_components(
  v_type = "Airport", 
  e_type = "flight_to"
)

內容解密：

  • strongly_connected_components 查詢用於檢測強連線元件，即網路中任意兩個頂點之間都存在路徑的群組。
  • 結果可以揭示全球航空路線網路中的自然群組，如區域樞紐和航線密集區域。
  1. 路徑規劃演算法：利用圖演算法最佳化航線規劃，減少飛行距離和時間，提高營運效率。
  2. 網路最佳化：透過分析網路結構，識別關鍵節點和邊，最佳化資源組態，提升網路韌性。
  3. 動態分析：結合實時資料，動態分析網路變化，預測和應對突發事件，提升網路穩定性。

技術選型考量

在進行航空路線網路分析時，選擇合適的圖資料函式庫和演算法函式庫至關重要。TigerGraph 作為一款高效的圖資料函式庫，能夠處理大規模複雜網路，提供實時的查詢和分析能力。其內建的圖資料科學函式庫提供了豐富的演算法，能夠滿足多樣化的分析需求。

實際應用場景

  1. 航線最佳化：航空公司可以利用中央性演算法和社群檢測結果，最佳化航線網路，提升營運效率。
  2. 機場營運：機場管理方可以根據分析結果，最佳化資源組態，提升服務品質。
  3. 政策制定：政府和監管機構可以利用分析結果，制定更有效的航空運輸政策，促進行業健康發展。

航空路線分析：從中介中心性到最短路徑探索

中介中心性分析結果解析

在分析全球機場網路的中介中心性（Betweenness Centrality）時，我們發現排名前十的機場分別為：

  1. Domodedovo
  2. 北京（Peking/Beijing）
  3. 芝加哥 O’Hare
  4. 伊斯坦堡（Istanbul）
  5. 波哥大（Bogota）
  6. 丹佛（Denver）
  7. 亞特蘭大（Atlanta）
  8. 馬尼拉（Manila）
  9. 布宜諾斯艾利斯（Bueno Aires）
  10. 達拉斯-沃思堡（Dallas–Fort Worth）

這些結果顯示出與直覺不同的結論。中介中心性指標賦予「瓶頸」或「閘道」節點較高的分數，例如巴拿馬運河在全球航運中的角色。我們可以推測，波哥大和布宜諾斯艾利斯在南美洲區域機場網路中扮演著重要的樞紐角色，而馬尼拉可能在菲律賓和東南亞地區發揮類別似的功能。

標準中介中心性演算法的侷限性

值得注意的是，標準的中介中心性演算法認為所有最短路徑具有相同的權重。因此，從洛杉磯（LAX）到紐約（JFK）的路徑重要性與從澳大利亞的薩爾（SXE）到格陵蘭的阿圖（QGQ）的路徑重要性相同。在實際應用中，我們可能需要考慮乘客流量或航班數量等因素來對這些路徑進行加權處理。

使用最短路徑演算法分析航線

無權重最短路徑分析

首先，我們使用無權重的最短路徑演算法來找出轉機次數最少的航線。接著，我們將採用考慮正權重的最短路徑演算法，來找出飛行里程最短的航線。

在加權圖中，從一個起點到所有其他頂點的最短路徑集合，可以在與計算到單一目標頂點的最短路徑幾乎相同的計算時間內完成。這是因為在加權圖中，必須遍歷圖中的每條邊，以確保演算法找到了絕對最短路徑。

尋找機場ID

在進行最短路徑分析之前，我們需要知道起點機場的ID。由於機場的命名系統並不統一，我們使用了一個名為 _search_for_vertex 的查詢來幫助尋找特定機場的ID。例如，要查詢克里夫蘭主要機場的ID，我們可以執行以下查詢：

RUN QUERY _search_for_vertex("Airport","city","Cleveland")

查詢結果顯示有三個與克里夫蘭相關的機場，其中克里夫蘭霍普金斯國際機場（Cleveland Hopkins International Airport）是主要機場，其ID為CLE-3486。

執行最短路徑演算法

使用名為 tg_shortest_ss_no_wt 的演算法，我們可以計算從CLE-3486出發到其他所有機場的最短路徑。該演算法的引數設定如下：

  • source = CLE-3486
  • v_type = Airport
  • e_type = flight_to

結果分析

演算法輸出的結果包含大量資料，顯示從CLE-3486出發到其他機場的最短路徑。例如，其中一條最短路徑如下：

{
  "v_id": "ZQZ-10940",
  "v_type": "Airport",
  "ResultSet.@min_dis": 4,
  "ResultSet.@path_list": [
    "CLE-3486",
    "YYZ-193",
    "TPE-2276",
    "SJW-6347",
    "ZQZ-10940"
  ]
}

自定義GSQL演算法最佳化輸出

為了使輸出結果更易讀，我們對原有的 tg_shortest_ss_no_wt 演算法進行了修改，建立了一個名為 tg_shortest_ss_modified 的新演算法。我們主要進行了以下四項修改：

  1. 新增城市名稱列表

    • 在原有的路徑列表（@path_list）基礎上，我們新增了一個用於儲存城市名稱的列表（@city_list）。
    ListAccum<VERTEX> @path_list;
ListAccum<STRING> @city_list; // 新增城市名稱列表

  2. 初始化城市名稱列表

    • 在演算法的起始步驟中，我們將當前頂點的城市名稱加入到 @city_list 中。
    s.@city_list = s.city, // 初始化城市名稱列表
s.@path_list = s;

  3. 更新城市名稱列表

    • 在遍歷鄰接頂點時，我們將鄰接頂點的城市名稱追加到 @city_list 中。
    t.@city_list = s.@city_list + [t.city], // 更新城市名稱列表
t.@path_list = s.@path_list + [t],

  4. 修改輸出內容並過濾結果

    • 我們修改了最終的輸出內容，使其包含城市名稱列表（@city_list），並且只輸出路徑長度不超過3的結果。
    PRINT ResultSet[ResultSet.@min_dis, ResultSet.@path_list, ResultSet.@city_list]
WHERE ResultSet.@path_list.size() <= 3; // 只輸出路徑長度不超過3的結果

#### 內容解密：

此步驟透過修改GSQL演算法，新增了對城市名稱的處理邏輯，並在輸出結果中包含了城市名稱，使得結果更加直觀易懂。同時，透過限制路徑長度，過濾掉了過長的路徑，使結果更加聚焦於較短的航線。

修改後的結果示例

經過修改後，演算法輸出的結果包含了城市名稱，並且只顯示路徑長度不超過3的結果。例如：

{
  "v_id": "LAR-5746",
  "v_type": "Airport",
  "ResultSet.@city_list": [
    "Cleveland",
    "Denver",
    "Laramie"
  ],
  "ResultSet.@min_dis": 2,
  "ResultSet.@path_list": [
    "CLE-3486",
    "DEN-3751",
    "LAR-5746"
  ]
}

  graph LR
    A[克里夫蘭] -->|第一跳|> B[丹佛]
    B -->|第二跳|> C[拉拉米]
    A -->|第一跳|> D[亞特蘭大]
    D -->|第二跳|> E[布朗斯維克]

圖表翻譯： 圖中展示了從克里夫蘭出發的兩條不同路徑：第一條路徑經過丹佛到達拉拉米，第二條路徑經過亞特蘭大到達布朗斯維克。每條路徑代表了一種可能的航線選擇。

#### 內容解密：

此圖表展示了從克里夫蘭出發的兩條最短路徑，分別到達拉拉米和布朗斯維克。圖中節點代表城市，邊代表航線連線關係。

使用正權最短路徑演算法最佳化航班路線分析

在進行航班路線分析時，若要最小化旅行距離，可以採用正權最短路徑演算法。此演算法對於希望減少行駛距離的旅客來說更為合適。如果將權重從里程轉換為二氧化碳排放量，該演算法同樣可用於最小化碳排放。

取得並執行最新演算法

首先，我們需要從 GitHub 倉函式庫取得最新的演算法函式庫。具體步驟如下：

  1. 開啟網頁瀏覽器，存取 https://github.com/tigergraph/gsql-graph-algorithms/blob/master/algorithms。
  2. 導航至 Path → shortest_path → weighted → positive → traceback，找到 tg_shortest_ss_pos_wt_tb.gsql 檔案。

在 GraphStudio 中建立並執行查詢

  1. 在 GraphStudio 的查詢選擇面板中，點選「建立查詢」（+ 符號）按鈕。
  2. 將新查詢命名為 tg_shortest_ss_pos_wt_tb。
  3. 將從 GitHub 倉函式庫取得的 tg_shortest_ss_pos_wt_tb.gsql 中的文字複製並替換 GraphStudio 中的現有查詢文字。
  4. 儲存並安裝該查詢。
  5. 使用以下設定執行演算法：
    • Vertex_id = CLE-3486
    • v_type = Airport
    • e_type = flight_to
    • wt_attr = miles
    • wt_type = INT
    • output_limit = 10000

結果分析

執行後，你可能會發現某些路徑具有 8 甚至 10 次跳轉。為了縮小結果範圍，可以對演算法進行修改，只顯示總成本（總里程）小於 3000 的路徑，這樣可以將結果限制在北美地區內。

修改演算法

  1. 找到列印輸出的程式碼行：
    PRINT tmp[tmp.@min_path_heap.top().cost as cost, tmp.@path_list as p];
  2. 新增 WHERE 子句並移動分號，修改為：
    PRINT tmp[tmp.@min_path_heap.top().cost as cost, tmp.@path_list as p]
WHERE tmp.@min_path_heap.top().cost < 3000;

發現與分析社群

在有向圖中，強連通分量（SCC）是指最大的頂點集合，其中每個頂點都可以到達該集合中的其他任意頂點。在航空路線網路中，如果航空公司在兩個機場之間提供雙向直飛服務，則很容易滿足 SCC 的要求。但在需求較低的地區，直飛服務可能不是雙向的，這時就可能出現斷裂，將圖分成不同的 SCC。

執行強連通分量演算法

使用以下引數設定執行 tg_scc 演算法：

  • v_type_set = Airport
  • e_type_set = flight_to
  • rev_e_type_set = reverse_flight_to
  • top_k_dist = 100
  • print_limit = 10000
  • result_attr = score

結果分析

切換到表格結果輸出，會看到兩個表格。@@cluster_dist_heap 表格顯示了社群的大小和數量，如表 9-6 所示。結果表明，最大的社群包含 3354 個機場，還有一些較小的社群和大量的單一機場。

表 9-6：機場社群大小與數量
csizenum
33541
101
81
43
23
14545

輸出結果還包括所有頂點的完整列表以及它們的社群 ID。為了獲得更友好的輸出，可以對演算法進行修改。

修改社群檢測演算法

  1. 新增 MapAccum 宣告：在 Accum 宣告部分新增以下程式碼：

    MapAccum<INT, ListAccum<VERTEX>> @@cluster_member_map;

    此資料結構將記錄屬於每個社群的頂點列表。

  2. 修改輸出結果：在輸出結果部分，找到以下程式碼區塊：

    v_all = SELECT s
FROM v_all:s
POST-ACCUM
@@cluster_size_map += (s.@sum_cid -> 1);

    在 POST-ACCUM 子句中新增一行，並在之後新增 FOREACH 區塊：

    v_all = SELECT s
FROM v_all:s
POST-ACCUM
@@cluster_member_map += (s.@sum_cid -> s),
@@cluster_size_map += (s.@sum_cid -> 1);
FOREACH (cid, member_list) IN @@cluster_member_map DO
    IF member_list.size() == 1 OR member_list.size() > 50 THEN
        @@cluster_member_map.remove(cid);
    END;
END;

    這樣可以移除過小或過大的社群列表。

程式碼解讀

MapAccum<INT, ListAccum<VERTEX>> @@cluster_member_map;

此行程式碼宣告瞭一個名為 @@cluster_member_map 的 MapAccum，用於儲存每個社群 ID 對應的頂點列表。

v_all = SELECT s
FROM v_all:s
POST-ACCUM
@@cluster_member_map += (s.@sum_cid -> s),
@@cluster_size_map += (s.@sum_cid -> 1);

這段程式碼在 POST-ACCUM 階段將每個頂點加入其對應社群 ID 的列表中，並統計每個社群的大小。

FOREACH (cid, member_list) IN @@cluster_member_map DO
   IF member_list.size() == 1 OR member_list.size() > 50 THEN
       @@cluster_member_map.remove(cid);
   END;
END;

這段 FOREACH 迴圈遍歷 @@cluster_member_map，移除成員數量為 1 或大於 50 的社群列表，以過濾掉過小或過大的社群。

圖表翻譯：

此圖表展示了社群檢測演算法的流程。首先，演算法根據機場之間的航班連線計算強連通分量（SCC）。接著，將計算出的 SCC 結果儲存並進行過濾，移除過小或過大的社群。最終輸出篩選後的社群列表及其成員。

透過這些步驟，我們可以更深入地瞭解全球機場網路的結構，並找出具有特定特徵的社群，從而為航空網路的最佳化提供有價值的參考。

玄貓

玄貓

技術愛好者，專注於分享程式開發、雲端技術與 AI 應用的心得體會。