GRASP-Tabu Search Algorithms for the Route Planning Problem in Spatial Crowdsourcing

Introduction

Crowdsourcing is a generic term for a variety of approaches that exploit the capacity of large crowds by issuing calls for contributions for specific tasks. Although crowdsourcing approaches can take many different forms, today it is increasingly done via the Web, which allows interaction with a plurality of contributors from around the world. Several crowdsourcing approaches include web platforms, Well-known examples are Wikipedia, Mechanical Turk applications. In recent years, Crowdsourcing research has attracted a lot of attention in variety of fields such as IT, Geographic Information Systems, management and many other areas that have discovered crowdsourcing as a useful approach. Collaboration in a crowdsourcing process is essential to the successful resolution of problems outsourced by the company. In these times crowdsourcing has become a better approach to enhance the company's service (Amrollahi & Ahmadi, 2019).

Since the rapid growth of mobile technology, a new framework called spatial crowdsourcing which replaced traditional Web-based crowdsourcing. The spatial crowdsourcing is used to enable workers to achieve spatial tasks. Each worker is physically needed to move to the place to perform the task close to his actual positions. For instance, the companies are interested in gathering photos or videos of their products for taking statistics for sale, verifying stokes from different areas of a city.

Spatial crowdsourcing has been commonly used in numerous applications in different fields such as business intelligence (TaskRabbit, Gigwalk, and Fieldagent,) and spatiotemporal data collection (OpenStreetMap). (Fielagent, 2019; Gigwalk, 2019; OpenStreetMap, 2019; TaskRabbit, 2019).

The Spatial Crowd Sourcing Platform specifies workers to accomplish near spatial tasks that enable workers to physically move to a specific location to perform those tasks. With spatial crowdsourcing, the companies emit his request to a spatial crowdsourcing platform, as a result, the spatial crowdsourcing platform crowrdrsouces the request included in the available workers in the close tasks. Once the workers complete their nearby tasks, the outcomes will be returned to the companies. There are two major modes in spatial crowdsourcing: one is the server assign tasks, and the other is the worker select tasks (Kazemi & Shahabi, 2012).

Recently, many of spatial crowdsourcing platforms have allocated tasks to workers on the basis of the nearest worker available. The spatial crowdsourcing platform assigns the closest worker upon obtaining a spatial task.

In practice, the previous approaches have the following weaknesses:

First, it assigns tasks depending on the worker's travel distance to the task. Second, it does not take into account rewards to plan an optimal route. Third, tasks may not be assigned to suitable workers because the workers look for the nearest task through their position. In addition, despite most of the existing techniques are only available for the matching and assignment task problem, these techniques utilize a heuristic method (Tong et al, 2019), and few researchers have dealt with the route planning in spatial crowdsourcing.

To overcome these weaknesses mentioned above, in this paper, the authors study a Route Planning problem in Spatial Crowdsourcing so that the objective is to find an optimal route based on maximizing the rewards of workers, provided that the tasks must be carried out with respect of some constraints (total time and deadline). The Route Planning problem can be compared to the Orienteering Problem (OP) and its variants. Each worker should then solve a variant of the OP (Gunawan et al., 2016). How to plan routes for appropriate workers is one of the most relevant issues in spatial crowdsourcing study.

This paper's principal contribution can be summarized as follows:

• •

  The author define Route Planning problem in spatial crowdsourcing to satisfy the need of the real world to plan a route for worker in order to maximize the reward of the worker.

• •

  The authors propose an approach based on GRASP with tabu search to solve the Route Planning problem in Spatial Crowdsourcing. GRASP-Tabu algorithm’s main feature integrates the benefits of its constituent algorithms. This algorithm allows the workers to choose tasks optimally.

• •

  The authors perform extensive experiments through Solomon’s and Cordeau et al.’s instances. The experimental results indicate that the proposed algorithm is efficient and effective.