面向路网的空间众包群组任务匹配和调度算法

钱勤红，刘 安，孙玉娥

1(苏州大学 计算机科学与技术学院，江苏 苏州 215006) 2(苏州大学 轨道交通学院，江苏 苏州 215137)

1 引 言

智能设备和移动互联网的发展使得空间众包的应用和研究日益流行.空间众包是一种新型的问题解决架构，通过雇佣大众工人来有效地完成具有时空属性的任务.目前著名的空间众包应用包括滴滴出行打车平台、饿了么外卖平台、Task Rabbit家政平台等.在空间众包系统中，任务可以分成两类：个人任务和群组任务.前者指的是单个工人就能完成的任务，比如一个外卖订单只需安排给一个骑手.后者指的是需要多个工人组成团队才能完成的任务，比如装修房屋的任务需要掌握刷墙、布线、组装家具等技能的工人团队合作才能完成.

综述[1]对空间众包的现有工作进行了全面的梳理和总结，并指出任务匹配和任务调度(任务规划)是研究空间众包的两个基础问题.大多数任务匹配工作[2-5]主要针对简单的个人任务展开研究的，即如何将任务分配最合适的工人.随着研究的深入，有工作研究了群组任务匹配[6-11]问题，该问题旨在组建满足任务约束的工人团队完成任务.现有的任务调度[12-17]工作都是针对个人任务展开研究的，为工人规划执行个人任务的调度序列.而关于群组任务调度问题暂时还没有工作对此展开研究.

考虑到现有工作的不足，本文研究了群组任务匹配和调度问题.该问题研究的是在考虑路网的场景下，不仅为动态到达平台的任务组建一个满足技能和时空约束的团队，同时安排团队中工人完成任务的路线.现有群组任务匹配工作与本文工作的不同在于，它们都没有从工人角度考虑.例如文献[11]研究在线多技能任务匹配问题，依次为动态到达平台的任务组建团队，但该工作没有考虑当工人能够完成多个任务且此刻需要去完成平台之前分配给他的其余任务时，工人应该以何种路线完成当前任务和剩余待完成任务.现有任务调度工作与本文工作的不同在于，它们都是基于任务是个人任务假设研究的，没有考虑群组任务需要多个具有专业技能的工人合作才能完成的情况.同时，现有绝大部分任务匹配和调度工作都是基于欧式距离假设展开研究的，用欧式距离估计工人与任务之间的旅行成本可能与实际工人完成任务的旅行成本有较大的偏差从而导致匹配或调度无效.如图1所示，假设任务和工人分别出现在v1和v12，两点之间的欧式距离很近而实际路网距离却很远.为了避免出现类似偏差同时更贴合实际，本文假设工人完成任务的旅行成本是基于路网距离计算的.

图1 路网样例Fig.1 Example of road network

解决本文问题的一个直接想法是遍历所有工人验证其是否满足截止时间、预算或技能约束找到有效工人集，然后在有效工人集中组建能完成任务的团队.在考虑路网的场景下，遍历验证工人是否能在任务指定截止时间之前或成本预算内完成任务涉及大量的最短路径计算，在大规模路网上的最短路径计算成本是昂贵的，同时待验证的工人数量是庞大的而实际满足约束的工人是少量的.也就是说遍历所有工人验证其有效性是浪费且耗时的.因此本文应用空间换时间的思想，提出基于网格索引的群组任务匹配和调度算法框架.该框架由网格索引、搜索有效工人集算法和组建团队算法组成.该框架首先通过网格索引存储路网信息和工人信息快速过滤掉不满足时间或预算约束的工人，避免大量无效的最短路径计算.然后利用基于剪枝策略的搜索算法搜索到满足任务约束的有效工人集.最后通过组建团队算法迭代地在有效工人集中选择最小成本覆盖比的工人加入团队完成任务.本文的具体工作如下：

1)首先介绍了空间众包中的群组任务匹配和调度问题，该问题旨在为动态到达平台的任务组建团队，同时安排团队中工人完成任务的路线，从而最大化任务完成效用.

2)为了解决该问题，提出了基于网格索引的群组任务匹配和调度算法框架，并详解介绍了框架内的网格索引、搜索有效工人算法和团队组建算法.

3)为了评估算法的性能，在真实数据集和合成数据集上进行了实验.结果表明，对比其他算法，本文提出的剪枝策略和组建团队算法更有效.

