航站樓旅客行李提取轉盤的指派優化分析

顏建影 石麗娜 黃自鵬

摘? 要：我國機場旅客吞吐量的不斷增長導致航站樓內運行資源越發緊張。為提高旅客行李提取轉盤運行效率，將遺傳算法用于行李提取轉盤分配問題中，以行李提取轉盤的均衡使用為目標函數，根據函數模型，設計遺傳算法求解步驟，并采用MATLAB進行仿真分析。與采用蟻群算法的行李提取轉盤指派方式的結果進行對比，表明在優化行李提取轉盤分配和使用效率問題上，遺傳算法比蟻群算法的指派方式更優，達到了目標要求，提供了一種為解決機場行李提取轉盤指派問題的可行方法。

關鍵詞：航空運輸;行李提取轉盤;遺傳算法;指派

中圖分類號：F560? ? 文獻標識碼：A

Abstract： With the continuous increase of passenger through put of airports in China， the operating resources in the terminal are becoming more and more tight. In order to improve the operating efficiency of luggage claiming turntables， genetic algorithm was applied and the balanced use of luggage claiming turntables was taken as the objective function. According to function model， genetic algorithm solution steps were designed， and MATLAB was used for simulation analysis. The results show that the genetic algorithm was more efficient than the ant colony algorithm in optimizing the claiming turntables allocation and service efficiency. The target requirement was satisfied， and a feasible method to solve the problem of airport luggage claiming turntables assignment was provided.

Key words： air transportation; luggage claiming tables; genetic algorithm; assignment

0? 引? 言

我國民航經濟的快速發展帶動了機場客流的迅猛增長，2019年我國機場旅客吞吐量達到了12.6億人次，作為到港旅客流程的重要環節——行李提取，未能合理、便捷、高效處理，已成為近幾年影響機場運行和旅客滿意度的重要因素。而且目前大多數機場行李提取轉盤規模仍維持原有規模，吞吐量的增加不僅加劇了行李提取問題的難度和復雜性，而且降低了機場的運行效率。因此，優化行李提取問題，對于航空公司和機場都有著重要意義。Ascó等人對離港行李分揀站整體進行了研究，得出工作均衡和緩沖時間是影響行李分揀站效率的關鍵因素，然后使用進化算法以工作均衡和緩沖時間最短為模型進行求解，以獲得優化分配方案[1]。蔡翔針對大型樞紐機場行李分揀站的實際運行需求，提出了一種行李分揀站的分配優化模型，并采用活動選擇算法求解該模型，以獲得優化的分配方案[2]。De Neufville和Odoni則通過對行李提取區域進行研究后發現，行李提取傳送帶的長度尤為關鍵，而且也是不可缺少的一項影響要素[3]。陸訊通過對離港行李提取區域進行研究，表明行李提取轉盤的分配，是影響行李提取區域擁擠問題的關鍵，并設計了蟻群算法來解決行李提取轉盤的分配問題[4-5]。

從上述研究成果不難發現，已有的研究主要針對行李分揀站方面，盡管國內外一些學者對離港行李提取區域進行過研究，但對行李提取轉盤指派問題的研究卻不多。事實上，行李提取轉盤的分配問題是至關重要的，從某種程度上來看，將會對是否應用均衡以及運行效率產生重要影響，最后關系到總體的運營效率。所以，本文采用遺傳算法對行李提取轉盤指派問題進行仿真優化研究，并將計算結果與采用蟻群算法的指派方式結果進行比較，以驗證本文設計遺傳算法的有效性。

1? 行李提取轉盤問題

1.1? 行李提取區域運行效率的影響因素

美國交通運輸研究委員調查得出行李提取轉盤的指派直接影響行李提取區域的運行效率，即主要影響行李提取區域等待旅客的擁擠程度與可用空間。因此對行李轉盤的分配優化是有必要的。

當前，在指派行李轉盤時，比較常見的方法有以下兩種，即：1∶1模式，即一個行李提取轉盤服務一個航班;1∶N模式，即一個行李提取轉盤服務于多個航班。綜上分析，基于實際大型樞紐機場考慮，當前機場航班和行李轉盤的分配主要是這兩種方式結合的形式。因此，本文指派模型的建立主要基于這兩種方式。

1.2? 模型目標函數的選擇

