航空行李提取轉盤分配優化建模及求解算法研究

摘 要：文中針對航空行李提取轉盤分配問題（BCAP），即如何將每個到達的航班分配到合適的行李提取轉盤，以滿足不同利益相關者的需求和偏好進行了研究優化。文中建立了一個綜合考慮行李分配均衡性和旅客步行距離的優化模型，并采用加權法將其轉化為單目標優化問題。設計了一種基于二進制差分進化（DE）算法的求解方法，通過對目標函數施加合適的懲罰和對不可行解進行修復操作，有效保證了解的可行性。通過算例仿真實驗展示了所提方法的尋優過程和優化結果，并與文獻中的方法進行了對比分析。實驗結果表明，文中方法在方差指標上要優于其他2種方法，同時也能保證解滿足所有約束條件。文中的研究為BCAP問題的解決提供了一種新的思路和方法，也為其他類似問題的研究提供了參考。

關鍵詞：航空行李轉盤；均衡分配；二進制差分進化算法；約束處理；算例仿真；MATLAB

中圖分類號：TP18 文獻標識碼：A 文章編號：2095-1302（2024）08-00-05

DOI：10.16667/j.issn.2095-1302.2024.08.025

0 引 言

航空行李提取轉盤分配問題（Baggage Carousel Assignment Problem， BCAP）是指在機場運營過程中，如何將每個到達的航班分配到合適的行李提取轉盤，以滿足不同利益相關者的需求和偏好[1-3]。這個問題對于提高乘客滿意度、降低運營成本、提高資源利用率等都具有重要意義。乘客在到達機場后，需要從登機口步行到行李提取轉盤，等待自己的行李，并在拿到行李后離開機場。因此，行李提取轉盤的分配方案會影響乘客的步行距離、等待時間、擁擠程度等，進而影響乘客的體驗。另一方面，航空公司、地勤公司和機場運營商也有自己的需求和偏好，例如保證航班準點性、平衡行李處理負荷、減少行李輸送距離等。因此，BCAP是一個多目標、多約束、多決策者的優化問題。

近年來，隨著機場運營環境的復雜性和不確定性的增加以及乘客需求和期望的多樣化和個性化，BCAP逐漸受到了更多關注[4-6]。文獻[4]是國內較早對BCAP開展研究的文獻，該文以最小化行李件數最多的轉盤上的行李件數為優化目標，采用蟻群算法（Ant Colony Optimization， ACO）求解。文獻[6]在文獻[4]中模型的基礎上提出采用遺傳算法（Genetic Algorithm， GA）求解，并通過實驗驗證了所提算法的有效性。然而，上述研究中存在優化目標單一、約束條件難以滿足等問題。如文獻[4]和文獻[6]中僅考慮了轉盤行李分配的均衡性，對旅客滿意度等指標并未涉及。同時，在問題求解過程中采用罰函數法對約束違反量進行懲罰，這種方法很難保證約束條件得到滿足[7]。在求解方面，由于BCAP是一個典型NP難問題，當航班數量和轉盤數量較大時，使用傳統的求解方法（如分支定界法[8]）很難在有限的時間內得到最優解或者可接受的近似解。差分進化（Differential Evolution， DE）算法是一種簡單有效的進化算法，能夠在有限的迭代次數內找到高質量的解，在實數優化和二進制優化中均有較為優秀的表現[9-10]。

基于上述分析，文中將對航空行李提取轉盤分配問題的模型建立和求解方法展開研究。首先對BCAP的優化目標進行改進和優化，并基于DE算法設計出更為高效和穩定的求解方法，最后通過實驗驗證所提方法的有效性。

1 BCAP優化模型構建

當前，機場對航班進行行李轉盤分配時一般遵循兩種模式：一種是1個轉盤僅服務1個航班的模式，即“1對1模式”；第二種是1個轉盤可以服務多個航班，即“1對N模式”。文中的模型也將基于這兩種模式建立。

（1）目標函數