2 相关工作

综述[1]指出任务分配、质量控制、隐私保护、激励机制是研究空间众包工作的四个核心问题.其中，任务分配通常被建模为匹配问题和调度问题，同时按任务的属性区分个人任务和群组任务.然而当前关于任务调度的工作都是基于个人任务假设开展研究的，且现有关于群组任务匹配的工作没有考虑工人是如何执行任务的.因此现有的方法不能直接应用解决本文提出的问题.接下来从任务调度和群组任务匹配角度分别回顾与本文相关的工作.

2.1 任务调度问题

任务调度是指不仅需要考虑将多个合适的任务分配给工人同时还需要规划工人完成任务的调度序列.文献[12]研究了单工人的任务调度问题，该问题旨在给定工人的出行成本约束下，通过精确算法和近似算法为一个工人找到完成任务的调度序列，从而最大化任务完成的数量.文献[15]研究了单工人的在线任务调度问题，考虑任务是动态到达平台的且工人是持续更新的场景下，为一个工人规划一条执行任务的调度序列.文献[14]研究了同时规划多个工人的任务调度序列问题，它是基于文献[2]和文献[12]扩展的工作.该工作通过迭代进行匹配和调度，逐步逼近最优解.文献[16]研究了多工人任务调度问题，通过树分解技术处理工人之间的任务冲突，从而最大化任务完成数量.文献[17]研究了多工人在线任务调度问题，通过延迟调度和快速调度两种算法规划工人执行任务的调度序列，从而使得任务完成总效用最大.

以上工作都是基于欧式距离假设展开研究的，但在实际应用中工人是按地图中的路线执行任务的.虽然有部分工作[13，18]考虑了路网信息，但它们研究的问题与本文不同.文献[13]研究的是基于路网的单工人任务调度问题，旨在为工人推荐多条互相非支配的执行任务路线.文献[18]研究的是基于路网的拼车问题，拼车问题是空间众包的一类实际应用问题.该工作根据拼车任务的特有属性设计了网格索引存储信息加快响应速度，但该网格索引不能直接解决本文问题.原因是一方面拼车的任务属性和本文研究的任务属性不同，另一方面将网格中心之间的距离作为近似网格距离，这会导致搜索到的有效工人集是不完整的.

2.2 群组任务匹配

群组任务匹配问题是指将多个工人组成团队去完成一个群组任务的匹配问题.文献[6]研究了以最大化时空多样性和可靠性为优化目标的任务匹配问题.该工作通过贪心、随机抽样和分治3种不同的启发式算法为任务组建时空多样性和可靠性最高的团队.文献[7]研究了多技能任务匹配问题，该问题旨在组建一个掌握任务所需技能的工人团队，在任务预算的约束下最大化平台收益.文献[8]研究了细粒度收费的群组任务匹配问题，该问题假设工人完成任务时的不同技能对应不同收费.文献[9]研究了以最大化团队合作质量为优化目标的群组任务匹配问题，该问题假设不同工人之间的合作质量是不同的.文献[10]研究了任务之间存在先后依赖关系的群组任务匹配问题.文献[11]研究了在线群组任务匹配问题，该工作通过贪心算法依次处理每个动态到达平台的任务和工人.

3 系统模型和问题定义

3.1 系统模型

本文研究的群组任务匹配和调度系统由空间众包平台、若干个任务发布者以及若干个工人组成，如图2所示.任务发布者通过移动设备(如智能手机)实时提交任务，每个任务都指定了地点、预算、截止时间和所需技能集.平台在收到新的任务后，将组建一个工人团队完成任务.要求该团队既满足当前任务的约束，同时不违反团队中各工人的现有任务调度序列中待完成任务的约束.最后通知工人和任务发布者当前任务的调度结果.

图2 群组任务匹配和调度系统Fig.2 Group task matching and scheduling system

3.2 问题定义

定义1.(路网) 通过图G=表示路网.其中每个节点v∈V表示一个实际位置点；每条边e=(u，v)∈E表示连接两个实际位置点的路段；每条边都与一个权重w(e)∈W关联，权重表示经过这条边的成本.旅行成本可以用距离或时间来衡量，当工人速度(由β表示)已知时，距离和时间可以相互转换，因此本文将旅行距离作为旅行成本.为了简单起见，本文假设路网是无向图且工人的速度是一致且恒定的，但本文提出的解决方案很容易扩展到有向路网和工人速度是随时间变化的场景中.

