Research On Task Location In Spatial Crowdsourcing

In recent years,many applications of spatial crowdsourcing are emerging,and the related research is also in full swing.As one of the core issues of spatial crowdsourcing,task assignment works only focus on the matching and scheduling of users and workers,and they usually assume that the locations of crowdsourcing tasks are specified by users.But this assumption is not always true.Because in many real scenarios,the specific locations of tasks need to be determined dynamically by the platform.Considering that the addresses of crowdsourcing tasks can affect the effect of task assignment and other sections,this paper proposes three different research points of spatial crowdsourcing task location based on three distinct scenarios where the task location needs to be determined by the platform.(1)Research on task location for two dimensional matching:In the scenario where tasks can be completed by multiple workers in multiple locations(such as data collection),a task location problem for 2D matching is proposed.In this problem,a batch of subtasks are put in multiple places and the total budget is split and allocated to each subtask,so that the number of workers who can form a 2D matching with any constructed subtask is the largest.After the Maximum Coverage Location Problem is reduced to this problem,three heuristic algorithms are proposed,including even clustering,uneven clustering and greedy algorithm.Finally,the effectiveness of the proposed algorithms is verified by experiments on real dataset.(2)Research on task location for three dimensional matching:In the scenario containing three objectives-worker,task location and user(such as taxi hailing),a task location problem for 3D matching is proposed.The purpose of this problem is to make workers save the most moving distance and users wait for the shortest service time by adjusting the task locations for 3D matching.According to the capacity of task locations,the original problem is transformed into bipartite maximum weight matching and tripartite maximum weight matching respectively,after which the corresponding solutions with optimization are given.Experimental results on real dataset show the effectiveness of the proposed algorithms.(3)Research on scheduling oriented task location:In the scenario where users may submit a request containing multiple tasks(such as errand service),a scheduling oriented task location problem is proposed.By finding an optimal task location sequence,we not only address each task,but also indicate the order in which the worker completes all tasks,so that the task completion order is close to the user’s expectation and the overall time consumption is short.After the Travelling Salesman Problem is reduced to the original problem,a greedy heuristic algorithm and an improved Viterbi algorithm are proposed.Experiments on real dataset show the effectiveness of the proposed methods.