文獻[4]和文獻[6]僅考慮最小化行李最多的轉盤上的行李數，旨在均衡分配各轉盤所服務的行李。實際上，為了實現各轉盤行李件數均衡分配，采用方差指標作為目標函數更能體現均衡性，若各轉盤服務行李數間的方差越小，則分配越均勻。另外，由于機場先對每個航班分配停機位，不同停機位到轉盤的步行距離不同，而過長的步行距離會降低旅客滿意度。因此，在目標函數中加入了步行距離項，實現了多維度優化。優化目標如下：

（1）

式中：N為航班數，由所有航班組成的集合A={1， 2， ...， N}；M為行李提取轉盤數，由所有提取轉盤組成的集合B={1， 2， ...， M}；xij表示第i個航班分配到第j個行李提取轉盤的變量，xij∈{0， 1}，若指定第j個轉盤服務于第i個航班，則xij=1，否則xij=0；bi為第i個航班的行李數量；dij為第i個航班到第j個轉盤的步行距離；由于各目標間可能存在沖突，因此設置權重系數λ1、λ2，用來調節各目標的重要性或占比。

式（1）中的目標函數由兩部分組成：第一部分是各轉盤服務行李數的方差，方差越小，表示各轉盤服務行李數越均勻，越能避免某些轉盤過載或空閑的情況；第二部分是乘客從飛機到行李提取轉盤的步行距離之和，總步行距離越小，表示乘客走的路程越短，越能提高乘客的滿意度。

（2）約束條件

每個航班只能分配一個行李提取轉盤，即：

（2）

一個轉盤在一個時段內可以服務多個航班，但在該時段所服務的行李件數不能超過其容量，即：

（3）

（4）

式中：Bmax為一個時段Ts內轉盤所能服務的最大行李件數，文中Bmax取300，Ts取15 min；Ik表示和第k個航班相差在15 min內的全部航班集合；ti為第i個航班的到達時間，i∈A；p為懲罰量。

2 基于差分進化算法的模型求解

2.1 二進制DE算法原理

前文已述，BCAP是一個帶有時間約束的混合整數優化問題，采用分支定界法等傳統方法無法在可接受的時間內得到較好的解。因此，此類問題更適合采用智能優化類算法求解，其可根據某種規則在解空間內對問題的解進行搜索，最終得到一個近似最優解。其中，差分進化（DE）算法是一種簡單而有效的進化算法，能夠處理多目標、非線性和混合整數規劃問題[9-10]。DE算法的基本思想是通過變異、交叉和選擇操作來不斷改進種群中的個體，直到達到預設的停止條件。文中采用一種改進的二進制DE算法來求解所建BCAP模型，其基本步驟如下。

初始化種群：設置種群規模P，隨機生成一個P×D矩陣pop，其中D為每個個體的維度，D=N×M。每個個體用Xi表示，i∈{1， 2， ...， P}。

（5）

為方便計算目標函數值和核驗約束條件，需要將1×D維的Xi轉換為一個N×M維的矩陣Xi'。

（6）

變異操作：DE算法中最常用的變異算子[11]是DE/best/1，即對于種群中的每個個體Xi，隨機選擇兩個不同的個體Xr1、Xr2，并與當前種群中的最優個體Xb生成一個變異向量Vi，如下：

（7）

式中：Vi， j為第i個變異向量的第j個元素；Xb， j、

Xr1， j、Xr2， j分別為最優個體和兩個隨機個體的第j個元素；r1、r2為[1， P]區間內2個不重復的隨機數；r為[0， 1]區間的隨機數；F為變異尺度，用來控制變異的強度，文中采用的是一種動態的變異因子。

（8）

式中：F0為最終變異尺度，可在0.1～0.5范圍內取值；G和Gmax分別為當前迭代次數和最大迭代次數。

由于文中的個體是二進制編碼，式（7）中的實數變異操作不再適用，但根據式（7）提出了二進制變異操作，見表1所列。

交叉操作：對于種群中的每個個體Xi和對應的變異向量Vi，按照一定的概率進行交叉，生成一個試驗向量Ui，如下：

（9）

式中：uij為Ui的第j個元素；randj為[0， 1]區間的隨機數；CR是交叉概率，是[0， 1] 區間的常數；jrand是一個在{1， 2， ...， D}中隨機選擇的整數，用來保證至少有一個元素發生交叉。

選擇操作：對于種群中的每個個體Xi和對應的試驗向量Ui，根據目標函數值進行選擇，如下：