定义4.(群组任务)t=表示一个群组任务.在时间att，任务被提交到平台上，要求在位置lt和截止时间dt之前被完成.同时分配给该任务的团队技能并集能够覆盖任务所需的技能集Kt={kt0，kt1，…}，且团队完成任务的总成本不超过预算Bt.

(1)

定义6.(工人的报酬)如果工人w被平台安排去完成任务t，那么平台会根据他的绕行成本支付给工人报酬R(w，t)=α.dcost(w，t).α是一个常数，表示工人报酬和绕行成本之间的比例关系.

定义8.(群组任务匹配和调度问题)给定道路网络G，更新后的工人集W，当前到达平台的任务t，组建能够完成任务的团队Wt，同时更新团队Wt中每个工人完成该任务以及剩余待完成任务的调度序列，从而最大化效用，即Max(U(t，Wt))，且满足以下约束：

1)截止时间约束：任务需要在截止时间之前被完成.

2)预算约束：任务发布者支付给团队的报酬不超过预算.

3)容量约束：工人的当前任务调度序列长度不超过容量.

4)不变性约束：任务调度序列一旦确定，则不能改变.

定义9.(有效任务调度序列)当且仅当以下条件成立时，Sw被称为有效任务调度序列：

1)|Sw|≤cw，即序列中待完成任务的数量不超过工人容量.

2)∀t∈Sw，expt≤dt，即序列中每个待完成任务的期望完成时间都不超过对应截止时间.期望完成时间是指工人在当前时间沿平台给定路线完成任务的时间，序列中每个任务都与它的期望完成时间关联，它可能因为新任务的插入而改变.

定义10.(有效工人)给定任务t，当且仅当以下条件成立时，工人w才称为有效工人，由vwt=表示，其中iloc和icost分别表示任务插入该工人任务调度序列的位置和成本：

1)Kw∩Kt≠∅，即工人掌握的技能和任务需要的技能交集不为空.

3)R(w，t)≤Bt，即工人完成任务的成本不超过任务预算.

4 解决方案

本章将介绍群组任务匹配和调度问题的解决方案.首先介绍基于网格索引的群组任务匹配和调度算法框架，然后介绍框架中网格索引、搜索有效工人集算法和组建团队算法.

4.1 基于网格索引的群组任务匹配和调度算法框架

在实际应用中，由于任务是动态出现的，平台只能依据当前的信息进行调度，因此本文假设平台依次处理每个动态到达平台的任务.对于每个任务，直接遍历所有工人验证其有效性然后组建团队的方法存在大量无效的最短路径计算.因此本文根据空间换时间的思想，提出了基于网格索引的群组任务匹配和调度算法框架，该框架通过网格索引预先计算存储的信息快速过滤掉不满足约束的工人，避免大量无效的计算，加快实时响应速度.

如算法框架1所示.对于每个动态出现的任务，平台首先根据工人的新状态更新索引结构，然后通过最新的索引结构找到有效工人集以及对应工人的有效任务序列，然后在有效工人集中找到满足约束的团队，最后通知团队内的每个工人按指定路线完成该任务，同时向任务发布者返回团队信息.若没有找到满足约束的团队，则拒绝该任务，任务发布者可以更改任务的基本信息(放宽约束，如增加预算)再次提交.

算法框架1.基于网格索引的群组任务匹配和调度框架

输入：任务T，道路网络图G，工人集W

输出：完成对应任务的团队集{…，，…}

1.构建网格索引(G，W)

2.Foreach新出现的任务ti∈T

3. 根据工人们的新状态更新网格索引

4.VWti=搜索有效工人算法(ti，W) //算法1

5.Wti=组建团队算法(t，VWti) //算法4

6. IfWti≠∅

7. 更新团队中工人的任务调度序列和路线

8. 通知工人完成任务

9. 通知任务发布者团队信息

10. Else

11. 通知任务发布者拒绝服务该任务

4.2 网格索引

本文使用网格划分路网并维护工人的位置信息，加快有效工人的搜索.

定义11.(边界节点)假设一条边e=(u，v)中的节点u和节点v不属于同一个网格，那么就称u和v为边界节点.每个网格单元gi都维护各自的边界节点列表，由BVi表示.如图1所示，节点v4和v5分别是g0和g5的一个边界节点.

