基于文化基因算法的機(jī)組排班問題研究

◆陳肯 張廣偉

（中國民用航空飛行學(xué)院空中交通管理學(xué)院 四川 618300）

機(jī)組排班是根據(jù)航班計(jì)劃和機(jī)型屬性等要求，為航班指派相應(yīng)的機(jī)組人員（包括機(jī)長(zhǎng)、副駕駛、機(jī)械員、領(lǐng)航員、通信員等）并實(shí)施航班飛行任務(wù)的過程[1]。機(jī)組排班問題主要分為任務(wù)環(huán)生成（Crew pairing problem，CPP）和機(jī)組人員指派（Crew assignment problem，CAP)。CPP 問題主要是任務(wù)的生成，發(fā)現(xiàn)一組往返飛行航線并且覆蓋所有的航班。CAP 問題是任務(wù)的分配，主要是將已分割完成的任務(wù)派遣給各組機(jī)組人員執(zhí)行[2]。本文的研究主要針對(duì)機(jī)組排班中最核心的問題任務(wù)環(huán)生成（CPP）問題。

Budi Santosa[3]提出了一種基于遺傳算法的簡(jiǎn)單迭代變異(SIMA)方法來解決航空公司機(jī)組排班問題。在排班的質(zhì)量與時(shí)間上均取得較好結(jié)果。Frédéric Quesnel[4]提出了一種啟發(fā)式分支定價(jià)算法解決了帶有語言限制的機(jī)組排班問題。張米[5]系統(tǒng)分析提出了機(jī)組排班問題模型并考慮了延誤因素，運(yùn)用列生成算法計(jì)算，取得了較好的優(yōu)化結(jié)果。

本文提出了一種基于動(dòng)態(tài)文化基因算法的中型航空公司任務(wù)環(huán)配對(duì)問題的求解方法。目標(biāo)是找到成本最低的機(jī)組人員配對(duì)。

1 文化基因算法

機(jī)組排班問題是典型的NP_hard 問題，受系統(tǒng)復(fù)雜性和多種約束條件的限制[6], 求解非常困難，常用算法有分支定價(jià)算法、分支切割算法、列生成算法以及遺傳算法等啟發(fā)式算法。其中遺傳算法是求解機(jī)組排班問題的經(jīng)典算法，有著相對(duì)成熟的理論體系。本文選用遺傳算法的改進(jìn)算法文化基因算法進(jìn)行求解，遺傳算法已被大量運(yùn)用于此問題的研究中并證實(shí)效果顯著[7]。但標(biāo)準(zhǔn)遺傳算法會(huì)過早向目標(biāo)函數(shù)的局部最優(yōu)解收斂且算法對(duì)初始種群的選擇具有一定的依賴性[8]。而文化基因算法是一種基于種群的全局搜索和基于個(gè)體的局部啟發(fā)式搜索的結(jié)合算法。

文化基因算法是一種框架,可以采用不同的搜索策略可以構(gòu)成不同的文化基因算法,如全局搜索策略可以采用遺傳算法、進(jìn)化規(guī)劃等,局部搜索策略可以采用爬山搜索、貪婪算法、禁忌搜索等[9]。這種局部與全局的混合搜索機(jī)制可以在某些問題領(lǐng)域比傳統(tǒng)遺傳算法快幾個(gè)數(shù)量級(jí)。文化基因算法基本框架如圖1所示。

圖1 文化基因算法框架圖

2 問題模型

2.1 航空公司排班基本原則和約束

在機(jī)組排班過程的任務(wù)環(huán)生成階段，依據(jù)中國民航局制定的飛行運(yùn)行手冊(cè)和各民航公司內(nèi)部制定的排班規(guī)則[10]，來組合任務(wù)環(huán)。包括飛行時(shí)間限制、值勤時(shí)間限制、航段個(gè)數(shù)限制、人員搭配限制以及機(jī)組資源本身的限制。現(xiàn)將主要規(guī)則整理如表1所示：

表1 限制條件匯總

2.2 數(shù)學(xué)模型

通過分析國內(nèi)外機(jī)組排班流程算法的特點(diǎn)、我國民航局及航空公司的相關(guān)規(guī)定,構(gòu)建了機(jī)組排班問題的數(shù)學(xué)模型

