基于神經網絡輔助的智能人員排班系統

陳子夷 豆亞杰 姜 江 楊克巍 譚躍進

人員排班是經典的組合優化問題,旨在根據已經確定的員工人數和工作時間段生成排班表.排班的難點在于各種不同的限制條件,例如員工對工作時間的偏好、法律、公司制度或者工作性質的要求,這些限制條件被稱之為硬約束和軟約束.硬約束是排班表必須滿足的條件,而軟約束在一定程度上可以違反,但必須為此付出代價,可以通過計算違反軟約束導致的懲罰值來評估排班表的質量.人員排班問題結構復雜且受到各種約束限制,導致此問題通常在計算上具有極高的挑戰性,因此,人員排班問題及其大多數變體被歸類為NP 難問題[1].

近20 年來,人員排班問題受到了來自運籌學、管理科學和計算機科學等相關研究領域研究者的極大關注.關于人員排班問題已有很多研究,這些研究可以被分為兩類：精確方法和元啟發式方法[2].精確方法主要包括整數規劃（integer programming,IP）[3-5]和約束規劃（constrained programming,CP）[6-8].其中,精確方法在特定的問題規模下可以找到最優解,但隨著問題規模和問題復雜度的增加,其時間成本也隨之變得非常昂貴,一般無法接受.為了解決這個問題,研究人員提出了元啟發式方法,包括可變鄰域搜索,遺傳算法和隨機算法以及各種定制的啟發式算法[9-14],這些方法可以在短時間內生成相對高質量的可行解,但是縮短的時間是以犧牲精確性為代價的.即便如此,這些復雜的方法仍然沒有得到很好的推廣應用,許多組織仍在手動安排排班表.

由于人員排班問題是從實際場景中提煉出來的經典組合優化問題,不同職業和工作場景的需求導致該問題長期以來沒有統一的問題定義與算例,因此,難以比較各種算法系統的優劣.于是,魯汶大學CODeS 研究團隊舉辦了排班競賽,并提出了用于幫助測試和開發算法系統的標準實例集合[15].而本文提出的基于神經網絡輔助的智能人員排班系統,正是基于該標準實例集合測試并開發,該系統的原理是使用深度神經網絡模型指導分支定界法以解決人員排班問題.它基于可學習的模型在分支選擇和修剪的過程中給出合理的建議.從對于人員排班這類經典組合優化問題的理論層面研究來看,該系統對于某些問題可以找到與已經證實的最優解相同懲罰值的可行解,利用深度神經網絡的輔助進行分支選擇和分支修剪,加快了求解過程.同時也探索了用自動化的方法解決人員排班問題和其他類似組合優化問題的可行性.從現實需求層面來看,人員排班問題在現實中對人員的需求隨著時間的變化具有不確定性,而深度神經網絡具有可學習性,因此,在前期積累好模型的訓練與學習,對于后期相同類型的離線排班問題求解上可以大大提高求解效率和質量.同時,希望利用深度神經網絡模型完成訓練之后使用便捷的優勢,達到更好的推廣效果.

該系統可用于解決標準集中的許多問題[15].這些問題都具有以下特征：

1）排班問題為離線排班模型；

2）問題的可行解決方案可以表示為矩陣,這些矩陣可以作為神經網絡的輸入進行傳遞；

3）可以通過一些矩陣變換將可行解轉變為最優解；

4）可以通過規劃模型對問題的目標和約束進行描述.

1 問題描述

在不同的工作情景下存在著很多人員排班問題,例如護士排班,酒店排班或其他情況.在人員排班問題中,有等待分配的員工,有不同時間段的班次,如早班和晚班,還有定義了分配排班時不同限制的各類約束.最終的排班表必須遵循所有的硬約束,同時盡量避免違反軟約束,當解決方案違反了軟約束時,將會產生一定的懲罰值.滿足所有硬約束條件的可行解可被視為一個可行的排班表.每個可行的排班表都有一個懲罰值,懲罰值取決于該可行排班表對于軟約束的遵守程度.而人員排班問題的目的就是找到一個滿足所有硬約束同時懲罰值最低的可行排班表.

1.1 問題建模