（10）

式中：f（·）是目標函數；G+1表示下一次迭代次數。

2.2 模型求解流程

在模型求解時，需要保證滿足約束條件，為此，文中采用2個措施來保證得到可行解。第一種措施是在計算目標函數時對約束違反量施加懲罰：

（1）航班分配約束懲罰：置懲罰量p=0，計數量c=0，對于Xi'的每個個體，i∈A，計算式（2）的條件是否滿足。不滿足時，c=c+1，當統計完該個體編碼下的所有航班后，置p=p+c·ξ，ξ為一個較大的懲罰系數，文中取ξ=103。

（2）轉盤行李數約束：一個轉盤同一時段可以服務多個航班，但在相同時段內（15 min內），一個轉盤同時服務的行李件數不能超過其容量Bmax。對于每個形如Xi'的個體，其每一列編碼表示該轉盤下所分配的航班，將該轉盤所分配航班的到達時間按升序排序，以15 min為一個時段進行時段劃分。如：某轉盤分配的航班有7個，到達時間為{2， 10， 15， 25， 30， 40， 50}（單位：min），根據規則可以將該7個航班分為3組，分別是{2， 10， 15}、{25， 30， 40}和{50}，分別計算每組中所對應航班的行李數之和是否超過Bmax，此時懲罰量計算公式為：

（11）

第二種措施是對不可行解進行修復操作：

（1）航班分配約束修復：對于i∈A，如果，則執行以下操作：若，則隨機生成一個整數j∈B，并將xij設為1，即將第i個航班分配到第j個轉盤；如果，則找出所有分配的轉盤索引Ji={j|xij=1}，然后隨機選擇一個索引j∈Ji，并保持xij為1，將其余索引下的編碼置為0。

（2）轉盤容量約束修復：對于每個形如式（6）的個體Xi'，對每個轉盤上分配的航班到達時間進行分段，計算每個時段下所對應航班的行李數之和，如果超過Bmax，則隨機選取移除該分段中的一個航班，并將其重新分配到行李數最少的一個轉盤中去。

通過以上措施，可以很好地保證所求解得到的方案能滿足所有約束條件。算法求解流程如圖1所示。

3 算例仿真

為驗證文中提出的模型和算法的有效性和優越性，設計了一個算例仿真實驗，并對實驗結果進行分析。航班數據采用文獻[4]中的原始數據，該機場10：00—11：00共有

40個航班到達，機場航站樓共有6個提取轉盤，數據中包括了40個航班的到達時間和行李數，每個轉盤在一個時段內能處理的最大行李數Bmax為300。但該數據集中無各登機口到各轉盤的步行距離，因此需要增加各到達航班距各轉盤的步行距離數據。登機口到行李轉盤的距離因機場而異，但一般來說都會盡量方便乘客，通常距離在數十米到一百米。為完成仿真實驗，文中從[20， 85]區間隨機生成了各航班距登機口各轉盤的步行距離數據，見表2所列。

算法參數設置：種群規模P=80，迭代次數Gmax=1 500，最終變異尺度F0=0.25，交叉概率CR=0.2。目標函數中的權重系數λ1、λ2取（λ1=1， λ2=0）、（λ1=0， λ2=1）和（λ1=1， λ2=1），分別表示僅優化行李均衡性目標、僅優化旅客步行距離目標和同時優化兩個目標。仿真實驗在MATLAB 2016b環境下進行，硬件平臺為Core i7 2.3G + 16G RAM。MATLAB環境下，程序的運行時間約為5.5 s；在C或Java環境下，代碼的執行時間將更短，大致可做到航班提取轉盤的實時指派。

針對每種優化權重，采用所提算法分別求解并將結果列于表3和表4。表3中給出的是各種目標權重下的優化目標值和6個轉盤中的最大、最小行李服務件數。表4中給出的是各優化目標權重下得到的各轉盤的服務行李數和行李數極差。

從表3和表4中可以看出，方差和步行距離兩個目標有一定的沖突，當僅優化方差時，得到的步行距離最大，但方差和最大行李件數最小。當僅優化步行距離時，結果正好與前者相反。而同時優化兩個目標時，得到的結果介于前面兩種情況之間。