式中cp代表任務(wù)環(huán)p的成本，包含機(jī)組的飛行津貼，撘機(jī)機(jī)組成本以及在外過夜成本[5]。xp是決策變量，0 代表任務(wù)環(huán)未被選中，1代表任務(wù)環(huán)被選中。afp=1 表示p任務(wù)環(huán)中包含i航班，否則afp=0。

式（1）目標(biāo)函數(shù)為最小化總?cè)蝿?wù)環(huán)成本。式（2）確保每個(gè)航班至少被覆蓋一次。式（3）限制了決策變量的可行域。

3 用深度搜索算法生成飛行任務(wù)環(huán)池（pairsALL）

本文利用啟發(fā)式算法來產(chǎn)生初始機(jī)組任務(wù)，事先考慮航班連接時(shí)的限制條件，在航班連接時(shí)避免了窮舉算法所有可能的無效率性，在處理實(shí)際問題時(shí)，可快速產(chǎn)生可行初始機(jī)組任務(wù)。

3.1 構(gòu)建航班網(wǎng)絡(luò)

構(gòu)建航班聯(lián)接的網(wǎng)絡(luò)圖時(shí)，需要考慮的因素包括航班聯(lián)接的物理地點(diǎn)約束與時(shí)間約束。前導(dǎo)航班與后續(xù)航班的起降時(shí)間滿足最短、最大轉(zhuǎn)換飛機(jī)時(shí)間約束，最短休息時(shí)間約束且前機(jī)的降落機(jī)場(chǎng)為后機(jī)的起飛機(jī)場(chǎng)本文便稱這兩個(gè)航班之間存在合法連接。對(duì)每個(gè)航班建立航班樹（圖2），運(yùn)用c++的鏈表結(jié)構(gòu)進(jìn)行編程，在以后碰到求航班的后續(xù)可行航班只要根據(jù)網(wǎng)絡(luò)查找下一個(gè)航班的航班樹，這樣可以減少計(jì)算量。本文構(gòu)建的航班連接的網(wǎng)絡(luò)圖示例如下：

圖2 航班網(wǎng)絡(luò)圖

1）節(jié)點(diǎn)。節(jié)點(diǎn)代表不同的航班。每個(gè)節(jié)點(diǎn)包含有航班的起止機(jī)場(chǎng)與時(shí)間信息。

2）連接線。每根連接線都代表節(jié)點(diǎn)與節(jié)點(diǎn)之間的合法連接，需要滿足包括時(shí)間、地點(diǎn)的約束等等。

如圖所示，圖中有三個(gè)航班樹，航班樹相連構(gòu)成航班網(wǎng)絡(luò)，航班1 的合法連接航班有3、4、5、6，航班3 的合法連接航班為4、6、7，航班6 的合法連接航班為2、8。在搜尋過程中，可以由航班1 的航班樹定位到航班6 的航班樹，可形成1、6、2 和1、6、8 兩個(gè)合法任務(wù)環(huán)，其余同理。

3.2 根據(jù)生成的勤務(wù)組組成飛行任務(wù)環(huán)池

任務(wù)環(huán)生成方法是一個(gè)遞歸的過程，借助3.1 提出的航班網(wǎng)絡(luò)，采用遞歸的方式進(jìn)行搜索。在第一階段，所有的航班都按照主要程序進(jìn)行審查。對(duì)于從基地開始的任務(wù)，將執(zhí)行搜索算法進(jìn)行遞歸，可以將符合條件的任務(wù)環(huán)加入到主集中。需要滿足的約束有：

時(shí)間約束：在外過夜不超過3 天，即同一個(gè)任務(wù)環(huán)最多包含4天的勤務(wù)

地點(diǎn)約束：下一個(gè)勤務(wù)起始的機(jī)場(chǎng)需要是上一個(gè)勤務(wù)終止的機(jī)場(chǎng)。

算法一：生成所有任務(wù)環(huán)

4 選擇初始子集（pairsActive）

