Research On The Problem Of Spatiotemporal Crowdsourcing Dynamic Task Allocation

In recent years,with the further popularization of smart devices which carrying geographic location sensors and the leap-forward development of mobile Internet from 3G to 4G and 5G,spatiotemporal crowdsourcing technology has deeply entered people’s daily lives and is playing an increasingly important role in social development.As the core issue of spatiotemporal crowdsourcing,task allocation is one of the hotspots of spatiotemporal crowdsourcing research.However,there are some deficiencies in the existing research.First of all,for the establishment of the spatiotemporal crowdsourcing task allocation problem,on the one hand,the movement requirements of the task are often ignored,on the other hand,there are few studies on the change of supply and demand relationship in spatiotemporal crowdsourcing.Secondly,for the optimization objective of task allocation,which is often optimized for only one specific objective,while the evaluation of the task allocation effect in practical applications usually needs to consider the influence of many factors and need to achieve a variety of objectives.In view of the above two deficiencies,the main research contents of this paper are as follows:(1)By simulating an application scenario which is similar to takeout delivery and online car hailing,the problem of spatiotemporal crowdsourcing dynamic task allocation with starting and ending points(SED-SCTA)and its related concepts are defined.The problem considers the movement requirements of the task,and effectively simulates the changes of supply and demand relationship.For the SED-SCTA problem,profit first greedy task allocation(PFGTA)and task allocation method based on improved genetic algorithm(GATA)are proposed.PFGTA greedily assigns the most profitable task to the closest crowdsourced worker;however by improving the coding mechanism,population initialization,fitness evaluation,crossover and mutation operations of genetic algorithm,GATA optimizes the overall goal by using the excellent global search ability of genetic algorithm,which makes up for the deficiency of PFGTA.The comparative experiments of control variables on real datasets and synthetic datasets prove the effectiveness of the proposed methods.(2)By taking the spatio-temporal crowdsourcing task allocation problem as a multiobjective optimization problem,task allocation method based on two-objective genetic algorithm(TWGATA)and task allocation method based on three-objective genetic algorithm(THGATA)are proposed,and for the multi-objective decision making of the two methods,three optimal individual selection strategies are proposed respectively.Among them,TWGATA modifies the crossover and mutation operations on the basis of GATA,and introduces the methods of fast non-dominated sorting and crowding distance comparison in NSGA-II to optimize two valuable objectives;THGATA changes the individual selection mechanism on the basis of TWGATA,and introduces the reference point correlation method in NSGA-III to optimize three valuable objectives.A series of experiments on real datasets prove the effectiveness of the proposed methods,and the optimal individual selection strategies of the two methods are compared and analyzed separately.