顏建影 石麗娜 黃自鵬

摘? 要：我國機(jī)場(chǎng)旅客吞吐量的不斷增長(zhǎng)導(dǎo)致航站樓內(nèi)運(yùn)行資源越發(fā)緊張。為提高旅客行李提取轉(zhuǎn)盤運(yùn)行效率，將遺傳算法用于行李提取轉(zhuǎn)盤分配問題中，以行李提取轉(zhuǎn)盤的均衡使用為目標(biāo)函數(shù)，根據(jù)函數(shù)模型，設(shè)計(jì)遺傳算法求解步驟，并采用MATLAB進(jìn)行仿真分析。與采用蟻群算法的行李提取轉(zhuǎn)盤指派方式的結(jié)果進(jìn)行對(duì)比，表明在優(yōu)化行李提取轉(zhuǎn)盤分配和使用效率問題上，遺傳算法比蟻群算法的指派方式更優(yōu)，達(dá)到了目標(biāo)要求，提供了一種為解決機(jī)場(chǎng)行李提取轉(zhuǎn)盤指派問題的可行方法。

關(guān)鍵詞：航空運(yùn)輸;行李提取轉(zhuǎn)盤;遺傳算法;指派

中圖分類號(hào)：F560? ? 文獻(xiàn)標(biāo)識(shí)碼：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? 引? 言

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

從上述研究成果不難發(fā)現(xiàn)，已有的研究主要針對(duì)行李分揀站方面，盡管國內(nèi)外一些學(xué)者對(duì)離港行李提取區(qū)域進(jìn)行過研究，但對(duì)行李提取轉(zhuǎn)盤指派問題的研究卻不多。事實(shí)上，行李提取轉(zhuǎn)盤的分配問題是至關(guān)重要的，從某種程度上來看，將會(huì)對(duì)是否應(yīng)用均衡以及運(yùn)行效率產(chǎn)生重要影響，最后關(guān)系到總體的運(yùn)營效率。所以，本文采用遺傳算法對(duì)行李提取轉(zhuǎn)盤指派問題進(jìn)行仿真優(yōu)化研究，并將計(jì)算結(jié)果與采用蟻群算法的指派方式結(jié)果進(jìn)行比較，以驗(yàn)證本文設(shè)計(jì)遺傳算法的有效性。

1? 行李提取轉(zhuǎn)盤問題

1.1? 行李提取區(qū)域運(yùn)行效率的影響因素

美國交通運(yùn)輸研究委員調(diào)查得出行李提取轉(zhuǎn)盤的指派直接影響行李提取區(qū)域的運(yùn)行效率，即主要影響行李提取區(qū)域等待旅客的擁擠程度與可用空間。因此對(duì)行李轉(zhuǎn)盤的分配優(yōu)化是有必要的。

當(dāng)前，在指派行李轉(zhuǎn)盤時(shí)，比較常見的方法有以下兩種，即：1∶1模式，即一個(gè)行李提取轉(zhuǎn)盤服務(wù)一個(gè)航班;1∶N模式，即一個(gè)行李提取轉(zhuǎn)盤服務(wù)于多個(gè)航班。綜上分析，基于實(shí)際大型樞紐機(jī)場(chǎng)考慮，當(dāng)前機(jī)場(chǎng)航班和行李轉(zhuǎn)盤的分配主要是這兩種方式結(jié)合的形式。因此，本文指派模型的建立主要基于這兩種方式。

1.2? 模型目標(biāo)函數(shù)的選擇

通過上述對(duì)行李轉(zhuǎn)盤區(qū)域進(jìn)行分析后發(fā)現(xiàn)，由于各個(gè)轉(zhuǎn)盤之間，相對(duì)距離比較小，一旦行李提取轉(zhuǎn)盤使用不均，會(huì)使行李負(fù)擔(dān)較大的提取轉(zhuǎn)盤旁旅客擁擠，同時(shí)相比其他負(fù)擔(dān)較少的轉(zhuǎn)盤運(yùn)行時(shí)間變長(zhǎng)，而行李負(fù)擔(dān)相對(duì)較少的轉(zhuǎn)盤，則會(huì)造成閑置，造成整體效率降低。因此，模型的目標(biāo)就是行李提取轉(zhuǎn)盤的使用均衡，進(jìn)而達(dá)到提高運(yùn)行效率和旅客滿意度，使區(qū)域內(nèi)資源得到充分利用。

1.3? 模型建立

經(jīng)上文研究后可知，本文轉(zhuǎn)盤指派問題采用的目標(biāo)函數(shù)即為行李提取轉(zhuǎn)盤的負(fù)荷均衡，也就是說，采取一系列的優(yōu)化指派，使得行李最多的轉(zhuǎn)盤行李件數(shù)盡可能小。

問題模型具體如下所示：

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）內(nèi)，I=p∈U|T-T<15， p≥15，Ti∈U指的是第i個(gè)航班的抵達(dá)時(shí)間，I指的是全部和第k個(gè)航班的抵達(dá)時(shí)間相差低于15min的全部航班的集合。設(shè)一個(gè)航班占用轉(zhuǎn)盤的時(shí)間為15min。