本文利用啟發(fā)式算法生成一個(gè)隨機(jī)任務(wù)環(huán)子集（從主集中選擇），這個(gè)子集中包含的任務(wù)環(huán)可以覆蓋所有航班，并不要求初始子集為最優(yōu)子集，只需保證可行性，在后續(xù)會(huì)通過啟發(fā)式算法對(duì)子集進(jìn)行更新優(yōu)化。下面開發(fā)了一種啟發(fā)式算法來生成初始子集。偽代碼如下：

1 對(duì)每一個(gè)航班在任務(wù)環(huán)總集（pairAll）中搜索包含該航班的任務(wù)環(huán)加入到子集中（pairsActive）。

2 在航班集合中尋找下一個(gè)未被覆蓋航班。

3 重復(fù)1 步驟，直到所有航班均被覆蓋。

上述三小節(jié)是為了產(chǎn)生成用于生成染色體的任務(wù)環(huán)子集（pairsActive），該集合任務(wù)環(huán)將作為遺傳算法的解空間。該集合越大，迭代選取到最優(yōu)組合的概率越大，但會(huì)增加算法無效的計(jì)算量，選取合適數(shù)量的子集有助于減少迭代到最優(yōu)的次數(shù)。

5 文化基因算法

5.1 基因編碼

本文基因編碼采用01 編碼，每一個(gè)染色體位代表任務(wù)環(huán)總體中相對(duì)應(yīng)的任務(wù)環(huán)是否被選中，0 代表任務(wù)環(huán)未被選入，1 代表該任務(wù)環(huán)被選入。

5.2 生成初始種群

初始種群是文化基因算法的第一階段。這個(gè)群體中的每一條染色體都代表了該問題的一個(gè)可行解決方案。本文開發(fā)了一種啟發(fā)式方法覆蓋每一次飛行任務(wù)，生成一個(gè)可行的初始種群。

算法二：初始化種群

5.3 適應(yīng)度

適應(yīng)度采用最小化成本

式中cj代表任務(wù)環(huán)j的成本，包含飛行固有成本加機(jī)組責(zé)任時(shí)間成本。nj代表任務(wù)環(huán)j 包含的過夜次數(shù)，hj代表旅店成本，xj表示任務(wù)環(huán)是否包含在該染色體中，0 表示未包含，1 表示被包含。si代表單次航班i的花費(fèi)，yi表示i航班是否為撘機(jī)航班，若是則為1，不是則為0。aij表示航班i是否被任務(wù)環(huán)配f 包含，若是，則為1，否則為0。

5.4 選擇算子

采用二元錦標(biāo)賽選擇法，在錦標(biāo)賽選擇法中，從種群中隨機(jī)挑選兩個(gè)個(gè)體，然后將適應(yīng)度最優(yōu)的個(gè)體選出進(jìn)入下一代。這個(gè)過程重復(fù)進(jìn)行直到子代種群數(shù)量達(dá)到規(guī)定數(shù)量。

5.5 交叉算子

在選擇祖先(母親和父親)染色體產(chǎn)生新的孩子后，可以利用交叉算子可以有助于將優(yōu)良個(gè)體的染色體片段遺傳給后代,同時(shí)交叉算子一般起全局搜索的作用,可以開采未知的空間。本文采用單點(diǎn)遺傳方法。

（1）先產(chǎn)生隨機(jī)數(shù)確定交位點(diǎn)；

（2）交叉位點(diǎn)后的基因?qū)崿F(xiàn)單點(diǎn)交換；

（3）交叉完成。

5.6 突變算子

采用位翻轉(zhuǎn)變異算子保證算法不捕捉局部最大值和局部最小值點(diǎn)。設(shè)置突變概率為0.2。

（1）隨機(jī)確定突變點(diǎn)位；

（2）突變點(diǎn)位的值由0 變1，或由1 變0。

5.7 啟發(fā)式修補(bǔ)算法

經(jīng)過遺傳交叉變異后的個(gè)體可能無法滿足航班約束（每一航班至少被覆蓋一次），所以需要設(shè)計(jì)一種啟發(fā)式算法修復(fù)子代染色體，使之滿足航班約束。本文設(shè)計(jì)了一種任務(wù)環(huán)選擇指標(biāo)，保證成本較低的任務(wù)環(huán)進(jìn)入到解集中。

