主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2020年专刊出版计划 微信服务介绍 最新一期:2019年第12期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
宋天舒,童咏昕,王立斌,许可.空间众包环境下的3类对象在线任务分配.软件学报,2017,28(3):611-630
空间众包环境下的3类对象在线任务分配
Online Task Assignment for Three Types of Objects under Spatial Crowdsourcing Environment
投稿时间:2016-07-31  修订日期:2016-09-14
DOI:10.13328/j.cnki.jos.005166
中文关键词:  空间众包  任务分配  在线算法  竞争比分析
英文关键词:spatial crowdsourcing  task allocation  online algorithm  competitive analysis
基金项目:国家重点基础研究发展计划(973)(2014CB340300);国家自然科学基金(61502021,71531001);软件开发环境国家重点实验室(北京航空航天大学)开放课题(SKLSDE-2016ZX-13)
作者单位E-mail
宋天舒 软件开发环境国家重点实验室(北京航空航天大学), 北京 100191  
童咏昕 软件开发环境国家重点实验室(北京航空航天大学), 北京 100191 yxtong@buaa.edu.cn 
王立斌 软件开发环境国家重点实验室(北京航空航天大学), 北京 100191  
许可 软件开发环境国家重点实验室(北京航空航天大学), 北京 100191  
摘要点击次数: 899
全文下载次数: 755
中文摘要:
      随着移动互联网技术与O2O(offline-to-online)商业模式的发展,各类空间众包平台变得日益流行,如滴滴出行、百度外卖等空间众包平台更与人们日常生活密不可分.在空间众包研究中,任务分配问题更是其核心问题之一,该问题旨在研究如何将实时出现的空间众包任务分配给适宜的众包工人.但大部分现有研究所基于的假设过强,存在两类不足:(1)现有工作通常假设基于静态场景,即,全部众包任务和众包工人的时空信息在任务分配前已完整获知,但众包任务与众包工人在实际应用中动态出现,且需实时地对其进行任务分配,因此,现存研究结果在实际应用中缺乏可行性;(2)现有研究均假设仅有两类众包参与对象,即众包任务与众包工人,而忽略了第三方众包工作地点对任务分配的影响.综上所述,为弥补上述不足,提出了一类新型动态任务分配问题,即,空间众包环境下的3类对象在线任务分配.该问题不但囊括了任务分配中的3类研究对象,即众包任务、众包工人和众包工作地点,而且关注动态环境.进而设计了随机阈值算法,给出了该算法在最差情况下的竞争比分析.采用在线学习方法进一步优化了随机阈值算法,提出自适应随机阈值算法,并证明该优化策略可逼近随机阈值算法使用不同阈值所能达到的最佳效果.最终通过在真实数据集和具有不同分布人造数据集上进行的大量实验,验证了算法的效果与性能.
英文摘要:
      With the rapid development of mobile Internet techniques and Online-to-offline (O2O) business models, various spatial crowdsourcing (SC) platforms become popular. In particular, the SC platforms, such as Didi taxi and Baidu meal-ordering service, play a significant role in people's daily life. A core issue in SC is task assignment, which is to assign real-time tasks to suitable crowd workers. Existing approaches usually are based on infeasible assumptions and have the following two drawbacks:(1) Existing methods often assume to work on the static scenarios, where the spatio-temporal information of all tasks and workers is known before the assignment is conducted. However, since both tasks and workers dynamically appear and request to be allocated in real time, therefore, existing works are impractical in real applications. (2) Existing studies usually assume that there are only two types of objects, tasks and workers, in SC and ignore the influence of workplace for task assignment. To solve the aforementioned challenges, this paper frames a novel dynamic task assignment problem, called online task assignment for three types of objects in spatial crowdsourcing, which not only includes the three types of objects, namely tasks, workers and workplaces, but also focuses on dynamic scenarios. Moreover, a random-threshold-based algorithm is designed for the new problem and a worst-case competitive analysis is provided for the algorithm. Particularly, to further optimize the algorithm, an adaptive threshold algorithm, which is always close to the best possible effectiveness of the random-threshold-based algorithm, is developed. Finally, the effectiveness and efficiency of the proposed methods are verified through extensive experiments on real dataset and synthetic datasets generated by different distributions.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利