Dij=min{spl(u，v)|u∈BVi，v∈BVj}

(2)

同时，为了精确估计两个节点之间的最短路径长度，需要预先计算并存储所有网格对之间的最短距离，由矩阵D表示.矩阵中每个元素Dij表示gi和gj之间的最短距离，由公式(2)计算可得，即网格对的各自边界节点之间的最短路径长度的最小值.

除此之外，每个网格单元gi都维护以下信息：

1)边界节点列表BVi：该列表记录网格的边界节点.

2)节点列表Vi：该列表记录位于该网格的所有节点，同时记录节点v∈Vi到各边界节点的最短路径长度的最小值，记为v.min=min{|u∈BVi}.

3)邻居网格列表NGi：该列表中的网格gj∈NGi与当前网格gi之间有路径可达，即Dij≠∞.同时该列表以Dij的值从小到大排序存储.

4)工人列表Wi：该列表记录当前时间位于网格gi的所有工人.该列表记录当前或即将位于网格gi的所有工人，即将位于网格的工人是指根据其调度路径行驶，在给定时间阈值内能够到达网格gi的工人.同时该列表以工人的当前位置到网格gi的边界节点的最短路径长度的最小值从小到大排序存储，由于工人位置是也是路网上的一个节点v，因此该最小值可以通过查询当前网格的节点列表可以快速获取，即该最小值为v.min.也就是说更新网格索引中的工人并维护其有序性是快速的.

本文通过两个节点之间的最短路径长度下界快速过滤掉不满足约束的工人从而加快响应速度，最短路径长度下界lspl(u，v)是基于网格对距离矩阵D计算的，如计算公式(3)所示.对于两个节点u∈gi和v∈gj，如果两个节点所在的网格相同，那么下界为lspl(u，v)=0；如果不同则lspl(u，v)=Dij+u.min+v.min，其中u.min和v.min是分别被存储在网格gi和网格gj的节点列表中，可快速查询得到.也就是说最短路径长度的下界计算时间复杂度为O(1).同样的，从节点v∈gj到网格gi的最短路径长度下界如计算公式(4)所示.

本文假设工人的当前位置和任务位置都可映射到一个路网节点上.为了简化公式，本文用lspl(w，t)=lspl(clw，lt)表示工人w从当前位置移动到任务t所在位置的最短路径长度下界.同样的，用lspl(ti，tj)=lspl(lti，ltj)表示任务ti和任务tj之间的最短路径长度下界.

最后，分析更新网格索引的时间复杂度.根据上述信息可知，只有工人列表是需要更新的，其余路网信息都是静态的，只需要计算一次.最坏情况是所有工人都移动到新的网格，也就是说需要更新每个网格的工人列表.因此更新网格索引的时间复杂度等于更新每个网格的工人列表并维护其有序性的时间复杂度，O(nng×nw×lognw).

(3)

(4)

4.3 剪枝策略

为了避免大量无效的最短路径计算，接下来根据之前公式(3)计算的最短距离下界设计不同的剪枝策略.

剪枝2.给定任务t，网格gi，若lspl(gi，lt)>(dt-att)×β，那么位于网格gi内的所有工人都将被剪掉.具体而言位于网格gi的所有工人无法在截止时间之前完成该任务，因此该网格内的工人可被安全剪去.同样的，给定一个工人w，若lspl(clw，lt)>(dt-att)×β，那么也无需继续验证该工人的有效性.

剪枝3.给定任务t，空闲工人w，若lspl(clw，lt)>Bt/α，那么该工人将被过滤掉.具体而言由于将当前任务插入空闲工人的任务调度序列产生的绕行成本下界超过了任务的预算成本，即支付给该工人的最低报酬超过了任务预算，因此不需要实际计算最短路径长度验证该工人的有效性.

剪枝4.给定任务当前的有效工人集VW，空闲工人w，若∃vw∈VW，Kw⊆Kvw且lspl(w，t)≥dcost(vw，t)，这表示w被vw支配[19].具体而言，若VW中存在一个有效工人vw，w掌握的技能被vw掌握的技能包含，同时w完成任务的绕行成本下界大于等于vw完成任务的绕行成本，则不需要验证该工人的有效性就可将其直接剪去.

