考慮不確定性多航段延誤運輸的航路時隙資源分配算法

摘" 要： 引起航班延誤的不確定性因素眾多，包括天氣、交通管制、機械故障等，導致航班信息存在不確定性，無法獲取最優資源分配方案。為此，提出一種考慮不確定性多航段延誤運輸的航路時隙資源分配算法。以不確定原因造成的多航段總延誤運輸損失最小、平均旅客延誤時間最小作為目標函數，構建航路時隙資源分配模型；以唯一性約束、時間順序約束、容量約束以及航班順序約束為約束條件，選取布谷鳥算法來求解所構建的時隙資源分配模型，輸出最優航路時隙資源分配方案。實驗結果表明，所提算法充分考慮了由于不確定性因素造成的多航段延誤運輸情況，能夠有效分配航路時隙資源，平均旅客延誤時間低于10 min。

關鍵詞： 航班延誤； 多航段； 航路時隙資源分配算法； 不確定因素； 約束條件； 布谷鳥算法

中圖分類號： TN929.5?34； V355" " " " " " " " "文獻標識碼： A" " " " " " " " " " " "文章編號： 1004?373X（2025）08?0122?05

A route slot resource allocation algorithm considering uncertainty

multi?segment delay transportation

SU Le， ZHAI Wenpeng

（Department of Management Science and Engineering， Civil Aviation University of China， Tianjin 300300， China）

Abstract： There are many uncertainty factors that cause flight delays， including weather， traffic control， mechanical failure， etc.， which will lead to uncertainty in flight information and the inability to obtain the optimal quota plan. On this basis， a route slot resource allocation algorithm considering uncertain multi?segment delay transportation is proposed. Taking the minimum total delay loss and minimum average passenger delay time caused by uncertain reasons as the objective function， the route slot resource allocation model is constructed. Taking uniqueness constraint， time sequence constraint， capacity constraint and flight sequence constraint as constraint conditions， the cuckoo algorithm is selected to solve the constructed time slot quota model， and output the optimal route time slot quota scheme. The experimental results show that the proposed algorithm can fully consider the multi?segment delay caused by uncertainty factors， and effectively allocate the route slot resources， and the average passenger delay time is less than 10 min.

Keywords： flight delay; multi?segment; route slot resource allocation algorithm; uncertainty factor; constraint condition; cuckoo algorithm

0" 引" 言

航空運輸系統是一個復雜且高度動態的網絡[1]。在現代航空運輸中，大多數航班都是多航段的，即乘客需要在不同的機場進行換乘或中轉。因此一段航班的延誤會導致后續航班的延誤，影響整個航班網絡的正常運行[2]。例如：惡劣的天氣條件會導致航班延誤；在高峰期間或者特殊情況下，交通管制的設立會影響航班的起降時間。航班延誤會導致需要重新調整航班的時隙資源分配，增加了資源分配方案的不確定性[3?5]。因此，研究航路時隙資源分配方法具有重要意義。

文獻[6]針對航線聯營下轉運的飛機航線路徑進行優化，減少不必要的飛行時間和成本，提高整體運營效率。但是該方法涉及多個航段和轉運點的協調，轉運本身會帶來額外的時間和成本，且未考慮航班延誤、取消或行李丟失等問題。文獻[7]通過優化航路配置，避免了資源浪費和重復配置；通過精準匹配市場需求和航線網絡布局，提高航班滿載率和運營效益。但是該方法需要綜合考慮市場需求、航線網絡布局、運營成本、安全標準等多個因素，增加了決策難度和不確定性，無法解決航班延誤情況。文獻[8]構建了安全感知實時空中交通流管理模型。通過優化策略確保航空器之間的安全間隔和避讓，提升空中交通系統的整體安全性。但是該方法應用于復雜航線網絡的航空公司，需要綜合考慮多航線的交互影響、航班時刻的協調以及不同航線的容量限制等因素，導致模型難以找到全局最優解。文獻[9]將C波段測量數據應用于航路優化中，基于C波段的測量數據支持高速空地通信需求，為航路優化提供了有力的數據支持。但是C波段測量數據主要用于分析空地信道的主信號分量，無法全面反映地形、天氣、航路容量、交通流量航路優化所需的所有信息，容易出現由于信息不全面導致的航線延誤情況。針對以上方法在航路優化中存在的問題，本文研究一種考慮不確定性多航段延誤運輸的航路時隙資源分配算法。以不確定原因造成的多航段總延誤運輸損失最小、平均旅客延誤時間最小作為目標函數，構建航路時隙資源分配模型；以唯一性約束、時間順序約束、容量約束以及航班順序約束為約束條件，選取布谷鳥算法來求解所構建的時隙資源分配模型，輸出最優航路時隙資源分配方案。實驗結果表明，所提算法充分考慮了由于不確定性因素造成的多航段延誤運輸情況，能夠有效分配航路時隙資源，平均旅客延誤時間低于10 min。

1" 航路時隙資源分配算法

1.1" 航路時隙資源分配模型

