陈子夷 豆亚杰 姜 江 杨克巍 谭跃进
人员排班是经典的组合优化问题,旨在根据已经确定的员工人数和工作时间段生成排班表.排班的难点在于各种不同的限制条件,例如员工对工作时间的偏好、法律、公司制度或者工作性质的要求,这些限制条件被称之为硬约束和软约束.硬约束是排班表必须满足的条件,而软约束在一定程度上可以违反,但必须为此付出代价,可以通过计算违反软约束导致的惩罚值来评估排班表的质量.人员排班问题结构复杂且受到各种约束限制,导致此问题通常在计算上具有极高的挑战性,因此,人员排班问题及其大多数变体被归类为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 符号定义Table 1 Definition of symbols
那么人员排班问题可以表述如下：
其中,式（1）是目标函数.式（2）～式（10）为问题的约束.式（2）规定了员工在一天之中最多只能被分配1个班次.式（3）规定了某些班次不能安排在特定的班次之后,比如第1 天上了晚班,则第2 天就不能再安排早班.式（4）用于限制可以分配给员工的每种类型的最大班次数量,例如,某些员工可能是兼职,只能上夜班不能上早班.式（5）限制了每个员工的最小和最大工作时间.式（6）和式（7）限制了最小连续工作班次和最大连续工作班次.式（8）以与最小连续工作班次约束类似的方式对最小连续休假天数进行了限制.式（9）限制了最大周末加班次数,如果员工在周六或周日被安排了班次,则认为该周末加班一次.式（10）描述了员工无法工作的特定日期[16].
深度神经网络辅助的分支定界法是将深度神经网络模型集成到分支定界法的树搜索过程中,以决定在搜索过程到达一个新的节点时,下一步选择哪一个分支,修剪掉哪些分支.深度神经网络模型通过对已有的排班问题的各种解决方案的监督学习,达到在搜索过程中辅助制定选择和修剪分支的决策.该方法的核心思想是将每个可行解视为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
本章中,将在标准实例[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 种变化策略组合和3种搜索策略来进行比较,它主要依靠提供的当前最佳解决方案来学习如何自行构建解决方案.
该系统对于某些问题可以找到与已经证实的最优解相同惩罚值的可行解,同时利用深度神经网络的辅助进行分支选择和分支修剪,加快了求解过程.这探索了用自动化的方法解决人员排班问题和其他类似组合优化问题的可行性.因此,该系统的应用有良好的前景,并不仅仅局限于人员排班,通过对解决方案转化为矩阵并对其进行结构性改变,同时利用深度神经网络进行辅助决策,可以为整个搜索过程提供有导向的有依据的决策.
目前国内中小企业、酒店、医院和高等院校等人员排班基本依靠人工经验来完成,如果可以与相应单位进一步的交流和沟通,依据历史数据对模型进行针对性的训练和学习,该系统算法可以作为后期推广应用的理论基础.
未来如果可以将其他优化问题建模为具有相似特征的标准模型,则可以将该系统的方法论应用于其他类似的优化问题.同时,如果可以将深度强化学习引入该方法,则可以使得模型在自适应训练学习的实时性上更进一步.这使对于人员排班这一经典组合优化问题的研究更具有实际价值和应用潜力.
猜你喜欢 定界班次分支 RTK技术在土地勘测定界中的应用研究房地产导刊(2022年4期)2022-04-19考虑编制受限的均衡任务覆盖人员排班模型①计算机系统应用(2021年11期)2022-01-06公交车辆班次计划自动编制探索山东交通科技(2020年1期)2020-07-24一类DC规划问题的分支定界算法应用数学(2020年2期)2020-06-24巧分支与枝学生天地(2019年28期)2019-08-25一类拟齐次多项式中心的极限环分支数学物理学报(2018年1期)2018-03-26基于外定界椭球集员估计的纯方位目标跟踪北京航空航天大学学报(2017年3期)2017-11-23带柔性休息时间的多技能呼叫中心班次设计计算机工程与应用(2015年19期)2015-04-16生成分支q-矩阵的零流出性山西大同大学学报(自然科学版)(2014年3期)2014-01-23硕果累累疯狂英语·口语版(2013年1期)2013-01-31