人員排班問題各符號可定義如表1 所示,其中,班次代表一天中不同的工作時段,可以通過不同的方式對班次進行分類,例如,按時間間隔（早班,中班,晚班）.不同的日期中,不同的班次需要的人員數量也不一樣.而排班的過程就是將人員按照約束要求分配到每天的不同班次中.在本文中,將解決方案視為一個矩陣,該矩陣中的每一個元素都代表著分配給員工的班次.

表1 符號定義Table 1 Definition of symbols

那么人員排班問題可以表述如下：

其中,式（1）是目標函數.式（2）～式（10）為問題的約束.式（2）規定了員工在一天之中最多只能被分配1個班次.式（3）規定了某些班次不能安排在特定的班次之后,比如第1 天上了晚班,則第2 天就不能再安排早班.式（4）用于限制可以分配給員工的每種類型的最大班次數量,例如,某些員工可能是兼職,只能上夜班不能上早班.式（5）限制了每個員工的最小和最大工作時間.式（6）和式（7）限制了最小連續工作班次和最大連續工作班次.式（8）以與最小連續工作班次約束類似的方式對最小連續休假天數進行了限制.式（9）限制了最大周末加班次數,如果員工在周六或周日被安排了班次,則認為該周末加班一次.式（10）描述了員工無法工作的特定日期[16].

2 深度神經網絡輔助的分支定界法

深度神經網絡輔助的分支定界法是將深度神經網絡模型集成到分支定界法的樹搜索過程中,以決定在搜索過程到達一個新的節點時,下一步選擇哪一個分支,修剪掉哪些分支.深度神經網絡模型通過對已有的排班問題的各種解決方案的監督學習,達到在搜索過程中輔助制定選擇和修剪分支的決策.該方法的核心思想是將每個可行解視為e×t 矩陣,通過幾種變化策略來對矩陣進行改變,從而逐漸接近最優解.在整個過程中,利用樹搜索來探索所有的可能性,輔以深度神經網絡模型來確定探索的順序,精簡搜索樹.每當搜索過程進入一個未探索節點時,深度神經網絡模型就會通過評估幾種既定的變化策略得到的子節點,預測哪一種變化策略得到的子節點具有最高的概率通向最佳解決方案,從而確定下一個搜索的節點.同時,通過對各個子節點的下界進行預測,修剪掉預測的下界比當前最優解懲罰值更高的節點,達到精簡搜索樹,縮短搜索時間的目的.

2.1 分支定界法

分支定界法可用于解決優化問題.分支定界法是從搜索樹的根節點開始,通過系統地探索根節點的子節點以及它們的后續節點來探索搜索樹.分支是不斷給樹增加新的子節點,而定界是在分支的過程中檢查子問題的下界,如果該下界比當前最優解差,那么就修剪掉這一支.直到達到停止條件,整個搜索流程結束.給定優化問題的解決方案可以理解為樹中的葉節點[17].

在整個搜索過程中,搜索樹中的每個節點代表著符合硬約束可行的人員排班表,即一個可行的解決方案.初始解決方案由根節點表示.每一個節點的對應子節點代表著根據既定變化策略的一次變化可以達到的最佳解決方案.

有許多種方法可以對矩陣進行簡單的變換,例如隨機交換矩陣中的兩行或者兩列,改變矩陣中的某個數字.為了使搜索過程收斂的更快,本文在第3章通過一些實驗確定了3 種變化策略,如圖1 所示.

圖1 變化策略示意圖Fig.1 The schematic diagram of variation strategies

策略1：隨機交換兩名不同員工同一天的班次.策略2：隨機交換同一名員工不同兩天的班次.

策略3：隨機選擇一名員工的休假日,將其安排為隨機班次.

2.2 深度神經網絡

深度神經網絡,是一種模仿生物神經網絡的結構和功能的模型,用于對函數進行估計或近似.神經網絡由大量的神經元聯結進行計算.每個神經元從上一層神經元接受一個或者多個加權輸入,將這些輸入匯總后由激活函數處理,所得的值將傳輸給下一層的神經元.深度神經網絡通過優化各層神經元之間連接的權重值來進行學習.深度神經網絡既可以用來解決分類問題（解空間由一組離散值組成）,又可以用于回歸問題分析[18]（解空間可以是實數中的任意值）.在本文中,使用的是回歸網絡模型.其中,分支決策深度神經網絡模型用來預測輸入的解決方案可能接近最優解的概率,而分支修剪深度神經網絡模型用來預測輸入的解決方案的最優下限.分別定義“距離”和“概率”來說明解決方案可能接近最優解的概率的含義.

