【摘要】

针对装维任务如何调度获取最高运维生产效益的问题，我们基于启发式病毒进化遗传算法（VEGA）计算最佳调度方案进行探索，将装维工单类型、施工难度、路况、距离、人员技能、预约时间等多种调度因素融合，精准派单到人，合理规划任务工单执行顺序及路径，提高装维调度准确性和合理性，使人员利用率达到最大化，运维成本达到最小化。

【关键词】

装维、最优任务调度、病毒进化遗传算法、适应度函数、NP-hard

引言

目前，宽带业务高速发展，业务量巨增，家宽装维工单如何高效、合理调度到人，减少时间和人力成本，是重要研究方向。

现阶段宽带装维工单调度采用固化策略方式，难以全面实时考虑装维人员的忙闲、距离、路况、人员技能等因素，无法精准高效调度，浪费时间人力。

时下业界对启发式智能算法的应用越来越成熟，已在多场景中运用成功。其原理是模拟自然界中群体性动物活动的过程，解决 NP-hard 类问题，而家宽装维多工单调度就是一种 NP-hard 问题。启发式算法可根据场景设置不同的约束条件，融合多因素计算工单执行人员、执行顺序，计算多任务多人员均衡派单，降本增效。

常见的启发式算法：蚁群算法、病毒进化遗传算法、模拟退火算法、神经网络算法等。其中病毒进化遗传算法搜索效率高，适用于多目标分配计算。经过算法选型比较，本文选用病毒进化遗传算法，在装维调度中的应用展开探索。

整体思路

最优派单方案指所有任务完成时间最短，人员利用率最高，路上消耗时间最短，保证每个任务单都能在预约时间之前到达。

通过深入调研，影响装维工单派单合理性、客户服务质量主要有三个因素，第一是路径路况消耗了较多时间，第二是装维人员能力各有所长，不能合理分配，第三是工单施工消耗时长未提前考虑到施工难易程度，影响下一个任务到达时间预测。因此，本方案以路径、人员能力、工单消耗时间预估作为计算条件。

基于病毒进化型遗传算法的智能调度整体思路：

利用病毒进化型遗传算法综合多因素搜索多工单多人员调度最优方案，使整体工单完成时间最短。计算结果人工审核校准，反馈模型调优。

• 因素采集：采集实时数据作为模型输入，包含：人员能力系数、工单类型、装机小区类型、GIS 地图路况等数据。

• 适应度函数：根据装维派单要求，建立适应度函数、约束条件。

• 算法选型：采用病毒进化遗传算法，计算出较优的解。

• 结果输出：得到工单分配最优方案，人工审核，反馈模型参数调优。

调度算法选型

NP-hard 类问题利用启发式算法计算，可尽可能得到一个较优解用来解决问题，易实现，较其他 AI 算法复杂度低，因而得到广泛运用。

以下为几种常见启发式算法优缺点分析

1. 模拟退火法(Simulated Annealing)：模拟物理现象中固体从升温到冷却，其粒子变化规律计算。利用这种概率突跳特性，快速计算全局最优解或近似最优解。但收敛慢，影响计算结果，难以在实际动态变化调度状况中使用。

2. 蚁群算法（ACO）：基于种群的模拟生态系统算法，从随机搜索到逐步正反馈学习，具有较强的鲁棒性，收敛速度快，适用全局搜索最优解，但用于多目标场景较复杂。

3. 遗传算法（GA）：模拟自然界遗传学优胜劣汰原则，利用染色体选择、交叉、变异的原理计算找到最优解。虽相比于前几种算法的收敛性好，但存在早熟缺点。

4. 病毒进化遗传算法（VEGA）：一种改进型遗传算法，在遗传算法基础上增加病毒感染过程，重新改变计算种群，避免算法早熟。两者结合形成动态搜索，提高搜索性能，缩短计算时间。常用于多目标分配场景。

总结：各种调度算法在不同程度上，都存在优缺点。家宽装维业务场景中大装维网格分配工单为多人多工单分派，较复杂，需融合各种调度因素，尽可能搜索最优派单方案，得到一个相对最优解，使整体工单完成效率最高，人力分配最合理。

因此，基于家宽装维属于多目标分配场景，利用病毒进化算法，可计算多任务多人员的任务分配最优解，实现精准派单。

