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

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

中圖分類號(hào)： TN929.5?34； V355" " " " " " " " "文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " " " "文章編號(hào)： 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" 引" 言

航空運(yùn)輸系統(tǒng)是一個(gè)復(fù)雜且高度動(dòng)態(tài)的網(wǎng)絡(luò)[1]。在現(xiàn)代航空運(yùn)輸中，大多數(shù)航班都是多航段的，即乘客需要在不同的機(jī)場(chǎng)進(jìn)行換乘或中轉(zhuǎn)。因此一段航班的延誤會(huì)導(dǎo)致后續(xù)航班的延誤，影響整個(gè)航班網(wǎng)絡(luò)的正常運(yùn)行[2]。例如：惡劣的天氣條件會(huì)導(dǎo)致航班延誤；在高峰期間或者特殊情況下，交通管制的設(shè)立會(huì)影響航班的起降時(shí)間。航班延誤會(huì)導(dǎo)致需要重新調(diào)整航班的時(shí)隙資源分配，增加了資源分配方案的不確定性[3?5]。因此，研究航路時(shí)隙資源分配方法具有重要意義。

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

1" 航路時(shí)隙資源分配算法

1.1" 航路時(shí)隙資源分配模型

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

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

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

由于不確定性原因造成多航段延誤運(yùn)輸以及航路擁擠等情況時(shí)，旅客的延誤時(shí)間增加[12]。選取考慮不確定性多航段延誤運(yùn)輸?shù)钠骄每脱诱`時(shí)間最小作為航路時(shí)隙資源分配模型的第二階段目標(biāo)函數(shù)，其表達(dá)式如下：

式中[ni]表示航班[i]的載客數(shù)。

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

針對(duì)考慮不確定性多航段延誤運(yùn)輸情況下構(gòu)建的航路時(shí)隙資源分配模型，設(shè)置約束條件如下。

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

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

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

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

式中：[pa，i]與[pa]分別表示鳥巢[i]中蛋被發(fā)現(xiàn)的概率以及布谷鳥蛋的平均發(fā)現(xiàn)概率；[n]與[fi]分別表示鳥巢數(shù)量以及航路時(shí)隙資源分配模型的適應(yīng)度值。

依據(jù)航路時(shí)隙資源分配模型發(fā)現(xiàn)概率[pa，i]的求解結(jié)果，對(duì)模型進(jìn)行局部開(kāi)發(fā)求解。通過(guò)全局探索與局部開(kāi)發(fā)的結(jié)合，提升航路資源時(shí)隙分配模型求解的搜索速度。本文基于Lévy算法，對(duì)布谷鳥飛行的全局探索的表達(dá)式如下：

式中：[xtl]與[xb]分別表示當(dāng)前鳥巢位置以及最優(yōu)鳥巢位置；[α]與[ξ]分別表示步長(zhǎng)控制因子以及飛行步長(zhǎng)；“[?]”與[Lévy]分別表示點(diǎn)積以及服從L[é]vy概率分布。

基于發(fā)現(xiàn)概率[pa]，對(duì)航路時(shí)隙資源分配模型求解局部開(kāi)發(fā)的表達(dá)式如下：

3） 聯(lián)合多種群進(jìn)行航路時(shí)隙資源分配最優(yōu)解的全局探索。利用式（9）進(jìn)行全局搜索，計(jì)算更新過(guò)程中的個(gè)體適應(yīng)度值，保留個(gè)體適應(yīng)度值更優(yōu)的個(gè)體。

4） 對(duì)利用上步驟生成的多種群，利用式（10）開(kāi)展局部開(kāi)發(fā)，生成新的種群。迭代過(guò)程中不斷更新個(gè)體適應(yīng)度值，保留更優(yōu)的解。通過(guò)以上過(guò)程，完成布谷鳥種群的一次進(jìn)化。

5） 利用以上過(guò)程，不斷進(jìn)行精華種群的更新，不斷將最優(yōu)個(gè)體保存至精華種群內(nèi)。

6） 當(dāng)最優(yōu)個(gè)體不再變化時(shí)，輸出航路時(shí)隙資源分配的最優(yōu)方案。若不滿足，返回至步驟2），繼續(xù)進(jìn)行航路時(shí)隙資源分配模型求解，直至輸出最優(yōu)解為止。

2" 實(shí)例分析

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

研究區(qū)域的航路信息如表1所示。20：00—21：00時(shí)間段的航班運(yùn)行信息如表2所示。

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

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

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

為了進(jìn)一步衡量本文算法的航路時(shí)隙資源分配性能，選取文獻(xiàn)[6]基于航線聯(lián)營(yíng)下轉(zhuǎn)運(yùn)的資源分配算法、文獻(xiàn)[7]基于航線網(wǎng)絡(luò)布局的資源分配算法、文獻(xiàn)[8]基于空中交通流管理模型的資源分配算法作為對(duì)比算法。統(tǒng)計(jì)不同算法分配航路時(shí)隙資源時(shí)的旅客平均延誤時(shí)間，統(tǒng)計(jì)結(jié)果如圖2所示。

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

統(tǒng)計(jì)采用本文算法分配航路時(shí)隙資源，航班的總延誤損失，結(jié)果如圖3所示。

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

3" 結(jié)" 論

本文建立了一種時(shí)隙資源分配模型，考慮航路的實(shí)際承載能力和限制條件，確保在分配時(shí)隙資源時(shí)不超出航路的容量限制。通過(guò)實(shí)驗(yàn)驗(yàn)證，該算法能夠準(zhǔn)確評(píng)估航段延誤的可能性，動(dòng)態(tài)調(diào)整航路時(shí)隙資源的分配，同時(shí)能夠滿足高效、安全、可靠的航路時(shí)隙資源分配的需求，為航空運(yùn)輸系統(tǒng)的優(yōu)化和改進(jìn)提供有力支持。

參考文獻(xiàn)

[1] 鄭靜雅，安軍社.SpaceFibre網(wǎng)絡(luò)服務(wù)質(zhì)量時(shí)隙資源分配算法[J].國(guó)防科技大學(xué)學(xué)報(bào)，2021，43（2）：74?83.

[2] 馬勇健，史旭華，王佩瑤.基于兩階段搜索與動(dòng)態(tài)資源分配的約束多目標(biāo)進(jìn)化算法[J].計(jì)算機(jī)應(yīng)用，2024，44（1）：269?277.

[3] 歐陽(yáng)聰，關(guān)靜，楊鳴.基于資源分配和動(dòng)態(tài)分組的合作協(xié)同演化算法[J].鄭州大學(xué)學(xué)報(bào)（工學(xué)版），2023，44（5）：10?16.

[4] 隋東，邢婭萍，涂詩(shī)晨.惡劣天氣條件下航路網(wǎng)絡(luò)修復(fù)優(yōu)化[J].航空學(xué)報(bào)，2021，42（2）：323?334.

[5] 王莉莉，謝昊松.突發(fā)事件下的航路網(wǎng)絡(luò)通行能力研究[J].計(jì)算機(jī)仿真，2022，39（12）：59?63.

[6] 閆妍，馬嘯來(lái).航線聯(lián)營(yíng)下基于轉(zhuǎn)運(yùn)的飛機(jī)航線路徑優(yōu)化[J].北京航空航天大學(xué)學(xué)報(bào)，2023，49（1）：115?127.

[7] 趙俊，劉志碩，李秋雨，等.稀缺國(guó)際客運(yùn)航權(quán)資源優(yōu)化配置[J].南京航空航天大學(xué)學(xué)報(bào)，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] 魏燕明，甘旭升，劉飛，等.基于灰狼優(yōu)化算法的軍用運(yùn)輸機(jī)航路規(guī)劃方法[J].火力與指揮控制，2021，46（1）：155?161.

[11] 呂宗磊，吳志帥，徐濤，等.面向空鐵聯(lián)運(yùn)的樞紐航線網(wǎng)絡(luò)優(yōu)化模型[J].計(jì)算機(jī)工程與設(shè)計(jì)，2021，42（4）：1188?1194.

[12] 李?yuàn)?，張洪海，劉?基于改進(jìn)元胞自動(dòng)機(jī)算法的物流無(wú)人機(jī)航路規(guī)劃[J].華中科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2023，51（12）：14?19.

[13] 奚軍，湯嘉立.關(guān)于動(dòng)態(tài)拓?fù)涞奈锫?lián)網(wǎng)終端任務(wù)時(shí)隙調(diào)度研究[J].計(jì)算機(jī)仿真，2022，39（1）：366?369.

[14] 鄧榮岳.基于多目標(biāo)優(yōu)化的航班擾動(dòng)恢復(fù)策略研究：以長(zhǎng)沙黃花機(jī)場(chǎng)為例[D].廣漢：中國(guó)民用航空飛行學(xué)院，2024.

作者簡(jiǎn)介：蘇" 樂(lè)（1984—），男，天津人，博士研究生，講師，研究方向?yàn)榻煌ㄟ\(yùn)輸、計(jì)算機(jī)軟件。

翟文鵬（1985—），男，天津人，博士研究生，副教授，研究方向?yàn)榻煌ㄟ\(yùn)輸、自動(dòng)化。

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金委員會(huì)青年科學(xué)基金項(xiàng)目（61603396）