剪枝5.给定任务t，非空闲工人w，和插入位置i∈{0，1，…，|Sw|}，若Sw.expti-1+lspl(lti-1，lt)/β>dt，那么对于插入位置i，i+1，…，|Sw|都直接跳过可行性检查.其中Sw.expti-1表示插入位置前一个任务在调度序列Sw内的期望完成时间，是在处理ti-1时计算并存储的.具体而言，将t插入w的Sw中的位置i时，若工人完成任务t的最早期望时间超过截止时间，则不需要验证当前以及后续插入位置i，i+1，…，|Sw|的有效性.

剪枝6.给定任务t，非空闲工人w，和插入位置i∈{0，1，…，|Sw|}，若ld(w，t，i)>Bt/α，那么对于非空工人的插入位置i跳过有效性检查.具体而言，将t插入w的Sw中的位置i时，若工人完成该任务的绕行成本下界超过任务预算成本，则无需计算实际绕行成本验证该插入位置是否有效.

ld(w，t，i)表示绕行成本下界，如计算公式(5)所示.公式(5)中，当i=0时，由于工人的当前位置在任务到达平台时已更新，这意味着工人的当前位置与任务t0的位置之间的距离为(Sw.expt0-att)×β，通过任务的期望完成时间避免了工人当前位置到任务t0的最短距离计算.其他插入位置的绕行成本下界以相同的方式计算.

(5)

剪枝7.给定任务t，非空闲工人w，插入位置i∈{0，1，…，|Sw|-1}，若∃tj∈{tsi，tsi+1，…}，Sw.exptj+ld(w，t，i)/β>dtj，那么对于非空工人的插入位置i跳过可行性检查.具体而言，将t插入w的Sw中的位置i时，若插入位置后的剩余任务的期望完成时间违反了自身的截止时间约束，则不需要计算实际绕行成本验证该插入位置是否有效.

剪枝8.给定有效工人集VW，非空闲工人w，插入位置i，若∃vw∈VW，Kw⊆Kvw且ld(w，t，i)≥dcost(vw，t)，则可以不继续检查该插入位置i的有效性.具体而言，若VW中存在一个有效工人vw，w掌握的技能被vw掌握的技能包含，同时w完成任务的绕行成本下界大于等于vw完成任务的绕行成本，则无需计算实际绕行成本验证该插入位置是否有效.

4.4 搜索有效工人集

由于任务有技能、时间和预算的约束，不是所有工人都能完成任务，因此应该在不违背约束条件的前提下找到可以完成任务的有效工人集.

对于每个动态任务t，根据有效工人的定义，本文设计了高效的搜索算法为任务找到有效工人集.搜索有效工人算法如算法1所示，该算法从任务所在的网格单元gt开始搜索工人，之后搜索该网格gt的邻居网格列表NGt(第3行).在搜索网格gi内的有效工人之前，需要验证当前搜索的网格是否有效，即若当前网格内所有工人的技能并集不包含一个或多个任务所需技能，则跳过该网格检查下一个网格(第4-5行，剪枝1)；若任务与当前网格gi的最短距离下界超过任务的最大等待距离，则直接跳出该循环结束搜索(第7-8行，剪枝2).原因是任务所在网格gt的邻居网格列表NGt是按最短距离升序存储的，也就是说在当前搜索网格gi的工人们无法按时完成任务，那么接下来待搜索的网格距离任务更远，完成任务的时间更晚，不可能满足任务的截止时间约束，因此不继续搜索剩余网格.接下来在合格网格中搜索有效工人集.同样的，根据剪枝1和剪枝2过滤掉无效的工人(第11-15行).需要注意的是，网格中工人列表也是其到网格边界节点的最短路径长度升序存储的，同时将任务插入空闲工人调度序列的位置和绕行成本是唯一确定的，因此若支付给该工人的最低报酬超过任务预算，则不需要验证剩余空闲工人的有效性，即通过skip_flag标记(第16-17行).最后，由于空闲工人和非空闲工人的任务调度序列不同，因此分别调用算法2搜索空闲工人的有效调度(第18-20行)和算法3搜索非空闲工人的有效调度(第21-22行)，需要注意的是，对于非空闲工人还需要检查他的容量约束.最后返回有效工人集(第23行).搜索有效调度的算法是基于插入启发式设计的，本文通过尽早将不满足约束的插入位置剪枝避免遍历所有插入位置验证而产生的无效计算

算法1.搜索有效工人算法

输入：任务t，基于路网的网格索引