通過上述對行李轉盤區域進行分析后發現，由于各個轉盤之間，相對距離比較小，一旦行李提取轉盤使用不均，會使行李負擔較大的提取轉盤旁旅客擁擠，同時相比其他負擔較少的轉盤運行時間變長，而行李負擔相對較少的轉盤，則會造成閑置，造成整體效率降低。因此，模型的目標就是行李提取轉盤的使用均衡，進而達到提高運行效率和旅客滿意度，使區域內資源得到充分利用。

1.3? 模型建立

經上文研究后可知，本文轉盤指派問題采用的目標函數即為行李提取轉盤的負荷均衡，也就是說，采取一系列的優化指派，使得行李最多的轉盤行李件數盡可能小。

問題模型具體如下所示：

F=minmaxXV? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （1）

s.t. x=1， ？坌i∈U? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（2）

xv≤v， k∈U， j∈V? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （3）

x∈0，1， i∈U， j∈V? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（4）

式（3）內，I=p∈U|T-T<15， p≥15，Ti∈U指的是第i個航班的抵達時間，I指的是全部和第k個航班的抵達時間相差低于15min的全部航班的集合。設一個航班占用轉盤的時間為15min。

式（1）表示使行李件數最多的轉盤上的行李件數盡可能最小，以達到均衡每個提取轉盤負荷的目的。

式（2）指的是各個到達航班僅可以在一個轉盤上進行分配。

式（3）可知，在相同時段，一個轉盤將會被很多航班占用，但是總體的行李件數應低于一個轉盤的最大容量。

式（4）指的是參數值所取范圍。

在這一模型中，所采用的符號與參數定義具體如下所述，即：

U：指派時間段T內進港航班集合，U>0，U=1，2，…，M;

V：指派時間段T內可以應用行李轉盤集合，V>0，V=1，2，…，N;

T：第i個航班的到達時間，i∈U;

v：第i個航班托運行李件數，i∈V;

v：行李提取轉盤在15分鐘內可以同時提供服務的行李數的最大值，按照相關規定得出，本研究所設定的行李數為300件;

x：0-1型變量，基于第i個航班的行李考慮，如果被分配至第j個轉盤，那么則等于1，不然則是0。

2? 轉盤指派問題算法設計

2.1? 指派問題的遺傳算法

遺傳算法是當今所有進化計算的隨機搜索和優化算法中最常用的。它不依賴于問題的某一特定領域，為解決復雜的系統優化問題提供了一個通用模式[6-7]。行李轉盤分配問題在運籌學中屬于NP難問題，NP難問題關于多項式時間的算法很難發現，若采用傳統的算法，其計算量和計算難度將會成倍增加，因此運用更加快速有效的算法去解決這類問題變得越來越重要[8]。而遺傳算法就具有解決此類問題的特有優勢，通常直接選取目標函數做為適應度函數，并且對所研究的問題類型魯棒性非常的強。其算法主要包括最優適應度的選擇和遺傳算子的選取，基于此將設計一種遺傳算法用來解決該轉盤的指派問題。

2.2? 遺傳算法實現

2.2.1? 染色體編碼和種群初始化

（1）染色體編碼

本文染色體設計使用自然數編碼，相比于二進制編碼來說，該編碼可以使各種問題得到有效解決，而且遺傳算子操作也更加方便[9]。在對行李轉盤進行編碼的過程中，如果采用了非零自然數，基因則是行李轉盤，按照每個航班抵達的時間次序，構成相應的染色體，其中第i位的取值表示第i架航班所分配的行李轉盤。

例如：在一段時間內，按照航班到達時間順序共有40個航班先后到達，行李提取轉盤共有6個，按照自然數編碼染色體，染色體的長度L為40，每一個基因的取值范圍為1～6，如X染色體：

染色體X：3 2 4 5 3 2 4 1 6 3 2 5 4 1 6 2 1 3 1 5 6 4 2 3 1 3 1 4 5 6 4 1 5 6 4 1 3 1 6 5

其中：第1位的取值為3，就是表示第1架航班分配在第3個行李提取轉盤上;第2位的取值為2，表示第2架航班分配在第2個行李轉盤上，以此類推。

（2）種群初始化

初始種群的產生可通過計算機從可能解中以隨機方式產生設定數量的染色體，即第一代種群。

