技术摘要：
本发明公开了一种无人驾驶运输装置的任务分配方法，在构造虚拟运输装置来补齐分配矩阵的过程中，提出了基于不同约束条件下寻找不同数量“能者”的策略，提出了能力差距的概念，给出了用不同数量的“能者”补齐分配方阵机制；在此基础上，本发明利用了分配机制，从理论 全部
背景技术：
无人驾驶汽车被越来越广泛的应用于物质运输领域，像港口的集装箱运输、工业 园区里的物流调度、大型小区的快递运输等。在这些应用场景中，往往是由多台不同性能的 无人运输装置组成编队用于灵活执行多个运输任务。比如说无人运输装置大小不同，运输 任务目的地不同，运输能力不同，导致每一台无人运输装置执行不同的运输任务都需要付 出不同的运输成本(包括运输时间、油耗等)。另外，现实生活中，往往是运输任务数量多于 运输装置的数量，往往导致同一台无人运输装置需要执行多趟运输任务。因此，如何合理的 分配任务，使完成任务所付出的总成本最低，具有很大的经济应用价值。 多任务分配问题可以分为平衡任务分配和非平衡任务分配两类，以无人运输装置 执行运输任务为例：平衡任务分配指无人运输装置数量与所要执行的运输任务数量相等， 任务和运输装置一对一分配，分配方案使其运输所需要的代价总和最小；非平衡任务分配 指无人运输装置数量小于运输任务数量，因此为了完成任务，必然需要部分无人运输装置 承担多项运输任务，分配方案使完成任务的代价总和最小。而在现实应用中，为了节省资 源，往往是运输任务的数量多于运输装置的数量。 因此，该无人运输装置运输任务分配问题可以描述成：假设有m台无人运输装置 (记为V)需要执行n项运输任务(记为T)，其中m
本发明的目的在于提供一种无人驾驶运输装置的任务分配方法，它能够解决该类 不平衡任务最优分配问题，尤其是对任务执行者在不同约束条件下如何进行任务分配的问 题。 本发明提出的一种无人驾驶运输装置的任务分配方法，包括如下步骤： S1：确定无人运输装置数量，运输任务数量，运输成本矩阵； S2：得到需要额外寻找k台无人运输装置； S3：根据运输约束条件，由运输能力最强的p台无人运输装置构造出k台拟承担运 输任务的无人运输装置，与原有的m台无人运输装置一起对n个任务进行分配，组成n×n的 分配方阵NC； S4：在分配方阵NC中每一列找出最小值minCi,i∈[1,m]，然后该列每一个值都减 去该最小值minCi； S5：在分配方阵NC中每一行找出最小值minRj,j∈[1,n]，然后该行每一个值都减 去该最小值minRj； S6：对存在0元素的行或者列画直线，用直线覆盖该行或者该列，确保所有存在0的 行或者列都被直线覆盖； S7：统计直线的数量NL，如果NL＜n，则进入步骤S8，如果NL≥n进入步骤S9； S8：在分配方阵NC里未被直线覆盖的元素中寻找最小值Sv； S9：首先找出只有一个0元素的行，其位置代表无人运输装置与运输任务一一对 应；然后清除该行和该列的所有元素；在这个过程中，如果过程中同一行中有多个0元素，则 去该0元素对应的原始运输代价矩阵中，找出原始代价值最小的0元素，作为任务分配关系； 持续分配直到所有任务分配完毕； S10：分配计算结束，输出分配结果。 所述的步骤S1包括如下步骤：所述的无人运输装置数量m，运输任务数量n，运输成 本矩阵Cij，i∈[1,m],j∈[1,n]，Cij表示第i台无人运输装置执行第j项运输任务所需要付 出的成本；所述的运输约束条件为每台无人运输装置能够承接的运输任务数量范围。 所述的k＝n-m，结合运输约束条件，找出能力最强的p台无人运输装置(p≤k)作为 “能者”并按能力进行排序； 具体过程如下： S21：约束条件指每台无人运输装置可执行的运输任务数量范围，其约束方程表示 为， 表示每台无人运输装置至少承接v个运输任务，最多承接u个运输任务， S22：对于同一个运输任务，在运输成本矩阵Cij(i∈[1,m],j∈[1,n])中找出最小 运输代价所对应的无人运输装置，列出每台无人运输装置所拥有的最小运输代价；找出拥 有最小运输代价最多项的无人运输装置，则该装置为运输能力最强，称为第一“能者”； S23：如果p＝1，则进行步骤S24；如果p≠1，排除第一“能者”，在剩余的无人运输装 置中，找出与第一“能者”能力差距最小的第二“能者”； 5 CN 111582804 A 说 明 书 3/11 页 其中，第a台无人运输装置与第b台无人运输装置之间的能力差距定义为 其中Cai表示第a台无人运输装置执行i任务所需的运输代价，Cbi表示 第b台无人运输装置执行i任务所需的运输代价； S24重复步骤S23直到得到p台“能者”。 所述的步骤S8包括如下： S81：对未被直线覆盖的所有元素减去Sv； S82：对被两条直线交叉覆盖的元素加上Sv； S83：进行步骤S6。 所述的步骤S9： 首先找出只有一个0元素的列，其位置代表无人运输装置与运输任务一一对应；然 后清除该行和该列的所有元素；在这个过程中，如果过程中同一列中有多个0元素，则去该0 元素对应的原始运输代价矩阵中，找出原始代价值最小的0元素，作为任务分配关系；持续 分配直到所有任务分配完毕。 本发明的有益效果在于：目前针对运输任务分配问题，现有的最优化分配方法对 非均衡任务分配并不适用，能适用于非均衡多任务分配的方法却不能保证得到最优结果。 本发明在能够得到最优分配方法的基础上，提出了一种“能者多劳”的分配思想，认为在非 均衡多任务分配问题中，能力越强的无人运输装置应该承接更多的运输任务，才能使总体 运输成本最优。在该思想的引导下，本发明针对现有算法无法应用于非平衡任务这个不足， 在构造虚拟运输装置来补齐分配矩阵的过程中，提出了基于不同约束条件下寻找不同数量 “能者”的策略，提出了能力差距的概念，给出了用不同数量的“能者”补齐分配方阵机制；在 此基础上，本发明利用了分配机制，从理论上保证了分配结果的最优性。本发明不仅仅适用 于无人运输装置的运输调度策略，针对工业园区的物质配送、小区快递站无人物流投送、港 口的集装箱运输等应用场景，基于本发明的运输调度能够给出最优的任务调度方案，使物 质运输总成本最低。 附图说明 图1为本发明提供的一种无人驾驶运输装置的任务分配方法的一种实施例的流程 示意图。
