Algorithms For Task Assignment And Route Planning In Spatial Crowdsourcing

The portable mobile terminals,represented by smartphones,have powerful capabilities of computing,sensing,storage,and wireless communication.With the popularity of portable mobile terminals,a new crowdsourcing mode that calls carriers of portable mobile terminals to perform tasks with Spatio-temporal characteristics has gradually emerged,which is known as spatial crowdsourcing.Spatial crowdsourcing has a wide application prospect because of its advantages of flexible working mode,low cost,and universality.At present,a large number of applications based on spatial crowdsourcing have been used in real life.A typical spatial crowdsourcing system is composed of a platform residing in the cloud and crowdsourcing users.A platform is responsible for managing users,tasks,and the spatial crowdsourcing process.Crowdsourcing users are divided into task requesters and workers according to their roles.Requesters post spatial tasks on the platform.Workers participate in completing tasks.The complexity and diversity of crowdsourcing tasks with different needs,and the different characteristics and purposes of crowdsourcing workers,make the appropriate task assignment become a vital problem.As an important factor,user satisfaction with task assignment which the results of task allocation can meet crowdsourcing users affects users’ determination to continue to use crowdsourcing applications,which in turn affects the development of crowdsourcing markets.Therefore,task allocation has become a key problem to be solved urgently in spatial crowdsourcing.Spatial crowdsourcing requires workers to move to the location of the task to complete the task.The reward and time cost of completing the task depend on the route chosen by workers.Reasonable routes considering trade-offs between rewards and costs should be planned to satisfy workers.Therefore,route planning becomes another important research topic in spatial crowdsourcing.This paper focuses on task allocation and route planning for spatial crowdsourcing.The main contributions include:First,this paper focuses on spatial task assignment with attribute preference.Although the existing work considers the effect of different attributes on task assignment goals.However,it lacks flexibility when applied to multi-objective optimization,and its performance and efficiency need to be further improved.This paper assumes that :(1)the tasks with higher budgets can select workers from a wider range;(2)The reward paid is proportional to the distance traveled.To motivate more high-quality workers to participate in the task,a reward calculation method is presented in light of the distance.Then,MultiAttribute Decision Making(MADM)model is introduced to define task allocation in spatial crowdsourcing as a MADA problem,and a new algorithm is proposed to maximize the quality of task response,and minimize the distance of task travel,meanwhile,reducing the budget utilization.With the real dataset and the synthetic dataset,extensive experiments are conducted to evaluate the performance and efficiency of the proposed algorithm.Secondly,this paper focuses on the spatial task assignment satisfying both requesters and workers.Existing task allocation methods either take the worker’s point of view or only consider the interests of the task requestor,and seldom pay attention to the expectations of both parties simultaneously.In practice,workers generally want to maximize rewards obtained and minimize costs spent.Similarly,a task requester wants the task to be responded to as soon as possible.Therefore,designing reasonable task allocation models and algorithms to meet the expectations of spatial crowdsourcing workers and minimize the waiting time of tasks is of positive significance to the development of crowdsourcing applications.This paper defines the model of delay-sensitive spatial crowdsourcing task assignment(DSTA)problem,the algorithm based on the greedy idea(DSTA-G)is proposed.Moreover,to extend the DSTA-G algorithm to large datasets,the spatial indexing technology Geohash is introduced,then the algorithm DSTA-GH is proposed.Simulation experiments have proved the superior performance of DSTA-G and DSTA-GH compared with TAW only considering the worker’s trade-off between reward and cost,and the significant improvement of DSTA-GH in task allocation efficiency.Finally,this paper focuses on route planning with a fixed start point and end point.With the available tasks and the worker with a fixed start point and end point,how to carry out reasonable route planning,so that :(1)The worker reaches the end point within the time budget;(2)The cost following the route is minimized;(3)The reward by completing the tasks located at the route is maximized.To solve the problem of route planning,an exact algorithm(EA)based on the existing research is designed and used as the baseline.The exact algorithm has a high complexity,and the existing algorithms based on K-Nearest Neighbor(KNN)and other traditional heuristics need to be further improved in accuracy.So,this paper analyzes the characteristics of the route planning problem,combining the advantages of genetic algorithm(GA)and simulated annealing algorithm(SA),and designs an approximate algorithm GA-SA to solve the problem.The performance of the proposed algorithm is verified by experiments.