從可能解中隨機方式產生一個染色體，若該染色體滿足模型中全部約束條件，則該個體稱為解染色體，若該染色體不滿足全部約束條件，則該染色體稱為非解染色體。最初解染色體的全體稱為初始種群，初始種群中解染色體的個體數稱為種群規模[10]。

2.2.2? 適應度函數及選擇算子

（1）適應度函數

因為模型中目標函數為求最小值，而遺傳算法適應度函數為求最大值，可采用取倒數的方式，故適應度函數為：

F=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（5）

式中：f=xv，F表示每個染色體適應度的大小，F越大表示其可行解越好，越能夠以較大概率遺傳到下一代群體中。

在組合優化問題中，處理不可行解的一種常用方法即為懲罰函數法[11]，因此其適應度函數優化后設計如下：

F=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（6）

式中：ξ=ρPn為懲罰函數，本文中Pn=max0，xv-v，ρ為懲罰因子，本文中取ρ=4。

（2）選擇算子

為了使種群的優良基因得到保證，選擇算子增大父代適應度值大的個體遺傳到下一代的幾率，從而促使種群個體可以與最優解靠攏。本文在研究的過程中，采用了輪盤賭的方式進行處理。

P=? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （7）

式中：P為染色體n被選擇的概率;F為染色體n適應度函數值;n為染色體n=1，2，…，S;S為種群大小。

式中得出，如果適應度值比較高，那么遺傳到下一代的幾率也會隨之加大。在此過程中，通過多次選擇來選取遷移染色體，其中累計概率為：

Q=P? ? r=1，2，…，n? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? （8）

式中：Q為染色體n的累計概率;P為個體r被選擇的概率。

算法每次選擇時都會產生一個在0，1內的均勻隨機數d，該隨機數將作為確定被選染色體遺傳到下一代的選擇指針。若d

例如：設規模為pop=5的種群S=nnnnn，染色體適應度F=20，F=17，F=10，F=29，F=16，染色體的選擇概率Pn=1，2，…，5，其計算結果如下：P=0.21，P=0.18，P=0.10，P=0.32，P=0.17。

則每個染色體的累加概率Q，結果如下：Q=0.21，Q=0.41，Q=0.52，Q=0.83，Q=1.0。

通過轉動輪盤5次，每次在0，1之間產生一個均勻隨機數，得到5個隨機數為：d=0.23，d=0.57，d=0.79，d=0.93，

d=0.35。

先從d=0.23開始觀察，位于Q與Q之間，因此選擇染色體Q遺傳到下一代;接著d=0.57位于QQ之間，因此選擇染色體Q遺傳到下一代;依次下去，新種群S=nnnnn。

2.2.3? 交叉算子

在遺傳算法中，通過交叉操作來模擬自然界生物進化過程中的基因重組，以此希望進化出更為優良的下一代個體，得到想要最優解的同時能夠以更快更好的方式。

本文采用單點交叉進行交叉操作，如表1所示。兩個父代染色體的交叉操作，首先通過隨機方式產生一個整數i，0

2.2.4? 變異算子

在種群規模一定下的遺傳算法，其廣度搜索能力越強，種群的多樣性就要越大。因此增大群體多樣性，擴展搜索空間，從而避免早熟，是變異算子的主要工作目標，本文采用適用于自然數編碼的交換變異實現變異操作。隨機產生兩個變異變量i，ji，j≤L，交換第i個航班與第j個航班的基因位，如表2所示。

即首先對于需要變異操作的父代染色體W以一定的概率選取，再以隨機方式選取該染色體的兩個基因位i，j1≤i， j≤L，通過交換該兩個基因位上的基因，新的染色體W從而形成。

2.2.5? 運行參數

編碼長度L：L=40。

種群規模S：規模大小的選取，既要考慮種群多樣性也要考慮運行時間，本文取S=200。

交叉概率P：既要保證以較快的速度發現新個體，也要兼顧保護種群中已形成的優良個體，一般取值為0.40～0.99，因此本文取P=0.90。

變異概率：較小的變異概率對于避免早熟現象和增加新個體的能力會較差，較大的變異概率隨機性過高，一般取值范圍為0.005～0.100，本文取0.010。

迭代代數：算法運行結束的條件之一，一般取100～1 000，本文最大迭代次數為200次。

2.3? 遺傳算法的步驟