定義1 距離：當前解決方案通過既定變化策略轉化為最優解決方案需要的變化次數.

定義2 概率：當前解決方案通過既定變化策略可以轉化為最優解決方案的可能性.對于

相應的,當前解決方案與最優解決方案之間的距離越短,概率越高,那么當前解決方案可以通過搜索得到最優解決方案的可能性也就越大.圖2 展示了距離和概率的關系示意圖.

圖2 距離和概率關系示意圖Fig.2 The schematic diagram of the relationship between the distance and the probability

下面介紹了進行分支決策的深度神經網絡模型在分支定界法中如何發揮作用.如圖3 所示,當搜索進度到達了某一節點A 時,對該節點依次采用3 種變化策略進行矩陣變換,變換后所得子節點分別為B,C 和D,將這3 個節點對應的解決方案矩陣作為輸入傳輸進分支決策深度神經網絡模型.通過分支決策模型得到輸出,該輸出即代表對應節點的概率值.然后使用這些輸出來確定下一步應該探索節點A 的哪些分支（例如,首先探索與對應概率值最高的節點所在分支,在圖3 中,子節點C 對應的概率最高,在概率優先的策略下,先探索子節點C）.概率值的存在不僅僅為這些子節點提供了一個先后排名,也可以代表由分支決策模型給予每個子節點的置信度.

圖3 分支決策深度神經網絡模型Fig.3 The deep neural network model of branch decision-making

定界決策深度神經網絡模型與分支決策模型具有相似的結構,如圖4 所示.兩種模型都使用同一個輸入（與子節點B,C 和D 對應的解決方案矩陣）,不同的是,定界決策模型的輸出代表所預測的該分支的最佳下界,這意味著如果后續搜索沿著該分支往下,可能會得到的最終最佳懲罰值的大小.所以,如果預測的最佳下界超過或等于當前已經找到的最佳解的懲罰值,那么該分支就不具有繼續探索的價值.由于定界決策模型在預測過程中波動稍大,因此,可以將其乘以0～1 之間的權重以減少其啟發式下限.圖4 顯示了整個搜索流程中定界決策的示例.其中,第1、2、3 個節點的輸出分別代表圖中子節點B,C和D 通過分支決策模型所得到的最佳預測下界,通過分別與目前已找到的最優懲罰值對比,在圖中所示的情況下,將修剪掉子節點B 和D,因為對它們預測的最佳下界已經大于當前的已經找到的最佳懲罰值.

圖4 定界決策深度神經網絡模型示意圖Fig.4 The schematic diagram of deep neural network model of bounding decision-making

本文使用的深度神經網絡第1 層為輸入層,它具有e×t 個節點,用于將輸入的多維矩陣一維化.中間層為隱藏層,其層數和每層的節點數通過參數調整確定.隱藏層的每個節點的激活函數均為ReLu 函數,其定義為ReLu=max {0,x}.輸出層只包括一個節點,用于輸出所預測的概率或最優下限.

2.3 深度神經網絡輔助的分支定界法

在進行樹搜索時可以采用多種搜索策略,例如,盡可能深地搜索樹的分支的深度優先搜索策略,沿著樹的寬度遍歷樹節點的廣度優先搜索策略.在本文中,參考了“深度優先搜索”的概念,并通過不同的方式對其進行了改進.新的搜索策略可以根據深度神經網絡模型給出的概率值來搜索樹中的節點,并考慮懲罰值的.本文將在下面詳細討論這些策略.

