《中国人工智能学会通讯》——12.20 核心研究问题与研究现状任务分配

12.20 核心研究问题与研究现状任务分配

任务分配指时空众包平台根据任务和参与者的时空属性和其他相关信息，为每个任务分配适当的众包参与者。现存研究根据不同应用场景下任务分配的具体需求，通常采用二分图匹配模型和任务规划模型这两种算法模型对该问题进行建模。

（1）基于匹配的分配模型
在每次为众包参与者分配一项任务的应用场景下，如滴滴出行等专车类服务，可使用基于匹配的分配模型。具体而言，该模型将任务分配问题规约为最大化或最小化加权二分图匹配问题[20] 。根据任务实时性要求的差异，该模型又可分为静态离线场景和动态在线场景的匹配模型。在静态离线场景下，将任务和参与者建模为二分图两个不相交的顶点集合，并基于时空约束和应用特点构造加权二分图。时空众包任务分配的早期研究大都采用此模型[21-23] 。 然而，现实应用中平台通常难以提前获知众包任务和参与者的时空信息，研究者转而采用动态在线匹配模型进行建模。在动态在线场景下，每当任务或参与者出现在平台时，由于无法获知后续参与者和任务的时空信息，匹配决策仅可根据当前已知信息进行。换言之，需仅根据部分二分图信息来进行匹配决策[24-27] 。文献 [24] 首次提出了在线双边加权二分图匹配模型来建模该问题，该模型允许任务与参与者以任意顺序动态地出现在二维空间中的任意位置。求解此类任务分配问题的算法被称为在线算法，其算法性能既受制于二分图结构，又特别依赖于二分图顶点的出现顺序。如图3所示,图3(d)显示了完整的离线二分图结构。然而，由于任务和参与者动态出现，仅根据局部二分图信息进行任务分配决策。假设给定任务和参与者的抵达顺序为〈w 1 , t 1 , t 2 , w 2 , t 3 , w 3 , t 4 , w 4 , t 5 〉，且采用简单的在线贪心算法（其指每次决策仅选择当前未分配边中权值最大的边），部分任务和参与者抵达时的算法分配情况，如图3(a)~(c)所示。此外，文献[25]提出了动态在线最小化二分图权值和匹配模型，并发现了一项有悖于该模型过去 25 年研究的新结论。该模型的研究一直认为贪心算法求解此问题会产生极差的效果。然而，若采用平均情况分析，可发现最差情况分析理论下的最差实例在平均情况分析下的竞争比仅为 3.195。实验也显示出贪心算法实际求解该模型具有很好的效果。
（2）基于规划的分配模型
当众包参与者在给定时间内要求执行多项众包任务时，可使用基于规划的分配模型。该模型适用于百度外卖等物流派送类服务，其中平台需为众包参与者规划任务执行的路径。现存基于规划的任务分配模型也可根据任务的实时性要求不同分为静态离线场景与动态在线场景的规划模型。静态离线场景下的任务规划问题通常被规约为经典的旅行商问题或者定向问题 (Orienteering Problem)，而在动态在线场景下，每当有新任务在众包平台发布时，平台需为每位参与者实时地决定是否将此项新任务加入到其当前的任务规划之中[28] 。