圖2所示為優化方差目標的算法尋優過程，可以看出，算法約在800次迭代時收斂。需要指出的是，圖2中目標值是在施加了約束違反懲罰后的值，所以算法迭代開始時目標函數值較大，但最終得到的解必然不能含有任何約束懲罰量。同時，表5給出了方差最優下的各航班轉盤分配結果。

為驗證文中算法的優越性，將文獻[4]和文獻[6]的結果與文中結果進行對比，結果見表6所列。

從表6中可以看出，文中算法所求得的結果在方差指標上要優于其他兩種方法。同時，文中所求的解嚴格滿足約束條件。而對比方法中的解則可能有違反約束的情況，如文

獻[4]中的結果顯示，27～30號航班（這4個航班先后在

5 min內到達）均指派5號轉盤為其服務，但4個航班的行李總和為381，明顯超過了由Bmax所限制的300。文獻[6]中也有類似的情況。但文中通過對目標函數值施加合適的懲罰和不可行解修復機制，有效保證了解的可行性。

4 結 語

文中對航空行李提取轉盤分配問題進行了深入研究，建立了一個綜合考慮行李均衡性和旅客步行距離的優化模型，并提出了一種基于二進制DE算法的求解方法。在求解過程中采用兩個措施來保證約束條件得到滿足，即對約束違反量施加懲罰和對不可行解進行修復操作。文中通過一個算例仿真實驗，展示了所提方法的尋優過程和優化結果，并與文獻中的方法進行了對比分析。結果表明，文中方法在方差指標上優于其他兩種方法，同時也能保證解的可行性。該研究為BCAP提供了一種新的思路和方法，也為其他類似問題的研究提供了參考。

參考文獻

[1] BARTH T C，PISINGER D. Baggage carousel assignment at airports：model and case study [C]// Operations Research Forum. Springer International Publishing. [S.l.]：[s.n.]，2021：1-27.

[2] CECEN R K. Multi-objective optimization model for airport gate assignment problem [J]. Aircraft engineering and aerospace technology，2021，93（2）：311-318.

[3] BARTH T C，HOLM J T，LARSEN J L，et al. Optimization of transfer baggage handling in a major transit airport [C]// Operations Research Forum. [S.l.]：Springer International Publishing，2021：1-35.

[4]陸迅，朱金福，覃義，等. 航站樓旅客行李提取轉盤指派問題[J]. 南京航空航天大學學報，2009，41（2）：262-265.

[5]陸迅. 機場旅客與行李流程的規劃和仿真研究[D].南京：南京航空航天大學，2008.

[6]顏建影，石麗娜，黃自鵬.航站樓旅客行李提取轉盤的指派優化分析[J].物流科技，2021，44（1）：89-93.

[7] KAWACHI T，KUSHIDA J I，HARA A，et al. Efficient constraint handling based on the adaptive penalty method with balancing the objective function value and the constraint violation [C]// 2019 IEEE 11th International Workshop on Computational Intelligence and Applications（IWCIA）. [S.l.]：IEEE，2019：121-128.

[8]申培萍，吳殿曉，王亞飛.全局求解線性多乘積規劃的分支定界算法[J].應用數學，2023，36（2）：290-294.

[9]朱永利，劉剛，黃政，等.基于二進制微分進化算法和目標函數分解的大規模機組組合求解[J].電力自動化設備，2019，39（10）：1-8.

[10]劉明凱，王占山，邢彥麗.基于強化多目標差分進化算法的電-氣互聯系統最優潮流計算[J].電工技術學報，2021，36（11）：2220-2232.

[11] JENA C，BASU M，PANIGRAHI C K. Improved differential evolution for combined heat and power economic dispatch [J]. International journal of emerging electric power systems，2016，17（2）：151-163.

收稿日期：2023-08-29 修回日期：2023-10-10

基金項目：貴州省科技廳科學技術基金項目（黔科合基礎-ZK [2022]一般178）；貴州開放大學科研重點項目（2023 ZD05）

作者簡介：劉 剛（1985—），男，貴州貴陽人，博士，副教授，研究方向為數據挖掘、機器學習、智能優化算法及其應用。

喻紅中（1984—），男，副教授，研究方向為航空機械設計與加工。