式（1）表示使行李件數(shù)最多的轉(zhuǎn)盤上的行李件數(shù)盡可能最小，以達(dá)到均衡每個(gè)提取轉(zhuǎn)盤負(fù)荷的目的。

式（2）指的是各個(gè)到達(dá)航班僅可以在一個(gè)轉(zhuǎn)盤上進(jìn)行分配。

式（3）可知，在相同時(shí)段，一個(gè)轉(zhuǎn)盤將會(huì)被很多航班占用，但是總體的行李件數(shù)應(yīng)低于一個(gè)轉(zhuǎn)盤的最大容量。

式（4）指的是參數(shù)值所取范圍。

在這一模型中，所采用的符號(hào)與參數(shù)定義具體如下所述，即：

U：指派時(shí)間段T內(nèi)進(jìn)港航班集合，U>0，U=1，2，…，M;

V：指派時(shí)間段T內(nèi)可以應(yīng)用行李轉(zhuǎn)盤集合，V>0，V=1，2，…，N;

T：第i個(gè)航班的到達(dá)時(shí)間，i∈U;

v：第i個(gè)航班托運(yùn)行李件數(shù)，i∈V;

v：行李提取轉(zhuǎn)盤在15分鐘內(nèi)可以同時(shí)提供服務(wù)的行李數(shù)的最大值，按照相關(guān)規(guī)定得出，本研究所設(shè)定的行李數(shù)為300件;

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

2? 轉(zhuǎn)盤指派問題算法設(shè)計(jì)

2.1? 指派問題的遺傳算法

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

2.2? 遺傳算法實(shí)現(xiàn)

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

（1）染色體編碼

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

例如：在一段時(shí)間內(nèi)，按照航班到達(dá)時(shí)間順序共有40個(gè)航班先后到達(dá)，行李提取轉(zhuǎn)盤共有6個(gè)，按照自然數(shù)編碼染色體，染色體的長(zhǎng)度L為40，每一個(gè)基因的取值范圍為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個(gè)行李提取轉(zhuǎn)盤上;第2位的取值為2，表示第2架航班分配在第2個(gè)行李轉(zhuǎn)盤上，以此類推。

（2）種群初始化

初始種群的產(chǎn)生可通過計(jì)算機(jī)從可能解中以隨機(jī)方式產(chǎn)生設(shè)定數(shù)量的染色體，即第一代種群。

從可能解中隨機(jī)方式產(chǎn)生一個(gè)染色體，若該染色體滿足模型中全部約束條件，則該個(gè)體稱為解染色體，若該染色體不滿足全部約束條件，則該染色體稱為非解染色體。最初解染色體的全體稱為初始種群，初始種群中解染色體的個(gè)體數(shù)稱為種群規(guī)模[10]。

2.2.2? 適應(yīng)度函數(shù)及選擇算子

（1）適應(yīng)度函數(shù)

因?yàn)槟Ｐ椭心繕?biāo)函數(shù)為求最小值，而遺傳算法適應(yīng)度函數(shù)為求最大值，可采用取倒數(shù)的方式，故適應(yīng)度函數(shù)為：

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

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

在組合優(yōu)化問題中，處理不可行解的一種常用方法即為懲罰函數(shù)法[11]，因此其適應(yīng)度函數(shù)優(yōu)化后設(shè)計(jì)如下：

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

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

（2）選擇算子

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

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

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

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

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

式中：Q為染色體n的累計(jì)概率;P為個(gè)體r被選擇的概率。

算法每次選擇時(shí)都會(huì)產(chǎn)生一個(gè)在0，1內(nèi)的均勻隨機(jī)數(shù)d，該隨機(jī)數(shù)將作為確定被選染色體遺傳到下一代的選擇指針。若d

例如：設(shè)規(guī)模為pop=5的種群S=nnnnn，染色體適應(yīng)度F=20，F(xiàn)=17，F(xiàn)=10，F(xiàn)=29，F(xiàn)=16，染色體的選擇概率Pn=1，2，…，5，其計(jì)算結(jié)果如下：P=0.21，P=0.18，P=0.10，P=0.32，P=0.17。

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

通過轉(zhuǎn)動(dòng)輪盤5次，每次在0，1之間產(chǎn)生一個(gè)均勻隨機(jī)數(shù)，得到5個(gè)隨機(jī)數(shù)為：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? 交叉算子

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

本文采用單點(diǎn)交叉進(jìn)行交叉操作，如表1所示。兩個(gè)父代染色體的交叉操作，首先通過隨機(jī)方式產(chǎn)生一個(gè)整數(shù)i，0

2.2.4? 變異算子

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

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

2.2.5? 運(yùn)行參數(shù)

編碼長(zhǎng)度L：L=40。

種群規(guī)模S：規(guī)模大小的選取，既要考慮種群多樣性也要考慮運(yùn)行時(shí)間，本文取S=200。

