(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211329088.2 (22)申请日 2022.10.27 (71)申请人 西安电子科技大 学广州研究院 地址 510006 广东省广州市黄埔区中新知 识城海丝中心B5、 B6、 B7栋 (72)发明人 赵宏　李龙君　陈文玮　史浩东　 袁浩　刘静　 (74)专利代理 机构 广州圣理华知识产权代理有 限公司 4 4302 专利代理师 李唐明 (51)Int.Cl. G06Q 10/06(2012.01) G06Q 50/26(2012.01) G06N 3/12(2006.01) (54)发明名称 基于惩罚因子和启发式搜索的警务人员智 能调度方法 (57)摘要 本发明公开了一种基于惩罚因子和启发式 搜索的警务人员智能调度方法， 涉及智能调度算 法领域， 包括以下步骤： 初始化参数和种群， 收集 警务人员偏好， 解码染色体， 计算个体适应值； 从 交配池随机选取个体执行交叉操作和变异操作， 生成子代个体； 重复交叉、 变异和进化操作， 直至 达到结束迭代条件， 输出当前最优解； 对最优个 体进行局部搜索操作优化， 并转化为最终排班方 案。 本发明结合了遗传算法和局部搜索算法的有 优点， 提高了算法的全局搜索能力和局部搜索能 力， 在满足调度硬约束的条件下能够找到满足更 多软约束条件的更优解。 在处理大规模调度方面 同样有着 很高的效率， 可以在短时间内得到调度 结果， 这有助于提升现有警力资源的利用率。 权利要求书2页 说明书7页 附图5页 CN 115545539 A 2022.12.30 CN 115545539 A 1.基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 包括以下步骤： S1、 初始化遗传算法参数， 包括种群规模Np、 交叉概率Pc、 变异概率Pm、 最大迭代代 数G以 及当前进化代数t,且t的初始值 为0； S2、 按照间接编码的形式初始化染色体编码； 对于N个小组在调度周期内的排班安排， 分别生成一个长度为3 ×M的序列编码， 每个序列编码包括数字1～3 ×M， 且数字随机排列； M 表示调度周期为M天； S3、 根据警务排班调度的要求的硬约束条件初始化种群； 所述硬约束条件包括第一硬 约束条件， 即每天 都有值班人员； S4、 收集警务人员对工作安 排的偏好， 形成偏好表； S5、 对种群的每个染色体编码进行解码， 转化为直接编码， 编码长度为M； 其中每一行代 表一个小组， 每一列代表一天； 排班的类型包括 “正班”、“副班”、“值班”、“休息”， 并分别用 “1”到“4”四个整数表示； S6、 对于解码后的个体， 即直接编码， 计算惩罚值， 并根据惩罚值计算个体的适应值； 个 体的惩罚值和适应值成反比； S7、 选择操作： 根据每个个体的适应值占所有个体适应值之和的比例， 采取轮盘赌选择 方法选择Np个染色体 个体放入交配池中； S8、 交叉操作： 从交配池中随机 选取一对个 体， 按照交叉概 率Pc进行交叉操作； S9、 变异操作： 每个个体按照概率决定是否进行变异操作； 对于产生的随机数rand， 若 rand＜Pm， 则对选中个体采用变异算子进行优化； 变异后的新个体仍需满足第一硬约束条 件； S10、 重复步骤S7～S9， 直至t等于G； 每次迭代， t的值加1； 当达到结束迭代条件后， 终止 进化并输出最优个 体， 即适应值 最高的个 体； S11、 评估个体并对优秀个体进行局部搜索操作， 选择最优结果， 即适应值最高的个体， 作为最终的排班方案 输出。 2.根据权利要求1所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S3中， 所述硬约束条件 还包括第二硬约束条件： M天的调度周期内休息R 天。 3.根据权利要求2所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S3中， 所述警务 排班调度的要求还 包括软约束条件： (1)值班后不 安排副班； (2)不安排连续副班； (3)不安排连续正班； (4)不安排连续两天及以上值班。 4.根据权利要求3所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S5中， 所述 解码的步骤为： S5‑1、 初始化 参数： 偏好表选择概 率Pp； S5‑2、 对于染色体编码， 从最左边开始， 每次读取一位编码x， 按照下述规则转化为指定 日和排班编码， 即指定日为D＝(x ‑1)/3+1， 排班编码为S＝(x ‑1)％3+1； S5‑3、 判断指定日是否已经安排班次； 如果没有执行步骤S5 ‑4； 否则， 继续读取下一位 编码；权　利　要　求　书 1/2 页 2 CN 115545539 A 2S5‑4、 判断按照当前排班编码对指定进行排班是否违反软约束； 若没有违反， 则按照当 前编码对指定日进行排班； 否则， 执 行步骤S5 ‑5； S5‑5、 生成随机数rand； 若rand＜Pp,则按照偏好表进行排班； 否则遍历后续编码列表直 到找到下一位表示同一指定日的排班的编码， 将该编码与当前编码交换位置， 并使用该编 码对当前指定日进行排班； S5‑6、 按照S5 ‑2至S5‑5步骤继续读取下一位编码,直至当前染色体编码所有位都被处 理， 或满足每 个小组每周已经 得到M‑R天的排班,即满足第二硬约束条件， 则终止解码过程。 5.根据权利要求3所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 步骤S6中所述个 体按照软约束条件计算 惩罚值， 计算方法为： (a)对于指定人员在指定日的排班， 若不符合偏好表的要求， 则惩罚值加1； 若指定人员 在指定日倾向于上班 但被安排休息， 则不进行惩罚； (b)若排班要求指定人员在指定日值班， 值班的第二天安排副班， 而安排不符合指定人 员在偏好表的要求， 则惩罚值加1； (c)若指定人员被安排连续两天正班， 且安排不符合指定人员在偏好表的要求， 则惩罚 值加1； (d)若指定人员被安排连续两天副班， 且安排不符合指定人员在偏好表的要求， 则惩罚 值加1； (e)若指定人员被安排连续两天及以上值班， 且安排不符合指定人员在偏好表的要求， 则惩罚值加1。 6.根据权利要求1所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S 8中， 所述交叉算子为循环交叉算子 。 7.根据权利要求6所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S 8中， 所述交叉操作为： 对于生成 的随机数ran d， 若rand＜Pc， 则对选取的一对个体采用交叉算子， 生产两个交 叉个体； 交叉过程中， 对个体的每一 维进行单独交叉， 新个体的值班和休息安排直接继承于 父代个体， 剩余天数则继承于另一个 个体的正班、 副班安 排， 保证新个 体满足硬约束条件； 若新个体仍存在未安 排调度的空 闲天数， 则在空 闲日随机安 排正班或者副班。 8.根据权利要求1所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S9中， 所述变异操作为： 在个体中的小组内随机选两天非值班的调度安排， 检查这两天被选中的小组是否休 息： 若被选取的每一天 都是正班或副班， 则随机设置为 正班或副班的一种； 若被选取的两天包 含休息， 则交换两天的调度安 排。 9.根据权利要求1所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S11中， 所述局部搜索操作为： 对同一天内不同小组的非休息班次进行随机 调换。 10.根据权利要求1所述的基于惩罚因子和启发式搜索的警务人员智能调度方法， 其特 征在于， 在步骤S11中， 所述局部搜索操作为： 对同一小组的不同天的非值班班次进行随机 调换。权　利　要　求　书 2/2 页 3 CN 115545539 A 3