空间众包中基于位置预测的任务分配

南京大学学报(自然科学版) ›› 2018, Vol. 54 ›› Issue (2): 471–.

空间众包中基于位置预测的任务分配

张　晨1，3*，郭玉超1，林培光1，2，3，任威隆1，张　森1，聂秀山1，2，3，任　可4

出版日期:2018-03-31 发布日期:2018-03-31
作者简介:1.山东财经大学计算机科学与技术学院，济南，250014；
2.山东大学计算机学院，济南，250002；
3.山东省金融信息工程技术研究中心，济南，250014；4.香港科技大学计算机与工程学院，香港，999077
基金资助:
基金项目：教育部人文社会科学研究项目(15YJAZH042)，山东省本科高校教学改革研究重点项目(2015Z058)
收稿日期：2017－12－31
*通讯联系人，E－mail：zhangchen.sdufe@gmail.com

Location prediction－based task assignment in spatial crowdsourcing

Zhang Chen1，3*，Guo Yuchao1，Lin Peiguang1，2，3，Ren Weilong1，Zhang Sen1，Nie Xiushan1，2，3，Ren Ke4

Online:2018-03-31 Published:2018-03-31
About author:1．School of Computer Science and Technology，Shandong University of Finance and Economics，Ji’nan，250014，China;
2．School of Computer Science and Technology，Shandong University，Ji’nan，250002，China；
3．Shandong Financial Information Engineering Research Center，Ji’nan，250014，China；
4．Department of Computer Science and Engineering，Hong Kong University of Science and
Technology，Hong Kong，999077，China

摘要/Abstract

摘要： 随着移动设备的普及和O2O(Online－To－Offline)商业模式的快速发展，越来越多的空间众包平台融入人们的日常生活中，例如滴滴出行、饿了么等等．空间众包中的一个核心问题是任务分配，主要研究如何将空间任务分配给合适的众包工人．任务分配方式主要分为服务器分配模式(Server Assigned Task，SAT)和用户选择模式(Worker Selected Task，WST)两种模式，目前多数统一规范化的众包服务采用SAT模式，即系统主动将任务分配给任务请求位置附近的众包工人．在此任务分配模式下，众包工人和任务之间的旅行成本变得至关重要，较少的旅行成本意味着较少的响应时间和较高的任务接受率．因此提出了基于位置预测的任务分配方式，该方式不仅考虑任务和众包工人的当前位置，还考虑未来任务可能出现的位置，从而降低旅行成本和相应时间．首先设计了贪婪方法(Greedy Approach)，然后在贪婪方法的基础上通过贝叶斯、支持向量机、决策树等方法预测未来任务的分布来辅助分配任务，最后在真实数据上进行的实验表明，该方法减小了在长时间内的总旅行成本，具有较好的性能．

Abstract: With the rapid development of mobile devices and the popularity of Online－To－Offline(O2O)business models，more and more spatial crowdsourcing platforms play a significant role in our daily life，such as DiDi taxis，Eleme meal－ordering service，etc. A core issue in spatial crowdsourcing is task assignment，which is to assign real－time tasks to suitable crowd workers. There are two types of task assignment，namely worker selected task(WST)and server assigned task(SAT). The most current unified and standardized crowdsourcing services adopt the SAT mode，by which the system proactively assigns tasks to workers in proximity of requested locations. Under this task assignment mode，the travel cost between workers and tasks becomes of vital importance，because less travel cost means less response time and higher task acceptance ratio. This paper proposes a task assignment method based on location prediction to reduce the cost and response time. This task assignment method considers not only the current location of tasks and workers，but also the locations which tasks may appear in the future. This paper proposes Greedy approach，and based on which leverages a list of methods，such as Bayes，SVM and decision－making tree，for predicting the distribution of further tasks to assist the tasks’ assignment. And the final experimentation based on the real data verifies the performance and effectiveness of the method proposed in this paper，which shortens the overall travelling cost in the long term.

张　晨1，3*，郭玉超1，林培光1，2，3，任威隆1，张　森1，聂秀山1，2，3，任　可4. 空间众包中基于位置预测的任务分配[J]. 南京大学学报(自然科学版), 2018, 54(2): 471–.

Zhang Chen1，3*，Guo Yuchao1，Lin Peiguang1，2，3，Ren Weilong1，Zhang Sen1，Nie Xiushan1，2，3，Ren Ke4. Location prediction－based task assignment in spatial crowdsourcing[J]. Journal of Nanjing University(Natural Sciences), 2018, 54(2): 471–.

