【摘 要】 在应对突发重大传染病时，社区防控是整个社会疫情防控的重要一环。在新型冠状病毒肺炎疫情社区防控实践经验的基础上，提出一个社区疫情排查调度问题的数学模型，根据相关疫情防控信息为社区重点住户估算风险指数，并在此基础上将重点住户分配给各个排查工作小组，为每个小组设定排查路线，从而尽可能高效地完成各项排查任务。为求解该问题，提出一种混合智能优化调度算法，它基于水波优化的启发式策略搜索解空间，并混合了两种局部搜索策略来提高解的精度，形成初步调度方案。在调度方案的实施过程中，如果排查到某个对象有特殊情况需要处置，算法将对方案进行动态调整，以适应变化后的排查任务。在浙江省多个社区排查的实际案例问题上的计算结果验证了方法的有效性。 【关键词】 疫情防控 ; 社区排查 ; 智能优化调度 ; 水波优化 陈鑫,吴佳宇,吴雪, 等. 社区疫情排查的智能优化调度方法[J]. 智能科学与技术学报, 2020, 2(2): 126-134.
CHEN X, WU J Y, WU X, et al. An intelligent optimization scheduling method for community patrolling and investigation in epidemic situations[J].Chinese Journal of Intelligent Science and Technology, 2020, 2(2): 126-134.
新型冠状病毒肺炎疫情传播速度快、感染范围广，街道、乡镇等基层社区面临巨大的防控压力。对重点人员的日常排查是社区防控的一项重点工作。很多社区存在人口密度大、人员分布和流动情况复杂、工作人员数量不足等问题，日常排查任务非常艰巨，因此需要对排查任务进行合理的规划调度。通过对浙江省多个社区日常疫情排查的需求进行分析以及对实践经验进行总结，本文提出了一个社区疫情排查调度问题的数学模型，它根据相关疫情防控信息为社区内的各个重点住户估算风险指数，在此基础上将重点住户分配给各个排查工作小组，并为每个小组设定排查路线，要求每个小组在不超过工作时间上限的前提下，尽早完成所有排查任务，同时尽量优先排查风险指数高的住户，以便于对危险因素早发现、早应对。在排查过程中，如果发现某个重点住户有特殊情况需要处置（如发高烧需要就医），该小组需要留在该住户处进行处置（如呼叫急救支援并等待救援到来），同时，剩余的排查任务还需要实时重新调度，以适应变化后的情况。 社区内各个重点住户的分布可以用一个图来表示，住户位置为图的顶点，社区交通路线为图的边，排查小组被视为在图中移动的车辆，那么可将该问题抽象为车辆路径问题（vehicle routing problem，VRP）的一个变种；与基本 VRP 不同，它考虑了不同排查小组之间的差异，而且在目标函数中引入了风险指数。VRP是一个NP难问题，传统的精确优化算法只能求解小规模的问题实例。近年来，利用以进化算法为代表的各类智能优化算法求解 VRP 成为研究热点，这些算法包括遗传算法（genetic algorithms，GA）、粒子群优化（particle swarm optimization，PSO）算法、蚁群优化（ant colony optimization，ACO）算法、人工蜂群（artificial bee colony，ABC）算法和生物地理学优化（biogeography-based optimization， BBO）算法等。利用进化算法求解VRP的综述可参见参考文献。 为有效求解社区疫情排查调度问题，本文提出了一种水波优化（water wave optimization，WWO）算法和局部搜索混合的智能优化调度算法。WWO算法是一种较新的启发式搜索策略，它借鉴不同波长的水波运动规律来平衡全局搜索和局部搜索。为提高解的精度，本文还设计了两种局部搜索策略，并将它们与WWO算法混合。针对排查过程中发现特殊情况需要处置的场景，本文还提出了一种对调度方案进行实时动态调整的方法，以高效完成剩余的排查任务。在浙江省多个社区排查的实际案例问题上的计算结果验证了本文方法的有效性以及本文方法相对于其他流行算法的性能优势。 疫情期间，每个社区基于日常登记信息、疾控部门通报、疫情图、大数据健康码等手段确定每日要排查的以下几类重点住户。在本文的研究中，根据具体情况给每个重点住户估算一个风险指数。
• 确诊患者的密切接触者。尚在隔离观察期内，设观察期共D天，当前为观察期的第d天，则风险指数估算为a(D-d)/D，其中a为一个系数，本文设置为70。
• 从外地返回社区的人员。尚在隔离观察期内，在观察期的第d天，风险指数估算为bj (D-d)/D，其中bj 是一个与人员出发地相关的系数，如从疫情图红色地区返回的人员设为70，橙色、黄色、蓝色、绿色地区分别设为56、42、28、14。
• 有发热、咳嗽等疑似症状的人员。风险指数由医生估计，一般为5~70的一个整数。
• 其余健康码非绿色的人员。本文对红码人员和黄码人员设置的基准风险指数分别为60和30 （社区工作人员也可根据具体情况进行调整）。
• 其他重点人员。如孤寡老人、残障人士等，其风险指数由社区工作人员估计，一般为 1~70 的一个整数（不一定代表感染风险，也可以表示因缺乏关注可能带来的其他风险）。
如果某一住户内有多名上述人员，则该住户的整体风险指数为个人风险指数之和。设一个社区内有n个重点住户，其中第j个住户的风险指数为rj ，对住户j执行询问、体检等排查任务所需的时间为 （1≤j≤n）； 社区排查工作由m个小组分头进行，其中第i个小组从出发到第j个住户所需的时间为 ，从第 j 个住户到第 j′个住户所需的时间为 （1≤i≤m; 1≤j,j′≤n）。 注意不同小组花费的时间可以各不相同，如有的小组步行，有的小组乘坐电瓶车（可能装载了给隔离住户运送的物品）。
疫情排查调度问题就是要将各个重点住户分配给各个排查工作小组，并为每个小组设定排查路线，从而尽可能高效地完成排查任务。问题的决策变量X可以表示为m个整数向量 ，其中 表示第i个小组被分配到的 个住户的排查序列。由此可按式（1）和式（2）估算出排查每个序列中每个重点住户 ,(1≤i≤m)需要的时间：
问题的目标是使得排查完所有重点住户需要的时间加权之和最小：
加入了每个住户的风险指数作为权重系数之后，调度方案需尽量优先排查风险指数高的住户，这样有利于对危险因素早发现、早处置。
问题的解还需要满足以下约束条件。
• 每个住户都被分配了一个排查小组，没有遗漏也没有重复。令 表示序列 中所有元素的集合，则每个解需要满足：
• 每个小组的工作时间不超过上限T（本文中设为12 h）：
上述问题模型可视为 VRP 的一个变种，与基本 VRP 相比，它考虑了不同工作组之间的差异，因此属于异质VRP（heterogeneous VRP），而且它的目标函数引入了每个住户的风险指数。本文提出了一种WWO算法和局部搜索混合的智能优化调度算法来高效求解该问题，并提出一种动态调整方法来应对排查过程中出现特殊情况需要处置的情况。 3.1 基于 WWO 算法和局部搜索的智能优化调度算法 WWO算法是一种受浅水波运动现象启发的智能算法。与绝大多数进化算法一样，它也是通过对一组解的不断进化来搜索解空间。其基本思想是将每个解X视为一个“水波”并赋予一个波长λ(X)，其值与解的适应度成反比。在每次迭代时，算法在每个解的波长范围内进行搜索：较优的解波长较小，故在较小范围内搜索；较差的解波长较大，故在较大范围内搜索。这就能在局部搜索和全局搜索间达到一个较好的平衡，如图1所示。
图1 水波优化算法基于波长的传播搜索示意图
针对本文的社区排查规划问题，这里将问题的每个解编码为一个长度为n+m-1的整数向量。算法先随机初始化一个解集P，其中每个解是随机生成的整数集{1,2,…,n}的一个排列，然后向其中随机插入m-1个0作为分隔符，这样整个排列被分为m个子序列，每个子序列代表一个排查小组的任务序列xi 。 问题的优化目标函数是式（3），参照参考文献中的策略，本文采用如下计算式来计算每个解的波长：
算法每次迭代时，对解X的搜索按如下方式进行：从左至右，在X的每一个非零维j上，以λ(X)为概率，随机反转从第 j 维到第 j'维的部分序列X[j...j′]，其中 j'是[j+1,n+m-1]的一个随机整数。由于j'是随机生成的，当部分序列X[j...j′]不包含分隔符0时，反转操作只改变一个排查小组的任务序列；当部分序列X[j...j′]包含了分隔符0时，反转操作将改变两个或两个以上小组的任务序列。λ(X)越大，执行反转操作的期望次数就越大，对X的改变也就越大。 为了进一步提高对问题的求解能力，本文还提出了两种局部搜索策略。 第一种局部搜索策略试图改进每个新生成的解，因为无论是随机生成的解，还是通过一系列随机反转操作产生的解，在排查任务分配上都没有细致优化，可能有较大的提升空间。该局部搜索策略反复比较了解中最早完成任务的小组和最晚完成任务的小组，尝试将后者的某个任务转交给前者来执行，从而平衡任务分配。该局部搜索在解X上的执行步骤如下。 第一步，选出X中最早完成任务的小组序列 和最晚完成任务的小组序列 。 第二步，对于 个位置中，在这些位置中选择一个使整个解的目标函数值 f(X)改进最大的一个。 第三步，执行使目标函数值 f(X)改进最大的移动操作。 第四步，重复第一步至第三步，直到目标函数无法继续改进。 第二种局部搜索策略只作用于新找到的当前最优解X* ，因为该解有可能非常接近实际的全局最优解或某个局部最优解。该局部搜索每次尝试交换X* 中的两个元素位置来生成一个邻域解；解的长度为n+m-1，因此最多可能生成(n+m-1)(n+m-2)/2个邻域解（由于元素中包括分隔符，有的邻域解可能无效，而被忽略）。 算法 1 给出了整个混合智能优化算法的伪代码，其中rand函数生成指定范围内均匀分布的一个随机数。 算法 1 求解社区疫情排查调度问题的混合智能优化调度算法。
3.2 方案动态调整策略
在排查过程中，如果一个小组排查到某个重点住户有特殊情况（如发高烧需要就医），则该小组需要留在该住户处进行处置（如呼叫急救支援并等待救援到来）。通常情况下，这种处置时间会比较长且难以估算，因此本文的策略是将该组剩余的任务实时分配给其他小组。不失一般性，设第1个小组在执行到其序列中的第j项任务时遇到了特殊情况，需要长时间处置，那么需要将序列x 1 1 的重点住户分配给其他小组。设遇到特殊情况时，其他每个小组i将要处理的下一个任务在序列x i i ；由于特殊情况的消息通信和重新调度都需要时间，本文的策略是不改变其他每个小组将要处理的下一个任务，即其他小组只有在处理完下一个任务后才可能去分担x 1 第二步，如果存在任务已全部完成的小组，即 ，则将x 1,j 分配给其中距离最近的一个小组。 第三步，否则，按式（8）选出一个小组i* ，将第1小组的当前任务x1,j 插入序列xi* 的第pi* 个和第p i * + 1 第五步，重复第一步至第四步，直到 ，即第1小组的剩余任务全部分配完毕。 在后续任务的执行过程中，如果第1小组对 的特殊情况处置完毕，那么该小组可以继续执行排查任务； 类似地，设此时其他每个小组i将要处理的下一个任务下标为 ，那么采用如下策略为该小组重新分配任务。 第一步，从其他小组中选出一个任务完成时间最长的小组 ，按式（9）从其序列中选出一个任务 ： 为了验证算法性能，笔者首先邀请有经验的社区工作人员对每个问题实例手工制定排查规划，他们的做法是将重点住户大致划分为几个区域，然后安排工作小组分别排查这些区域，每个小组的路线大致按照由近到远的贪心策略来规划。接下来，在每个问题实例上，笔者分别运行了GA、ACO算法和BBO算法（这3个算法的参数均按参考文献中的推荐设置）来与本文的WWO混合算法进行比较。相比而言，WWO混合算法只需要设置解集P的大小，不需要设置其他参数；这里解集大小初始值设为50，并随着算法迭代逐步减少到6（每次迭代删除解集中的最差解）。除了人工方法外，每个智能优化算法在每个实例上随机重复 30 次，算法终止条件均设置为 CPU 运行时间不超过 30 min。计算环境为Intel i7-6500 2.5 GHz CPU，8 GB DDR4内存，Windows 7操作系统。 图2给出了12个测试实例上的算法比较结果，其中基于经验的人工方法标记为Man；针对每个智能优化算法，本文分别给出了其返回解的目标函数值的最小值（Min）、最大值（Max）、中位数（Median）、下四分位数（Q1）和上四分位数（Q3）。为便于表示，设每个实例上所有算法求解次数中得到的最佳解的目标函数值为f * ，图2中把所有目标函数值 f(X)统一缩放为 f(X)/f * 。结果表明，在所有的问题实例上，最佳解f * 都是WWO算法取得的。先比较人工方法和WWO算法，前者的目标函数值总是比后者 30 次运行中得到的最大值还要大；在小规模的实例#1和#2上，人工方法的目标函数值大约是WWO算法的2倍；在中等规模的实例#3～#8上，人工方法的目标函数值约是WWO算法的3~8倍；在大规模的实例#9～#12 上，人工方法的目标函数值超过了WWO算法的10倍，而且人工方法的解还违反了式（6）的约束。在所有实例上，人工方法的性能也都低于其他算法。这说明社区排查调度是一个复杂的问题，最优解乃至大部分次优解需要对分组和线路进行巧妙的组合优化才能发现，仅凭经验很难找到较优的解。
图2 计算实验结果
再比较4个智能优化算法。在所有的问题实例上，WWO算法不仅中位数总是最小的，其他各项指标也都显著优于其他3个算法。而且随着问题规模的增长，WWO算法相对于其他算法的优势越来越明显，这说明WWO算法能够有效求解大规模的复杂问题实例。在4个算法中，GA的总体性能表现最差，在中小规模的实例#2～#5上，其目标函数值大约是WWO算法的2倍；而在后面更大规模的实例上，GA的目标函数值最多达到了WWO算法的9倍，这是因为GA的搜索机制使其很容易陷入局部最优。BBO算法在较小规模的实例#1和#2上的性能接近WWO算法，说明其在较小的解空间内的搜索能力较强，但随着解空间的增长，BBO算法全局探索能力的不足逐渐显现；在最后两个实例#11和#12上，BBO算法的目标函数值约为WWO算法的6倍。ACO算法的性能在小规模实例上略逊于 BBO 算法，但在更大规模的实例上逐渐赶上甚至超过了BBO算法，这说明ACO算法在较大的解空间中的搜索能力相对更强；尽管如此，在实例#10～#12 上，ACO 算法的目标函数值也达到了WWO算法的3倍。这些实例问题上的计算结果表明，本文提出的基于WWO算法的混合智能优化调度算法相对于其他算法具有明显的性能优势。 上述问题实例中，有8个实例出现了需要特殊处置的情况。类似地，笔者也请社区工作人员手工制定对特殊情况的修改方案，其基本策略是把出现情况的小组的剩余任务按由近到远的顺序分配给其他小组。图3在这8个实例上分别比较了以下几项： • 按手工方案无特殊情况发生的任务最终完成时间（记为MAN）； • 按手工方案应对特殊情况后的任务最终完成时间（记为MAN-R）； • 按 WWO 计算方案无特殊情况发生的任务最终完成时间（记为WWO）； • 按 WWO 计算方案应对特殊情况后的任务最终完成时间（记为WWO-R）。 结果表明，按手工方案应对特殊情况后，任务完成时间平均增加了约 102 min，而本文方法应对特殊情况的任务完成时间只增加了48 min，这充分说明了本文的应对方法更为敏捷和有效。在大规模问题实例 #11和 #12上，按手工方案计算出的任务完成时间接近或达到24 h，应对特殊情况后的任务完成时间更是超过24 h，这在实际应用中显然是无法满足需要的。因此，应用本文方法对社区疫情排查进行优化调度，并在出现特殊情况后进行有效应对，对提高排查效率有巨大帮助。
图3 手工方案和WWO计算方案应对特殊情况前后的任务最终完成时间对比
本次新型冠状病毒肺炎疫情防控的重点和难点在于基层，最大力量也在基层。但在疫情高发区，社区排查任务十分繁重，需要对排查任务进行高效的调度。本文提出了一种基于WWO算法的混合智能优化调度算法来实现社区疫情排查调度，并提出一种实时调整方法来应对排查过程中可能遇到的特殊情况。在浙江省多个社区排查的实际案例问题上的计算结果验证了本文方法的有效性。 本文研究中假定排查人员的分组是已经确定的。在更复杂的任务条件下，还需要按人员分工先进行分组，如区分一般工作人员、医护人员、安保人员等，以便更有效地处置不同类型的重点住户。下一步研究将考虑把人员优化分组也集成到整个优化模型中，并设计更有效的算法来求解集成后的问题。后续还拟将本文方法扩展应用于学校、工厂等其他重点区域的疫情排查，并引入网络监测和分析来提高风险评估效果。
作者简介 About authors
陈鑫（1997-），女，杭州师范大学信息科学与工程学院硕士生，主要研究方向为智能优化算法 。 吴佳宇（1996-），女，浙江工业大学计算机科学与技术学院硕士生，主要研究方向为智能优化调度 。 吴雪（1996-），女，浙江工业大学计算机科学与技术学院硕士生，主要研究方向为智能优化调度 。 张敏霞（1968-），女，博士，浙江工业大学计算机科学与技术学院副教授，主要研究方向为智能交通和智慧物流 。 郑宇军（1979-），男，博士，杭州师范大学信息科学与工程学院教授，主要研究方向为智能优化计算 。
转载本文请联系原作者获取授权，同时请注明本文来自王晓科学网博客。 https://blog.sciencenet.cn/blog-951291-1244388.html
上一篇：
[转载]基于多模态影像下的抑郁症大脑异常 下一篇：
[转载]刘跃进：学问的高低，不仅要比谁掌握了更多的新资料，更难的是在寻常材料中发现新问题
