MB-GVNS: Memetic Based Bidirectional General Variable Neighborhood Search for Time-Sensitive Task Allocation in Mobile Crowd Sensing

Abstract

With the explosive growth of mobile devices, it is convenient for participants to perform mobile crowd sensing (MCS) tasks. It is a useful way to recruit participants to perform location-dependent tasks. We first investigate Min-Max Task Planning (MMTP) problem on time-sensitive MCS systems, considering time-sensitivity and heterogeneity of sensing tasks, and people-variability of the participants. Namely, how to design a cooperation method for the participants so that they spend as little time as possible. To address the MMTP problem, we propose a Memetic based Bidirectional General Variable Neighborhood Search (MB-GVNS) algorithm, in which all tasks are separated into groups and traveling path is planned for each participant. Moreover, we consider the task in both people-invariable and people-variable scenarios. Finally, extensive experiments are conducted to demonstrate the benefits of our method, outperforming other similar state-of-the-art algorithms.