基于自適應(yīng)模擬退火算法的服務(wù)業(yè)智能排班系統(tǒng)

陳學(xué)文 陳銳瀚 李志 陸運勇 朱健君 唐奕澤 葉敏華 李升

摘要：人員排班管理對于服務(wù)行業(yè)，特別是飯店、超市和零售店等領(lǐng)域具有重要意義。然而，目前在服務(wù)行業(yè)的排班管理領(lǐng)域，排班編制工作主要依賴于人工手動操作，這導(dǎo)致了排班表生成效率的低下問題。對于傳統(tǒng)排班系統(tǒng)的架構(gòu)問題，傳統(tǒng)的單體架構(gòu)隨著功能增多而出現(xiàn)橫向擴展難、模塊之間緊密耦合、更新和維護困難等問題，難以適應(yīng)不斷變化的排班需求。為了解決這些難題，該研究采用了自適應(yīng)模擬退火算法，并結(jié)合了TPE-BP神經(jīng)網(wǎng)絡(luò)、Web技術(shù)與微服務(wù)架構(gòu)等，成功開發(fā)出了一套能夠滿足大部分服務(wù)行業(yè)門店排班需求的智能排班系統(tǒng)。該系統(tǒng)按功能拆分為多個服務(wù)模塊，有效地降低了系統(tǒng)耦合度，高度可擴展，能夠自動化、靈活化、高效化地進行排班編制，提高了排班表生成的效率，為服務(wù)行業(yè)提供了更為便捷和智能的排班管理工具。

關(guān)鍵詞：智能排班；自適應(yīng)模擬退火；微服務(wù)架構(gòu)；服務(wù)行業(yè)

中圖分類號：TP311? ? ? 文獻標(biāo)識碼：A

文章編號：1009-3044（2023）35-0038-05

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）

0 引言

人員排班管理對于服務(wù)零售等行業(yè)具有重要意義。目前，在服務(wù)行業(yè)中，主要依賴手動排班來分配人力資源以降低成本，通過人工計算和制定排班表格，這一流程不僅煩瑣耗時，而且伴隨多個問題。此外，協(xié)調(diào)不同門店值班人員時，必須滿足多重約束條件，包括員工的崗位匹配和技能要求、員工的意愿工作時間，以及門店的具體工作需求[1]。使用人工方式進行排班容易引發(fā)錯誤，通常造成排班表不符合門店甚至行業(yè)要求，很難確保最佳的排班結(jié)果。此外，值班員工的時間安排受到多項限制，服務(wù)行業(yè)相關(guān)規(guī)定包括連續(xù)值班時長、休息時間、每周總值班時長，以及每月總值班時長等多項要求。這些規(guī)定對門店的員工排班加以限制，直接影響員工的薪酬，然而手動排班難以確保這些規(guī)定的公平和合理性，這也導(dǎo)致了人力資源的不合理分配問題[2]。

當(dāng)前，已有研究學(xué)者研究了智能排班。1992年，Melachrinoudis.E和Olafsson.M提出一種移位選擇整數(shù)線性規(guī)劃模型，并將其有針對性地應(yīng)用于當(dāng)時位于馬薩諸塞州波士頓的Stop & Shop超市商店[3]。2018年，宋兵結(jié)合貪心算法與Web技術(shù)，開發(fā)了一個專為沈陽空中交通管制中心設(shè)計的管制員智能排班系統(tǒng)[4]。在2023年，夏天舒等人設(shè)計了一種基于遺傳算法的銀行員工智能排班算法[5]。以上研究均提高了他們所針對研究區(qū)域的人員排班效率，但它們的普適性有限。為了滿足服務(wù)行業(yè)門店的排班需求，開發(fā)一款智能員工排班系統(tǒng)，集成了自動化生成推薦排班表功能，以替代傳統(tǒng)的手動排班，同時提供便捷而安全的排班數(shù)據(jù)管理，顯然至關(guān)重要。

該系統(tǒng)采用B/S架構(gòu)，使用Python進行數(shù)據(jù)處理和核心算法的編寫，Java服務(wù)端開發(fā)技術(shù)用于排班管理業(yè)務(wù)邏輯的實現(xiàn)。系統(tǒng)架構(gòu)基于MVC模型，以實現(xiàn)用戶界面和服務(wù)端應(yīng)用邏輯完全解耦。此外，該架構(gòu)還秉承分布式系統(tǒng)理論，確保了系統(tǒng)的高可用性和卓越的擴展性。門店需求預(yù)測功能采用TPE-BP神經(jīng)網(wǎng)絡(luò)算法，根據(jù)門店歷史客流量數(shù)據(jù)以及其余特征來預(yù)測未來客流量，為排班提供依據(jù)。排班功能利用自適應(yīng)溫控模擬退火算法，根據(jù)員工的多種工作偏好和門店規(guī)則自動生成合理的員工排班表。管理員可以生成、預(yù)覽、保存和查詢本周或下幾周的排班表，查看和調(diào)整詳細的日排班，支持靈活的班次指派。

