張旭

摘要：排班問(wèn)題是一個(gè)重要的組合優(yōu)化問(wèn)題[2]，每種特定情況下的排班都有各自不同的解決手段。本文在考慮到管制員排班過(guò)程中的各種限制條件的情況下提出一種基于排班時(shí)長(zhǎng)公平性的遺傳算法[4]管制員排班模型。經(jīng)過(guò)實(shí)驗(yàn)改進(jìn)算法程序能夠在幾分中之內(nèi)得出一個(gè)周期內(nèi)的具體排班。

一、管制員排班的特點(diǎn)

在民航系統(tǒng)中，管制員是守護(hù)安全的第一線人員，由于崗位的特殊性，他的崗位排班與人員的資質(zhì)直接相關(guān)，在現(xiàn)場(chǎng)運(yùn)行過(guò)程中由于人員的資質(zhì)不相同，相應(yīng)的個(gè)人排班代碼也不盡相同（如領(lǐng)班代碼只能由具有領(lǐng)班資質(zhì)的人值守）。隨著各種限制要求的增加，人工排班過(guò)程中不時(shí)會(huì)出現(xiàn)顧此失彼的情況，本文綜合上述考慮，從人員搭配，人員資質(zhì)，平均時(shí)長(zhǎng)，特定日期代碼需求，上下半夜教員排班五個(gè)方面著手建立遺傳算法排班模型。

二、管制員排班模型

2.1 排班限制條件分析

日常排班過(guò)程中，首先要考慮的是管制員的資質(zhì)問(wèn)題，現(xiàn)有參與排班的管制員資質(zhì)大致如下：領(lǐng)班，教員，管制員，新放單管制員，部分放單管制員。每種資質(zhì)所對(duì)應(yīng)的代碼集合都不一樣，在實(shí)際排班中用不同的代碼字符表示。人員特定日期的代碼需求可以預(yù)先在代碼表中體現(xiàn)出來(lái)，此過(guò)程體現(xiàn)在預(yù)排班中。每類資質(zhì)人員的排班代碼和人員搭配有不同的要求。本文主要的排班目標(biāo)為，整體管制員工作小時(shí)數(shù)最平均，盡量避免連續(xù)大夜，滿足上下半夜均有教員，滿足資質(zhì)搭配要求，滿足個(gè)人的輪空需求這五個(gè)方面進(jìn)行排班，求解多目標(biāo)條件下的極值[3]。

算法模型

其中表示相應(yīng)的權(quán)重系數(shù)，fs表示小時(shí)數(shù)的方差，fn表示連續(xù)大夜的罰值函數(shù)，fp表示滿足人員代碼需求的罰值函數(shù)，fj表示滿足上下半夜教員排班的罰值函數(shù)，fm表示人員資質(zhì)搭配的罰值函數(shù)。

其中表示每個(gè)人的排班周期內(nèi)的小時(shí)數(shù)總數(shù)，表示排班的周期內(nèi)的平均小時(shí)數(shù)。

其中表示第i為管制員的相鄰兩個(gè)代碼，為判斷函數(shù)，若果為兩個(gè)連續(xù)大夜則返回1，否則為0。

其中分別為排班表和特定需求表，為判斷函數(shù)，如果ScheduleTable里面特定 位置的與Personneeds中相應(yīng)位置的相同則返回0，否則返回1。

其中表示教員資格的人數(shù)，分別表示第i時(shí)段的教員代碼集合，上半夜代碼集合，下半夜代碼集合。為判斷函數(shù)，如果Gi中的代碼既在patternS里面又在patternX里面則表示上下半夜都有教員，則返回1，否則返回0。

其中分別表示不能搭配的人員的代碼對(duì)集合和排班代碼中相互搭配的代碼對(duì)集合。為判斷函數(shù)，如果在中則返回1，否則為返回0。

對(duì)于遺傳算法函數(shù)的松弛函數(shù)的確定，通過(guò)

綜上所述：整體基于遺傳算法的管制員排班模型為下：

2.2 算法復(fù)雜性分析

根據(jù)排列組合原理計(jì)算可以得到，N位排班人員在T周期之內(nèi)排班的解空間大小為，從中可以看出隨著排班周期和人數(shù)的增加解空間的大小呈指數(shù)增加，傳統(tǒng)的算法很難在有限的時(shí)間內(nèi)求得滿意解，因此選擇啟發(fā)式算法。根據(jù)遺傳算法的特點(diǎn)，本文針對(duì)管制員算法的特定，設(shè)計(jì)了相關(guān)的遺傳算法。算法能夠在5分中之內(nèi)求得滿足條件的滿意解，大大減少了排班的人力成本 。通過(guò)跟現(xiàn)場(chǎng)的各個(gè)小組的排班人員的調(diào)查分析了解到。正常情況下制訂一個(gè)有特定需求的排班，平均需要花費(fèi)1～2小時(shí)，有時(shí)候甚至需要更長(zhǎng)的時(shí)間。并且由于口算的局限性，很難保證同時(shí)滿足多個(gè)限制條件。

2.3 遺傳算法設(shè)計(jì)