航班延誤有諸多不確定性因素，如天氣、機械故障、交通管制等，導致航班信息存在不確定性。總延誤運輸損失最小可以幫助航空公司降低額外成本，提高經濟效益；平均旅客延誤時間最小則關乎乘客體驗和滿意度[10]。因此，本文以總延誤運輸損失和平均旅客延誤時間為目標函數，綜合考慮這些不確定性因素對航路時隙資源分配的影響。

由于臨時航路與計劃航路的運行成本存在明顯的差異，因此航班在臨時航路上航行時，需要付出的成本更高[11]。以多航段總延誤運輸損失最小作為目標，構建時隙資源分配模型第一階段的目標函數，其表達式如下：

式中：[qkt]與[qs]分別表示臨時航路[k]與計劃航路航行的單位時間延誤成本；[xij]與[ykij]分別表示航班[i]分配到航路[j]，選擇計劃航路與臨時航路[k]的決策變量；[asi]與[tj]分別表示計劃到達時刻與時隙起始時刻。

由于不確定性原因造成多航段延誤運輸以及航路擁擠等情況時，旅客的延誤時間增加[12]。選取考慮不確定性多航段延誤運輸的平均旅客延誤時間最小作為航路時隙資源分配模型的第二階段目標函數，其表達式如下：

式中[ni]表示航班[i]的載客數。

1.2" 航路時隙資源分配模型的約束條件

針對考慮不確定性多航段延誤運輸情況下構建的航路時隙資源分配模型，設置約束條件如下。

1） 為確保每個時隙只能分配給一個航班，設置時隙資源分配的唯一性約束，避免資源的重復利用或沖突分配[13]，航班僅可以分配1個時隙。

1.3" 基于布谷鳥算法的模型求解

由于航班信息的不確定性，無法獲取最優資源分配方案。同時，考慮到航班延誤問題存在多個目標，包括減小總延誤運輸損失和平均旅客延誤時間，而布谷鳥算法適用于多目標優化問題，并能夠找到一種平衡各目標的最佳解決方案。該方法具有較快的收斂速度，能夠快速搜索解空間，并找到接近最優解的解決方案。

設存在不確定性多航段延誤運輸的航班與可選航路數量分別用[i]與[B]表示，每個航路內包含的可分配時隙數量為[M]。考慮模型所設置約束條件的情況下，每個航班需要在[BM]種可能的時隙中，選擇最佳的航路時隙資源分配方案。布谷鳥算法引入了發現概率，從全局隨機探索以及局部隨機開發兩方面，求解所構建的時隙資源分配模型。

式中：[pa，i]與[pa]分別表示鳥巢[i]中蛋被發現的概率以及布谷鳥蛋的平均發現概率；[n]與[fi]分別表示鳥巢數量以及航路時隙資源分配模型的適應度值。

依據航路時隙資源分配模型發現概率[pa，i]的求解結果，對模型進行局部開發求解。通過全局探索與局部開發的結合，提升航路資源時隙分配模型求解的搜索速度。本文基于Lévy算法，對布谷鳥飛行的全局探索的表達式如下：

式中：[xtl]與[xb]分別表示當前鳥巢位置以及最優鳥巢位置；[α]與[ξ]分別表示步長控制因子以及飛行步長；“[?]”與[Lévy]分別表示點積以及服從L[é]vy概率分布。

基于發現概率[pa]，對航路時隙資源分配模型求解局部開發的表達式如下：

3） 聯合多種群進行航路時隙資源分配最優解的全局探索。利用式（9）進行全局搜索，計算更新過程中的個體適應度值，保留個體適應度值更優的個體。

4） 對利用上步驟生成的多種群，利用式（10）開展局部開發，生成新的種群。迭代過程中不斷更新個體適應度值，保留更優的解。通過以上過程，完成布谷鳥種群的一次進化。

5） 利用以上過程，不斷進行精華種群的更新，不斷將最優個體保存至精華種群內。

6） 當最優個體不再變化時，輸出航路時隙資源分配的最優方案。若不滿足，返回至步驟2），繼續進行航路時隙資源分配模型求解，直至輸出最優解為止。

2" 實例分析

為了驗證所研究的航路時隙資源分配算法，分配航路時隙資源的有效性，選取某民航的航路運行數據作為仿真數據。該航路包含1條計劃航路以及2條臨時航路。選取2021?11?18T20：00—21：00的航空數據作為仿真數據。受惡劣天氣影響，航路容量受限，出現多航段延誤運輸情況。該區域的兩條臨時航路分別生成了流量受限區。

研究區域的航路信息如表1所示。20：00—21：00時間段的航班運行信息如表2所示。

該時間段各航路的可用時隙信息如表3所示。

采用本文算法充分考慮由于不確定性多航段延誤運輸對航路的影響，獲取最終的航路時隙資源分配結果，如圖1所示。