1 系統(tǒng)總體框架

根據(jù)模塊化思想將本系統(tǒng)分為三個功能模塊，分別是綜合信息管理模塊、門店需求預(yù)測模塊、智能員工排班管理模塊。

以管理員身份成功登錄系統(tǒng)后，在綜合信息管理模塊，管理員具備查詢門店和員工信息的權(quán)限，同時可根據(jù)實際需求進行信息的增加、刪除、修改和查詢操作。在門店需求預(yù)測模塊中，管理員可以選擇特定時間段進行客流量的預(yù)測，以進一步分析門店所需員工數(shù)量。在自動排班模塊，管理員能夠獲得各時段的員工需求人數(shù)以及相應(yīng)的排班表，一旦操作完成，排班表將被更新并管理員可以安全退出系統(tǒng)。本系統(tǒng)的主要功能模塊示例如圖1所示。

2 數(shù)據(jù)庫設(shè)計

本系統(tǒng)使用MySQL數(shù)據(jù)庫，MySQL作為一款廣泛應(yīng)用于多個行業(yè)的開源關(guān)系型數(shù)據(jù)庫管理系統(tǒng)，適用于各種數(shù)據(jù)規(guī)模的應(yīng)用，以其卓越的性能、可擴展性、易用性、安全性和低成本而享譽業(yè)界。在本系統(tǒng)主要用于存儲門店、員工以及排班相關(guān)信息，以實現(xiàn)排班數(shù)據(jù)的持久化。系統(tǒng)數(shù)據(jù)庫信息表詳見表1。

3 門店需求預(yù)測模塊算法流程

本系統(tǒng)的門店需求預(yù)測模塊采用了TPE算法來優(yōu)化BP神經(jīng)網(wǎng)絡(luò)的參數(shù)，以實現(xiàn)門店客流量的全自動預(yù)測。這一方法在無須管理員手動輸入模型參數(shù)的同時實現(xiàn)了最優(yōu)的客流量預(yù)測效果。

3.1 TPE算法原理

TPE算法采用對[px | y]和[py]同時建模的方法，代替僅對 [py | x]建模 [6]。在這里，[py]代表解的分布情況，而[px | y]代表已知解的情況下，參數(shù)[x]的分布情況。[px | y]的計算詳見式（1）：

[px | y=lx? ? ?y<y'gx? ? y≥y'] （1）

式中： [y']是一個預(yù)先定義的閾值; [lx]表示觀測值[xi]的損失函數(shù)小于[y']的密度估計值；[gx]表示觀測值[xi]的損失函數(shù)大于[y']的密度組成。

優(yōu)化標(biāo)準(zhǔn)[EI]的定義詳見式（2） 。

[EIy*x∝y+gxlx1-y-1] （2）

在最大化[EI]尋找更優(yōu)的超參數(shù)過程中，[EI]應(yīng)該逐步逼近最大概率的[lx]和最小概率的[gx]。

3.2 BP神經(jīng)網(wǎng)絡(luò)

BP神經(jīng)網(wǎng)絡(luò)屬于一種多層前饋神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)，由輸入層、隱藏層和輸出層構(gòu)成。BP神經(jīng)網(wǎng)絡(luò)實現(xiàn)步驟如下：

第一步：輸入數(shù)據(jù)序列[N=X1，X2... ，Xm]；經(jīng)權(quán)值和激活函數(shù)映射到隱藏層，生成新序列[W1，W2... ，Wn]，新序列即為隱含層輸入值。這些值通過隱藏層的激活函數(shù)[θ·]計算，然后經(jīng)過輸出層的權(quán)值和激活函數(shù)返回輸出值。

第二步：通過誤差的反向傳播不斷調(diào)整權(quán)重和閾值，推導(dǎo)公式詳見式（3） 、式（4） ：

隱藏層權(quán)值：

[Δwij=-γp=1p n=1NTpn-Opn??'netn?wji?φ'neti?xj] （3）

輸出層權(quán)值：

