面向全局优化的时空众包任务分配算法
2020-08-06聂茜婵余敦辉张兴盛
聂茜婵,张 阳,余敦辉,2*,张兴盛
(1.湖北大学计算机与信息工程学院,武汉 430062;2.湖北省教育信息化工程技术研究中心(湖北大学),武汉 430062)
(*通信作者电子邮箱yumhy@hubu.edu.cn)
0 引言
随着Web2.0 技术的兴起,大量在线Web 应用催生了众包[1-3]这种通过群体智慧求解问题的新兴商业生产模式。众包是指“一种把过去由专职员工执行的工作任务通过公开的Web 平台,以自愿的形式外包给非特定的解决方案提供者群体来完成的分布式问题求解模式”[4]。而随着智能移动设备的普及和共享经济模式的迅猛发展,赋予了众包任务更多的时空属性,衍生出一种全新的众包类型——时空众包[5-7]。时空众包是指在时空约束的条件下,将具有时空特性的众包任务分配给非特定的众包工人群体,并要求众包工人以主动或被动的方式来完成众包任务。近年来,全国流行的各类实时专车类服务平台,例如滴滴出行、Uber 等,均采用时空众包方式提供服务。而在很多线上到线下(Online-to-Offline,O2O)应用、灾情监控和物流管理等领域,也将时空众包技术运用其中以提高其服务质量。然而,现有的研究大多局限从众包平台或工人的单一角度出发进行优化,且没有满足实际应用中连续分配任务的需求。因此,本文提出一种基于预测分析的全局优化在线任务分配算法(Global Optimization online Mission Assignment algorithm based on predictive analysis,GOMA),该算法基于在线随机森林和门控循环单元网络预测出下一时间戳内众包对象(众包任务和工人)的分布情况,进而结合当前时间戳内众包对象的情况构造二分图模型,最后采用带权二分图最优匹配算法完成任务分配,从而实现众包平台、众包任务、众包工人三方综合效益的全局优化。……