分析圖1的航路時隙資源分配結果得出，本文算法構建的航路時隙資源分配模型考慮了不確定性多階段延誤運輸情況，時隙分配較為均勻，改善了航路延誤的情況。未考慮多航段延誤運輸情況時，容易出現航路時隙過小的問題，造成大量乘客延誤。本文算法通過航路時隙資源的高效分配，有助于改善乘客延誤的情況，提升航空公司的服務質量。

為了進一步衡量本文算法的航路時隙資源分配性能，選取文獻[6]基于航線聯營下轉運的資源分配算法、文獻[7]基于航線網絡布局的資源分配算法、文獻[8]基于空中交通流管理模型的資源分配算法作為對比算法。統計不同算法分配航路時隙資源時的旅客平均延誤時間，統計結果如圖2所示。

從圖2實驗結果可以看出，采用本文算法進行航路時隙資源分配，旅客的平均延誤時間明顯低于其他三種算法。本文算法分配航路時隙資源時，其旅客平均延誤時間低于10 min，其他三種算法分配航路時隙資源時，其旅客平均延誤時間均高于10 min。對比結果驗證了本文算法充分考慮了由于不確定性造成的多航段延誤運輸情況，通過航路時隙資源的合理分配，降低了旅客的平均延誤時間。

統計采用本文算法分配航路時隙資源，航班的總延誤損失，結果如圖3所示。

從圖3實驗結果可看出，采用本文算法分配航路時隙資源，不同航班數量時，總延誤損失均低于5萬元。驗證了采用本文算法分配航路時隙資源，充分考慮了不確定性多航段延誤運輸情況，改善了由于不確定原因造成的航段延誤，降低了總延誤損失，滿足所構建的航路時隙資源分配模型目標，促進了航路時隙資源的高效利用。

3" 結" 論

本文建立了一種時隙資源分配模型，考慮航路的實際承載能力和限制條件，確保在分配時隙資源時不超出航路的容量限制。通過實驗驗證，該算法能夠準確評估航段延誤的可能性，動態調整航路時隙資源的分配，同時能夠滿足高效、安全、可靠的航路時隙資源分配的需求，為航空運輸系統的優化和改進提供有力支持。

參考文獻

[1] 鄭靜雅，安軍社.SpaceFibre網絡服務質量時隙資源分配算法[J].國防科技大學學報，2021，43（2）：74?83.

[2] 馬勇健，史旭華，王佩瑤.基于兩階段搜索與動態資源分配的約束多目標進化算法[J].計算機應用，2024，44（1）：269?277.

[3] 歐陽聰，關靜，楊鳴.基于資源分配和動態分組的合作協同演化算法[J].鄭州大學學報（工學版），2023，44（5）：10?16.

[4] 隋東，邢婭萍，涂詩晨.惡劣天氣條件下航路網絡修復優化[J].航空學報，2021，42（2）：323?334.

[5] 王莉莉，謝昊松.突發事件下的航路網絡通行能力研究[J].計算機仿真，2022，39（12）：59?63.

[6] 閆妍，馬嘯來.航線聯營下基于轉運的飛機航線路徑優化[J].北京航空航天大學學報，2023，49（1）：115?127.

[7] 趙俊，劉志碩，李秋雨，等.稀缺國際客運航權資源優化配置[J].南京航空航天大學學報，2021，53（6）：872?880.

[8] SANDAMALI G G N， SU R， SUDHEERA K L K， et al. A safety?aware real?time air traffic flow management model under demand and capacity uncertainties [J]. IEEE transactions on intelligent transportation systems， 2021， 23（7）： 8615?8628.

[9] MIELKE D M， SCHNECKENBURGER N， FIEBIG U C， et al. Analysis of the dominant signal component of the air?ground channel based on measurement data at c?band [J]. IEEE transactions on vehicular technology， 2021， 70（4）： 2955?2968.

[10] 魏燕明，甘旭升，劉飛，等.基于灰狼優化算法的軍用運輸機航路規劃方法[J].火力與指揮控制，2021，46（1）：155?161.

[11] 呂宗磊，吳志帥，徐濤，等.面向空鐵聯運的樞紐航線網絡優化模型[J].計算機工程與設計，2021，42（4）：1188?1194.

[12] 李姍，張洪海，劉皞.基于改進元胞自動機算法的物流無人機航路規劃[J].華中科技大學學報（自然科學版），2023，51（12）：14?19.

[13] 奚軍，湯嘉立.關于動態拓撲的物聯網終端任務時隙調度研究[J].計算機仿真，2022，39（1）：366?369.

[14] 鄧榮岳.基于多目標優化的航班擾動恢復策略研究：以長沙黃花機場為例[D].廣漢：中國民用航空飛行學院，2024.

作者簡介：蘇" 樂（1984—），男，天津人，博士研究生，講師，研究方向為交通運輸、計算機軟件。

翟文鵬（1985—），男，天津人，博士研究生，副教授，研究方向為交通運輸、自動化。

收稿日期：2024?04?01" " " " " "修回日期：2024?05?16

基金項目：國家自然科學基金委員會青年科學基金項目（61603396）