[Δwij=-γp=1p n=1NTpn-Opn?φ'netn?yi] （4）

其中，i表示隱藏層節(jié)點，j表示輸入層節(jié)點，k表示輸出層節(jié)點，γ表示學(xué)習(xí)率，[neti]表示神經(jīng)元i的輸入加權(quán)和，[wij]代表節(jié)點[i]到節(jié)點[j]之間的權(quán)值，n代表輸入層第[j]個節(jié)點的輸入值，[φ]表示隱藏層的激勵函數(shù)，[?]中代表輸出層激勵函數(shù)，[Tpk]表示輸出層第k個節(jié)點期望輸出值，[Opk]表示輸出層第[k]個節(jié)點的輸出值。

第三步：模型均方誤差計算公式詳見式（5） ：

[Ek=12j=1nYnj-ynj2] （5）

3.3 基于TPE優(yōu)化參數(shù)的BP神經(jīng)網(wǎng)絡(luò)

在本系統(tǒng)中，門店需求預(yù)測模塊采用TPE-BP神經(jīng)網(wǎng)絡(luò)算法，它以多種因素作為輸入特征，包括是否節(jié)假日、促銷活動的程度、上班高峰期、天氣預(yù)報狀況以及過去同一時間段的平均客流量，而本周該時間段的客流量則作為輸出特征進行訓(xùn)練。本系統(tǒng)的TPE-BP神經(jīng)網(wǎng)絡(luò)算法流程如圖2所示：

4 門店需求預(yù)測模塊算法流程

4.1 排班規(guī)則

在人工排班的情況下，排班規(guī)則通常多種多樣且缺乏規(guī)范性，然而，當(dāng)需要運用運籌學(xué)算法來實現(xiàn)排班時，各種規(guī)則必須以可表達的方式進行描述。如表2所示，這些規(guī)則需要進行分類并確定各自的優(yōu)先級。

4.2 自適應(yīng)模擬退火算法

模擬退火算法的理念源自固體退火原理，其在處理離散變量優(yōu)化和非線性優(yōu)化問題中具有獨特的優(yōu)勢受到了廣泛關(guān)注。模擬退火算法通過模擬金屬退火過程中的溫度變化來搜索問題的最優(yōu)解，以解決組合優(yōu)化問題。本系統(tǒng)的模擬退火算法進行了自適應(yīng)改進：

1） 初始溫度的改進：

不合適的初始溫度會影響模擬退火算法性能。因此，為提高算法性能，本系統(tǒng)設(shè)置了改進初始溫度，詳見式（6） ：

[T=-EXmax-EXminlnX] （6）

其中，E（Xmax） 和 E（Xmin） 分別代表解空間內(nèi)隨機選取的N個可行解對應(yīng)的目標(biāo)函數(shù)值的最大值和最小值。X值的設(shè)定范圍推薦為 （0.9， 0.99），而在本項目中，X的值默認(rèn)被設(shè)定為 0.99[7]。

2） Metropolis準(zhǔn)則的改進：

Metropolis準(zhǔn)則是決定是否接受經(jīng)過擾動的新解的關(guān)鍵步驟，這直接影響算法的性能和速度[8]。原始Metropolis準(zhǔn)則詳見式（7） 。

[P=? ? ? ? ? ? ? ? 1，? ? ? ? ? ? ? ? ?EXnew<EXolde- EXnew-EXoldT? ?EXnew>EXold] （7）

在不同規(guī)模的組合優(yōu)化問題中，[EXnew-E（Xold）]可能與當(dāng)前的T值存在數(shù)量級差異，導(dǎo)致 P 值過大或過小，從而影響算法的性能。本系統(tǒng)采用了改進的表達式，詳見式（8） ：

[P=e- EXnew-EXoldS?T] （8）

其中，[S=e- EXAverage-EXminT0]，[EXAverage]和[EXmin]分別表示從解空間內(nèi)隨機選取的N個可行解對應(yīng)的目標(biāo)函數(shù)的平均值和最小值，T0是初始溫度。通過S的調(diào)節(jié)，Metropolis準(zhǔn)則能夠更加靈敏地適應(yīng)[EXnew-E（Xold）]和當(dāng)前T值的數(shù)量級差異。

3） 溫度控制方式的改進

合適的溫度控制可以減少局部最優(yōu)解的風(fēng)險。因此，本系統(tǒng)針對智能員工排班問題的多目標(biāo)規(guī)劃，對傳統(tǒng)模擬退火算法的溫度控制方式進行了改進。當(dāng)溫度T小于終止溫度時，判斷是否還存在未成功安排的排班班次，若存在，則執(zhí)行如式（9） 所示的回溫公式：

[T=T+lnTinitial?Sizeschedule] （9）

其中：[Tinitial]是初始溫度，[Sizeschedule]為排班矩陣的大小。

本系統(tǒng)的改進模擬退火算法總體流程如圖3所示。

5 微服務(wù)系統(tǒng)架構(gòu)設(shè)計

微服務(wù)架構(gòu)是一種分布式系統(tǒng)架構(gòu)模式，該架構(gòu)將單個大型系統(tǒng)按功能拆分為多個相對獨立的服務(wù)模塊，以便進行開發(fā)和維護，并使用容器化技術(shù)進行服務(wù)部署。與傳統(tǒng)單體架構(gòu)相比，微服務(wù)架構(gòu)有高度可擴展、高內(nèi)聚、低耦合、故障可隔離以及資源利用率高等特點，這些特性提升了開發(fā)團隊的系統(tǒng)開發(fā)和維護效率。

5.1 系統(tǒng)架構(gòu)分析

本系統(tǒng)適合采用微服務(wù)架構(gòu)，系統(tǒng)可以按功能拆分為多個模塊，如綜合信息管理模塊、智能員工排班管理等，符合微服務(wù)的服務(wù)可拆分特性。此外，排班系統(tǒng)需要具備高度可伸縮性，以應(yīng)對門店排班工作負(fù)載的不斷變化。在實現(xiàn)綜合信息管理模塊和排班生成功能時，使用適當(dāng)?shù)募夹g(shù)可以提升排班效率。微服務(wù)架構(gòu)支持不同服務(wù)使用不同技術(shù)，使模塊的開發(fā)更加靈活、獨立。