1）深度優先搜索.深度優先搜索是用于遍歷或搜索樹或圖的算法.該算法盡可能深地搜索樹的分支.當某一節點的所有邊都被搜索之后,搜索將回溯到發現該節點的那條邊的起始節點.這一過程一直進行到已發現從源節點可達的所有節點為止.如果還存在未被發現的節點,則選擇其中一個作為源節點并重復以上過程,整個進程反復進行直到所有節點都被訪問為止.這種算法不會根據圖的結構等信息調整執行策略[19],如圖5 所示.根據深度優先原則,節點0 是開始的初始節點.然后從節點0 的所有未探索子節點的最左邊的節點開始,節點1 是第1 個被探索的節點.同理,探索完節點1 之后,接著探索節點2 而不是探索同一層的節點6,直到到達該分支的最底部節點3.接下來返回到節點6,重復深度優先遍歷,直到訪問了樹中的所有節點.節點上的數字代表了搜索的順序.

圖5 深度優先搜索示意圖Fig.5 The schematic diagram of depth-first search

2）概率優先搜索.該策略仍然遵循了盡可能深地搜索樹的原則.但是,本文通過深度神經網絡模型為樹中的每個節點附加了一個概率值,然后將其用于替換最左優先順序.這意味著在探索某一節點的子節點時,將首先探索具有較高概率值的子節點,而不是最左側的子節點,即原來的變化策略1 所得到的子節點.但是,概率優先這一原則僅適用于具有同一父節點的同一層的子節點.對于不在同一層中的節點或不具有同一父節點的子節點,此原則不適用,如圖6 所示.雖然是同一個搜索樹,但是由于附加的概率不同,因此,搜索的順序也不同.

圖6 概率優先搜索示意圖Fig.6 The schematic diagram of probability first search

3）懲罰值加權搜索.在人員排班問題中,懲罰值決定了解決方案的質量.懲罰值加權搜索就是在以概率優先搜索的基礎上,加權考慮懲罰值的影響.本文需要將概率和懲罰值標準化為相同的度量單位,并賦予它們不同的權重,以得到一個值來代替先前策略中的概率值.

2.4 搜索流程

在構建并訓練了深度神經網絡模型之后,本文將它應用于整個的搜索流程之中.當搜索進度到達某一節點時,如前文所述,通過3 種既定的解決方案,將該節點相關聯的解決方案矩陣進行變化,遍歷每種變化策略中的所有可能性并獲得3 個變化后的解決方案集合.然后將3 個集合中所有的解決方案矩陣輸入分支決策深度神經網絡模型,這些數據將通過神經網絡進行傳播,并到達輸出層,在輸出層中使用激活函數來獲取0～1 之間的結果,這些結果便可以被視為概率.然后,將每個策略所得集合中概率最高的結果留下來,作為該策略分支的子節點,因此,對應3 個策略,每個父節點都會有3 個子節點.將這些子節點再次輸入給定界決策深度神經網絡模型,將模型輸出的結果與當前已找到的最優懲罰值進行比較,如果小于當前已找到的最優懲罰值,則保留該子節點對應的分支,否則修剪掉該子節點對應的分支.而這些留下的子節點對應的概率將用于確定其探索順序,決策過程由上一節提出的搜索策略確定,例如,首先通過概率優先搜索原則探索概率最高的節點.圖7 展示了整個搜索流程示意圖.

圖7 搜索流程示意圖Fig.7 The schematic digram of search process

3 實驗

本章中,將在標準實例[15]上驗證本文系統,并嘗試回答以下3 個問題：

1）不同的變化策略組合對系統算法的性能有何影響？

2）不同的搜索策略對系統算法的性能有何影響？

3）該系統算法的求解速度及求得的解的質量如何？

針對第1 個問題,本文比較了不同變化策略所組成的組合.針對第2 個問題,本文通過同樣的標準實例對深度優先搜索、概率優先搜索和懲罰值加權搜索進行比較,以找到合適的搜索策略.針對第3 個問題,將本文系統用于標準實例集中實例1～實例8并觀察系統的表現.

3.1 實驗設置

構建本系統時,在輸入層中設置了足夠數量的節點以保證系統可以用來學習和預測不同規模的實例（冗余的節點將被分配空值）.所使用的訓練數據為標準實例集中的實例1,排班周期從星期一開始,排班天數為14 d,包含一種班次類型和8 名員工,更加詳細的參數設置請參考人員排班問題標準實例[15].在完成訓練后,嘗試使用本系統去完成以下不同的實驗.

