基于遺傳算法管制員崗位排班

張旭

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

一、管制員排班的特點

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

二、管制員排班模型

2.1 排班限制條件分析

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

算法模型

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

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

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

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

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

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

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

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

2.2 算法復雜性分析

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

2.3 遺傳算法設計

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

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

其中表示第i個人第j時段的代碼。

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

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

變異過程示意圖：

算法分析：

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

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

算法檢驗

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

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

三、分析與展望

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

參考文獻：

[1] 武廣號， 文毅， 樂美峰. 遺傳算法及其應用[J]. 應用力學學報， 2000， 23（6）：9-10.

[2] 孫宏. "航空公司飛機排班問題：模型及算法研究." 西南交通大學， 2003.

[3] 胡毓達. 實用多目標最優(yōu)化[M]. 上?？茖W技術出版社， 1990.

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

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