任務(wù)環(huán)選擇指標(biāo)=任務(wù)環(huán)P 的成本/集合中未被覆蓋的航班數(shù)量，偽代碼如下：

（1）遍歷染色體，搜索未被覆蓋航班；

（2）在子集（pairActive）中搜尋包含該航班的任務(wù)環(huán)；

（3）選擇任務(wù)環(huán)選擇指標(biāo)最小的任務(wù)環(huán)加入染色體中。

5.8 局部啟發(fā)式搜索算法

局部啟發(fā)式搜索算法是文化基因算法的一個(gè)重要特征，用局部啟發(fā)式搜索可以模擬由大量專業(yè)知識(shí)支撐的變異過程,以使解決算法更有效率。這一過程目的減少無用的任務(wù)任務(wù)環(huán)，確保了染色體的適應(yīng)度優(yōu)化的同時(shí)保證滿足航班約束。偽代碼如下：

算法四：局部搜索算法

（1）選擇染色體解集中的任務(wù)環(huán)，將該任務(wù)環(huán)從染色體中移除；

（2）若解集中航班覆蓋約束不被滿足（不是所有航班都被覆蓋），則將該航班重新加入；

（3）重復(fù)上述兩步，直到遍歷所有解集中的任務(wù)環(huán)。

5.9 種群替代策略

文化基因算法的最后一步是種群置換。在這一步，父代和子代的染色體需要通過一種選擇策略確保種群數(shù)量的固定。因?yàn)榉N群的數(shù)量是固定的，所以種群替代策略可以確保種群的數(shù)量保持不變。種群更替階段使用的兩種主要方法是世代法和穩(wěn)態(tài)法。本研究采用穩(wěn)態(tài)方法。在這種方法中，在每次迭代中生成一個(gè)或兩個(gè)子代。然后，這個(gè)后代的染色體取代了種群中最差的個(gè)體。

6 文化基因算法偽代碼

文化基因算法偽代碼如下：

（1）對(duì)每個(gè)個(gè)體計(jì)算適應(yīng)度

（2）while 終止標(biāo)準(zhǔn)不滿足do

（3）Parent1 ←Select-Parent(population,tour-size)

Parent2 ←Select-Parent(population,tour-size)//應(yīng)用錦標(biāo)賽算法選擇父代

（4）Child1 ← Apply-Crossover(one-point ceossover, Parent1,Parent2)

Child2 ←Apply-Crossover(one-point ceossover,Parent1,Parent2)

（5）Child1′←Apply-Mutation(bit-flip random,Child1)

Child2′←Apply-Mutation(bit-flip random,Child2)//進(jìn)化算子

（6）Child1′←局部搜索(lc,Child1′),Child2′←局部搜索(lc,Child2′)

（7）將種群中最差的兩個(gè)個(gè)體替換為父代和子代中最好的兩個(gè)//種群替代；

end while

7 優(yōu)化方案和實(shí)現(xiàn)部分

通過c++語言，在visual studio 平臺(tái)上進(jìn)行程序編寫。設(shè)置迭代次數(shù)為1800 次,每迭代100 進(jìn)行一次更新搜索空間算法。錦標(biāo)賽選擇法行程為2，交叉概率為0.9，突變概率為0.2，設(shè)置種群規(guī)模為20。機(jī)組飛行小時(shí)津貼為400 元/小時(shí)，每個(gè)機(jī)組的任務(wù)津貼為1000 元/天，機(jī)組在外過夜的旅館成本為500 元/天。航班加機(jī)組成本，每個(gè)航段的成本是不相同的，這里為了研究方便，假設(shè)加機(jī)組成本都是一個(gè)固定值500/小時(shí)[13]。選用國內(nèi)某中型航空公司一周的航班數(shù)據(jù)，分別用Kornilakis 所提遺傳算法[14],更新解空間的遺傳算法與本文所提算法進(jìn)行實(shí)驗(yàn)（表2所示分別用算法一二表示）。該公司一周共有航班549 架次，通過深度搜索算法產(chǎn)生了1683 個(gè)勤務(wù)組和79862 個(gè)任務(wù)環(huán)。實(shí)驗(yàn)結(jié)果如下：

表2 對(duì)照實(shí)驗(yàn)算法