输出：有效工人集VW={，…}

1.初始化有效工人集VW={}

2.任务位于网格gt内

3.Foreach待搜索网格gi∈{gt∪NGt}

5. Continue// 剪枝1

6. 按公式(3)计算距离下界lspl(gi，lt)

7. Iflspl(gi，lt)>(dt-att)β

8. Break// 剪枝2

9. skip_flag = 0

10. Foreach待验证工人w∈Wt

11. IfKw∩Kt==∅

12. Continue// 剪枝1

13. 按公式(3)计算距离下界lspl(clw，lt)

14. Iflspl(clw，lt)>(dt-att)β

15. Break// 剪枝2

16. Iflspl(clw，lt)*α>Bt

17. Skip_flag = 1// 剪枝3

18. IfSw==∅ and(not skip_flag)

19. If not IsDominated(VW，w) // 剪枝4

20.VW=VW∪搜索空闲工人有效调度(t，w)

21. Else if|Sw|

22.VW=VW∪ 搜索非空闲工人有效调度(t，w)

23.ReturnVW

搜索空闲工人有效调度算法如算法2所示.由于空闲调度序列为空，因此任务插入其调度序列的位置是确定唯一的，即将当前任务分配该工人后生成的任务调度唯一的.直接调用最短路径长度函数计算工人与任务之间的实际最短距离，若工人满足任务的截止时间和预算约束(第1-3行)，则返回该工人以及任务即将插入该任务序列中的位置0和绕行成本spl(clw，lt)(第4行).

算法2.搜索空闲工人有效调度算法

输入：任务t，空工人w

输出：有效插入位置及成本

1.spl(clw，lt)=shorestPathLength(clw，lt)

2.Ifspl(clw，lt)≤(dt-att)β

3. Ifspl(clw，lt)≤Bt/α

4. Return

搜索非空闲工人有效调度算法如算法3所示.和验证空闲工人不同的是，任务插入非空闲工人任务调度的位置是不确定的，需要依次验证每个插入位置是否满足约束并计算对应的实际绕行成本，找到实际绕行成本最小的那个插入位置.具体而言，首先初始化最佳插入位置和最小插入成本(第1行)，接着依次验证每个插入位置的有效性，即若将当前任务t插入Sw中的位置i之后，任务t的最早期望完成时间超过它的截止时间，则跳出循环结束验证(第4-6行，剪枝5)；按公式(5)计算绕行成本下界，若该下界超过任务预算成本约束，则跳过该位置的验证(第7-9行，剪枝6)；若插入当前任务后，插入位置之后其他任务的最早期望完成时间超过它的截止完成时间，则跳过该位置的验证(第10-12行，剪枝7).之后调用最短路径长度函数和绕行成本计算公式得到实际最短距离和绕行成本验证插入位置的有效性并保存最小插入成本的位置(第13-23行).最后返回有效非空闲工人以及最佳插入位置和最小插入成本(第24-25行).需要注意的是，插入位置i=0的前一个位置是工人的当前位置，插入位置i=|Sw|则不需要检查剩余任务的期望完成时间是否超过自身的截止时间.

算法3.搜索非空闲工人有效度算法

输入：任务t，非空工人w

输出：有效插入位置及成本

1.ilocbest=-1，icostmin=∞

2.Foreach插入位置i=[0，1，…，|Sw|]

3. flag=1

6. Break// 剪枝5

7. 按公式(5)计算绕行成本下界ld(w，t，i)

8. Ifld(w，t，i)>Bt/α

9. Continue// 剪枝6

10. Foreach插入位置之后的任务

11. Ifld(w，t，i)/β+exptj>dtj

12. flag=0 and Break // 剪枝7

13. If flag and(not Is Dominated(VW，w，i)) //剪枝8

16. Break

17. 按公式(1)计算实际绕行成本dcost(w，t，i)

18. Ifdcost(w，t)≤Bt/α

19. Foreach插入位置之后的任务

20. Ifdcost(w，t)/β+exptj>dtj

21. flag=0 and Break

22. If flag anddcost(w，t)

23.ilocbest=i，icostmin=dcost(w，t)

24.Ificostmin<∞

25. Return

最后，分析搜索有效工人算法的时间复杂度.最坏情况是所有工人都满足任务的约束且所有工人的任务调度序列长度为|Sw|=cw-1，即需要验证每个非空闲工人的的每个插入位置的有效性，因此搜索有效工人算法的时间复杂度是O(|W||C|)，其中|C|表示工人的容量.

