Complicated-Skills-Based Task Assignment in Spatial Crowdsourcing

摘要

Spatial crowdsourcing is an activity consisting in outsourcing spatial tasks to a community of online, yet on-ground and mobile, workers. Presently an increasing number of spatial crowdsourcing applications emerges due to the related technologies tends to maturity. Distinct from traditional crowdsourcing dualistic entities, task and worker, a special kind of applications imports the third one of skill. Consequently, a novel assignment problem called multiple skills assignment problem (MSAP) is generated which extends the entity relationship from 2 to 3 dimensions. Inspired by group strategy we first propose a lightweight algorithm GMA that could achieve approximate optimal solution quickly. However, GMA exists a defect of ignoring that workers with multiple skills can decrease total travel distance significantly. Thus we propose a revised algorithm RGMA to cut down distance cost. With synthetic datasets, we empirically and comparatively evaluate the performance of the baseline and two proposed algorithms.