交叉概率P：既要保證以較快的速度發(fā)現(xiàn)新個(gè)體，也要兼顧保護(hù)種群中已形成的優(yōu)良個(gè)體，一般取值為0.40～0.99，因此本文取P=0.90。

變異概率：較小的變異概率對(duì)于避免早熟現(xiàn)象和增加新個(gè)體的能力會(huì)較差，較大的變異概率隨機(jī)性過高，一般取值范圍為0.005～0.100，本文取0.010。

迭代代數(shù)：算法運(yùn)行結(jié)束的條件之一，一般取100～1 000，本文最大迭代次數(shù)為200次。

2.3? 遺傳算法的步驟

在進(jìn)行操作的過程中，全部航班以及轉(zhuǎn)盤，根據(jù)前文的算法進(jìn)行設(shè)計(jì)，具體步驟如下所述，即：

Step1：將航班的基本信息輸入至其中，行李提取轉(zhuǎn)盤信息，算法參數(shù);

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

=1;

Step3：計(jì)算染色體適應(yīng)值，對(duì)種群染色體適應(yīng)值進(jìn)行評(píng)價(jià);

Step4：判斷終止條件：滿足，將會(huì)得到相應(yīng)的群體適應(yīng)值，將最優(yōu)結(jié)果輸出之后，完成算法：不滿足，則令g=g+1，繼續(xù)執(zhí)行以下步驟;

Step5：對(duì)算法群體執(zhí)行遺傳操作：采用輪盤賭方法選擇算子，選擇出適應(yīng)度較大的個(gè)體，進(jìn)行交叉變異，產(chǎn)生新一代種群群體，返至Step3。

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

3? 算例仿真與分析

本文采用的算例以文獻(xiàn)[5]中的數(shù)據(jù)為原始數(shù)據(jù)，機(jī)場(chǎng)航站樓共有旅客行李提取轉(zhuǎn)盤6個(gè)，根據(jù)航班時(shí)刻表，40個(gè)航班先后從10：00到11：00到達(dá)，各個(gè)航班到達(dá)時(shí)間和行李件數(shù)如表3所示。

該文獻(xiàn)采用的蟻群算法指派方式，得到的結(jié)果如表4所示。

與本文設(shè)計(jì)的遺傳算法相結(jié)合，通過對(duì)MATLAB 求解程序進(jìn)行編寫之后，解本實(shí)例。設(shè)置種群規(guī)模為200，交叉概率P

=0.90，變異概率P=0.01，最大迭代次數(shù)為200次，得到遺傳算法最優(yōu)點(diǎn)變化趨勢(shì)圖，如圖2所示。對(duì)行李提取轉(zhuǎn)盤指派的結(jié)果如表5所示。

對(duì)遺傳算法和蟻群算法兩種結(jié)果進(jìn)行對(duì)比分析后，結(jié)果如表6所示。

根據(jù)表6中的對(duì)比結(jié)果，采用遺傳算法得到的服務(wù)行李件數(shù)的極差為20，比蟻群算法縮小了約2.5倍。均方差是334，比蟻群算法縮小了約5.5倍，均低于蟻群算法指派結(jié)果。表明各個(gè)行李提取轉(zhuǎn)盤的行李數(shù)量更均衡，達(dá)到了預(yù)期的目標(biāo)。說明了本文對(duì)行李提取轉(zhuǎn)盤指派問題的優(yōu)化采用遺傳算法是可行的。

4? 結(jié)? 論

本文為機(jī)場(chǎng)旅客行李提取轉(zhuǎn)盤指派問題的優(yōu)化研究，依據(jù)相應(yīng)的指派模型，其目標(biāo)以均衡使用行李提取轉(zhuǎn)盤，對(duì)遺傳算法求解步驟進(jìn)行了設(shè)計(jì)。通過實(shí)例結(jié)果分析，表明遺傳算法對(duì)于優(yōu)化行李提取轉(zhuǎn)盤分配的可行性和優(yōu)越性，提出了一種對(duì)解決機(jī)場(chǎng)旅客行李提取轉(zhuǎn)盤指派問題的可行方法，為機(jī)場(chǎng)服務(wù)質(zhì)量的提升提供了參考。

參考文獻(xiàn)：

[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ī)場(chǎng)行李分揀站的分配優(yōu)化研究[J]. 機(jī)械工程與自動(dòng)化，2017（5）：37-39.

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

[4] 陸迅，朱金福，唐小衛(wèi). 多航班多行李提取模型[J]. 交通運(yùn)輸工程學(xué)報(bào)，2008，8（5）：104-108.

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

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

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

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

[9] 李明. 遺傳算法的改進(jìn)及其在優(yōu)化問題中的應(yīng)用研究[D]. 長(zhǎng)春：吉林大學(xué)（碩士學(xué)位論文），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遺傳算法工具箱及應(yīng)用[M]. 西安：西安電子科技大學(xué)出版社，2014.