在進行操作的過程中，全部航班以及轉盤，根據前文的算法進行設計，具體步驟如下所述，即：

Step1：將航班的基本信息輸入至其中，行李提取轉盤信息，算法參數;

Step2：編碼染色體，采用隨機的方式，形成初始種群，設置最大迭代次數及迭代計數器[12]。令遺傳代數初始化，初始令g

=1;

Step3：計算染色體適應值，對種群染色體適應值進行評價;

Step4：判斷終止條件：滿足，將會得到相應的群體適應值，將最優結果輸出之后，完成算法：不滿足，則令g=g+1，繼續執行以下步驟;

Step5：對算法群體執行遺傳操作：采用輪盤賭方法選擇算子，選擇出適應度較大的個體，進行交叉變異，產生新一代種群群體，返至Step3。

遺傳算法具體流程圖如圖1所示。

3? 算例仿真與分析

本文采用的算例以文獻[5]中的數據為原始數據，機場航站樓共有旅客行李提取轉盤6個，根據航班時刻表，40個航班先后從10：00到11：00到達，各個航班到達時間和行李件數如表3所示。

該文獻采用的蟻群算法指派方式，得到的結果如表4所示。

與本文設計的遺傳算法相結合，通過對MATLAB 求解程序進行編寫之后，解本實例。設置種群規模為200，交叉概率P

=0.90，變異概率P=0.01，最大迭代次數為200次，得到遺傳算法最優點變化趨勢圖，如圖2所示。對行李提取轉盤指派的結果如表5所示。

對遺傳算法和蟻群算法兩種結果進行對比分析后，結果如表6所示。

根據表6中的對比結果，采用遺傳算法得到的服務行李件數的極差為20，比蟻群算法縮小了約2.5倍。均方差是334，比蟻群算法縮小了約5.5倍，均低于蟻群算法指派結果。表明各個行李提取轉盤的行李數量更均衡，達到了預期的目標。說明了本文對行李提取轉盤指派問題的優化采用遺傳算法是可行的。

4? 結? 論

本文為機場旅客行李提取轉盤指派問題的優化研究，依據相應的指派模型，其目標以均衡使用行李提取轉盤，對遺傳算法求解步驟進行了設計。通過實例結果分析，表明遺傳算法對于優化行李提取轉盤分配的可行性和優越性，提出了一種對解決機場旅客行李提取轉盤指派問題的可行方法，為機場服務質量的提升提供了參考。

參考文獻：

[1]? Ascó A， Atkin J A D， Burke E K. The airport baggage sorting station allocation problem[C] // Proceedings of the 5th Multidisciplinary International Conference on Scheduling： Theory and Application （MISTA 2011）. USA： [s.n.]， 2011：419-444.

[2] 蔡翔. 機場行李分揀站的分配優化研究[J]. 機械工程與自動化，2017（5）：37-39.

[3] Neufville D， Odoni. Airport Systems： Planning， Design， and Management[M]. McGraw-Hill Professional， 2000：63-68.

[4] 陸迅，朱金福，唐小衛. 多航班多行李提取模型[J]. 交通運輸工程學報，2008，8（5）：104-108.

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

[6] 李險峰. 基于改進遺傳算法的汽車裝配生產線平衡問題研究[D]. 北京：北京科技大學（博士學位論文），2017.

[7] 陳宵. DNA遺傳算法及應用研究[D]. 杭州：浙江大學（博士學位論文），2010.

[8] 黃文奇，許如初. 近世計算理論導引：NP難度問題的背景、前景及其求解算法研究[M]. 北京：科學出版社，2004：87-88.

[9] 李明. 遺傳算法的改進及其在優化問題中的應用研究[D]. 長春：吉林大學（碩士學位論文），2004.

[10]? TAO Y， TANG D， SHEN H. Design and implementation of USB key-based Java EE dual-factor authentication system[C]

// Proceed-ings of the 2009 International Conference on Information Manage-ment， Innovation Management and Industrial Engineering. Wash-ington， DC： IEEE Computer Society， 2009：443-446.

[11]? Kalyanmoy Deb. An efficient constraint handling method for genetic algorithms[J]. Computer Methods in Applied Mechanics and Engineering， 2000，186（2）：311-338.

[12] 雷英杰，張善文. MATLAB遺傳算法工具箱及應用[M]. 西安：西安電子科技大學出版社，2014.