Clustering Based Priority Queue Algorithm for Spatial Task Assignment in Crowdsourcing
Yue Ma, Xiaofeng Gao, Shahzad Sarwar Bhatti, Guihai Chen
Abstract
Spatial crowdsourcing is an increasingly popular category in the era of mobile Internet and sharing economy, where tasks have spatio-temporal constraints and must be completed at specific locations. In this paper, we focus on <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">the</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ulti-</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">bjective</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">S</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">patio-</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">emporal task assignment (MOST) problem</i> considering the worker heterogeneity in spatial crowdsourcing and model it as a combinatorial multi-objective optimization (MOO) problem with the goals of maximizing the overall task completion rate and minimizing the average task time cost. Finding the optimal global assignment turns out to be intractable since it does not simply imply optimality for an individual worker, as a typical nearest-neighbor heuristic generally does not render a satisfactory result. We prove that the problem is NP-hard. Subsequently, we formulate an efficient algorithm for the MOST problem — <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"/> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Ta</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">sk Clustering based</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">M</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ixed</i> <bold xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">P</b> <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">riority Queue Scheduling (TAMP)</i> . First, we improve the spectral clustering algorithm to evenly divide the task network into different subdomains according to tasks' geographical locations, considering the task clustering phenomena in real scenarios. We then design a mixed priority queue strategy considering the geographical influence and temporal urgency, to schedule workers finishing tasks in sequence. Experiments on synthetic and real datasets demonstrate the efficiency of our solution over other methods.