當(dāng)系統(tǒng)排班請求流量較大時，使用單體架構(gòu)可能會導(dǎo)致單個服務(wù)無法處理大量請求，從而導(dǎo)致整個系統(tǒng)崩潰。但采用微服務(wù)架構(gòu)可以創(chuàng)建多個排班微服務(wù)實例，利用負(fù)載均衡器將請求均勻分布到各個排班微服務(wù)實例。當(dāng)微服務(wù)實例存在故障時，負(fù)載均衡器將自動隔離故障實例，并將請求分發(fā)到其他實例，確保了系統(tǒng)具有高可用性和可靠性。本系統(tǒng)的負(fù)載均衡器請求分發(fā)過程見圖4。

5.2 服務(wù)間的遠程調(diào)用

在本系統(tǒng)中，通過對服務(wù)進行拆分以減少耦合度，并將服務(wù)部署在不同容器或主機上，導(dǎo)致無法通過本地調(diào)用的方式實現(xiàn)必要的功能。為了確保各個服務(wù)能夠遠程調(diào)用彼此的接口，系統(tǒng)采用了OpenFeign技術(shù)，這是一種基于HTTP協(xié)議的RESTful API客戶端，具有聲明式特性，通常與Spring Cloud微服務(wù)框架一起使用。通過HTTP請求，OpenFeign允許訪問遠程服務(wù)。

集成該技術(shù)只需引入依賴，創(chuàng)建被調(diào)用服務(wù)的接口方法，并添加必要的注解即可啟用遠程調(diào)用功能。這種調(diào)用方式有良好的封裝性，調(diào)用者只需按照接口方法名進行調(diào)用，無須深入了解具體實現(xiàn)細節(jié)，類似于本地方法的調(diào)用方式。OpenFeign遠程調(diào)用圖如圖5。

在智能員工排班管理模塊中調(diào)用綜合信息管理模塊獲取員工信息及偏好列表如下流程。在實現(xiàn)流程中，智能員工排班管理模塊充當(dāng)接口的消費者服務(wù)，綜合信息管理模塊充當(dāng)生產(chǎn)者服務(wù)。

1） 創(chuàng)建一個feign模塊并在pom.xml項目文件引入OpenFeign的依賴。將所需實體類（員工類，員工偏好類）添加到feign模塊。

2） 在feign模塊中創(chuàng)建員工Client接口類，使用@FeignClient注解來標(biāo)識生產(chǎn)者服務(wù)的名稱。編寫接口方法，確保接口方法的路徑和請求方式與員工控制類對應(yīng)的接口一致。

3） 分別在生產(chǎn)者服務(wù)和消費者服務(wù)引入feign模塊的依賴，并在配置文件中配置feign的屬性。在這兩個服務(wù)的啟動類添加@EnableFeignClients注解以啟用Feign，并指定要掃描的Client的包路徑。