表3 對(duì)其他作者開發(fā)的遺傳算法和本文所提算法進(jìn)行的測(cè)試結(jié)果。在兩項(xiàng)實(shí)驗(yàn)中分別對(duì)最優(yōu)解的在外過夜次數(shù)，撘機(jī)次數(shù)，撘機(jī)總時(shí)間總花費(fèi)（元）等關(guān)鍵績(jī)效指標(biāo)進(jìn)行了統(tǒng)計(jì)。在評(píng)估解決方案的優(yōu)劣時(shí)需要參考的三個(gè)重要參數(shù)為執(zhí)勤總時(shí)間、撘機(jī)總時(shí)間和在外過夜次數(shù)。比較遺傳算法，所提的更新搜索空間策略能有效縮減解空間大小，且在減少撘機(jī)次數(shù)和過夜次數(shù)方面有顯著效果。對(duì)比遺傳算法與所提算法可以看出，局部搜索策略能夠起到小幅優(yōu)化效果。通過對(duì)這三個(gè)重要參數(shù)的比較且同時(shí)參考比較三種種算法的其他KPIs 表明，本文所提出的算法比之前的研究產(chǎn)生了更好的結(jié)果，該算法具有良好的性能。

表3 機(jī)組排班實(shí)驗(yàn)數(shù)據(jù)

表4 列出了三個(gè)重要的參數(shù)：執(zhí)勤總時(shí)間、撘機(jī)總時(shí)間和在外過夜次數(shù)在迭代過程中的優(yōu)化趨勢(shì)。在600到800次迭代之后趨于收斂。

表4 所提算法不同迭代次數(shù)的最優(yōu)解KPIs

圖4 為兩種算法的適應(yīng)度變化曲線，可以看出本文所提算法在解決機(jī)組排班問題上具有更優(yōu)的性能。

圖4 適應(yīng)度變化曲線圖

8 結(jié)束語

針對(duì)航空公司機(jī)組人員配對(duì)問題，本文提出了一種基于動(dòng)態(tài)文化基因算法的改進(jìn)算法。由于機(jī)組任務(wù)環(huán)配對(duì)是排班過程中成本識(shí)別的主要環(huán)節(jié)，如何降低機(jī)組成本、增加機(jī)組效用、實(shí)現(xiàn)最優(yōu)機(jī)組配對(duì)具有重要意義。所以本文的優(yōu)化從關(guān)鍵績(jī)效指標(biāo)(KPIs)，如撘機(jī)時(shí)間、勤務(wù)天數(shù)和在外過夜次數(shù)等與機(jī)組任務(wù)環(huán)優(yōu)化相關(guān)的成本指標(biāo)著手，提出了基于動(dòng)態(tài)文化基因算法的改進(jìn)算法。實(shí)驗(yàn)結(jié)果顯示，與現(xiàn)有方法相比，本文所提出的算法生成了更優(yōu)解。所提出的更新搜索空間的算法對(duì)減少撘機(jī)時(shí)間和減少過夜停留次數(shù)有顯著效果。

本研究的主要貢獻(xiàn)如下：

第一項(xiàng)貢獻(xiàn)是利用動(dòng)態(tài)遺傳算法和每次迭代的染色體長(zhǎng)度變化來解決任務(wù)環(huán)配對(duì)問題。該算法基于文化進(jìn)化理論，采用全局搜索與局部搜索相結(jié)合，有效加快了基因進(jìn)化的速度。

第二項(xiàng)貢獻(xiàn)是利用深度優(yōu)先搜索算法結(jié)合航班網(wǎng)絡(luò)設(shè)計(jì)了用于快速生成可行任務(wù)環(huán)的啟發(fā)式算法。經(jīng)試驗(yàn)該算法可生成大量可行的任務(wù)環(huán)。

綜合考量來看，本模型綜合考慮了機(jī)組人員撘機(jī)次數(shù)、過夜次數(shù)、機(jī)組人員的成本等問題，解決了傳統(tǒng)排班方法無法給出的算法模型，為航空公司機(jī)組排班算法的進(jìn)一步研究提供了良好的理論依據(jù)，對(duì)實(shí)際應(yīng)用提供了較好的參考。