工单调度建模

1 场景问题描述

本文业务场景指任务工单从前端营业厅/客服派发到施工装维人员的过程。一个工单只派给一个装维人员，整体工单完成有时间限制。

派发任务的考虑的因素即限制条件有：

• 若工单已预约，计算中需要考虑预约时间，分配时间不能晚于预约时间。

• 装维人员被分配工单数量需限制，保障工单分配均衡性。

• 根据人员技能，功能不能分配给耗时最多的人员。

2 适应度函数

假设本场景中，任务并发派给多个装维人员。因此，最后一个工单完成的时间表示所有装维任务完成的时间。

假设装维人员有 m 个，待装任务有 n 个，每个装维人员按照顺序完成多个任务，一个任务只能一个装维人员完成。

公式一（适应度函数）：

公式二：

（1） 公式一为适应度函数，C 表示完成 n 个任务的最短时间。其中$t_n$示第 n 个任务的完成时间之和。

（2） 表示 n 个任务完成的时间之和，因为任务并行执行，一个装维人员若有多个工单，按顺序执行。

（3） 公式二表示$t_n$整体时间为路途上消耗的时间、装维消耗的时间与小区装维需要的额外时间之和。

装维工单时间根据装维人员技能计算，以家宽各业务单举例，假设有 6 个装维人员。每个人技能根据历史工单处理时长，得到每种工单平均历时时间。

不同工单类型完成的时长（单位：分钟）示例如下表：

表示小区额外消耗时间，分为标准小区和非标准小区，标准小区不需要额外耗时，非标准小区需要统计耗时时间进行计算。

非标准小区额外耗时标准化示例：

其他约束条件如下：

• 保证每个工单预约时间

• 示装维人员在忙判断标准为预计完成时间

• 得到病毒进化算法的适应函数，其他约束条件作为算法收敛准则。

3 遗传算法计算流程

病毒进化型遗传算法，相较于传统遗传算法，在计算过程中，融入了病毒种群进行计算。当主种群（即可行方案集合）通过选择、交叉、变异后，再用病毒种群（对应某个装维人员固定执行某个方案）进行感染计算，扩展了算法的多样性和搜索的广度，避免了过早拟合。

在计算的过程中，具体步骤如下图所示：

（1） 先初始化种群，包含主种群（随机若干个可行解）和人工设定的病毒种群（某个装维人员固定被分配某个任务）。

（2） 根据适应度函数计算主群体初始适应度。

（3） 开始计数器迭代，计数器 K=0，执行多次主群体的遗传算子选择、交叉、变异操作。

（4） 在主群体迭代中，内循环进行病毒感染变异的计算，计数器 i=0，使主染色体变异生成新的病毒个体，增强搜索效率。

（5） 主群体迭代计算次数 K<Cmax，Cmax 表示病毒进化遗传算法冗余迭代次数临界点，判断条件为病毒进化遗传算法若连续 N 次迭代时，子代群体的进化率比进化率最小值小，这时，判断其进入了冗余迭代，进化率最小值可根据实际数据量动态调整，不断学习调优。

（6） 当计算到达病毒进化遗传算法的临界点时，输出前三个较优个体，终止病毒进化算法，选择这前 3 个最优方案输出结果。

4 调度场景模拟说明

装维调度派单理想条件下为静态调度，本次关于病毒进化型算法计算的探索是基于静态调度探索，即工单和人员数量不变，各工单为施工状态，人员执行工单顺序确定不变。

在实际生产过程中，装维调度常会出现约束条件改变，需随异常状况动态调整调度，为动态调度。如人员请假、工单临时加时长、临时加单、客户取消订单或者改期等特殊状况，则需算法重新计算。

总结：病毒进化遗传算法支持装维调度场景，融合多种调度因素，精准派单到人，合理规划任务顺序及路径，使调度合理、装维人员耗时最少。

方案展望

启发式算法能让装维工单调度合理化，提高精准率和人员利用率，降低时间成本。未来可结合预测算法、聚类算法等进一步提升。

智能调度算法主要运用在调度中心，支撑全网运营调度体系，特别是云网新业务的不断发展，不仅需要人员调度，还需要业务调度，对调度智能化要求也越来越高。引入智能算法，可促进调度中心迈向智能型的新一代云网运营支撑体系。