考慮到排班過(guò)程中，每天的代碼都是相同的，所以每個(gè)在產(chǎn)生初始種群的過(guò)程中，我們根據(jù)實(shí)際的排班要求隨機(jī)產(chǎn)生每天的排班，也就是排班表中的一列的數(shù)據(jù)（遺傳基因），然后通過(guò)循環(huán)來(lái)產(chǎn)生一個(gè)周期內(nèi)的排班表（染色體）。在常規(guī)的遺傳算法的運(yùn)算過(guò)程中，交叉操作是為了產(chǎn)生新的優(yōu)良的個(gè)體，變異操作是為了防止算法過(guò)早的陷入局部最優(yōu)解。一旦在初始種群確定之后，整個(gè)種群的基因就基本上是確定的了，交叉操作并不能保證整個(gè)搜索的遍歷性，因此本文中，變異也作為產(chǎn)生新個(gè)體的一個(gè)重要的手段，因此在本文中設(shè)置的變異概率要遠(yuǎn)遠(yuǎn)大于常規(guī)遺傳算法的變異概率。

產(chǎn)生初始種群，本文將每一個(gè)可能的排班表作為一個(gè)遺傳父本。

其中表示第i個(gè)人第j時(shí)段的代碼。

關(guān)于遺傳算法的設(shè)計(jì)的基礎(chǔ)知識(shí)在[1]已經(jīng)有較為詳細(xì)的描述，本文采用類似的遺傳算法編碼方法。本文直接將每個(gè)排班表作為父本，進(jìn)行算法操作。算法交叉操作

本文采用兩點(diǎn)交叉法。為了能夠使得遺傳向著較好的方向進(jìn)行，更快地逼近最優(yōu)解。在算法運(yùn)算過(guò)程中再加入一些特殊的點(diǎn)交叉具體過(guò)程如下圖

變異過(guò)程示意圖：

算法分析：

根據(jù)每個(gè)系數(shù)的設(shè)置我們可以看出適應(yīng)度函數(shù)值的跨度比較大。從1000～10。這樣在遺傳算法的執(zhí)行過(guò)程中，很可能會(huì)使得函數(shù)過(guò)早地陷入局部最優(yōu)解。因此在算法在執(zhí)行過(guò)程中有很大的可能性較早的陷入局部最優(yōu)解。因此，本文在算法執(zhí)行過(guò)程中設(shè)置了一個(gè)操縱算法——偽變異過(guò)程。在計(jì)算過(guò)程中將小時(shí)數(shù)最多的人的一個(gè)大夜代碼與小時(shí)數(shù)最少的對(duì)應(yīng)位置的代碼互換。如圖所示

為了能夠較好地，較全面地搜索到最優(yōu)解，設(shè)置變異地概率在50%以上。

算法檢驗(yàn)

在本算法設(shè)計(jì)過(guò)程中，產(chǎn)生新的遺傳個(gè)體的產(chǎn)生并不是主要通過(guò)交叉過(guò)程獲得，而是通過(guò)隨機(jī)的變異過(guò)程來(lái)獲得。因此實(shí)驗(yàn)中變異的概率要設(shè)置在50%以上，才能很好的保證算法的遍歷性。

上圖是一個(gè)預(yù)排班表，列表示排班周期為9，排班人數(shù)為13人。字符O表示人員的代碼需求，實(shí)際排班中表示輪空代碼，不能搭配人員序號(hào)組合為[9 13;7 13]。右側(cè)為算法排班結(jié)果，本次實(shí)驗(yàn)用時(shí)178秒。

三、分析與展望

雖然本文針對(duì)具體的管制員排班進(jìn)行分析，但是文中所提到的編碼手段對(duì)于此類排班都是有效的，通過(guò)適當(dāng)方式的編程方式能夠?qū)崿F(xiàn)在一分鐘之內(nèi)就能得到較滿意的解。罰值函數(shù)的確定和罰值函數(shù)系數(shù)的確定是遺傳算法能否有效搜索的重要條件。文中所給出的系數(shù)都是通過(guò)參考罰值函數(shù)的值，然后預(yù)估一個(gè)較合適的系數(shù)，再通過(guò)多次試驗(yàn)不斷改進(jìn)得出的，并沒(méi)有確定罰值函數(shù)系數(shù)的計(jì)算公式，這是在未來(lái)研究的一個(gè)方向，如果能夠確定準(zhǔn)確的罰值函數(shù)系數(shù)組合，那么算法的收斂速度和搜索的精度就會(huì)大大的提高，排班結(jié)果也會(huì)更好。

參考文獻(xiàn)：

[1] 武廣號(hào)， 文毅， 樂(lè)美峰. 遺傳算法及其應(yīng)用[J]. 應(yīng)用力學(xué)學(xué)報(bào)， 2000， 23（6）：9-10.

[2] 孫宏. "航空公司飛機(jī)排班問(wèn)題：模型及算法研究." 西南交通大學(xué)， 2003.

[3] 胡毓達(dá). 實(shí)用多目標(biāo)最優(yōu)化[M]. 上海科學(xué)技術(shù)出版社， 1990.

[4] https：//baike.baidu.com/item/%E9%81%97%E4%BC%A0%E7%AE%97%E6%B3

（民航局運(yùn)行監(jiān)控中心 北京 100010）