参考文献

[1]　Howe J. Crowdsourcing：Why the power of the crowd is driving the future of business. New York：Crown Business，2008，336.
[2] Tong Y X，She J Y，Ding B L，et al. Online mobile Micro－Task Allocation in spatial crowdsourcing 2016 ∥ IEEE 32nd International Conference on Data Engineering(ICDE). Helsinki，Finland：IEEE，2016：49－60.
[3] 冯剑红，李国良，冯建华. 众包技术研究综述. 计算机学报，2015，38(9)：1713－1726.(Feng J H，Li G L，Feng J H. A survey on crowdsourcing. Chinese Journal of Computers，2015，38(9)：1713－1726.)
[4] Chen L，Lee D，Milo T. Data－driven crowdsourcing：Management，mining，and applications ∥ 2015 IEEE 31st International Conference on Data Engineering(ICDE). Seoul，South Korea：IEEE，2015：1527－1529.
[5] 童咏昕，袁　野，成雨蓉等. 时空众包数据管理技术研究综述. 软件学报，2017，28(1)：35－58.(Tong Y X，Yuan Y，Cheng Y R，et al. Survey on spatiotemporal crowdsourced data management techniques. Journal of Software，2017，28(1)：35－58.)
[6] 施　战，辛　煜，孙玉娥等. 基于用户可靠性的众包系统任务分配机制. 计算机应用，2017，37(9)：2449－2453.(Shi Z，Xin Y，Sun Y E，et al. Task allocation mechanism for crowdsourcing system based on reliability of users. Journal of Computer Applications，2017，37(9)：2449－2453.)
[7] Chen Z，Fu R，Zhao Z Y，et al. gMission：A general spatial crowdsourcing platform. Proceedings of the VLDB Endowment，2014，7(13)：1629－1632.
[8] Kazemi L，Shahabi C. GeoCrowd：Enabling query answering with spatial crowdsourcing ∥ Proceedings of the 20th International Conference on Advances in Geographic Information Systems. Redondo Beach，CA，USA：ACM，2012：189－198.　
[9] To H，Shahabi C，Kazemi L. A server－assigned spatial crowdsourcing framework. ACM Transactions on Spatial Algorithms and Systems，2015，1(1)：2.
[10] Hassan U U，Curry E. A multi－armed bandit approach to online spatial task assignment ∥ 2014 IEEE 11th International Conference on Ubiquitous Intelligence and Computing and 2014 IEEE 11th International Conference on Autonomic and Trusted Computing and 2014 IEEE 14th International Conference on Scalable Computing and Communications and Its Associated Workshops. Bali：IEEE，2014：212－219.
[11] Cheng P，Lian X，Chen Z，et al. Reliable diversity－based spatial crowdsourcing by moving workers. Proceedings of the VLDB Endowment，2015，8(10)：1022－1033.
[12] Li Y，Yiu M L，Xu W J. Oriented online route recommendation for spatial crowdsourcing task workers ∥ 14th International Symposium on Spatial and Temporal Databases. Hong Kong，China：Springer，2015：137－156.

[13] 宋天舒，童咏昕，王立斌等. 空间众包环境下的3类对象在线任务分配. 软件学报，2017，28(3)：611－630.(Song T S，Tong Y X，Wang L B，et al. Online task assignment for three types of objects under spatial crowdsourcing environment. Journal of Software，2017，28(3)：611－630.)
[14] Orda A，Rom R. Distributed shortest－path protocols for time－dependent networks. Distributed Computing，1996，10(1)：49－62.
[15] Yuan J，Zheng Y，Zhang C Y，et al. T－drive：Driving directions based on taxi trajectories ∥ Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems. San Jose，CA，USA：ACM，2010：99－108.
[16] Phithakkitnukoon S，Veloso M，Bento C，et al. Taxi－aware map：Identifying and predicting vacant taxis in the city ∥ 1st International Joint Conference on Ambient Intelligence. Malaga，Spain：Springer，2010：86－95.
[17] Basak D，Pal S，Patranabis D C. Support vector regression. Neural Information Processing－Letters and Reviews，2007，11(10)：203－224.
[18] Belkin M，Niyogi P，Sindhwani V. Manifold regularization：A geometric framework for learning from labeled and unlabeled examples. The Journal of Machine Learning Research，2006，7：2399－2434.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed