·1042· 智能系统学报 第15卷 cpe T 任务的执行速度都是相同的，可以通过计算完成 (5) 所有任务的总路程，来换算出执行完成所有任务 式中：WT:为每个工人完成所有被分配任务所耗 的平均时间，优化的最终目标就是最小化平均任 费的时间；n为完成的任务数；R为完成所有任务 务执行时间。 的平均耗费时间；Couple,,是一个匹配参数，当工 人w和任务1匹配成功并且完成时间早于任务的 9 截止时间并且距离范围符合要求时，则任务完 8 成，Couple=l,否则视为任务未完成，Couple=O。 C为任务完成数量，希望尽可能地完成所有任务， 6 5 同时满足以下约束条件： 号 1)每个任务都有最后的结束时间，要求工人 必须在任务结束前将任务带到任务执行地点并完 成任务，假设工人们的技术水平相同，并且任务 到达任务执行地点便视为任务完成，如式(3)所示。 0 2345678910 2)任务完成具有先后顺序，必须先领取任 相对距离km 务，才能将任务带到执行地点，未领取任务之前 图1任务、工人和任务执行地点位置示意 便到达任务执行地点则不能视为任务完成，即式 Fig.1 Locations of tasks,workers,and customers (4)中工人领取任务的时间必须早于工人到达任 表1任务、工人和任务执行地点信息表 务t对应的地点c的时间。 Table 1 Information of tasks,workers,and customers 3)同一个工人执行的任务数不可过多，为保 对象 坐标km 报酬 服务质量 证总体的执行时间较少，在保证时间约束和总路 t (3.1,8.7 1 程最小化的前提下，将任务平均地分配给工人， t2 (5.5,4.7 1 使得每个工人都能凭劳动力获得报酬。如式 (2.82.3) 1 (5)所示，等号左边为工人w完成任务的数量， 5 W和T分别为该地区工人和任务的总数。 CL (10.0,9.7) 4)众包任务、工人以及任务执行地点要求在 C2 (7.7,6.0) 一定的区域范围内，距离过远的对象将不能进行 S (6.1,1.4) 任务分配，如式(3)所示。 WI (4.6,9.5) 0.635153 例1描述了任务分配的执行过程。 W2 (1.5,4.0) 0.469222 例1假设众包工作环境中有3个众包任务 、2、3,2个众包工人w和w2,以及每个众包任 由于问题的背景为动态情景，为了避免出现 务所对应的任务地点c、c2、c3,它们的位置如图1 局部最优的情况，设置了时间窗，即在一定的时 所示，每个点的信息如表1所示。众包工人和众 间段内，该时间段出现的3类对象的所有信息都 包任务随机散落在各个位置，当有任务出现的时 是可知的。众包工人和众包任务随机散落在各个 候，其所对应的执行地点也会相应地出现，此时 位置，当有任务出现的时候，其所对应的执行地 首先出现的任务就会分配给符合条件的工人去执 点也会相应地出现，此时首先出现的任务就会分 行，工人需要前往任务地点领取任务，随后再前 配给符合条件的工人。 往任务对应的执行地点完成任务。在对象出现的 假设工人%首先上班，此时任务出现，其 过程中，一般会进行两种决策过程：第1种是直接 所对应的任务执行地点c同时出现，系统将任务 将任务分配给最近的众包工人；第2种是暂不对 分配给工人w,工人需要前往1所在地点领取任 任务和工人进行分配，而是设置一个时间窗，在 务并送达c1。在工人w1前往领取任务的过程中， 时间窗内出现的全部对象进行整体的合理匹配。 任务2以及其所对应的任务执行地点c2出现。 众包任务、众包工人以及任务执行地点都有自己 在一定时间窗内，系统判断如果工人w,在领取了 对应的属性信息，包括地理位置，通过地理位置 任务后，再前往领取任务2，之后再送达也可以 可以计算出各个对象之间的距离，假设所有的众 满足时间约束的条件。那么系统会在保证先领取 包工人具有同等的技术水平，包括行进速度以及 任务后执行的前提下，在t、2、c、c2几个对象之∑ |w| i=1 Couplewti ≈ |T| |W| (5) WTi n R Couplewt w t Couplewt Couplewt C 式中： 为每个工人完成所有被分配任务所耗 费的时间； 为完成的任务数； 为完成所有任务 的平均耗费时间； 是一个匹配参数，当工 人 和任务 匹配成功并且完成时间早于任务的 截止时间并且距离范围符合要求时，则任务完 成， =1，否则视为任务未完成， =0。 为任务完成数量，希望尽可能地完成所有任务， 同时满足以下约束条件： 1) 每个任务都有最后的结束时间，要求工人 必须在任务结束前将任务带到任务执行地点并完 成任务，假设工人们的技术水平相同，并且任务 到达任务执行地点便视为任务完成，如式 (3) 所示。 t c 2) 任务完成具有先后顺序，必须先领取任 务，才能将任务带到执行地点，未领取任务之前 便到达任务执行地点则不能视为任务完成，即式 (4) 中工人领取任务的时间必须早于工人到达任 务 对应的地点 的时间。 w W T 3) 同一个工人执行的任务数不可过多，为保 证总体的执行时间较少，在保证时间约束和总路 程最小化的前提下，将任务平均地分配给工人， 使得每个工人都能凭劳动力获得报酬。如式 (5) 所示，等号左边为工人 完成任务的数量， | |和| |分别为该地区工人和任务的总数。 4) 众包任务、工人以及任务执行地点要求在 一定的区域范围内，距离过远的对象将不能进行 任务分配，如式 (3) 所示。 例 1 描述了任务分配的执行过程。 t1、t2、t3 w1 w2 c1、c2、c3 例 1 假设众包工作环境中有 3 个众包任务 ，2 个众包工人 和 ，以及每个众包任 务所对应的任务地点 ，它们的位置如图 1 所示，每个点的信息如表 1 所示。众包工人和众 包任务随机散落在各个位置，当有任务出现的时 候，其所对应的执行地点也会相应地出现，此时 首先出现的任务就会分配给符合条件的工人去执 行，工人需要前往任务地点领取任务，随后再前 往任务对应的执行地点完成任务。在对象出现的 过程中，一般会进行两种决策过程：第 1 种是直接 将任务分配给最近的众包工人；第 2 种是暂不对 任务和工人进行分配，而是设置一个时间窗，在 时间窗内出现的全部对象进行整体的合理匹配。 众包任务、众包工人以及任务执行地点都有自己 对应的属性信息，包括地理位置，通过地理位置 可以计算出各个对象之间的距离，假设所有的众 包工人具有同等的技术水平，包括行进速度以及 任务的执行速度都是相同的，可以通过计算完成 所有任务的总路程，来换算出执行完成所有任务 的平均时间，优化的最终目标就是最小化平均任 务执行时间。 t1 t2 t3 c1 c2 c3 w1 w2 10 9 8 7 6 5 4 3 2 1 1 2 3 4 5 6 7 8 9 10 0 相对距离/km 相对距离/km 图 1 任务、工人和任务执行地点位置示意 Fig. 1 Locations of tasks,workers, and customers 表 1 任务、工人和任务执行地点信息表 Table 1 Information of tasks,workers, and customers 对象 坐标/km 报酬 服务质量 t1 (3.1,8.7) 1 t2 (5.5,4.7) 1 t3 (2.8,2.3) 1 c1 (10.0,9.7) c2 (7.7,6.0) c3 (6.1,1.4) w1 (4.6,9.5) 0.635 153 w2 (1.5,4.0) 0.469 222 由于问题的背景为动态情景，为了避免出现 局部最优的情况，设置了时间窗，即在一定的时 间段内，该时间段出现的 3 类对象的所有信息都 是可知的。众包工人和众包任务随机散落在各个 位置，当有任务出现的时候，其所对应的执行地 点也会相应地出现，此时首先出现的任务就会分 配给符合条件的工人。 w1 t1 c1 w1 t1 c1 w1 t2 c2 w1 t1 t2 t1 t2 c1 c2 假设工人 首先上班，此时任务 出现，其 所对应的任务执行地点 同时出现，系统将任务 分配给工人 ，工人需要前往 所在地点领取任 务并送达 。在工人 前往领取任务的过程中， 任务 以及其所对应的任务执行地点 出现。 在一定时间窗内，系统判断如果工人 在领取了 任务 后，再前往领取任务 ，之后再送达也可以 满足时间约束的条件。那么系统会在保证先领取 任务后执行的前提下，在 、 、 、 几个对象之 ·1042· 智 能 系 统 学 报 第 15 卷