文档介绍：时空众包环境下时效均衡的在线任务分配算法
摘 要:针对时空众包任务分配研究中单一考虑任务分配总效用或任务等待时间,导致总体分配效果不佳的问题,提出一种基于分配时间因子的动态阈值算法。首先,基于预估等待分配时间和已等待分配时间计proving the total utility of task allocation, to achieve the balance between the total allocation utility and the task waiting time.
英文關键词Key words: spatial crowdsourcing; online task assignment; total utility of task allocation; waiting time of task; allocation time factor; dynamic threshold algorithm
0 引言
众包[1-3]这一概念由美国人Jeff Howe在美国《连线》杂志上于2006年首次提出,通常指一种把工作任务通过公开的 Web 平台以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式。随着互联网技术的发展,这种通过群体智慧求解问题的新模式也受到了工业界和学术界的广泛关注,像AMT (Amazon Mechanical Turks)这类众包平台得到了迅速发展。近年来,伴随移动互联网技术和共享经济的兴起,以及移动智能设备的普及和应用,为众包模式带来更多的外延需求,不再满足于传统众包模式下单一的任务类型,扩展了更多包含时空属性,从而发展为时空众包[4],例如,滴滴出行、百度外卖等。 在时空众包环境下,任务分配[5]依然是其核心问题之一。针对这一问题学术界展开了积极研究,文献[6-8]重点考虑任务分配总效用: 文献[6]提出一种基于两阶段框架模型的全球在线微任务分配改进算法(Two phase based Global Online AllocationGreedy, TGOAGreedy),确保分配速度的同时优化分配总效用,但算法以贪心算法作为基线算法,任务的分配总效用可进一步提升;文献[7]基于当前的阈值机制,提出了一种根据任务分配情况自动调整阈值的自适应阈值算法,对比随机阈值算法提升了分配总效用,但算法阈值是从确定集合中选择,分配效用仍存在很大的提升空间;文献[8]提出一种基于统计预测的自适应阈值算法,进一步优化了分配总效用,不足是任务分配率偏低。文献[9-10]从缩短匹配距离,同时减小众包工人差旅成本入手展开研究:文献[9]提出了一种面向距离的阈值算法,旨在最小化最大的匹配距离,但实际应用中更多考虑的是平均匹配距离,因此算法缺乏实用性;文献[10]针对最小化分配总距离问题进行了综合性实验,证明了贪心算法解决这类问题时的高效性,但缺乏稳定可靠性。文献[11-12]综合考虑了分配效用和差旅成本,进行双目标优化:文献[11]提出了一种将双目标优化和多臂赌博机相结合的动态分配方法,旨在尽量减少差旅成本的前提下最大限度地提高任务的可靠性,同时提升分配效用,但没有考虑任务和工人活跃范围的限制;文献[12]提出基于二分法框架模型来最大化任务分配的数量,同时最小化差旅