4） 在生產(chǎn)者服務(wù)的控制器類中編寫需要進行遠程調(diào)用的接口，包括獲取員工列表的接口和獲取員工偏好列表的接口。在消費者服務(wù)的服務(wù)層實現(xiàn)類中，當(dāng)使用上述兩個接口方法時，需要先將員工Client類的實例通過依賴注入的方式注入實現(xiàn)類，再調(diào)用接口方法獲取返回值。

6 系統(tǒng)主要功能模塊和頁面設(shè)計

6.1 綜合信息維護模塊

本系統(tǒng)綜合信息管理模塊包括門店信息子模塊和員工信息子模塊。門店信息子模塊具備對門店營業(yè)時間、門店地址、占地面積、門店員工的基本信息以及正式員工數(shù)量等信息進行“增加、刪除、修改、查詢”的功能。員工信息子模塊則允許根據(jù)員工的工號、性別、職位、技能等條件進行特定員工的查詢，同時也提供“增加、刪除、修改、查詢”的操作選項，頁面設(shè)計見圖6。

6.2 門店需求預(yù)測模塊

本系統(tǒng)門店需求預(yù)測模塊包含員工需求預(yù)測模塊和門店需求查詢模塊。員工需求預(yù)測模塊用于設(shè)定門店在特定時間段內(nèi)的客流量與員工需求量的預(yù)測。門店需求查詢模塊則用于在排班周期內(nèi)查詢各時段的需求人數(shù)。門店員工需求量是智能排班模塊制定具體員工班次的重要決策依據(jù)，頁面設(shè)計見圖7。

6.3 自動排班管理模塊

本系統(tǒng)智能員工排班管理模塊是系統(tǒng)的核心功能，該模塊采用自適應(yīng)溫控模擬退火算法，基于門店需求預(yù)測模塊生成的門店員工需求量，結(jié)合門店員工的工作時間偏好和請假情況等因素，生成詳細的員工排班表，并提供多種查詢功能以滿足不同需求。頁面設(shè)計見圖8。

7 結(jié)束語

本系統(tǒng)以服務(wù)業(yè)員工排班為案例，實際上是對具備一定條件的排列組合進行優(yōu)化。系統(tǒng)的門店需求預(yù)測模塊采用了TPE-BP神經(jīng)網(wǎng)絡(luò)，充分利用歷史客流量數(shù)據(jù)，實現(xiàn)了對未來門店客流量的全自動預(yù)測。同時，引入自適應(yīng)模擬退火算法到智能排班模塊中，有效解決了傳統(tǒng)模擬退火算法中需要手動設(shè)置參數(shù)的問題，實現(xiàn)了全自動排班。系統(tǒng)界面友好，操作簡便，具有高度實用性，可滿足服務(wù)零售門店的員工排班需求，為解決服務(wù)業(yè)排班問題提供了可行的解決方案。

參考文獻：

[1] 程丹丹，何利力.基于遺傳算法關(guān)聯(lián)規(guī)則的零售戶行為特征挖掘[J].工業(yè)控制計算機，2016，29（8）：116-117，120.

[2] 夏正洪，潘衛(wèi)軍.呼叫中心智能排班系統(tǒng)關(guān)鍵技術(shù)[J].計算機工程與設(shè)計，2015，36（5）：1332-1336.

[3] MELACHRINOUDIS E，OLAFSSON M.A scheduling system for supermarket cashiers[C]//Proceedings of the 14th annual conference on Computers and industrial engineering.ACM，1992：121-124.

[4] 宋兵.管制員智能排班系統(tǒng)設(shè)計[J].信息與電腦（理論版），2018（15）：77-79.

[5] 夏天舒，李宇豪，宣明輝，等.基于遺傳算法的銀行智能排班系統(tǒng)設(shè)計[J].現(xiàn)代信息科技，2023，7（12）：128-132，136.

[6] 查雯婷，閆利成，陳波，等.基于TPE-LSTM的區(qū)域超短期風(fēng)電功率預(yù)測[J].計算機應(yīng)用與軟件，2022，39（11）：25-30，111.

[7] 陳晟宗，張紀(jì)會，于守水，等.求解旅行商問題的波動溫控模擬退火算法[J].控制與決策，2023，38（4）：911-920.

[8] 湯飛，何永義.基于離散二進制粒子群-模擬退火算法求解0-1背包問題[J].工業(yè)控制計算機，2021，34（5）：83-84，86.

【通聯(lián)編輯：謝媛媛】