4.5 组建工人团队

通过搜索有效工人算法为任务搜索到一个有效工人集VW={，…}，该集合中每个元素表示工人w能够以icost的绕行成本完成该任务，假设该工人被选中完成任务，那么将任务插入任务序列sw的iloc位置，并更新插入位置之后的待完成任务的期望完成时间.

文献[11]证明了在有效工人集中组建团队问题是一个NP难问题，因此提出最小成本覆盖比值贪心算法为当前任务组建团队.其基本思想是，每次迭代选出icostw/|Kw∩Kt|(绕行成本与工人覆盖技能的比值，该比值越小表示支付给该工人的报酬越少而工人掌握任务所需技能越多)最小的工人加入团队，直到任务所需技能被全覆盖或待验证有效工人集为空.如算法4所示.每次循环都选出比值最小的工人(第3行)，若将该工人加入团队的成本不超过任务的剩余预算，则将他加入团队，从待组建工人集(即有效工人集)中删除，并更新任务当前所需覆盖的技能以及当前预算，同时将不包含一个或多个任务当前所需覆盖技能的工人从待组建工人集中删除(第4-8行).若将该工人加入团队的成本超过任务的剩余预算，则将他从待组建工人集中删除(第9-10行).最后如果任务所需技能全部被覆盖，则返回工人团队Wt(第11-12行).该算法的时间复杂度是O(|K||VW|)，其中|K|和|VW|分别表示任务所需技能集的大小和有效工人集的大小.

算法4.最小成本覆盖比值组建团队算法

输入：一个任务t，有效工人集VW

输出：工人团队Wt

1.初始化工人团队Wt={}，团队成本C=0

2.WhileKt≠∅ andVW≠∅

3.w*=argminw∈VWicostw/|Kw∩Kt|

4. Ifα*icostw*≤Bt

5.Wt=Wt∪{w*}，VW=VW-w*

6.Kt=Kt-Kw*，Bt=Bt-α*icostw*

7.RW={w|∀w∈VW，|Kw∩Kt|=∅}

8.VW=VW-RW

9. Else

10.VW=VW-w*

11.IfKt= =∅

12. ReturnWt

5 实验分析

5.1 实验数据与参数设置

通过OpenStreetMap获取香港路网数据，路网由包含32450个顶点和66090条边的无向图表示.网格索引中相关路网信息提前计算并存储.假设当工人的任务调度序列不为空时，工人沿着给定路线行进，否则在原地等待.

本文通过由两部分组成的合成数据集验证算法的有效性和可扩展性.一部分是Meetup(基于位置的社交应用)中的真实事件和用户的位置、标签信息.和文献[11]类似，将Meetup中的事件将视作任务，将用户视作工人，他们自带的标签作为各自的技能集，并根据事件的时间先后依次处理每个相关联的任务.本文使用分布在香港(经度为113.843～114.283，纬度22.209～22.609)的事件和用户初始化任务和工人信息，共计1234个任务、3275个工人.另一部分是随机生成的信息，即任务的位置和工人初始位置随机映射到路网中的节点上，而任务所需技能集大小、发布时间、最大等待时间(开始时间加上最大等待时间是截止时间)、预算以及工人的容量属性都随机生成.随机生成的数据都服从以默认值为均值的高斯分布.参数设置的具体信息如表4所示，其中粗体作为默认值.本文使用表1中参数来研究算法性能.在每个实验中，只更改一个参数并将其它参数设置为默认值.评价指标包括运行时间、任务完成效用，每个衡量指标值是所有任务的平均值.

表1 实验参数Table 1 Experimental parameters

5.2 对比算法

为了评估本文提出的算法，需要使用其他算法作为对比算法.但是本文研究的问题不同于现有工作，即已有算法不能直接应用解决本文研究的问题.因此针对本文研究的问题，设计了两类对比算法：最大覆盖技能组建团队算法和基于欧式距离剪枝策略的搜索算法分别对比本文的算法框架、剪枝策略和组建团队算法的有效性.

1)最大覆盖技能组建团队算法(Maximum Coverage Skill Team Formulation，MCSTF)的基本思想是根据工人掌握技能数量贪心迭代地组建团队，即每轮迭代都从所有工人中选出一个掌握技能与待覆盖的任务所需技能交集元素最多的工人，直到待覆盖的任务所需技能为空或待验证工人集为空.

