（計算機(jī)應(yīng)用技術(shù)專業(yè)論文）遺傳算法在人員排班問題上的應(yīng)用研究.pdf

浙江工業(yè)大學(xué) 孓7 9 6 5 學(xué)位論文原創(chuàng)性聲明 本人鄭重聲明：所提交的學(xué)位論文是本人在導(dǎo)師的指導(dǎo)下，獨立進(jìn)行 研究工作所取得的研究成果。除文中已經(jīng)加以標(biāo)注引用的內(nèi)容外，本論文 不包含其他個人或集體已經(jīng)發(fā)表或撰寫過的研究成果，也不含為獲得浙 江工業(yè)大學(xué)或其它教育機(jī)構(gòu)的學(xué)位證書而使用過的材料。對本文的研究作 出重要貢獻(xiàn)的個人和集體，均已在文中以明確方式標(biāo)明。本人承擔(dān)本聲明 的法律責(zé)任。 作者簽名：魂毛飛 日期：衛(wèi)刃一年l 一月修日 學(xué)位論文版權(quán)使用授權(quán)書 本學(xué)位論文作者完全了解學(xué)校有關(guān)保留、使用學(xué)位論文的規(guī)定，同意 學(xué)校保留并向國家有關(guān)部門或機(jī)構(gòu)送交論文的復(fù)印件和電子版，允許論文 被查閱和借閱。本人授權(quán)浙江工業(yè)大學(xué)可以將本學(xué)位論文的全部或部分內(nèi) 容編入有關(guān)數(shù)據(jù)庫進(jìn)行檢索，可以采用影印、縮印或掃描等復(fù)制手段保存 和匯編本學(xué)位論文。 本學(xué)位論文屬于 1 、保密口，在年解密后適用本授權(quán)書。 2 、不保密口。 ( 請在以上相應(yīng)方框內(nèi)打“4 ”) 作者簽名：童憋壬飛 導(dǎo)師簽名：菘位才 日期：五闔年一月昭日 日期：研年r 月 日 遺傳算法在人員排班問題上的應(yīng)用研究 摘要 人員排班問題一直是調(diào)度問題中經(jīng)常碰到的經(jīng)典問題，屬于n p h a r d 問題。目前解決人員排班問題的方法基本上可以歸為兩大類，一類為最優(yōu) 化算法( o p t i m a ls o l u t i o na l g o r i t h m ) ，所謂最優(yōu)化算法，即在已知的求 解條件限制下，對于其欲求解的目標(biāo)式在可行解空間內(nèi)，搜尋一個最優(yōu)的 解。但此法有一個缺點，就是計算時間較長，效率較低。另外一類為啟發(fā) 式的算法，目前應(yīng)用于人員排班方面的啟發(fā)式算法有模擬退火算法，遺傳 算法等。其中遺傳算法是一類借鑒生物界自然選擇和自然遺傳機(jī)制的隨機(jī) 化搜索算法，其應(yīng)用優(yōu)勢在于處理傳統(tǒng)搜索方法難以解決的復(fù)雜和非線性 問題。 選擇遺傳算法是因為其具有搜尋大范圍可行解空間，避免陷入局部最 優(yōu)解的特性，因此在國內(nèi)外處理最優(yōu)優(yōu)化問題時是備受矚目的一個算法。 但是由于遺傳算法在遺傳后期的波動現(xiàn)象，導(dǎo)致了迭代次數(shù)過大和準(zhǔn)確率 不高。本文所用的免疫遺傳算法在傳統(tǒng)遺傳算法全局隨機(jī)搜索的基礎(chǔ)上， 借鑒了生物免疫機(jī)制中抗體的多樣性保持策略，改善了遺傳算法的群體多 樣性，具有更好的全局搜索能力，將該算法應(yīng)用在人員排班問題上，通 過與傳統(tǒng)遺傳算法在性能的比較，在實驗分析中獲得了較好的結(jié)果。 關(guān)鍵詞：人員排班問題，遺傳算法，免疫遺傳算法 第一章緒論 遺傳算法( g e n e t i c a l g o r i t h m - - - - g a ) ，是一類以達(dá)爾文的自然進(jìn)化論與遺傳變 1 異理論為基礎(chǔ)的求解復(fù)雜全局優(yōu)化問題的仿生型算法。它借鑒生物界自然選擇和 自然遺傳機(jī)制，以概率論為基礎(chǔ)在解空間中進(jìn)行隨機(jī)化搜索，最終找到問題的最優(yōu) 解。 遺傳算法的興起是在8 0 年代末9 0 年代初期，但是它的歷史可以追溯到6 0 年代 初期。早期的研究大多以對自然遺傳系統(tǒng)的計算機(jī)模擬為主。早期遺傳算法的研究 特點是側(cè)重于對一些復(fù)雜的操作的研究。其中像自動博弈、生物系統(tǒng)模擬、模式識 別和函數(shù)優(yōu)化等給人以深刻的印象，但總的說來，這是一個無明確目標(biāo)的發(fā)展時期， 缺乏帶有指導(dǎo)性的理論和計算工具的開拓。這種現(xiàn)象直到7 0 年代中期由于h o l l a n d f i 匐 和d e j o n g 的創(chuàng)造性研究成果的發(fā)表才得到改觀 。1 9 6 7 年，b a g l e y 在他的論文中 首次提出了遺傳算法( g e n e t i ca l g o r i t h m ) 這一術(shù)語，并討論了遺傳算法在自動博弈 r m h 】 中的應(yīng)用。1 9 7 0 年，c a v i c c h i o 把遺傳算法應(yīng)用于模式識別中。第一個把遺傳算 剛 法應(yīng)用于函數(shù)優(yōu)化的是h o l l s t i e n ，1 9 7 1 年他在論文計算機(jī)控制系統(tǒng)中魄人工遺 傳自適應(yīng)方法中闡述了遺傳算法用于數(shù)字反饋控制的方法。1 9 7 5 年在遺傳算法研 究的歷史上是十分重要的一年，h o l l a n d 出版了他的著名專著自然系統(tǒng)和人工系統(tǒng) 1 的適配該書系統(tǒng)的闡述了遺傳算法的基本理論和方法，并提出了對遺傳算法 理論研究和發(fā)展極為熏要的模式理論( s c h e m a t at h e o r y ) ，該理論首次確認(rèn)了結(jié)構(gòu)重 組遺傳操作對于獲得隱并行性的重要性。j h o l l a n d 教授和他的研究小組圍繞遺傳算 法進(jìn)行研究的宗茸有兩個：一是抽取和解釋自然系統(tǒng)的自適應(yīng)過程，二是設(shè)計具有 自然系統(tǒng)機(jī)理的人工系統(tǒng)。周年，d e j o n g 完成了他的重要論文遺傳自適應(yīng)系統(tǒng)的 行為分析，他把h o l l a n d 的模式理論和他的計算實驗結(jié)合起來，這可以看作遺傳算 法發(fā)展過程中的一個里程碑，盡管d e j o n g 和h o l l s t i e n 一樣主要側(cè)重于函數(shù)優(yōu)化的 研究，但他將選擇、交叉和變異操作迸一步完善和系統(tǒng)化，同時又提出了諸如代溝 6 ( g e n e r a t i o ng a p ) 等新的遺傳操作技術(shù)，為遺傳算法及其應(yīng)用打下了堅實的基礎(chǔ)。 進(jìn)入8 0 年代，遺傳算法迎來了興盛發(fā)展時期，理論研究和應(yīng)用研究都成了十分熱門 的話題。 本文的研究課題是人員排班問題，人員排班問題一直是調(diào)度問題中經(jīng)常碰到的 經(jīng)典問題。國內(nèi)外的許多文獻(xiàn)已有不同程度的探討與研究，它在學(xué)術(shù)領(lǐng)域被定義是 一個特定的數(shù)學(xué)規(guī)劃問題。在國內(nèi)外許多學(xué)者的努力下，已有許多不同的求解方法 被應(yīng)用于不同的人員排班問題，但綜觀所有的求解方法，其基本上仍然可以歸為兩 大類：一為最優(yōu)化算法( o p t i m a ls o l u t i o na l g o r i t h m ) ，所謂最優(yōu)化算法，即在已知的 求解限制條件下，對于其欲求解的目標(biāo)式在可行解空間內(nèi)，搜尋一個最優(yōu)的解的方 法，但此法有一個缺點，就是計算時間較長，在遇到大型的人員排班闖題時，往往 要耗費太多的時間?；诖?，我們在處理大型的人員排班問題時，一般會去選擇設(shè) 計一套啟發(fā)式的算法，來求得一個較佳近似解。所謂啟發(fā)式算法是指尋求一種能產(chǎn) 生可行解的啟發(fā)式規(guī)則，以找到一個最優(yōu)解或近似解的方法。雖然此近似解并不一 定為最優(yōu)解，但卻能大大縮短求解時間，提高求解效率。敵在處理大型的人員排班 問題時，我們一般都采用此類方法來進(jìn)行求解。關(guān)于應(yīng)用于人員排班方面的啟發(fā)式 算法有很多，如模擬退火算法( s i m u l a t e da n n e a l i n g ) ，遺傳算法( g e n e t i ca l g o r i t h m ) 等。 選擇遺傳算法是因為其具有搜尋大范圍可行解空間，避免陷入局部最優(yōu)解的特 性，因此在國內(nèi)外處理最優(yōu)化問題時，該算法是備受矚目的一個算法。但是由于遺 傳算法在遺傳后期的波動現(xiàn)象，導(dǎo)致了迭代次數(shù)過大和準(zhǔn)確率不高。本文所用的免 疫遺傳算法是在傳統(tǒng)遺傳算法全局隨機(jī)搜索的基礎(chǔ)上，借鑒了生物免疫機(jī)制中抗體 的多樣性保持策略，改善了遺傳算法的群體多樣性，具有更好的全局搜索能力，將 該算法應(yīng)用于人員排班問題上，通過與傳統(tǒng)遺傳算法在性能上的比較，我們發(fā)現(xiàn)它 是解決人員排班問題的較好的方法。 本論文包括以下幾個部分：第一章：緒論；第二章：遺傳算法的基本理論與工 作機(jī)制；第三章：人員排班問題的研究背景；第四章：遺傳算法在人員排班問題的 應(yīng)用現(xiàn)狀分析；第五章：免疫遺傳算法工作機(jī)制；第六章：基于遺傳算法的人員排 班問題研究。第七章免疫遺傳算法設(shè)計；第八章：結(jié)論與展望。 第二章遺傳算法基本理論 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，隱含并行性和全局搜 索特性是它的兩大顯著特征，而且這是一個以適應(yīng)度函數(shù)( 或目標(biāo)函數(shù)) 為依據(jù)， 通過對群體個體施加遺傳操作實現(xiàn)群體內(nèi)個體結(jié)構(gòu)重組的迭代處理過程。在這一過 程中，群體個體( 闊題的解) 一代一代得以優(yōu)化并逐次逼近最優(yōu)解。本章介紹了遺 傳算法所依賴的基本遺傳操作：選擇、交叉和變異算予，并分析了遺傳算法的基本 機(jī)理，這些主要原理是以后各章研究的理論基礎(chǔ)。 2 1 模式定理 模式( s c h e m a ) 是一個描述字符串集的模板，該字符串集中串的某些位置上存 在著相似性。不失一般性，我們考慮二值字符集( 0 ，1j ，由此產(chǎn)生通常的0 ，1 字符 串。現(xiàn)在我們增加一個符號“ ”，稱作“無關(guān)符”( d o n tc a r e ) 或通配符，即“ ” 既可以被當(dāng)作“0 ”，叉可以被當(dāng)作“1 ”。這樣，二值字符集f 0 ，1 ) 就擴(kuò)展為三值字 符集( 0 ，1 ，十) ，由此可以產(chǎn)生諸如0 1 1 0 、o $ l l 料、$ 0 1 豐。等字符串。 定義2 1 基于三值字符集f 0 ，l ，) 所產(chǎn)生的能描述具有某些機(jī)構(gòu)相似性的0 、 1 6 1 字符串集的字符串稱作模式。 以長度為5 的串為例，模式* 0 0 0 1 描述了在位置2 、3 、4 、5 具有形式“0 0 0 1 ” 的所有字符串，即 1 0 0 0 1 ，0 0 0 0 1 ) 由此可以看出，模式的概念為我們提供了一種簡潔 的用于描述在某些位置上具有結(jié)構(gòu)相似的0 、1 字符串集合的方法。然而，模式概念 的引入并不是僅僅為了描述上的方便。在引入模式概念前，我們所看到的遺傳算法 是：在某一代中，n 個互不相同的串在選擇、交叉、變異等遺傳算子作用下產(chǎn)生下 代的n 個互不相同的串。那么，在兩代之間究竟保留了什么性質(zhì)，破壞了什么性 質(zhì)，我們無從得知，因為我們看到的串是相互獨立的，互不聯(lián)系的。而引入模式的 概念后，我們看到一個串實際上隱含了多個模式( 長度為l 的串隱含著2 。各模式) ， 一個摸式可以隱含在多個串中，不同的串之間通過模式麗相互聯(lián)系。遺傳算法中串 的運算實際是就是模式的運算，因此，通過分析模式在遺傳操作下的變化，從而把 握遺傳算法的實質(zhì)，這正是模式定理所要揭示的內(nèi)容。 定義2 2 模式h 中的確定位置的個數(shù)稱作該模式的模式階，記作o ( h ) 。 比如模式0 1 l 十1 的階數(shù)為4 ，而模式0 女 料的階數(shù)為1 。顯然，一個模式的階數(shù)越 高，其樣本數(shù)就越少，因而確定性越高。 定義2 。3 模式h 第一個確定位置和最后一個確定位置之間的距離稱作該模式 的定義距，記作8 ( h ) 。 比如模式0 1 l 1 女的定義距為4 ，而模式0 料 的定義距為0 。 定義2 4 設(shè)x ：i “：( b l ) “為遺傳算法群體狀態(tài)空間，h v l = o ，i ，牢) 是任一模式， p ( t ) = x 。( t ) ，x ：( t ) ，x n ( t ) 】x 表示遺傳算法在第t 代時的群體，f ：i r 1 為逶應(yīng) 度函數(shù)，則稱公式( 2 - 1 ) 旭歸面去廁。7 s ( d 1 為模式h 的平均適應(yīng)值，這里1 日np 0 】表示集合h f 、p ( t ) 中元素的個數(shù)，既 p ( t ) 中含有h 中元素的個數(shù)。稱公式( 2 - 2 ) 廠( f ) = i ( d i h ( 2 2 ) h p ，j 為p ( t ) 的平均適應(yīng)值。 定理2 1 ( 模式定理，s c h e m at h o o r o m ) 設(shè)遺傳算法的交叉概率和變異概率 分別為p o 和p ，模式h 的定義長度為8 ( h ) 、階為0 ( h ) ，第t + l 代群體p “+ 1 ) 含有h 中元素個數(shù)的數(shù)學(xué)期望值記為e h c ) p ( t + 1 ) ，則 9 e h a e ( ，+ 1 心聊( f 】幫。卜罟卻b 證明由于遺傳算法采用按適應(yīng)值比例的選擇策略，則易見h n p ( t + 1 ) 中元素得 以選擇的期望值為 。贏，孚中嗍) 掣 由于交叉操作是隨機(jī)選取1 到l i 中的一個位置并交換兩父體的一個對應(yīng)子 串，于是屬于模式h 的個體經(jīng)過交叉后仍屬于h ( 稱為未被破壞) 的概率不小于 1 一見智。而一個個體經(jīng)過變異后朱被破壞的概率為( 1 一p ，) “。另外p ( t ) 中 不屬于h 中的元素也有可能經(jīng)過交叉、變異后屬于h ，所以第t + l 代群體p ( t + 1 ) 中 屬于h 的個體數(shù)目的期望值不小于 哪l 掣。h 料( 1 - 又因為在遺傳算法中p 。一般取值很小，故有 h 智 ( 卜擴(kuò)1z h 矧( 1 一。瀛洶智叫蹺 于是定理得證。 推論2 1 在遺傳算法中，定義長度較短、低階且適應(yīng)值超過平均適應(yīng)值的模 式h ，在群體中數(shù)目的期望值按指數(shù)級遞增。 證明設(shè)對任意f 1s f ，都有壘! ! ! ! 大于一個常數(shù)c i ，再記 九) 足= c 卜智一。h 若k i ，則由定理2 i 知 l o 立。 否。 e 0 日n p ( f 十1 如1 日n p o 】足 由此遞推易得：矗1 日n p o + q 】舊n p 剛k 1 。于是推論成立。 雖然模式定理可以在一定意義上解釋遺傳算法的有效性，但它仍有以下的缺點： ( 1 ) 模式定理只對二進(jìn)制編碼才適用，對其它編碼方案尚沒有相應(yīng)的結(jié)論成 ( 2 ) 模式定理提供的只是期望值的一個下界，我們無法根據(jù)它推斷算法收斂與 ( 3 ) 模式定理對算法的設(shè)計如控制參數(shù)的選取沒有太大的幫助。 2 2 內(nèi)含并行性定理 我們已經(jīng)知道，一個串實際上隱含了多個模式，遺傳算法事實上是模式的運算。 對于一個長度為l 的串，其中隱含著2 個模式。那么，若群體規(guī)模為n ，則其中隱 含的模式個數(shù)介于2 。和n 2 。之間。顯然，由予交叉操作的作用并非所有的模式都能 高概率的處理，因為一些定義距較長的模式將遭到破壞。本節(jié)禱介紹遺傳算法中能 阻指數(shù)級增長的模式個數(shù)的下界。 在這方廄。h o l l a n d 和g o l d b e r g “1 指出了遺傳算法有效處理的模式個數(shù)為o ( r 1 2 ) ， 這意味著，盡管遺傳算法實際上只對n 個申個體進(jìn)行運算，但卻隱含的處理了o ( n 3 ) 個模式。h o l l a n d 將這一性質(zhì)稱為內(nèi)含并行性( i m p l i c i tp a r a l l e l i s h a ) 。其結(jié)論如下： 定理2 2 ( 內(nèi)含并行性定理) 設(shè)e 是一個小正數(shù)，l 。 o ，令t = 妄t ，若群體規(guī)模n = n ( b ) = 2 見，這 里1 3 0 是個參數(shù)，則有 ( 1 )遺傳算法一次處理的那些存活率大于l e 且定義長度2 l 。的模式數(shù) 目的期望值至少與加) 廚同階，其中 g 歸) = - + 吾 當(dāng)0 丹 1 這里h g ) = 一 l o g s - ( 1 一f ) l o g ：( 1 一f ) ，( 0 c fc 1 ) 稱為熵函數(shù)； ( 2 ) 當(dāng)b 1 時，n 咖i 薩大于某一常數(shù) ( 3 )當(dāng)b 1 時， 存活率1 2 e 1 的模式數(shù)至少與三2 州幅同階6 2 3 遺傳算法的工作機(jī)制 2 3 1 引言 j o h ny o nn e u m a n n 在1 9 6 0 年提出了一個自我復(fù)制( s e i f _ p r o d u c t i n g ) 的理論，此 理論奠定了遺傳算法發(fā)展的基礎(chǔ)，其后j o h n h o l l a n d 更進(jìn)一步地延續(xù)了此理論，并 在此理論中加入達(dá)爾文的“物競天澤，適者生存”的進(jìn)化思想，繼而在1 9 7 0 年發(fā)明 了簡單遺傳算法( s i m p l e g c n 哦a i g o r i t l r i l s ，s g a ) ，成為遺傳算法槊構(gòu)的初步模型【s , 1 0 。 遺傳算法的整個進(jìn)化過程雖然是隨機(jī)的，但可以憑借著每代解的適應(yīng)度作進(jìn)化 及篩選的工作，逐步淘汰掉適應(yīng)度較差也就是較差的解，同時保留適應(yīng)度較佳的個 體經(jīng)由交叉，變異等機(jī)制繁衍出適應(yīng)度較佳的下一代也就是較佳的解，使得整個群 體的適應(yīng)度能夠提升。 由于遺傳算法是利用簡單的系統(tǒng)架構(gòu)、運算機(jī)制，就能產(chǎn)生強(qiáng)大的搜尋能力，而 且也具備較高的問題獨立性，同時具有多點搜尋，再伴隨世代交替以及隨機(jī)搜尋的 特性。這種平行處理問題的能力使其不易陷入局部最優(yōu)解( 1 0 c a lo p t i m u m ) i 中而無法跳 脫，而是逐步向整體最優(yōu)解( g l o b a lo p t i m u m ) 收斂，這些特點使遺傳算法被廣泛應(yīng)用 p 0 啦蜮 n 三口 于各個領(lǐng)域之中。 2 3 2 遺傳算法的工作機(jī)制 遺傳算法的基本架構(gòu)源自達(dá)爾文的進(jìn)化論，經(jīng)由基因的編碼，復(fù)制，交叉，變 異，取代來達(dá)到進(jìn)化的目的，以下分別敘述這些機(jī)制的概念9 】： 一，編碼f e n c o d i n g ) 與解碼e c o d i n g ) ： 遺傳算法操作的對象通常為能夠表示可行解的字串而非決策變數(shù)本身，因此在 進(jìn)行遺傳算法之前必須先通過編碼的程序?qū)栴}的決策變數(shù)轉(zhuǎn)換成字串或稱染色 體。至于如何將問題的決策變數(shù)轉(zhuǎn)化為染色體的形式，主要關(guān)鍵有二【1 1 】：其一是如 何將問題顯性空間( p h e n o q 審es p a c e ) 的特性融入基因空i 圃( g e n o t y p es p a c e ) 中，其二是 當(dāng)算法在運作時其基因的變化方式與形態(tài)。一般來說主要的編碼形式有兩種： l 、二值編碼( b i n a r ye n c o d i n g ) ：此編碼方式是以= 進(jìn)制位碼 0 ，l 表示，通常應(yīng)用 于數(shù)值形態(tài)的問題。 2 、字符編碼( c h a re n c o d i n g ) ：此編碼方式是以數(shù)字或字符的方式來進(jìn)行編碼，較常 運用于排序型的問題。 在求解適應(yīng)度函數(shù)值時，再將染色體解碼為實際的形態(tài)進(jìn)行運算，一般而言一 個染色體解碼后的結(jié)果代表一個可行解。 二，初始種群與種群大j 、( p o p u l a t i o ns i z e ) ： 遺傳算法可以同時對多點進(jìn)行搜尋，因此在執(zhí)行算法前，必須先建立一組包含 多個染色體的初始種群。每個染色體代表一個可行解，再經(jīng)由染色體之間多方向的 進(jìn)化產(chǎn)生較佳的下一代。一般而吉初始種群的產(chǎn)生方式有兩種，其一為隨機(jī)產(chǎn)生， 此外也可針對問題設(shè)計啟發(fā)式程序產(chǎn)生。而種群大小則為必須事先決定的參數(shù)值， 種群越大代表搜尋的空間越大，也就是說得到最優(yōu)解的機(jī)會越大，但相對耗費的記 憶體較大，演算速度相對也就較慢。種群太小則較難搜尋到最優(yōu)解，同時也越容易 陷入局部最優(yōu)解中，因此研究者必須視問題特性來設(shè)計種群大小。 三，適應(yīng)度函數(shù)( f i t n e s sf u n c t i o n ) ： 為了評估染色體的優(yōu)劣程度，必須導(dǎo)入一個評估指標(biāo)作為演算機(jī)制的判斷依據(jù)， 透過適應(yīng)度函數(shù)的運算可得到適應(yīng)度值，適應(yīng)度值越佳者表示其被選取的機(jī)會越高， 反之適應(yīng)度值越差者其淘汰的機(jī)會也越大。一般而言適應(yīng)度函數(shù)為模式的目標(biāo)函數(shù)， 由于遺傳算法并不處理限制式，因此碰到不合乎限制條件的染色體，通常需加注一 處罰值，借由處罰值使其適應(yīng)度值變差自然被淘汰。以下舉一個簡單的模式說明。 m a x ，0 ) = 聾2 s t0 x 3 2 j c i n t 我們可以用一個5 位的二進(jìn)制數(shù)代表一個x i 值( b i n a r yb i t s ) ，如下面的染色體代 表x i = 1 3 染色體表示為：臣丑臣 j j 衛(wèi) 展開式：0 2 4 + l x 2 3 + l x 2 2 + o x 2 1 + l x 2 0 = 1 3 四，復(fù)制或選擇( s e l e c t o n ) ： 復(fù)制或選擇是從群體中挑選出準(zhǔn)備產(chǎn)生下一代的個體，由于選擇的機(jī)制使得遺 傳算法在搜尋最優(yōu)解中更為有利。選擇的機(jī)制越強(qiáng)，即個體好壞程度的落差大者， 其收斂速度較快，相對也較容易陷入局部最優(yōu)解中；反之，選擇的機(jī)制不強(qiáng)烈，其 進(jìn)化速度較慢。一般麗言為了避免過早收斂，在進(jìn)化的早期給予其較弱的選擇機(jī)制， 以避免因過早收斂而落入局部解中，到了進(jìn)化的后期則給予其較強(qiáng)的選擇機(jī)制，以 提高求解的效率。 一般常被運用的選擇機(jī)制稱為輪盤法( r o u l e t t ew h e e ls e l e c t i o n ) ，輪盤法為一個 啟發(fā)式隨機(jī)選擇機(jī)制，先將種群中每個染色體的適應(yīng)度值求和，將此總適應(yīng)度值視 為一個輪盤，每個染色體在輪盤上占有的面積是依其適應(yīng)度值與種群總適應(yīng)度值的 比例分配而定的。假設(shè)種群大小為n ，第i 個染色體其適應(yīng)度值為，則其被選擇的 機(jī)率為，爭，面積越大者代表其為較佳的個體，相對也有較高的機(jī)會被選中，其 “| 急” 特征也越容易遺傳給下一代；反之亦然。以下舉一個例子【1 2 l 說明如下。 濺燃黼鬻黼黼麟粼麟黼黼麟 10 1 1 0 11 31 6 9 1 4 4 21 1 0 0 0 2 45 7 64 9 2 30 1 0 0 0 86 4 55 4u 3 0 l l 9 3 6 i3 0 9 | 求和 1 1 7 01 0 0 ( 3 ) 5 5 圖2 - i 輪盤法 五，交叉( c r o s s o v e r ) ： 交叉是一種提供個體間彼此交換信息的機(jī)制，透過此機(jī)制來產(chǎn)生下一代的個體， 如圖2 3 所示主要流程為選擇機(jī)制中隨機(jī)所挑選出來的個體，然后在每組個體中隨 機(jī)產(chǎn)生交叉點，經(jīng)由交叉點上的基因值互換產(chǎn)生新的子代。交叉的目的主要是希望 借由不同基因組合找尋出較佳的個體，般常見的交叉方法有以下三種”1 ： l 、單點交叉法( s i n g l ep o i n t ) ：隨機(jī)產(chǎn)生一個交叉點進(jìn)行基因互換，主要是組合染色 體左右兩端字元的缺陷，可能產(chǎn)生無法將母代的優(yōu)越性表現(xiàn)出來的現(xiàn)象。 2 、雙點交叉( t w o p o i n t ) ：隨機(jī)產(chǎn)生兩個交叉點，交換母代彼此的基因，可以克服單 點交叉過程中的一些缺點。 3 、制式交叉( u n i f o r m ) ：在一隨機(jī)平臺上隨機(jī)產(chǎn)生0 或l 。0 代表予代的基因值遺傳 自其中一個體。l 代表子代的基因值遺傳自另一個體。制式交叉法在交叉時不 會受到染色體編碼位置的影響，但可能使母代染色體結(jié)構(gòu)受到破壞，而無法保 留住母代染色體的些特性。 4 、其他：運用于t s p 等節(jié)點順序交叉法主要有以下3 種，部分匹配交叉( p a r t i a l l y m a t c h e dc r o s s o v e r ) ，簡稱p m x ：順序交叉( o r d e rc r o s s o v e r ) ，簡稱o x 與o r d e r - b a s e c r o s s o v e r 簡稱o x 2 。 交叉前： 交叉后： 染色體l 染色體2 子代l 子代2 六，變異( m u t a t i o n ) ： i l l o i o tl0 i l 嫠i 。璐肇i 鬻i i 鬻測淵茹徽瓣裂薅裂i 罄圖j 辮 交叉點 i j i ( l 0 燃燃燮i 麟激黲 蹴o 瓣i 。粼囝l 渤# 瓣li 【1 l 圖2 2 交叉機(jī)制 變異過程是將交叉后所產(chǎn)生的子代，根據(jù)預(yù)先設(shè)定的變異機(jī)率進(jìn)行變異，其 主要目的是要避免過早收斂，可借由變異機(jī)制開發(fā)新的搜尋空間，使搜尋方向能 朝各個方向進(jìn)行，防止陷入局部最優(yōu)解中。與交叉相同，變異前須預(yù)先設(shè)定一變 異機(jī)率作為基因是否進(jìn)行交異的依據(jù)，在進(jìn)化初期變異機(jī)率通常設(shè)定為一較小的 機(jī)率值。一般常見的變異方法是將基因值轉(zhuǎn)變。如圖2 3 所示以二值編碼為例， 若發(fā)生變異，則其基因值變化為0 變?yōu)? ，l 則變?yōu)? 。此外運用于t s p 類似問題 的變異方法則有反轉(zhuǎn)變異法，亦即將染色體中兩個隨機(jī)選取的字元加以交換，如 圖2 4 所示。 變異點 變異前染色體 變異后染色體 亙 二工 塑重要 圈 變異前染色體 圖2 3 變異機(jī)制 變異點 童童 變異后染色體 i 二 二 】薹璧豇二至二匿鋈薹圈 圖2 - 4 反轉(zhuǎn)變異法 七，取代( r e p l a c e m e n t ) 。 經(jīng)由上述幾個步驟后會產(chǎn)生一組新的群體稱為予代，子代去替換舊有的群體或 稱母代的過程就叫做取代，一般而言常見取代方法有下列3 種 1 3 , t 4 3 ： ( a ) 、完全取代策略：即在每一次產(chǎn)生新的予代后，原有的母代就被全部淘汰換掉， 予代成為新的母代，如此一直重復(fù)到終止條件為止。 ( b ) 、保留精英策略：即在種群中保留少數(shù)較佳的母代不被替換掉，其余部分由子代 來取代，如此可將表現(xiàn)優(yōu)良的基因值保留到下一代。 ( 曲、穩(wěn)定狀態(tài)策略：不產(chǎn)生子群體，而改以產(chǎn)生子代個體，再由種群中隨機(jī)挑選表 現(xiàn)較差的個體予以淘汰換掉。 2 3 3 遺傳算法的基本流程 經(jīng)過上述選擇，交叉，變異，取代等運算機(jī)制后，就產(chǎn)生了一批新的種群，這 批種群一直熏復(fù)進(jìn)行上述操作，直到滿足終止條件為止，一般就達(dá)到了預(yù)期的效果。 其中一般終止的條件有兩大類： 一 1 、達(dá)到事先指定的進(jìn)化代數(shù)。 2 、個體適應(yīng)度無法再有效地改進(jìn)。 整個遺傳算法的基本流程圖如圖2 - 5 所示。 圈2 - 5 遺傳算法基本流程圈 糶 2 3 4 遺傳算法的優(yōu)點與存在的問題 從本質(zhì)上來講，無論是傳統(tǒng)g a ，還是實施特定遺傳策略的g a ，其基本搜索能 力均來自于群體和選擇、交叉、變異等遺傳算子，從而發(fā)現(xiàn)編碼空間上的全局最優(yōu) 解位串。 g a 作為一種優(yōu)化問題求解的隨機(jī)搜索過程，與任何基于解空間上的個體或群 體、單點或多點的搜索方法一樣，當(dāng)問題解空間存在多個局部極值點時，比如多峰 函數(shù)優(yōu)化問題，搜索方法應(yīng)當(dāng)在求泛和求精的能力方面進(jìn)行恰當(dāng)平衡，以充分利用 計算資源。一般來講，探索解空間上的全局最優(yōu)解需要較長的時間，具有較大的隨 機(jī)性：完善當(dāng)前局部最優(yōu)解則應(yīng)當(dāng)充分利用已獲得的解信息快速逼近局部極值點， 盡量減少資源消耗并提高解的質(zhì)量。 g a 在對連續(xù)多模式函數(shù)求最優(yōu)值時通常面臨一定的不足，這主要是由于g a 本身的兩大缺陷造成的，即早熟收斂和開采能力差。這些缺陷使得g a 在大量問題 中不具有實用價值。實際上，早熟收斂的發(fā)生常常使得g a 只能獲得個局部優(yōu)化 值，而得不到全局最優(yōu)值。而開采能力差又常導(dǎo)致g a 在獲得一定精度結(jié)果時收斂 速度緩慢。早熟收斂的主要原因是種群中缺乏個體多樣性( d i v e r s i t y ) 。因此克服這 個問題的一種有效方法是維持種群的多樣性，從而在進(jìn)化過程中有利于對搜索區(qū)域 進(jìn)行連續(xù)探測。盡管遺傳算法是一種適用于n p h a r d 的智能算法，它有自己的優(yōu)點 與不足。 一，優(yōu)點 l 、多點隨機(jī)式同步搜尋：遺傳算法是用隨機(jī)的方式去主導(dǎo)搜尋的方向，而不是決定 性( d e t e r m i n i s t i c ) 的法則，其搜尋的方式雖然是盲目的( b l i n d ) ，卻不是無條件的亂 走( r a n d o mw a l k ) ，它有別于一般傳統(tǒng)的搜尋法則。它搜尋時是同時考慮搜尋空間 上的多個點而非傳統(tǒng)做法的單一個點，因此能較有效率地獲得較佳的近似解，避 免陷入局部最優(yōu)解中。 2 、適應(yīng)度函數(shù)：在g a 中，適應(yīng)值是用來區(qū)分群體中個體的好壞。g a 正是基于適 應(yīng)值對個體進(jìn)行選擇，以保證適應(yīng)值好的個體有機(jī)會在下一代中產(chǎn)生更多的子個 體。在使用g a 求解具體問題時，適應(yīng)值函數(shù)的選擇對算法的收斂性以及收斂速 度的影響較大，針對不同的問題需根據(jù)經(jīng)驗來確定相應(yīng)的參數(shù)。遺傳算法只利用 模式中的目標(biāo)函數(shù)當(dāng)作適應(yīng)度函數(shù)，必要時導(dǎo)入處罰值外并不需要其他的信息， 不借要推導(dǎo)復(fù)雜的數(shù)學(xué)公式。 3 、基因編碼：遺傳算法操作的對象通常為能夠表示可行解的字串而非決策變數(shù)本身， 因此在進(jìn)行遺傳算法之前必須先通過編碼的程序?qū)栴}的決策變數(shù)轉(zhuǎn)換成字串或 稱染色體。遺傳算法的運算子是直接作用于參數(shù)的編碼字串上而非參數(shù)本身，因 此不受搜尋空間的限制。 二，存在的問題 l 、函數(shù)特性：由于遺傳算法屬于啟發(fā)式近似解法，適用于凹性函數(shù)，若求解的函數(shù) 為凸性函數(shù)，則其求解的效率不如牛頓法等最優(yōu)化搜尋方法來得好。 2 、編碼的設(shè)計問題：對于編碼的設(shè)計必須是不同的問題設(shè)計不同的編碼方式，因編 碼方式直接影響到求解效率與結(jié)果，不能只運用簡單基因的編碼方式。 3 、重復(fù)搜尋的問題：由于遺傳算法的運算過程只與適應(yīng)度函數(shù)相關(guān)，同時又不具備 記憶功能，所以往往重復(fù)搜尋到相同的點，降低了求解的效率。 4 、求解效果：除非模式能提供最優(yōu)解的參考值，否則無法確定所求得的解為最優(yōu)解。 2 1 3 1 引言 第三章人員排班問題的研究背景回顧 人員捧班是日常生活中的常見問題，小到民間組織的人員安排，大到政府相關(guān) 單位的人力調(diào)配。從管理學(xué)的觀點來說，就是在適當(dāng)?shù)臅r間安排適當(dāng)?shù)娜藛T在適當(dāng) 的工作崗位上，而管理者在處理排班問題時候往往需要面對3 個層面： 1 、效率：就是管理者所安排的人員在一定的工作崗位上要體現(xiàn)出一定的效率，也 就要達(dá)到管理者所要求的結(jié)果。 2 、公平；就是管理者在安排人員時，要體現(xiàn)公平性。不要出現(xiàn)人員分布有多有少， 不要出現(xiàn)人浮于事的現(xiàn)象。 3 、合理性：就是管理者在安排人員時，要在適合人的工作范圍之內(nèi)，不要出現(xiàn)不臺 理的現(xiàn)象。具體可以用d 粕t z i g 于1 9 5 4 年提出的數(shù)學(xué)模型來表示，簡單 表示如下： m i n c j s t x d j z g o ，1 ) vf 緲 、l s 嘉j ：工作班決策變量，其值為1 時，表示工作班存在于集合中，為0 則否。 c ，：工作班的單位成本。 d j ：工作單位的人員需求a a 口：若為l 表示工作班內(nèi)含工作單位，否則為0 a 形：所有工作單位i 的集合。 s ：所有工作班j 的集合。 3 2 人員排班問題的分類 文獻(xiàn)i “。7 】上人員排班問題的類型大致分為3 大類：大眾運輸人員排班問題，航 空公司人員排班問題和一般人員排班問題。 一、大眾運輸人員排班( m a s st r a n s i tc r e ws c h d u l i n g ) 相關(guān)名詞解釋： 1 、車旅次“e h l c l eb l o c k ) 指單車輛所執(zhí)行的最小工作量，通常為車輛從某一場 站( d e p o t ) l 出發(fā)至另場站的旅次，或是回到同場站的旅次。 2 、務(wù)( t r i p 或t a s k ) 指司機(jī)在同一車旅次內(nèi)所執(zhí)行的最小工作燕，其端點為換班 點( r e l i e f p o i n 0 或是場站( d e p o o 。 3 、連續(xù)乘務(wù)( p i e c e ) 一指司機(jī)在同一車旅次內(nèi)聯(lián)系服務(wù)的一組任務(wù)。 4 、工作班( s h i f t 或w o r k d a y ) 一指單一司機(jī)每日所服務(wù)的一組任務(wù)。 經(jīng)由分解，車旅次( v e h i c l e b l o c k ) 成為人員工作量的最小單位，即乘務(wù)( t r i p ) 。則 此乘務(wù)的組合問題即為大眾運輸人員排班的問題。在現(xiàn)實世界的人員排班問題中， 我們所需考慮的層面非常廣，如中午的休息時間、勞動法所規(guī)定的工作時間、工作 福利等等，因此所有的乘務(wù)被組合成許多組工作班( s h i f c ) 。若工作班之內(nèi)的連續(xù)乘務(wù) 太長，則表示違反勞動法。對于上面的情況，般來說有兩種解決方法，種方法 是在模型中加入嚴(yán)格的限制條件，另一種方法是在目標(biāo)函數(shù)中加入一個懲罰值來處 理。 ；百吃p 娩氣p 手； d e p o tor e l i e f p o m t s h i f t ：p i e c el + p i e c e2 圖3 一l 大眾運輸人員捧班問題名詞定義示意圖 二、航空公司人員排班 相關(guān)名詞解釋： l 、班次( n i g h tl e g ) 一指飛機(jī)在二城市間的飛行任務(wù)，與任務(wù)相似。 2 、班次鏈( d u t y ) 一指一組聯(lián)系的班次構(gòu)成一班次鏈，與任務(wù)鏈相似。 3 、班次組合( p a i r i n g ) 指一組班次鏈構(gòu)成一班次組臺( p a i r i n g ) ，與工作班相似。 一般來說，航空公司排班問題分成兩個部分：第一部分為班次組合的產(chǎn)生；第 二部分為輪班表的產(chǎn)生。通常航空公司的人員排班問題即為構(gòu)建一組最小成本的班 次組合來滿足航空公司所排定的時刻表，只有班次組合產(chǎn)生后，才能去構(gòu)建一個月 或一星期的輪班表。 三、一般人員排班 一般人員排班泛指除上述兩類人員排班以外的排班問題，諸如護(hù)理人員排班 警察人員排班，作業(yè)人員排班等。由于此類問題與上述兩項相比屬于中小型問題 因此文獻(xiàn)上大多采用啟發(fā)式算法來進(jìn)行求解。 3 3 人員排班問題的算法探討 一般來說在人員排班問題的求解方法上，主要分為兩大類求解方法：一類是最 優(yōu)化算法、另類為啟發(fā)式算法。當(dāng)模型本身允許的求解時間較長時，則可使用復(fù) 雜程度較高的最優(yōu)化算法。但若模型本身具有及時性，或是模型規(guī)模過于龐大麗無 法求得最優(yōu)解時，為了能在有效的時間內(nèi)求得較優(yōu)的近似解，則可采用復(fù)雜程度較 低的啟發(fā)式算法。 一、最優(yōu)化算法( e x a c ts o l u t i o nm e t h o d s ) 目前對有關(guān)人員捧班問題最優(yōu)化算法的研究，在作法上通常將問題構(gòu)建成集合 涵盞( s e t c o v 晡n g ) 或集合分割( s e t p a 嘶t i o n i n g ) 模式，并配合最優(yōu)解的求解策略加以 求解，一般稱這種方法為集合涵蓋( 或集合分割) 法。m a r s t e n 在求解h e l s i n k ec i t y 的 公車司機(jī)排班問題時，將模式構(gòu)建成為一集合分割形式并簡化成一個最短路徑問題， 然后利用分枝界定法和次梯度法來進(jìn)行求解。 在求解鐵路司機(jī)排班問題時，主要將其分為兩個層面來探討，其一為工作班 ( c r e ws c h e d u l i n g ) 產(chǎn)生階段，另一個為工作輪班表( c r e wr o s t e r i n g ) 產(chǎn)生階段。在工作 班產(chǎn)生階段中，主要將現(xiàn)有時刻表的車次加以切割，并依照排班相關(guān)規(guī)定予以重新 組合成為工作班，主要目的則是以最少的工作班數(shù)目涵蓋時刻表上所有的車次，同 時期望成本最小，故視此階段為一多目標(biāo)集合涵蓋問題。該該問題的目標(biāo)分別為： ( 1 ) 使成本最小，( 2 ) 使工作班數(shù)目最小。主要求解過程是在每一次迭代的過程中，不 斷開發(fā)可行解的區(qū)域，把可行解代入目標(biāo)函式中來求解。在輪班表產(chǎn)生階段中我 們將其視為旅行銷售員問題( t r a v e l i n g - s a l e s m a np r o b l e m ，t s p ) 的延伸，依司機(jī)員輪 班規(guī)她的相關(guān)規(guī)定設(shè)計限制式，并加以求解，至于在求解過程中產(chǎn)生予迪圈的現(xiàn)象， 則是尋找適當(dāng)?shù)臄帱c，將兩個遛圈串連成為一個單一的迪圈，迪圈則視為司機(jī)員輪 班的周期，而且每個司機(jī)員皆須執(zhí)行到所有的工作班組合。 嚴(yán)格來說，上述解法并不髓算為最優(yōu)解法，因為在利用集合涵蓋( 或分割) 闖題 求解時，除非能證明所有的組合皆被考慮過，才有可能獲得最優(yōu)解。由于本排班問 題規(guī)模過于龐大，要列出所有可能的組合需要很長時間有鑒于此一般都利用啟發(fā) 式算法來縮小可行解的范圍，從而來進(jìn)行求解。 = 、啟發(fā)式算法( h e u t i s t i es o l u t i o nm e t h o d s ) 一般常見的人員排班問題皆屬于n p h a r d 問題，大多數(shù)研究都用啟發(fā)式算法 來進(jìn)行求解，從而來避免因為規(guī)模過大而無法有效地求得最優(yōu)解。而啟發(fā)式算法 一般又可分為兩太類；一類是構(gòu)造式( c o n s t r u c t i v es e a r c h ) 啟發(fā)式解法，另一類是 改良式( i m p r o v i n gs e a r e d 啟發(fā)式解法。前者通常以貪心算法( g r e e d y l ，插入法 ( i n s e r t i o n ) 以及節(jié)省法( s a v i n g ) 等來求解；后者則是以一個可行解為出發(fā)點，以交 換的方式持續(xù)改善所獲得的可行解。通常的方法有禁止搜尋法( t a b us e a r c h ) 、區(qū) 域搜尋法( l o c a ls e a r c h ) 、模擬退火算法( s i m u l a t e da n n e a l i n g ) 、遺傳算法( g e n e t i c a l g o r i t h m ) 等。本研究則用遺傳算法來求解人員捧班問題，這在后面章節(jié)中會將遺 傳算法做一詳細(xì)的介紹。 c a m p b e l l ，k e v i nw e t a l 【1 刀利用模擬退火算法( s i m u l a t e da n n e a l i n g ) 求解航空組 員的月執(zhí)勤組合。主要思路是：( 1 ) 任意選取目前可行月執(zhí)勤組合中的兩組合上 的一個執(zhí)勤航班微交換，若交換前與交換后的成本差符合式3 - 1 或式3 - 2 則予以 交換；否則放棄并重新選取；( 2 ) 適當(dāng)?shù)亟档蛅 值：( 3 ) 若演算代數(shù)達(dá)到預(yù)定或未 能有效改善目標(biāo)函數(shù)則停止；否則回到步驟( 1 ) 。 i f ( 交換前與交換后的成本差1 o( 式3 1 ) i f ( 某設(shè)定的任意數(shù)) 1 0 ，在全局最大值周圍有一圈脊，使得 函數(shù)有無數(shù)個局部極大值，且極大值與全局最大值非常接近。這樣，算法在搜索時 很容易陷入局部極大值，但函數(shù)只有個全局最大值。本文算法與文獻(xiàn)【1 8 1 所用s g a 的仿真結(jié)果進(jìn)行了比較，群體大d 、( 1 0 0 ) 、編碼長度和給定閾值與文獻(xiàn)相同，算 法獨立運行3 0 次取平均值。仿真結(jié)果比較如表5 1 所示，從中可以看出本文所提 算法能以較快的速度收斂剄全局最大值。 表5 1 ：人工免疫算法與s g a 的結(jié)果比較 編碼最大迭代 s g a人工免疫算法 函數(shù)閥值平均迭阻滯平均迭阻滯 長度次數(shù) 代次數(shù)次數(shù)代次數(shù)次數(shù) 2 20 9 9 92 0 01 7 3 92 31 1 0 46 _ 本文借鏊免疫機(jī)理來提高遺傳算法的全局和局部搜索性能，并且大大改善了早 熟收斂的缺陷。雖然本文只是把免疫的思想應(yīng)用于函數(shù)優(yōu)化。但是，除此之外，免 端 + l 礅而 第六章基于遺傳算法的人員排班問題研究 6 1 工作班集合產(chǎn)生模式的構(gòu)建 6 1 1 模式的構(gòu)建 本階段的主要目的是將所有乘務(wù)，在考慮相關(guān)限制的條件下予以適當(dāng)?shù)倪B結(jié)， 產(chǎn)生一組可行工作班的集合，以作為下一階段處理排班問題時的搜索空間，本人 將此一問題定為一多剛示集合涵蓋問題( s e t c o v e r i n gp r o b l e m w i t h m u l t i o b j e c t i v e s ) 。 參照【i 5 】于文獻(xiàn)中的做法，以網(wǎng)絡(luò)的概念來產(chǎn)生符合限制條件的可行工作班集合( 結(jié) 合某鐵路公司現(xiàn)有的排班特性) 。關(guān)于以網(wǎng)絡(luò)概念作為可行工作班集臺產(chǎn)生的做 法，首先是排出兩乘務(wù)間所有符合規(guī)則且可行的接續(xù)組合做為基本的乘務(wù)連結(jié)， 從而形成多乘務(wù)的排班網(wǎng)絡(luò)。 6 1 2 可行工作班演算法 對于可行工作班的產(chǎn)生，主要有兩種方法：一是對所有乘務(wù)做判斷，其是否 加入工作班的組合中，依照窮舉法例出所有可行工作班組合，然后再逐步剔除不 符條件的工作班組合，產(chǎn)生一套可行工作班集合。在乘務(wù)變數(shù)不多的情況下，該 做法可以找出所有可能的乘務(wù)組合，但如果乘務(wù)數(shù)目太多，若要找出所有可能的 乘務(wù)組合，可能會達(dá)到龐大的數(shù)目。為增加求解效率，本人采用第二種方法即啟 發(fā)式演算法來產(chǎn)生可行工作班集合，由于上述的效率問題外，也考查了直接以遺 傳算法隨機(jī)挑選工作班，必須逐一檢查各項對某鐵路公司規(guī)則是否有違反，因為 個體在有限的可行解區(qū)間下極易產(chǎn)生違反限制的解。 本模式工作班產(chǎn)生方法主要以樹妝網(wǎng)絡(luò)結(jié)構(gòu)來產(chǎn)生所有工作班，在條件與限 制范圍內(nèi)，先列舉所有的基本乘務(wù)連結(jié)節(jié)線( b a s i cl i n k s ) ，再依此節(jié)線逐步擴(kuò)充 至多乘務(wù)連結(jié)規(guī)模，每一階層皆保留其工作班數(shù)至可行工作班集合中，可行工作 班網(wǎng)絡(luò)結(jié)構(gòu)如下圖6 1 所示9 1 ，其中t ，為乘務(wù)節(jié)線，成本為該乘務(wù)j 的工作時間， 包括乘務(wù)時間與一般工作時間；r 為乘務(wù)間休息節(jié)線；連接兩起迄端點某地站的為 4 a 起始、結(jié)束節(jié)線，表示一個工作班的開始或結(jié)束： ， 呻 ( 注：乘務(wù)節(jié)線 f ，一+ 休息節(jié)線 r - - - - 起始， 結(jié)束節(jié)線) 圖6 - 1 可行工作班產(chǎn)生網(wǎng)絡(luò)示意圖 演算主要分為四個步驟，分別是：l 、乘務(wù)連結(jié)節(jié)線的產(chǎn)生，2 、多乘務(wù)工作 班的產(chǎn)生，3 、可行工作班集合的產(chǎn)生，4 、以排序準(zhǔn)則和篩選方式控制乘務(wù)分布 需求。具體分述如下： 一、乘務(wù)連結(jié)節(jié)線的產(chǎn)生 乘務(wù)連結(jié)節(jié)線指的是任兩個乘務(wù)所串接而成的可行組合，對圖6 1 而言即為 所有可行休息節(jié)線組合，其屬性為兩個乘務(wù)( 包括前乘務(wù)與后乘務(wù)) 與連結(jié)節(jié)線， 節(jié)線表示“前乘務(wù)”在合法的狀態(tài)下可接續(xù)“后乘務(wù)”。簡單地來說，每個最終產(chǎn) 生的工作班都是由一個或數(shù)個乘務(wù)連結(jié)節(jié)線所組成( 如2 個乘務(wù)工作班需一條乘 務(wù)連結(jié)節(jié)線，3 個乘務(wù)工作班需2 條乘務(wù)連結(jié)節(jié)線。) ，在一些連結(jié)準(zhǔn)則如休 息時間長短的條件限制下，本步驟目的是產(chǎn)生所有可行乘務(wù)連接節(jié)線，形成基本 連結(jié)的資料集合，以完成后續(xù)的多乘務(wù)工作班組合。 為了列舉出可能的乘務(wù)連結(jié)現(xiàn)象，所以本步驟給予的限制條件傾向于寬松， b 因此僅以休息時間為考慮。此外觀察菜鐵路公司實際排班情形可以分析出四種主 要的乘務(wù)連結(jié)現(xiàn)象，分別為：1 、日班情形；2 、夜班情形；3 、同部列車連續(xù)乘務(wù) 情形；4 、特殊乘務(wù)情形。 1 、日班情形 日班乘務(wù)的連結(jié)情形指的是乘務(wù)的連結(jié)并不需要考慮到過夜時間的問題，因此 兩乘務(wù)間連結(jié)的間隔時間( 即休息時間) 較短，此一情形多發(fā)生于乘務(wù)到站時間 為晚上2 0 ：0 0 之前。本人參考某鐵路公司某地機(jī)務(wù)段實際排班情形，將乘務(wù)串接 的原則歸納如下： ( 1 ) 、車站接續(xù)。 ( 2 ) 、乘務(wù)之間隔時間區(qū)間為7 0 分鐘 6 小時( 實際情形整理) 。 ( 3 ) 、符合工作班產(chǎn)生規(guī)定的工作時間上限。 2 、夜班情形 為了使夜間到站的乘務(wù)能符合外段過夜休息或中退返家休息的作法，乘務(wù)連 結(jié)間的間隔時間應(yīng)較目班情形寬松，由某鐵路公司夜班排定現(xiàn)象可知，其最大間 隔為5 9 3 分鐘，故本研究以較寬裕的時闖l o 小時( 6 0 0 分鐘) 作為夜班乘務(wù)間隔 時間的上限值。因此關(guān)于夜班乘務(wù)連結(jié)的原則歸納如下： ( 1 ) 、同一車站接續(xù)。 ( 2 ) 、兩乘務(wù)的間隔區(qū)間為7 0 分鐘1 0 小時( 實際情形整理) 。 ( 3 ) 、符合工作班產(chǎn)生的工作時間上限。 3 、同部機(jī)車連續(xù)乘務(wù)情形 本乘務(wù)連結(jié)的目的是希望產(chǎn)生同一車輛乘務(wù)形態(tài)的可能連結(jié)情形，對于有著 相同機(jī)車