3.2 實驗1：變化策略組合比較

分支定界法搜索過程中正確的變化策略對于搜索的速度至關重要.因此,本文提出了變化策略的4種不同可能的組合.在這4 種組合中,每種策略都是對矩陣進行變化的基本方法.例如,“連續2 d 交換2位護士的班次”可以通過連續使用兩次策略1“隨機交換兩名不同員工同一天的班次實現”.本文在標準數據集上訓練模型,然后將模型應用于具有不同變化策略組合的算法,以評估它們對算法性能的影響.用于比較的變化策略組合如下：

組合1：

策略1：隨機交換兩名不同員工同一天的班次.

策略2：隨機交換同一名員工不同兩天的班次.

策略3：隨機選擇一名員工的休假日,將其安排為隨機班次.

組合2：

策略1：隨機選擇一名員工的工作日,將其安排為休假日.

策略2：隨機交換同一名員工不同兩天的班次.

策略3：隨機選擇一名員工的休假日,將其安排為隨機班次.

組合3：

策略1：隨機交換兩名不同員工同一天的班次.

策略2：隨機選擇一名員工的工作日,將其安排為休假日.

策略3：隨機選擇一名員工的休假日,將其安排為隨機班次.

組合4：

策略1：隨機交換兩名不同員工同一天的班次.

策略2：隨機交換同一名員工不同兩天的班次.

策略3：隨機選擇一名員工的工作日,將其安排為休假日.

評價算法的標準是懲罰值的大小（解的質量）和解決問題的平均時間（當前最佳懲罰值的收斂過程）.由于某些的方法找到的最終解決方案并非最優,因此,將使用最終懲罰值來代表在完整算法過程中找到的最佳解決方案.

從表2 可以看出,從最終解的懲罰值來看,組合1 可以找到與已知最優解相同懲罰值的解決方案,而組合2、組合3 和組合4 都無法到達已知最優解,說明這3 種變化策略的組合欠缺某種可以達到最優解決方案的變化形式.從運行時間上來看,組合1 用時36.12 s,排名第3,但它與組合2 和組合3 的時間差距是可以接受的,僅僅在30 s 之內.盡管組合2 和組合3 在總時間上略好于組合1,但它們的最終解懲罰值卻比組合1 差.這與變化策略的組合緊密相關.策略1“隨機交換兩名不同員工同一天的班次”可以確保解決方案矩陣的元素可以上下交換.策略2“隨機交換同一名員工不同兩天的班次”可以確保解決方案矩陣的元素左右互換.策略3“隨機選擇一名員工的休假日,將其安排為隨機班次”可以控制矩陣中不同元素的數量.這3 種策略可以確保組合所能作出的變換涵蓋所有可能性.

表2 變化策略組合比較結果Table 2 Comparison results of variation strategy combination

3.3 實驗2：搜索策略比較

為了找到最佳的搜索策略,需要比較上述3 種搜索策略,即深度優先搜索,概率優先搜索和懲罰值加權搜索.從表3 可以看出,概率優先搜索和懲罰值加權搜索都可以找到懲罰值與已知最優懲罰值相同的最終解決方案,雖然概率優先搜索需要的時間更長,但是只有不到7 s.而深度優先搜索的性能則遠不及前兩者.因此,結果表明,在分支定界方法中引入深度神經網絡模型具有一定的效果.最終結果進一步證明了將深度神經網絡與分支定界法相結合的方法確實有效.與概率優先搜索相比,懲罰值加權搜索的尋優速度要更快一點.這就是本文提出懲罰值加權搜索的原因.通過在選擇分支時為懲罰值賦予一定的權重,可以幫助搜索樹在搜索時盡可能快地到達根節點.

表3 搜索策略比較結果Table 3 Comparison results of search strategies

3.4 實驗3：標準實例應用

