1、104 建设机械技术与管理 2023.01 检验维修改进遗传算法的建筑机械检测任务智能分配研究Intelligent Dispatch of Mechanical Inspection and Testing Orders Based on Improved Genetic Algorithm周义辰1,3 董恒尧1,3 王云飞2,3 黄超禄2,3（1.上海市建筑科学研究院科技发展有限公司，上海201506；2.上海市建筑科学研究院有限公司，上海200032；3.上海建筑机械安全智能控制工程技术研究中心，上海200032）摘要：在建筑机械检验检测任务分派过程中，存在着任务类型多样、地点分散、组别
2、差异化较大、分配效率低等问题。针对上述问题，考虑了多目标优化的机械检测订单分派，构建以加权总里程数最短、任务完成时间最短和组别差异度最小为目标的数学模型，并提出基于遗传算法的优化改进算法。采取整数编码，增设断点编码，设计多目标下的加权和为适应度函数；在进化过程中添设断点编码、组人数的动态修正操作；并在进化、变异引入模拟退火算法的思想，提高解的质量和算法搜寻效率。最后，采用历史数据进行实验求解，结果显示能够显著减少总里程数和组别间差异，已投入实际应用并持续迭代优化。关键词：机械检测；遗传算法；智能分派；多目标优化中图分类号：TP399 文献标识码：A0 引 言建筑机械安装质量检验检测是建筑工程机
3、械安全管理工作的关键组成部分。现场检验检测任务主要包含塔式起重机、施工升降机、龙门架及井架物料提升机、货用升降机、流动式起重机、桩工机械、高处作业吊篮等安装质量检验检测及老旧设备安全评估等。智能派单主要研究的问题是按照设定目标将所有订单分配给一定数量的组别并安排对应检测员。由于设备类型复杂多样，并且需要专业人员到达现场进行作业，而检测地点往往又呈散状分布且普遍相距较远，人员前往任务地点路线复杂耗时长。然而在保证个检测地点路线合理则会造成任务分配不均，团队间人员绩效差别大的衍生问题。两者很难均衡。为实现该目标，就要引入并研究一套合适的算法程序进行机器自动派单才能更有效地解决问题。因此本文研究任务
4、智能分配算法旨在将所有任务分配给相关检测负责人员时，能遵循里程少、时间短、效率高、任务分配均衡等，实现通过减少油费、过路费、工作时长增加人员工作效率的目标。检测订单分配的过程可以归结为一个调度和决策的过程。Ahmadi 等人1针对以最大完工时间最短为目标，使用一辆容量有限的运输车辆将一类加工完成后的工件配送到预先指定的顾客的问题提出一种动态规划算法。Li 等人2研究了一个目标为工件抵达总时间最短的配送车辆的路由决策问题。Selvarajah 等人3对从单个供应商为多客户多产品需求提供服务的最优批量调度问题进行了研究，通过把整体分解为单产品单客户问题设计了多项式算法。Jia 等人4针对目标为总加
5、权流量时间和交付成本和最小的单台机器加工并分批配送问题进行了研究，首先证明了该问题是 NP-困难问题，并针对批量有限的情况提出一种基于动态规划的伪多项式算法。Wang 等人5针对总运输和总加权拖运成本和最小为目标的物流系统在产品交付阶段存在的两种不同运输方式问题提供了一个具有不同下界的分支定界算法。由于大多数的调度问题都属于 NP 难问题，当问题规模逐渐扩大后几乎不可能找到一个具有多项式时间复杂度算法的最优解。因此研究学者们采用多技术手段对这些调度排序问题进行了研究，设计了各种优化算法来减少计算复杂性并求得近似最优解。优化算法大致可以分类归为近似算法、动态规划算法、启发式算法和智能算法等678
6、910，并被广泛地应用于各种实际调度规划的问题中11121314。而遗传算法(Genetic Algorithm,GA)是求解复杂的组合优化问题的一种有效方法，其由 John Holland 于 1967 年首次提出，是在调度领域中应用最为广泛的进化算法之一。1 问题描述本文将智能派单问题进行拆解转化成两步，第一步是所有订单的分组问题，即某天存在 n 个订单（编号为 1-n，0 表示检测中心位置），指定组别数量 m 和待分配的总绩效DOI:10.13824/ki.cmtm.2023.01.0172023.01建设机械技术与管理 105检验维修人数k。设订单i和订单j之间的驾驶距离为dij(0i
7、,jn)，订单 i 的绩效和任务耗时为 ci，ti。将这些订单进行分组，期望得到分组结果为一个 nm 的矩阵：=(x11x1mxn1x m)resultn1,第 i 个订单被分配到第 j 组0,第 i 个订单未被分配到第 j 组)x=ij (1)设立三个优化目标：目标 1：每个组别将从检测中心出发，遍历所有其被分配到的订单位置，并最终返回检测中心。目标期望得到所有组别遍历订单位置的总里程数最短。f1=D=x dmj=1ni=1+d0jmj=1+dj0mj=1 minjjii(2)目标 2：每个检测订单根据检测设备类型、数量的不同，以及所分配到的人数不同对应有不同的任务耗时。目标期望得到所有组别
8、累计任务耗时最短。xmj=1ni=1minj if2=T=ti (3)目标 3：使用方差来度量组别之间人均绩效/组任务耗时的差异，目标期望得到该方差值最小，即组别间差异最小。minj if3=V (C/T)=(x ci/timj=1,1 i n)pparminarV (4)采用加权求和的方式将f1，f2，f3合并为最终的目标函数，其中 w1，w2，w3表示 f1，f2，f3对应的重要程度，其值可以根据实际应用中的被重视程度进行动态调整。f1=w1*f1+w2*f2+w3*f3 (5)上述数学模型中的约束条件如下所示：minj if3=V (C/T)=(x ci/timj=1,1 i n)ppa
9、rminarV =1，1 i n (6)式(6)表示每个订单有且仅存在于一个组别中。该订单分组问题从内核上分析可以归纳成一个具有多目标多约束的抽象的多人旅行商问题（MTSP），该问题包含了旅行商路和旅行商回路15。旅行商问题（TSP）是一个公认的 NP 完全问题，而大规模的旅行商问题通常无法求得最优解，因此算法的目标往往趋向寻找一个比较优秀的解。第二步是人员的分配问题，目前每组的人员分配设定有一个硬性要求：一位驾驶员，即组内至少有一名成员可以驾驶，且每个组别设有固定的默认驾驶员，在分配驾驶员时，应当尽可能地安排这位默认驾驶员。另外，部分订单含有对应的报检人，则该报检人应当按照能排则排的原则，尽
10、可能地被分入有其报检订单，且组绩效最大的组别中。2 数据处理2.1 数据介绍本文所使用的原始数据来源于报检用户通过微信公众号进行线上委托检测，这些委托订单个别存在某些特殊情况不适合进行统一的机器智能分配。因此上传至机械检测平台后，分配人员首先会对所有订单进行人工初筛，把情况特殊的订单、组别和人员提前筛除后，将其余订单及组别人员选择进行智能分配后，算法从指定数据接口获取这些数据进行后续操作。数据类别分为三大块：订单数据、组别数据、成员数据。订单数据主要包括设备类型(EquipType_Name)、设备数量(Qty)、单台耗时(TaskTime)、耗时类型(TimeType)、绩效(Cost)、报
11、检人(User_Name)、经度(lat)、纬度(lng)。组别数据主要获取需要被分配的组别名称，用大写字母表示，同时获取其对应的默认驾驶员。成员数据主要包含成员名字(User_Name)、驾驶标识(DriveFlag)，1 表示成员可以驾驶，0 表示不可驾驶、检验员标识(DetectFlag)，1 表示需计入绩效人数，0 表示不需计入绩效人数。2.2 数据预处理在数据预处理中，首先将需要用到的数据筛出，并对重复数据进行去重操作。其次将每个订单的经纬度按照编号1-n 顺序处理成经度纬度对的形式，存为一个(n+1)2 的矩阵，矩阵首行为检测中心即起始点的经纬度对。订单绩效和报检人信息（有报检人元
12、素为报检人名字，无则为空字符串）分别以长度为(n+1)的矩阵表示，组别数据以长度为 m的矩阵表示，成员数据分别按照其检测员标识和驾驶员标识为 1/0 进行分类存储，结果如下例所示：=0011nn performance=0p1pn user_name=groups=ACF locationslnglnglnglatlatlatxxxxx3 算法设计遗传算法模仿生物进化遗传的现象，根据问题设定的目标去构造一个适应度函数，对由多个解（个体）构成的种群进行评估，并通过进化、变异、选择来不断更新种群，模拟多代繁殖，最终获得一个适应度最好的个体作为该次求解的最优解。3.1 遗传算子设计3.1.1 个体编
13、码和初始化本文采用整数编码方式，其中 0 表示检测中心，1-n图 1 检测订单数据来源微信公众号 人工初筛 机械检测平台 委托受理 委托检测 提交派单 指定数据接口 106 建设机械技术与管理 2023.01 检验维修表示订单的顺序编号，即 i 表示第 i 个订单。同时本文设置一个对应的断点编码，其作用相当于将所有订单进行组别的分割，断点编码的长度为指定组别数量 m-1，例如图 2，设有 14 个订单，组别数量为 4，那么将订单用整数编号按序编码，断点编码长度为 3，元素表示断点位置分割个体，得到组 1 的订单为 1，2，3、组 2 的订单为 4，5，6，7，8、组 3的订单为 9，10，11
14、、组 4 的订单为 12，13，14。且算法规划的出检顺序也遵循从左到右，例如组 1 的路径就是检测中心-1-2-3-检测中心。劣程度的标准，并决定了其遗传机会的大小，其选取将直接影响到算法的收敛速度和是否能找到最优解，属于遗传算法的核心组成部分。本文中适应度函数总是取非负值，且以求函数最大值为优化目标，因此将直接利用适应度函数值作为个体的适应度，函数值越大说明个体适应能力越强，遗传机会也就越大。在前文提到，订单分组的总原则是追求总里程数最短，总耗时最短，绩效/任务耗时平均，因此本文同样将适应度函数划分为由三部分组成。第一部分是总里程数，第二部分是总耗时（行驶时间+任务耗时），第三部分为各组别
15、人均绩效/任务耗时的方差，方差越小说明组别间偏离程度越小，指标也就越趋于平均。由于派单的目标是希望总里程数、总耗时和组间指标的差异尽可能小，因此适应度函数设计为三者之和的倒数。另外，在实际实验中会发现，随着订单数量的增加，算法在订单分组上所得到的结果在地点上相对分散。而从实际角度出发，每组订单的地点应当相对集中且也更有助于缩短里程和驾驶时间。因此算法在计算每组的里程数时，增加了一个组内所有订单的经纬度方差，用来衡量组内订单地点的离散程度，将其和里程数相乘来替代原本简单的里程数总数。fitness=1 总里程数+总耗时+var(组人均绩效/任务耗时)(7)除此之外，对于组任务耗时和人均绩效的方差
16、，算法并不追求极致的平均，当组别之间的差距缩小到一定数值范围内，即可认为其已经达到“平均”效果。也就是说，当组之间的差异缩小到一定合理的程度内后，在适应度函数的计算上将其方差值直接置为 0 使得算法在接下来的进化繁殖时，更加专注于总里程数，总时长的缩短。3.1.3 选择算子本文采用轮盘赌选择法作为遗传算法的选择算子，它也是最简易和常用的选择方法。在此方法中，各个体的选择概率和其适应度大小成正比，适应度越大，被选中的概率也就越大。而在实际进行轮盘赌选择时，个体的选择往往是根据累积概率进行选择。假设某一个体 xi的适应度值为 f(xi)，其被选中的概率为p(xi)，累计概率为 q(xi)，计算方法如下：p(xi)=f(xi)fjnj=1/(8)q(xi)=p(xj)ij=1 (9)式(9)中的累积概率 q(xi)表示每个个体前所有个体的选择概率之和，其相当于在轮盘上的跨度，当跨度越大，也就越容易被选中。轮盘赌选择方法的过程如下：轮盘赌选择流程:图 2 个体和断点编码示例检测中心 订单 i 组 1 组 2 组 3 组 4 本文在做初始化操作时，主要包含四块初始化部分：(a)行驶距离、时间矩阵