2)改进的最大覆盖技能组建团队算法(Improved Maximum Coverage Skill Team Formulation，IMCSTF).由于MCSTF中每轮迭代选择最佳工人时，不涉及最短路径长度的计算，因此可以不采用本文提出的先搜索后组建的框架，而是直接组建团队.具体而言，对于当前到达平台的任务，每轮迭代都从所有工人中选出一个掌握技能与待覆盖的任务所需技能交集元素最多的工人，然后直接计算最短路径长度验证该工人的时空有效性同时找到最佳插入位置，若有效则将他添加至工人团队，否则跳过该工人.直到待覆盖的任务所需技能为空或待验证工人集为空.

3)欧式距离剪枝策略(Euclid Distance Pruning Strategy，EDPS)是将两点间的欧氏距离作为最短路径长度下界对待检查工人进行剪枝.

4)基于网格索引的群组任务匹配和调度算法(Group Task Matching and Scheduling based Grid Index Algorithm，GTMSGIA)，即本文提出的算法.其基本思想是对于当前到达平台的任务通过算法1先搜索有效工人集，然后基于有效工人集组建团队，每轮迭代在有效工人集中选择成本覆盖比值最小的工人，直到任务所需技能被团队掌握技能并集覆盖或待验证工人集为空.

5.3 实验结果和分析

本文通过改变任务数量、工人数量和工人容量分别对比GMTSGIA、IMCSTF、EDPS的运行时间.因为改变搜索验证有效性的先后关系或剪枝策略并不影响团队完成任务的效用，所以仅对比GMTSGIA、MCSTF的任务完成效用.

5.3.1 任务数量变化对算法的影响

图3展示了不同任务数量下的各算法运行时间，均随着任务数量的增加而上升.这是因为任务数量的增加意味着工人的待完成任务增加，从而导致待验证的插入位置增加.可以看出本文提出的算法运行时间远小于其他两个算法，其中IMCSTF的运行时间比EDPS更少的原因是，前者是选出覆盖技能元素最多的工人之后再计算最短路径长度验证该工人是否有效，而后者需要遍历所有工人验证有效性，同时欧式距离只是两点间最短路径长度的最小值，因此它的剪枝效果远远不如本文提出的剪枝策略.

图4展示不同任务数量下的各算法的任务完成的平均效用.不论在何种任务数量下，本文提出的算法都优于MCSTF，而且接近于任务的预算均值，这表示工人完成任务的旅行成本比较小，而MCSTF算法的任务完成的平均效用仅接近预算的1/3.

5.3.2 工人数量变化对算法的影响

图5展示了不同工人数量下的各算法运行时间，均随工人数量的增加而上升.这是因为工人数量的增加导致待验证的工人数量增加.可以看到EDPS急剧上升，而本文提出的算法一直稳定在100ms的左右运行时间.

https：//openstreetmap.org

图6展示不同工人数量下的各算法的任务完成的平均效用.不论在何种工人规模下，本文提出的算法都优于MCSTF.

6 总 结

本文针对现有研究中任务调度问题忽略了群组任务以及底层的路网信息提出了群组任务匹配和调度问题，并提出了基于网格索引的群组任务匹配和调度算法框架解决该问题.该框架首先通过网格索引存储的路网和工人信息快速过滤掉不满足时间或预算约束的工人，避免大量无效的最短路径计算.然后利用基于剪枝策略的搜索算法搜索满足任务约束的有效工人集.最后通过组建团队算法迭代地在有效工人集中选择最小成本覆盖比的工人加入团队完成任务.最后设计了对比实验验证本文提出的解决方案的有效性和高效性.

GTMSGIAIMCSTFEDPS543210运行时间()s1K2K3K4K5K2402.2911.3409.3871.4293.08.0977.1121.1401.1582.0.140.1570.1590.1630.165GTMSGIAMCSTF25201510501K2K3K4K5K效用237.221.235.24239.9103.114.97.81.GTMSGIAIMCSTFEDPS76543210运行时间()s1K3K5K7K9K0059.014.02.023.0234.024.08.1467.2317.3124.0484.2402.3718.GTMSGIAMCSTF3025201510501K3K5K7K9K效用237.221.9228.251.252.91.107.119.153.