用于評估系統的標準實例的參數如表4 所示,結果如表5 所示,神經網絡決策的分支定界法在用于驗證的8 個實例中,有4 個找到了與已知的最優懲罰值相同懲罰值的解決方案,而在剩余4 個實例中的表現也并不差,最大的差距僅為8%,結合表4和表5 可以看出,隨著問題規模變大,求解所需時間也更長,這是因為該系統是基于遍歷搜索設計,因此,問題規模越大,所要搜索的解空間也就越大.可能需要更多時間才能獲得更好的結果.但是8 個標準實例所求解所需時間最長為583.69 s,不到10 min,處于可接受的時間范圍之內,這證明該系統可以應用于標準實例集并進行推廣.

表4 標準實例部分參數Table 4 Partial parameters of standard instances

表5 求解標準實例結果Table 5 Results of the solution of standard instances

除此之外,本文將該系統與前人代表性方法就該問題的求解能力進行了對比,表5 的第5 列～第9列分別列出了整數規劃方法、約束規劃方法、可變領域搜索方法、模擬退火方法和彈射鏈方法在10 min的求解時間中[16,20-22],針對實例1～實例8 的求解結果,從表5 可以看出,整數規劃方法作為經典的精確方法,在所有實例上都表現出良好的性能,在實例1～實例7 中都求出了與最優懲罰值相同懲罰值的解決方案,同樣屬于精確方法的約束規劃方法在大部分實例上都表現出了良好的性能,僅在實例5、實例6 和實例8 上與最優懲罰值差距明顯,可變領域搜索方法在所有實例上都取得了較好的條件,但僅僅在實例1 上可以求出與最優懲罰值相同懲罰值的解決方案,經過設計模擬退火方法的表現僅次于整數規劃方法,同樣在實例1～實例7 上求出了與最優懲罰值相同懲罰值的解決方案,僅在實例8 的結果質量上略差于整數規劃方法,而彈射鏈方法則表現較差,除了實例1、實例2 和實例4 外,彈射鏈方法針對其他實例的求解質量均與其他方法求出的解決方案質量有較為明顯的差距.而本文設計的系統與其他方法相比仍具有競爭力,針對所有實例的求解結果均優于彈射鏈方法和可變領域搜索方法,與精確方法約束規劃方法相比,僅針對實例4 的求解結果略差于約束規劃方法,針對剩余實例均表現出了相同或更優秀的性能,與整數規劃方法和模擬退火方法相比,針對實例1、實例2、實例3 和實例6,該系統均求解出了與最優懲罰值相同懲罰值的解決方案,針對剩余4 個實例,該系統的求解結果與整數規劃方法和模擬退火方法的差距也十分微弱.因此,從表5 展示的結果和以上分析可以看出,神經網絡輔助的分支定界法在求解時間和解決方案質量方面都有較為優秀的表現,說明了將深度神經網絡模型引入分支定界法是有意義的.

4 結論

基于神經網絡輔助的智能人員排班系統,使用深度神經網絡來輔助分支定界法的分支選擇和分支修剪.通過實驗表明,在標準實例中,該系統可以找到與最佳解決方案相同或接近的良好解決方案.深度神經網絡決策的分支定界法只需很少的用戶輸入即可解決問題,系統設計了4 種變化策略組合和3種搜索策略來進行比較,它主要依靠提供的當前最佳解決方案來學習如何自行構建解決方案.

該系統對于某些問題可以找到與已經證實的最優解相同懲罰值的可行解,同時利用深度神經網絡的輔助進行分支選擇和分支修剪,加快了求解過程.這探索了用自動化的方法解決人員排班問題和其他類似組合優化問題的可行性.因此,該系統的應用有良好的前景,并不僅僅局限于人員排班,通過對解決方案轉化為矩陣并對其進行結構性改變,同時利用深度神經網絡進行輔助決策,可以為整個搜索過程提供有導向的有依據的決策.

目前國內中小企業、酒店、醫院和高等院校等人員排班基本依靠人工經驗來完成,如果可以與相應單位進一步的交流和溝通,依據歷史數據對模型進行針對性的訓練和學習,該系統算法可以作為后期推廣應用的理論基礎.

未來如果可以將其他優化問題建模為具有相似特征的標準模型,則可以將該系統的方法論應用于其他類似的優化問題.同時,如果可以將深度強化學習引入該方法,則可以使得模型在自適應訓練學習的實時性上更進一步.這使對于人員排班這一經典組合優化問題的研究更具有實際價值和應用潛力.