Research on incentive strategy based on service quality in spatial crowdsourcing task allocation

Abstract

In order to further improve the enthusiasm of spatial crowdsourcing workers, considering the service quality of workers, different incentive strategies are proposed and tasks are assigned. Firstly, the incentive model is constructed from the unit time revenue of task and online idle time, and the evaluation function of the evaluation model is constructed; Secondly, the task allocation is transformed into a combinatorial optimization problem by delay matching, and an improved glowworm swarm algorithm is proposed to solve the problem by discrete coding, introducing six kinds of mobile modes, adaptive probability matching and infeasible solution processing; Finally, the algorithm is used to solve the task allocation. The experimental results show that compared with the travel cost minimization strategy and random allocation strategy, the positive incentive index of the proposed strategy is improved by 11.79% and 14.60% respectively, and the fair incentive index is improved by 0.83% and 0.22% respectively, which can effectively improve the positive incentive range and incentive fairness of workers.

Keywords

Spatial crowdsourcing service quality task assignment glowworm swarm algorithm

1 Introduction

With the continuous development and application of the Internet, smartphones and GPS terminal products, spatial crowdsourcing has emerged and now extensively employed. It has developed more and more mature in our daily life, such as taxi, food take-out, logistics and so on. Spatial crowdsourcing requires one or more workers to respond to the platform within a certain time, and to complete the corresponding tasks at the designated place at the specified time. The platform will allocate the corresponding benefits to the workers after the task is completed [1]. For example, Uber, Didi taxi and Meituan Takeaway, all of them have a high popularity and are widely used in spatial crowdsourcing [2].

At present, the main research fields of spatial crowdsourcing include task allocation, incentive mechanism, quality management and privacy protection [1]. Among them, task allocation is the core of spatial crowdsourcing research, because task allocation is the basis of other research, and ultimately affects the income of workers and users’ sense of experience. The incentive mechanism primarily addresses the incentive to employees and investigates ways to entice additional workers to join the platform while also improving the quality and enthusiasm of their work.

The goals of task allocation generally include maximizing the number of tasks allocated, and minimizing the travel cost of task allocation [3 –6]. Location entropy is used to express the number of workers near the location, and prioritize fewer tasks with workers nearby, boosting the number of tasks allocated [3]. Region entropy is used to represent the number of workers in a certain space, which makes less region entropy have higher allocation priority, and the Greedy algorithm is used to solve the problem [4]. A new algorithm of adaptive model cost based on the Greedy algorithm is proposed under the condition of limited budget and a task requiring specific skills [5]. Tasks are randomly assigned to nearest neighbor workers to save travel expenses [6].

Incentive mechanism is generally studied from two aspects: pricing model and incentive model. The pricing model literature is as follows: Dynamic pricing which has been applied in Uber, taking higher price in areas with more passengers to attract workers to participate [7, 8]. A dynamic pricing method based on single threshold [9]. If the number of workers is greater than the threshold, the lower one will be chosen. Markov chain decision-making process is used, which takes into account factors such as driver direction and time, and it is solved with a polynomial-time algorithm [10]. Workers’ reputation is divided into high, medium and low. Those with a good reputation are rewarded well, whereas workers with a bad reputation are not rewarded at all and are gradually phased out [11]. The incentive model literature is as follows, when designers receive a remote task, they should pay the remote subsidies which below a certain threshold to the workers to motivate them [12]. Workers are encouraged to speed up task response by adaptive pricing, and they will get less reward [13]. In an auction pricing model, the workers who participate in the bidding platform shall decide the final allocation according to the quotation [14]. A dual pricing model means that workers and users offer auction prices respectively, the system matches it optimally as expected by both parties [15].

Most of the existing tasks are allocated by using Greedy algorithms, which are locally optimal solutions but do not obtain better solutions globally. Existing incentive-based task allocation typically accounts from pricing and subsidy methods, and most consider task gains rather than real gains per unit time, nor the waiting time of the next task at the end of the task. Although higher pricing can motivate workers, it will reduce the users’ sense of experience. In addition, the auction model takes into account the pricing model with the participation of different market or regional workers, which has low robustness in different regions, it doesn’t have wide applicability in various regions.

Intelligent optimization algorithm is the important algorithm to solve combinatorial optimization problems in recent years, which mainly include particle swarm optimization algorithm (PSO) [16], ant colony algorithm (ACA) [17], artificial bee colony algorithm (ABC) [18], glowworm swarm optimization algorithm (GSO) [19] and so on. The GSO algorithm has the characteristics of few parameters, simple process and easy implementation [19]. From the mechanism of GSO, the attraction between glowworms is inversely proportional to the generate multiple subgroups, and acquire the ability to deal with multiple extreme values. By setting parameters such as the individual perception radius of the algorithm, it can adjust the algorithm form and adapt to the specific problem solving ability [20]. As it has fast operation speed and better optimization ability in multi-dimensional space, so it can get better solutions in different scale datasets and multidimensional data. The glowworm swarm optimization algorithm (GSO) was first proposed in the paper [19], and the firefly algorithm (FA) was first proposed in the paper [21]. The two algorithms have similar principles and slightly different formulas and steps. This paper selects GSO algorithm to solve the problem. But the GSO algorithm converges prematurely and only applies to continuous functions. The discrete GSO algorithm usually improves the performance of the algorithm from coding [20 , 23], mobile mode [20, 24], variable step [25, 26] and other aspects.

To sum up, the existing incentive strategies for spatial crowdsourcing task allocation mainly adopt dynamic pricing and auction, etc., and the income index usually used to measure is not considering the income per unit time or online idle time, so it is not the real income. In addition, existing studies lack strategies to transform workers’ service quality into competitive advantages in each task assignment, which is conducive to improving workers’ enthusiasm and service quality. This paper makes a supplement to the existing research, and its main contributions include the following aspects:

Constructing a worker incentive strategy based on service quality, designing two incentive strategies from two perspectives of revenue per unit time and online idle time. In each task assignment, it can play a quantitative incentive role according to the level of service quality of workers

Two new evaluation functions, positive motivation index and fair motivation index, are constructed to evaluate the scope and fairness of worker motivation.

An IGSO (Improved glowworm swarm) algorithm is proposed and experimentally compared with other similar algorithms on different datasets, IGSO algorithm has better convergence and stability.

The IGSO-ISSCTA (Improved glowworm swarm algorithm on space crowdsourcing task allocation from incentive strategy) is proposed to solve the task assignment under the worker incentive policy with the improved glowworm swarm algorithm, which transforms the spatial crowdsourcing task assignment into a combinatorial optimization problem through the delayed matching approach.

Through doing experiments on different datasets, the evaluation function values and benefit values of task assignment under different incentive strategies are calculated to verify that the strategy in this paper can incentivize workers more extensively and fairly when compared to the travel cost minimization strategy and the random assignment strategy.

2 Task allocation model based on service quality incentive

2.1 Model definition

The research scenario hypothesis model meets the following preconditions: (1) Only online spatial crowdsourcing workers can receive task assignments. (2) The workers who are in the process of completing the task and cannot receive new tasks. (3) The server cannot be changed after task assignment. (4) The server only considers tasks that existed online at the time, and tasks are considered to exist online from the stage when they start to be posted until the deadline. (5) Suppose that the task income is proportional to the distance, see definition 2 for details. The definitions of model related concepts are as follows:

Definition 1. Spatiotemporal Unit: The area R is divided equally into N squares, each square within time T forms spatial-temporal unit k, $k = (R, T ρ_{k}^{w}, ρ_{k}^{u}, pn)$ , $ρ_{k}^{w}$ means the density of workers in spatial-temporal unit k, $ρ_{k}^{u}$ means the density of users in spatial-temporal unit k, pn_k denoting the ratio of supply to demand in spatiotemporal unit k, ${pn}_{k} = ρ_{k}^{w} / ρ_{k}^{u}$ .

Definition 2. Spatial crowdsourcing task [1]: The spatial crowdsourcing task is published by users, u = (bl_u, ol_u, t_u, r_u, de_u), bl_u means the starting position of task u, ol_u means the end position of task u, t_u means the start time and end interval of task u, r_u means the task return, which is usually in a positive proportion to the distance size, r_u = dis (ol_u, bl_u) * α, α means the price coefficient, de_u means the traffic congestion coefficient from the starting point to the end of the task.

Definition 3. Spatial crowdsourcing Worker [1]: w = (l_w, c_w, v_w, z_w), l_w means the current position of worker W, c_w means the current status of worker (whether online, whether completing the task, etc.), v_w means the average driving speed of worker, z_w means the service quality of worker.

Definition 4. Service Quality of Worker [21]: The service quality of workers is composed of the historical service quality of workers and the users’ evaluation after each new task is completed. z_w = (zh_w, zn_w, zhwe_w, znwe_w),.zh_w means the score of the historical service quality of workers, zn_w means the score of the service quality of workers completing new tasks, zhwe_w means the weight of historical service orders of workers in the total tasks, znwe_w means the weight of new tasks to the total number of task, z_w = zh_w * zhwe_w + zn_w * znwe_w.

Definition 5. The Unit Time Income:

Task revenue per unit time is allocated by task corresponding to unit time, ets_uw = r_u/t_uw. Task allocation revenue takes service quality into consideration, t_uw means wasting time for workers to complete corresponding tasks.

Definition 6. Online Idle Time: The waiting time between completion of a task and the next task of the online state workers. The online idle time of the worker belongs to a spatiotemporal unit k expressed as odt_w = (l_w, c_w, k). If the worker reaches the end of the task belonging to the unit k, and the online idle time is t_c when the task supply-demand ratio of unit k is 1, so.

2.2 Construction of incentive model

(1) Strategy 1 Considering the impact of traffic congestion and unit time benefit of the task $max {ZETS}_{uw} = \sum_{i = 1}^{m} \sum_{j_{1}}^{j_{m}} {zets}_{{uw}_{i}}$ (1) $min L_{uw} = \sum_{i = 1}^{m} \sum_{j_{1}}^{j_{m}} l_{{uw}_{i}}$ (2)

S. t. $\begin{matrix} I = {i | i = 1, 2, . . ., m}; J_{I} = {j | j = j_{1}, . . ., j_{i}, . . ., j_{m}} \\ {zets}_{{uw}_{i}} = r_{u_{i}} * z_{w_{ji}} \div (dis ({bl}_{u_{i}}, {ol}_{u_{i}}) / (v_{w_{ji}} / {de}_{u_{i}})) \\ \forall i \in I, \forall j \in J_{I} \\ r_{u_{i}} = {\begin{matrix} r_{c}, dis ({bl}_{u_{i}}, {ol}_{u_{i}}) ⩽ d_{c} \\ r_{c} + dis ({bl}_{u_{i}}, {ol}_{u_{i}}) * α, dis ({bl}_{u_{i}}, {ol}_{u_{i}}) > d_{c} \end{matrix}, \forall i \in I \\ l_{{uw}_{i}} = dis ({bl}_{u_{i}}, l_{w_{j_{i}}}),, \forall i \in I, \forall j \in J_{I} \\ {zh}_{w_{ji}} \in [0, R^{+}), v_{w_{ji}} \in R^{+}, {de}_{u_{i}} \in R^{+}, r_{c} = c_{1}, c_{1} \in R^{+} \\ c_{w_{j_{i}}} = {0, 1}, \forall i \in I, \forall j \in J_{I} \\ α \in R^{+}, d_{c} \in R^{+}, {bl}_{u_{i}} \in R, {ol}_{u_{i}} \in R, l_{w_{ji}} \in R \end{matrix}$ (3)

The task reward usually has a fixed starting price within the basic mileage in daily life. After exceeding the basic mileage, it generally increases in positive proportion with the increase of distance. For example, the return of Didi express is closely related to mileage. However, each task is affected by the traffic congestion in a different time and space environment, and the actual time consumption is quite different.

Combined with the starting point and endpoint of the task and the corresponding task release time, different tasks correspond to different traffic congestion factors. By retrieving the real-time data of the traffic congestion factor, the time consumed to complete the task can be estimated, so that workers with higher service quality can obtain tasks with higher revenue per unit time as much as possible. In spatial crowdsourcing task allocation, the travel cost of workers arriving at the mission site is usually considered. The optimization objectives of strategy 1 are such as the Equations (3).

The Equation (1) means the maximum value of the total revenue per unit time. The Equation (2) means the minimum value of the total travel cost corresponding to the matching of all tasks and workers in a task allocation.The Equation (3) represents the set of users and corresponding workers, unit time income including service quality score weight, worker income, the calculation formulas of the distance of worker and task, and the value range of relevant variables (introduced in the model definition) in turn. Among them, c_w = 0 means that the worker is not online or is completing the task and cannot receive the task assignment, and c_w = 1 means that the worker is online and idle so they can accept the task assignment.

(2) Strategy 2 Considering the online idle time at the end of the task

In real life, workers tend to work in areas with a shorter waiting time. Even if the current task returns are higher, but the probability of receiving orders at the end point is low, then workers’ willingness to receive orders will be lower. Within a spatiotemporal unit, the relative number of tasks and workers will determine the average waiting time of tasks. The more tasks and the fewer workers lead to the greater the supply-demand ratio, and the expectation of average waiting time of task allocation will be shorter. According to the current task allocation time and the traffic congestion coefficient, the estimated arrival time can be calculated. At present, some scholars predict the occurrence of future workers and tasks based on the historical data through deep learning [27]. According to the predicted supply-demand ratio, the expected online idle time can be calculated. The online idle time of the end of the task is considered in the current task assignment. The worker who has higher service quality are assigned the task of shorter the online idle time, so they can accept more tasks at the same time. The optimization objectives of strategy 2 are as follows: $min {ZODT}_{uw} = \sum_{i = 1}^{m} \sum_{j_{1}}^{j_{m}} {zodt}_{u_{w_{i}}}$ (4) $min L_{uw} = \sum_{i = 1}^{m} \sum_{j_{1}}^{j_{i}} l_{{uw}_{i}}$ (5)

s. t.

${\begin{cases} z o d t_{w_{j i}} = t_{c} / p n_{k_{i}} * z_{w j i}, \forall i \in I, \forall j \in J_{I} \\ p n_{k i} = ρ_{k_{i}}^{u_{i}} / ρ_{k_{i}}^{w_{i}}, \forall i \in I, \forall j \in J_{I} \\ t_{c} = c_{2}, c_{2} \in R^{+}, z_{w} \in [0, R^{+}) \\ ρ_{u i} \in R^{+}, ρ_{w i} \in R^{+} \end{cases}$ (6)

The Equation (4) means the minimum value of the total online idle time. The Equation (5) means the minimum value of the total travel cost of all tasks and workers in a task assignment.The Equation (6) is the formula for calculating the online idle time with the weight of service quality score and the corresponding supply-demand ratio at the end of a task. The range of related variables are shown in Equation (3).

2.3 Two evaluation indexes

Two evaluation indexes, the positive incentive index and the fair incentive index, are constructed to evaluate the effect of incentive strategies from the perspectives of coverage and fairness.

(1) Positive incentive index

It is used to measure the coverage of positive incentive workers in the matching result of a task assignment. Specifically, it refers to the result of each assignment. After the descending order of the service quality score of workers, the income of two adjacent tasks is compared to observe whether the workers with higher service quality scores get more income. As shown in Equation (7). $corins = \frac{\sum_{i = 1}^{m - 1} {cor}_{i}}{m - 1}; {cor}_{i} = {\begin{matrix} 1, z_{{ets}_{i}} ⩾ z_{{ets}_{i + 1}} \\ 0, z_{{ets}_{i}} < z_{{ets}_{i + 1}} \end{matrix}$ (7)

As shown in Table 1, in one task assignment, a total of 6 workers and task combinations are formed. After the assignment, they are ranked in descending order according to the score of service quality. If the workers in order 1, 3 and 4 are greater than the adjacent 2, 4 and 5 respectively, they are counted as three positive incentives, with a total of 5 comparison times. According to Equation (7), the positive incentive index is 0.6.

Table 1

Calculation example of incentive index

Income	1	2	3	4	5	6
z _w	0.9	0.8	0.7	0.6	0.5	0.4
zets _uw	9	8.8	9.1	9	5.5	7.2
ets _uw	10	11	13	15	11	18

(2) Fair incentive index

Worker quality of service scores is not the same. In order to motivate workers and consider fairness, the improved Gini coefficient is introduced as the evaluation index to measure the fairness of incentive strategies.

Gini coefficient is the coefficient used to measure the inequality of social income distribution in economics developed by economist Gini on the basis of Lorentz curve [28]. The smaller the Gini coefficient g is, the higher the degree of fairness is; The greater the Gini coefficient, the lower the degree of fairness. The area between the Lorenz curve and the absolute equality line of income distribution is called unequal distribution area (area A); The area between the Lorenz curve and the absolute inequality line of income distribution is called the actual distribution area (area B), and the ratio of the two is Gini coefficient G. There are many calculation methods for Gini coefficient, and there is a certain error with the change of M. Equation (8) can obtain the approximate value with higher accuracy [28, 29]. The fair incentive index gins are as follows: Equations (9) $gins \approx 1 - \frac{2}{m} \sum_{i = 1}^{m - 1} W_{i} - \frac{3 + W_{1} + W_{n - 1}}{4 m}$ (8) $W_{i} = {zets}_{{uw}_{i}} / \sum_{i = 1}^{m} {zets}_{{uw}_{i}}$ (9)

Under the fair incentive strategy, workers with higher service quality scores get a higher proportion of income. After dividing the unit time income and work quality score, the unit time income corresponding to each unit service quality score is obtained, as shown in Equation (9). In Table 1, the corresponding fair incentive index is 0.548 by calculation with z_w and 0.642 by calculation with zets_uw. Thus, the results calculated with z_w are higher than those calculated by zets_uw, which shows that the distribution is more unfair.

3 The IGSO-ISSCTA method

When spatial crowdsourcing tasks are assigned, workers and tasks appear in real-time at any location in space, with a great deal of randomness. If you do a real-time allocation, you can’t change the allocation after the allocation, making it difficult to achieve high allocation efficiency. The “delayed matching” strategy [30] can be used to improve the allocation efficiency and profitability. The specific idea is that after waiting for a certain length of time stamp, the set of tasks that have not reached the deadline in a spatial unit and the set of online workers are matched with each other to find a better allocation result. If there are m workers and n tasks in a spatiotemporal unit k (if m ⩾ n), each assignment forms a number of combinations as $C_{m}^{n} * m!$ , which are NP-hard problems [24, 25], and the swarm intelligence optimization algorithm is applied to find the better solution. In this paper, we use the improved IGSO algorithm to solve.

3.1 GSO algorithm and improvement

3.1.1 GSO algorithm

GSO algorithm has fluorescein update, selection of movement direction, position update, decision domain update and other stages. The fluorescein corresponds to the objective function, thus combining the algorithm with the objective optimization, as follows: $l_{i} (t) = (1 - ρ) l_{i} (t - 1) + γ J (x_{i} (t))$ (10) $N_{i} (t) = {j : ∥ x_{j} (t) - x_{i} (t) ∥ < r_{d}^{i} (t); l_{i} (t) < l_{j} (t)}$ (11) $ρ_{ij} (t) = \frac{l_{j} (t) - l_{i} (t)}{\sum_{k \in N_{i} (t)} l_{k} (t) - l_{i} (t)}$ (12) $x_{i} (t + 1) = x_{i} (t) + s (\frac{x_{j} (t) - x_{i} (t)}{∥ x_{j} (t) - x_{i} (t) ∥})$ (13) $r_{d}^{i} (t + 1) = min {r_{s}, max {0, r_{d}^{i} (t) + β (n_{t} - | N_{i} (t) |)}}$ (14)

Of which, l_i (t) is fluorescein, ρ is the volatilization coefficient of fluorescein, γ represent respectively enhancement of fluorescein coefficients, J (x_i (t)) represent objective function values; N_i (t) is the set formed by glowworms at the t iteration in the decision domain, which are brighter than glowworms, ρ_ij (t) represents the probability of the current glowworm x_i moving to a brighter glowworm x_j; is the perception radius coefficient, is the threshold for the number of fireflies in neighborhoods, and is the sensing radius.

3.1.2 The steps of the IGSO algorithm

The discrete glowworm algorithm is improved from the aspects of initial coding, introducing six movement modes, adaptive probability matching and infeasible solution processing to make it be suitable for task allocation applications.

Step 1 Discrete coding and decoding

The initial solution is encoded as follows: Subscripts of each dimension represent the number of users, numbers on each dimension represent worker number, such as [2 5 6] indicates worker 2 service user 1, worker 5 service user 2, worker 6 service user 3, and so on.

Step 2 Six movement strategies

For the purpose of ensuring multivariate optimization of glowworm I, in addition to the algorithm’s moving strategy, a set of six modes of movement were developed, including exchange, two adjacent transformations, inversion, random reservation and reverse learning. According to the Table 2, assuming that the 2nd and 7th dimensions of the original glowworm i move, six different strategies are used to get the corresponding new location. Among them, exchange, left-adjacent transformation and right-adjacent transformation are local moves, inversion, random reservation and reverse learning are large-scale moves.

Table 2
Examples of six movement strategies

Movement style The values of each dimension of glowworm i

Glowworm i 4 3 6 8 1 2 5 7

Exchange [25] 4 5 6 8 1 2 3 7

Left-adjacent transformation 3 4 6 8 1 5 2 7

Right-adjacent transformation 4 6 3 8 1 2 7 5

Inversion [25] 4 5 2 1 8 6 3 7

Insertion [25] 4 6 8 1 2 5 7 3

Reverse learning [24] 5 6 3 1 8 7 4 2

Movement style	The values of each dimension of glowworm i
Glowworm i	4	3	6	8	1	2	5	7
Exchange [25]	4	5	6	8	1	2	3	7
Left-adjacent transformation	3	4	6	8	1	5	2	7
Right-adjacent transformation	4	6	3	8	1	2	7	5
Inversion [25]	4	5	2	1	8	6	3	7
Insertion [25]	4	6	8	1	2	5	7	3
Reverse learning [24]	5	6	3	1	8	7	4	2

Step 3 Adaptive probability matching

In order to select the mobile mode better and improve the optimization ability of the algorithm, the adaptive probability matching strategy is introduced to select the mobile mode [31], the details are shown in Equation (15): $q_{g} (t + 1) = q_{g} (t) + h * [r_{g} (t) - q_{g} (t)]$ (15)

represents the recent performance of the g mobile mode, is adaptation rate, represents the contribution of the nth mobile mode in the t generation. In order to keep the convergence rate of the algorithm, the probability matching is updated once every 10 iterations, the probability of using the moving mode g is as Equation (16): $p_{g} (t + 1) = p_{min} + (1 - S * p_{min}) * \frac{q_{g} (t + 1)}{\sum_{n = 1}^{N} q_{g} (t + 1)}$ (16)

Step 4 Distance of discrete glowworms

Measure step length through using Hamming distance, suppose that glowworm and glowworm have the same value in the dimension, is recorded as 0, different is recorded as 1, the sum of the values on each dimension of the glowworms is the distance between the two glowworms, see Equations 17 18 for details, of which. $dis tan ce (i, j)_{h} = {\begin{matrix} 0, x_{i}^{h} = x_{j}^{h} \\ 1, x_{i}^{h} \neq x_{j}^{h} \end{matrix}$ (17)

$dis tan ce (i, j) = \sum_{h = 1}^{m} | dis tan ce (i, j)_{h} |$ (18)

Step 5 Not feasible for solving

As shown in Table 3, glowworm flies toward glowworm, which has a better neighborhood, and converges in dimensions 1 and 4, when dimensions 1 and 5 are both 1 and dimensions 4 and 8 are both 7. The scenario application is that each worker can only serve a certain user at the same time, so this is not a feasible solution. The processing is to keep the 1st and 4th dimensions after the change of glowworm, and regenerate the non-repeating numbers in the duplicated 5th and 8th dimensions.

Table 3

Moving treatment of infeasible solutions

Glowworm	Glowworm values for each dimension
Glowworm	4	3	6	8	1	2	5	7
Glowworm	1	3	5	7	2	4	6	8
Glowworm after moving	1	3	6	7	1	2	5	7
After processing	1	3	6	7	4	2	5	8

3.2 IGSO-ISSCTA algorithm overall solution

3.2.1 IGSO-ISSCTA algorithm objective function

The objective functions of strategy 1, strategy 2 and strategy 3 are shown in Equations (20), respectively. Where are the coefficients that let the two parts of the data in the objective function out of a uniform measure are the parameters that reflect the importance of the dual objectives in the objective function. Equation (19) is the optimal maximum value, and Equation (20) is the optimal minimum value. $F_{1} (I, J_{I}) = c_{1} * r_{1} * {ZETS}_{uw} - c_{2} * r_{2} * L_{uw}$ (19) $F_{2} (I, J_{I}) = c_{1} * r_{1} * {ZOTS}_{uw} + c_{2} * r_{2} * L_{uw}$ (20)

3.2.2 IGSO-ISSCTA algorithm

As shown in Fig. 1, the IGSO-ISSCTA algorithm consists of the ISSCTA model and the IGSO algorithm in the following steps.

Fig. 1

IGSO-ISSCTA framework.

Step 1 Traffic data pre-processing includes patio-temporal cell segmentation and normalization of data, which is mapped to the specified spatiotemporal cell;

Step 2 Divide the given space-time into space-time units, and give a unique number to the users and workers in each space-time unit;

Step 3 According to the coding rules, initialize the glowworm population, update the population fluorescein, and calculate the value of the objective function corresponding to different incentive strategies;

Step 4 The glowworm swarm is guided by the learning factor parameters and chooses to move towards the brightest glowworm in the neighborhood or according to six improved adaptive probability matching strategies;

Step 5 Solve the objective function according to the incentive strategy, and continuously update the solution space according to the objective function;

Step 6 Check the new solution after the move, checking and processing the infeasible solution;

Step 7 Compare the objective function value with the bulletin board, and if better, replace the bulletin board value;

Step 8 Check whether the termination conditions are met, and if so, output the task assignment plan to motivate the worker.

3.2.3 IGSO-ISSCTA complexity analysis

Suppose the size of the population is m, number of users is m, and number of workers is m₁ (assuming m > n). The number of matches is m, each glowworm (m dimensions) represents one task assignment, and the maximum number of iterations is t. The initialization IGSO population time complexity is O(n), and the utility time complexity for calculating the task assignment strategy for one incentive worker is O(m), so the total task assignment time complexity is O(n*m) in each iteration; The time complexity of calculating the distance between firefly individuals in each iteration is O(m); Although there are a variety of ways to move, choose the most ways to move when each dimension is moved, the maximum time complexity of calculating the individual movement of glowworms in each iteration is O(n*m), IGSO-ISSCTA algorithm time complexity is O(n*m*t). The initialized IGSO algorithm population space complexity is $O (C_{m}^{n} * m)$ , and the space complexity corresponding to matching and position update in each task assignment is O(m), so this IGSO-ISSCTA space complexity is $O (C_{m}^{n} * m)$ .

4 Experiment and analysis

4.1 Experiment and data description

(1) Data description

The experiment was done in Matlab R2021a with PC parameters of system Windows 10, RAM (16 G), CPU Intel(R) Core (TM) i5-10600 (4.1 GHz). IGSO parameters, IGSO-ISSCTA parameters, and datasets as detailed in Table 4. The first two parts of the parameters are the IGSO algorithm parameters, referring to the corresponding literature and parameter experiments, respectively, and the constants are the coefficients in the objective function of the IGSO algorithm, and this paper focuses on worker excitation, so takes a larger value.

Table 4
Experimental data explanation

Parameter Type Specific parameters Values Sources

IGSO algorithm ρ, γ, β, η ρ = 0.4 γ = 0.6 β = 0.08 n = 20 Literature [20, 21]

r_s, n_t, s_c r_s = 30 n_t = 8 s_c = 0.8 Parameter experiment

c₁, c₂, r₁, r₂ c₁ = 10 c₂ = 1 r₁ = 0.95 r₂ = 0.05 Constants

Data set and size D ₁ (dataset1 dataset5), m₁=(10,20,30,40,50) Randomly generated

D ₂ (dataset6 dataset10), m₂= (100,500,1000,2000,4000) Synthesis

IGSO-ISSCTA algorithm Pn pn ∈ [0.5, 2] Real data mapping

v_w, z_w v_w ∈ [1, 1.2] z_w ∈ (0, 100) Randomly generated

l_w, bl_u, ol_u, de_u l_w ∈ (0, 1000) bl_u ∈ [0, 1000] ol_u ∈ [0, 1000] de_u ∈ [0.5, 2] Real data mapping

α = 0.05 t_c = 50 r_c = 10 d_c = 200 Constants

Parameter Type	Specific parameters	Values	Sources
IGSO algorithm	ρ, γ, β, η	ρ = 0.4 γ = 0.6 β = 0.08 n = 20	Literature [20, 21]
	r_s, n_t, s_c	r_s = 30 n_t = 8 s_c = 0.8	Parameter experiment
	c₁, c₂, r₁, r₂	c₁ = 10 c₂ = 1 r₁ = 0.95 r₂ = 0.05	Constants
Data set and size	D ₁	(dataset1 dataset5), m₁=(10,20,30,40,50)	Randomly generated
	D ₂	(dataset6 dataset10), m₂= (100,500,1000,2000,4000)	Synthesis
IGSO-ISSCTA algorithm	Pn	pn ∈ [0.5, 2]	Real data mapping
	v_w, z_w	v_w ∈ [1, 1.2] z_w ∈ (0, 100)	Randomly generated
	l_w, bl_u, ol_u, de_u	l_w ∈ (0, 1000) bl_u ∈ [0, 1000] ol_u ∈ [0, 1000] de_u ∈ [0.5, 2]	Real data mapping
		α = 0.05 t_c = 50 r_c = 10 d_c = 200	Constants

There are two data sets, D₁ and D₂. D₁ is the simulated data set, each data in D₁ is randomly generated in the range of values, the size of the simulated data set is small; D₂ is a synthetic data set, using the cab trajectory of Shanghai on February 20, 2007 provided by literature [32], containing ID, time, latitude and longitude data, etc. 4316 in total; The traffic congestion index is obtained from the dataset [33] of traffic congestion coefficients for May 29, 2021 for each region of Shanghai from Baidu Maps Smart Traffic, with a total of 4208, The other datasets are randomly generated within the definition, and the first 4000 data are taken to synthesize the dataset. IGSO-ISSCTA algorithm contains multiple data. Data of location, traffic congestion coefficient, etc. They are mapped to the corresponding intervals with real data. Speed, service quality score, supply-demand ratio and other data are randomly generated, the starting price and default online idle time are taken as constants.

(2) Experimental description

The experiment is divided into 3 parts. Part 1 experiments validate the effectiveness of the two incentive strategies and compare them with two commonly used allocation strategies. The validation of the effectiveness of strategy introduces the cumulative earnings of two workers in addition to comparing the evaluation index of one allocation to illustrate the effectiveness and fairness of the incentive strategy at macro and micro levels. The second part of the experiment mainly compares the performance of the IGSO algorithm with the other three similar algorithms, including the results of the objective function search on different data sets, the effect of different movement methods and their combination on the performance and parameter experiments. The third part of the experiment involves solving the final result and comparing it to other algorithms in a big data scenario that is relevant to real-world applications.

Strategy 3 [6] targets the total cost of travel of per allocation and Strategy 4 is a randomly selected strategy. Strategy 3 is the most commonly used optimization goal in the current research on spatial crowd-sourcing task allocation, while Strategy 4 is the most commonly used strategy in daily life. Therefore, these two strategies are selected as comparative strategies. In the comparison experiment, the same improved GSO algorithm and data are used to obtain different allocation schemes by using these two objective functions and the objective function of the strategy in this paper. Then the evaluation function is calculated and compared to obtain the incentive results of different strategies for workers.

4.2 Validation of the effectiveness of the motivation strategy

4.2.1 Validation of strategy 1

As shown in Table 5, from the positive incentive indices obtained on the five datasets on D₁, it can be seen that the mean value of the positive incentive indices obtained from strategy 1 is always greater than that of strategies 3 and 4, indicating that strategy 1 can play a positive incentive role to a greater extent, so that more workers with high service quality can be assigned tasks with higher returns per unit of time. The standard deviations corresponding to strategy 1 are smaller than those of strategies 3 and 4, indicating that strategy 1 has better stability of the positive incentive index corresponding to task assignment. On the datasets dateset1, dateset2, dateset4 and dateset5, the optimal values of strategy 1 are better than those of strategy 3 and 4, indicating that strategy 1 can find a larger range of positive incentives for the task assignment scheme.

Table 5
Calculation results of strategy 1 and comparison strategies on D₁

Dataset Strategy index Positive incentive index Fair incentive index

Strategy 1 Strategy 3 Strategy 4 Strategy 1 Strategy 3 Strategy 4

dataset1 Mean value 0.8388 0.6444 0.5833 0.7328 0.7623 0.7393

Optimum value 1.0000 0.8889 0.7778 0.7189 0.7239 0.7204

Standard deviation 0.1082 0.1144 0.1104 0.0211 0.0279 0.0121

dataset2 Mean value 0.6737 0.5737 0.5556 0.8650 0.8691 0.8660

Optimum value 0.7368 0.6842 0.6667 0.8612 0.8634 0.8618

Standard deviation 0.0488 0.0642 0.0786 0.0024 0.0065 0.0039

dataset3 Mean value 0.6069 0.5759 0.5552 0.9102 0.9110 0.9107

Optimum value 0.7241 0.6897 0.6897 0.9167 0.9166 0.9172

Standard deviation 0.0527 0.0557 0.0544 0.0017 0.0026 0.0025

dataset4 Mean value 0.5064 0.4974 0.4974 0.9314 0.9331 0.9325

Optimum value 0.5897 0.6154 0.5128 0.9318 0.9665 0.9662

Standard deviation 0.0396 0.0496 0.0440 0.0002 0.0077 0.0079

dataset5 Mean value 0.5235 0.4867 0.4980 0.9446 0.9448 0.9452

Optimum value 0.5918 0.5714 0.5714 0.9417 0.9419 0.9450

Standard deviation 0.0361 0.0410 0.0373 0.0012 0.0011 0.0014

Dataset Strategy index		Positive incentive index	Fair incentive index
dataset1	Mean value	0.8388	0.6444	0.5833	0.7328	0.7623	0.7393
	Optimum value	1.0000	0.8889	0.7778	0.7189	0.7239	0.7204
	Standard deviation	0.1082	0.1144	0.1104	0.0211	0.0279	0.0121
dataset2	Mean value	0.6737	0.5737	0.5556	0.8650	0.8691	0.8660
	Optimum value	0.7368	0.6842	0.6667	0.8612	0.8634	0.8618
	Standard deviation	0.0488	0.0642	0.0786	0.0024	0.0065	0.0039
dataset3	Mean value	0.6069	0.5759	0.5552	0.9102	0.9110	0.9107
	Optimum value	0.7241	0.6897	0.6897	0.9167	0.9166	0.9172
	Standard deviation	0.0527	0.0557	0.0544	0.0017	0.0026	0.0025
dataset4	Mean value	0.5064	0.4974	0.4974	0.9314	0.9331	0.9325
	Optimum value	0.5897	0.6154	0.5128	0.9318	0.9665	0.9662
	Standard deviation	0.0396	0.0496	0.0440	0.0002	0.0077	0.0079
dataset5	Mean value	0.5235	0.4867	0.4980	0.9446	0.9448	0.9452
	Optimum value	0.5918	0.5714	0.5714	0.9417	0.9419	0.9450
	Standard deviation	0.0361	0.0410	0.0373	0.0012	0.0011	0.0014

From the fair incentive indices obtained on the five datasets, it is clear that overall strategy 1 achieves better results than strategy 3 and 4; On datasets dateset2 dateset5, the mean value of the fairness indices obtained for strategy 1 is smaller than those obtained for strategy 3 and 4, indicating that the task assignment scheme of strategy 1 is fairer and enables workers with higher quality service scores to have a higher probability of achieving the corresponding proportional benefit. On the datasets dateset1, dateset2, dateset4 and dateset5, the optimal value of strategy 1 is better than that of strategy 3 and 4, indicating that strategy 1 can find a more equitable task assignment solution; On dataset1, the mean value of strategy 1 is lower than that of strategy 3 which indicates that strategy 1 does not yield the fairest results in every dataset assignment scheme, which may be due to factors such as closer worker service quality scores and insignificant disparity in unit time gain between tasks. On the dateset1 and dateset5, the mean value of strategy 1 is slightly lower than strategy3 and 4, indicating that the stability is slightly weaker than strategies 3 and 4, and the stability of strategy 1 is stronger than strategy 3 and 4 on dateset2 dateset4, indicating that the stability of the solution is better for strategy 1 in most cases.

As the size of the dataset increases, the quality of the results obtained from strategy 1 is closer than those obtained from strategies 3 and 4 for both positive and fair incentive indices, and the gap in incentive indices keeps decreasing. For example, strategy 1 in dateset1 seeks a significantly higher positive incentive index than strategies 3 and 4, with 30.17% and 43.8% improvement respectively; in dateset2 compared to strategies 3 and 4, with 17.43% and 21.26% improvement respectively, and in dateset5 compared to strategy 3 and 4, only 7.55% and 5.12% improvement respectively. The fair incentive indices derived from the three strategies, except for dateset1, also show a trend of decreasing disparity as the size of the dataset becomes larger.

In summary, strategy 1 is more effective than the positive incentives of the two comparison strategies. Compared with strategy 3 and strategy 4, the positive incentive index of strategy 1 is improved by 11.79% and 14.60% respectively, and the fair incentive index is improved by 0.83% and 0.22% respectively. Strategy 1 task assignment results in a wider range of incentives to participating workers, and the equity incentive index indicates that the task assignment scheme of Strategy 1 is also fair. This shows that it is effective to take worker service quality and unit time benefit as objective function elements of task allocation. But the incentive advantage of strategy 1 over the comparison strategy tends to decrease continuously as the data set increases.

4.2.2 Validation of strategy 2

As shown in Table 6, from the positive incentive indices obtained on the five datasets, it can be seen that the mean, optimal values obtained for strategy 2 are always greater than or equal to strategies 3 and 4, indicating that strategy 2 can play an incentive role to a greater extent, allowing more workers with high service quality to be assigned tasks with shorter expected online idle time; On the datasets dateset1∼dateset4, the standard deviation of strategy 2 is smaller than strategies 3 and 4, indicating that strategy 2 is more stable.

Table 6
Calculation results of strategy 2 and other strategies on D₁

Dataset Strategy index Positive incentive index Fair incentive index

Strategy 2 Strategy 3 Strategy 4 Strategy 2 Strategy 3 Strategy 4

Dateset1 Mean value 0.6556 0.4833 0.4389 0.7228 0.7477 0.7349

Optimum value 0.8889 0.6667 0.6667 0.7207 0.7231 0.7209

Standard deviation 0.0923 0.1011 0.1137 0.0011 0.0164 0.0123

Dateset2 Mean value 0.6632 0.6000 0.5868 0.8644 0.8687 0.8675

Optimum value 0.7368 0.6316 0.6842 0.8631 0.8639 0.8632

Standard deviation 0.0714 0.0453 0.0507 0.0006 0.0053 0.0037

Dateset3 Mean value 0.6310 0.5776 0.5586 0.9096 0.9101 0.9109

Optimum value 0.7241 0.6552 0.6897 0.9127 0.9158 0.9092

Standard deviation 0.0464 0.0406 0.0603 0.0008 0.0015 0.0031

Dateset4 Mean value 0.5051 0.5013 0.5026 0.9313 0.9332 0.9326

Optimum value 0.5897 0.5641 0.5897 0.9314 0.9675 0.9675

Standard deviation 0.0466 0.0425 0.0384 0.0001 0.0079 0.0082

Dateset5 Mean value 0.5143 0.5143 0.5020 0.9469 0.9466 0.9469

Optimum value 0.5918 0.5714 0.5510 0.9422 0.9421 0.9419

Standard deviation 0.0441 0.0396 0.0356 0.0069 0.0069 0.0071

Dataset Strategy index		Positive incentive index	Fair incentive index
Dateset1	Mean value	0.6556	0.4833	0.4389	0.7228	0.7477	0.7349
	Optimum value	0.8889	0.6667	0.6667	0.7207	0.7231	0.7209
	Standard deviation	0.0923	0.1011	0.1137	0.0011	0.0164	0.0123
Dateset2	Mean value	0.6632	0.6000	0.5868	0.8644	0.8687	0.8675
	Optimum value	0.7368	0.6316	0.6842	0.8631	0.8639	0.8632
	Standard deviation	0.0714	0.0453	0.0507	0.0006	0.0053	0.0037
Dateset3	Mean value	0.6310	0.5776	0.5586	0.9096	0.9101	0.9109
	Optimum value	0.7241	0.6552	0.6897	0.9127	0.9158	0.9092
	Standard deviation	0.0464	0.0406	0.0603	0.0008	0.0015	0.0031
Dateset4	Mean value	0.5051	0.5013	0.5026	0.9313	0.9332	0.9326
	Optimum value	0.5897	0.5641	0.5897	0.9314	0.9675	0.9675
	Standard deviation	0.0466	0.0425	0.0384	0.0001	0.0079	0.0082
Dateset5	Mean value	0.5143	0.5143	0.5020	0.9469	0.9466	0.9469
	Optimum value	0.5918	0.5714	0.5510	0.9422	0.9421	0.9419
	Standard deviation	0.0441	0.0396	0.0356	0.0069	0.0069	0.0071

From the fair incentive indices obtained on datasets dateset1∼dateset4, it can be seen that overall strategy 2 has a smaller mean value of the fairness indices obtained than strategies 3 and 4, indicating that the task assignment scheme of strategy 2 is fairer. The optimal value of the fairness index found by strategy 2 is smaller than that found by strategies 3 and 4, indicating that strategy 2 can find a more equitable task assignment solution; On the datasets dateset1∼dateset3, the corresponding standard deviations of strategy 2 are smaller than those of strategies 3 and 4, indicating that strategy 2 has a better stability.

As the size of the data set expands, the advantages of strategy 2 continue to shrink compared with other comparison strategies, whether it is a positive incentive index or a fair incentive index. The standard deviation of the positive incentive index of strategy 2 solved on dateset5 is greater than that of strategy 3, and the fair incentive index solved on dateset5 is greater compared to strategy 3, and the optimal value is greater compared to strategy 4, which indicates that the stability and effectiveness of strategy 2 on dateset5 are not good.

Compared with strategy 3 and strategy 4, the positive incentive index of strategy 2 is improved by 9.29% and 12.08% respectively, and the fair incentive index is improved by 0.71% and 0.41% respectively. In summary, the task assignment result of strategy 2 can motivate the participating workers to a greater extent than the two comparison strategies, comparing with the two comparison strategies, so that workers with high service quality scores are more likely to receive the current task with less idle time in the end. And workers with high service quality scores can receive the waiting idle time corresponding to their own high scores, taking into account the fairness. This shows that it is also valid to consider worker service quality and online idle time as objective function elements of task allocation. But the incentive advantage of strategy 2 tends to decrease or even disappear as the data set increases.

4.2.3 Comparison and discussion on cumulative benefits of two workers

Because each worker has different competitors at each assignment time, in order to study the cumulative benefits of strategy incentive from the perspective of the individual, this paper pays attention to the actual cumulative benefits of two special workers, namely, the workers with the highest and lowest service quality scores, w₁ and w₂. Assuming that the service quality of workers is not affected by the evaluation of recent services, under the premise of constant service quality score, five task assignments are conducted on dataset1∼dataset5 respectively. Each task allocation generates 20 groups of assignment results according to different strategies. The mode of the corresponding tasks matching by the workers is taken as the decision-making scheme of final task allocation, and the calculation results are shown in Table 7.

Table 7
Cumulative income of workers under different strategies of w₁ and w₂

Income index Different strategies Strategy 1 Strategy 2 Strategy 3 Strategy 4

Income index Average of mode 16.8/20 9.5/20 8/20 3.8/20

Average value of Cumulative revenue 141.1141 148.1744 162.2004 197.9669

Worker w₁ Accumulated time 1564.1707 4440.2098 2852.1036 4549.8584

Accumulated online idle 336.2407 137.8186 237.0849 191.4517

ets _uw 0.0902 0.0334 0.0569 0.0435

iets _uw 0.0743 0.0324 0.0525 0.0418

Income index Average mode 7.8 9.4 7.4 3.4

Average value of Cumulative revenue 105.8857 207.9399 140.6789 135.1813

Worker w₂ Accumulated time 3181.1911 2796.0885 3796.6863 3029.6767

Accumulated online idle 171.3977 379.9532 172.5002 207.5582

ets _uw 0.0333 0.0744 0.0371 0.0446

iets _uw 0.0316 0.0655 0.0354 0.0418

Income index Different strategies		Strategy 1	Strategy 2	Strategy 3	Strategy 4
Income index	Average of mode	16.8/20	9.5/20	8/20	3.8/20
Average value of	Cumulative revenue	141.1141	148.1744	162.2004	197.9669
Worker w₁	Accumulated time	1564.1707	4440.2098	2852.1036	4549.8584
	Accumulated online idle	336.2407	137.8186	237.0849	191.4517
	ets _uw	0.0902	0.0334	0.0569	0.0435
	iets _uw	0.0743	0.0324	0.0525	0.0418
Income index	Average mode	7.8	9.4	7.4	3.4
Average value of	Cumulative revenue	105.8857	207.9399	140.6789	135.1813
Worker w₂	Accumulated time	3181.1911	2796.0885	3796.6863	3029.6767
	Accumulated online idle	171.3977	379.9532	172.5002	207.5582
	ets _uw	0.0333	0.0744	0.0371	0.0446
	iets _uw	0.0316	0.0655	0.0354	0.0418

From the average mode of the five strategies of worker w₁, the task assignment results of strategy 1 are concentrated, the stability is higher, strategy 3 is the lowest, which conforms to the strong randomness of the random strategy. The cumulative revenue is not consistent with ets_uw, the order from high to low is (4,3,2,1), the order of unit time revenue ets_uw and unit revenue considering online idle time iets_uw is (1,3,4,2), which is mainly affected by the cumulative time. The comparison demonstrates that ets_uw and iets_uw can more accurately represent the income of the employees. Compared with strategy 3 and 4, strategy 1 have increased 58.64%, 30.98% respectively, with an average increase of 107.34%, 71.20% respectively, indicating that strategy 1 can expand the positive incentive range. The cumulative idle time corresponding to strategy 2 is the minimum, which indicates the effectiveness of strategy 2. However, the income index of strategy 2 corresponding to the current task is low, which indicates that the allocation is carried out according to strategy 2. Although the expected idle waiting time of the task end point is very short, the sum of the current task allocation is ignored.

From the average mode of w₂ strategies, strategy 2 is more stable, task allocation results are more concentrated, and strategy 3 is the lowest. The order of cumulative income, ets_uw and iets_uw is not consistent, and the cumulative income is (2,3,4,1) from high to low, ets_uw and iets_uw from high to low (2,4,3,1). The comparison shows that ets_uw and iets_uw can more truly reflect the income of workers. Strategies 1 are compared with strategies 3 and 4, ets_uw decreased by 10.17%, 21.31% respectively, iets_uw decreased by 10.17%, 21.31% respectively. It reveals that strategy 1 can effectively adversely inspire the employees with poor ratings of service quality. The cumulative online idle time corresponding to strategy 2 is the longest, which indicates the effectiveness of strategy 2, but the corresponding income indicators of strategy 2 are the highest. It indicates that task allocation is conducted according to strategy 2. Although the idle waiting time of task destination is long, it can match the low service quality score, but the sum of tasks that are currently assigned is very high, which can not play the due punishment role.

To sum up, experiments verify that the two strategies are effective. The comparative experiment of the cumulative income of two workers shows that under the pricing background of the positive correlation between task income and distance, strategy 1 is significantly better than strategy 2 in terms of cumulative income and incentive effect. Strategy 2 can reduce online idle time significantly and save time to accomplish more operations, so it is suitable for application scenarios with less waiting time.

4.2.4 IGSO-ISSCTA applicability and range of m

The main results of the above experimental calculation shows that the average positive excitation index is effective on five datasets. But relatively speaking, the effectiveness on dataset1 to dataset3 is better than that on dataset4 to dataset5. And the above experimental calculation show that the average fair incentive index is effective on dataset1 to dataset4, and has no significant effect on dataset5. Furthermore, in order to achieve better results, it is suggested that m value is within 40. The specific method is to control the size of m by segmenting the spatiotemporal units when the spatiotemporal data is preprocessed.

4.3 Algorithm performance experiment

4.3.1 Performance comparison of algorithm

In this paper, we use the “delay matching” strategy to solve the problem of dynamic task assignment online into static cumulative combination optimization. In recent years, some scholars have solved the problem of combination optimization by improving IDFA [22] and IFA [23]. In addition, some scholars use the improved Greed Random (GR) [34] to calculate the spatial crowd-sourcing task allocation utility. So IDFA, IFA and GR are selected as the comparison algorithms, and the IDFA algorithm and IFA algorithm have the similarity of mechanism and GR has the comparability in application.

As shown in Fig. 2, the performance of the IGSO algorithm and the other three comparison algorithms is tested by repeating 20 experiments on dataset1 to dataset6 and iterating 1000 times. In terms of the final objective function optimization results of the four algorithms, the IGSO algorithm is always better than the other three algorithms, and it is close to IDFA on dataset1, dataset2 and dataset4, which is obviously better than the IFA algorithm and GR algorithm. The results of the IGSO algorithm on dataset3, dataset5 and dataset6 are better than the other three algorithms. From the convergence speed of the four algorithms, within 0 ∼ 20 iterations.

Fig. 2

Performance comparison between IGSO and comparison algorithms.

IGSO algorithm is slightly worse than IDFA algorithm on dataset1 and datesat2 and IGSO algorithm is equivalent to IDFA algorithm on dataset3 and dataset4, and they are better than IFA algorithm and GR algorithm; In 20 ∼ 400 iterations, the four algorithms can find better and stable solutions, and IGSO algorithm is slightly or significantly higher than the other three algorithms. To sum up, the IGSO algorithm outperforms the competition in terms of effectiveness and convergence.

4.3.2 Performance of six kinds of mobile modes and different combinations

Through 20 experiments on dataset1, dataset3 and dataset5, and iterating 1000 times, and then Fig. 3 is obtained by taking the average. In order to compare the performance of six kinds of mobile modes, the learning factor is set to 0. It means that the GSO algorithm is not used to optimize its own process. Among them, reverse learning is just a solution obtained by a reverse learning based on the original solution, and does not have the ability to update the solution repeatedly, therefore the learning factor is set to 0.1.

Fig. 3

Performance comparison of six mobile modes.

As shown in Fig. 3, from the final results of optimization, the objective functions of the inversion method on three data sets are the highest, and of the reverse learning method are the lowest. From the convergence rate of optimization, the reverse learning method is obviously weaker than other methods. Within 0 ∼ 100 iterations, the left adjacent transformation and the right adjacent transformation are better in dataset1, the inversion and insertion are better in dataset3, and the inversion and exchange are better in dataset5. Within 100 ∼ 500 iterations, on dataset1, the optimization results of the right adjacent transformation are better in 100 ∼ 200 iterations, and the optimization results of left adjacent transformation are better in 200 ∼ 500 iterations; On dataset3, the optimization results of inversion and left adjacent transform are better in the range of 200 ∼ 500; On dataset5, the optimization result of interchange is better. Within 500 ∼ 1000 iterations, the overall effect of inversion on the three data sets is better. To sum up, in different iteration stages, the performance of the six kinds of mobile modes is different, and each has its own level. On the whole, the inversion mode is better, and the reverse learning mode is worse.

In order to further verify the effectiveness of adaptive probability matching combination, three combination allocation methods are selected for comparison, namely average allocation, local policy priority and global policy priority. As shown in Fig. 4, average distribution means that the utilization rates of the six kinds of mobile modes are the same or close; Local strategy priority means that the first three strategies are more likely to be used, while the last three strategies are less likely to be used, because the first three mobility modes are local dimension mobility, which can be considered as local optimization, while the last three mobility modes are global optimization because many dimensions are moving; Global strategy priority means that the first three strategies are less used and the last three mobile modes are more likely to be used. The use probability ranges of the six mobile modes are shown in Table 8.

Fig. 4

Performance comparison of four combinations.

Table 8

Utilization rate of different mobile mode combinations

Combination mode	Exchange	Left adjacent transform	Left adjacent transform	Inversion	Insert	Reverse learning
Adaptive probability matching	The initial value is allocated averagely, and the matching probability is changed once every 10 iterations according to the adaptive probability matching formula
Average distribution	[0,0.16)	[0.16,0.32)	[0.32,0.48)	[0.48,0.64)	[0.64,0.8)	[0.8,1]
Local strategy first	[0,0.25)	[0.25,0.5)	[0.5,0.7)	[0.7,0.8)	[0.8,0.9)	[0.9,1]
Global policy first	[0,0.1)	[0.1,0.2)	[0.2,0.3)	[0.3,0.55)	[0.5,0.8)	[0.8,1]

The algorithm with different combinations of four mobile modes is repeated 20 times in dataset1, dataset3 and dataset5, with 1000 iterations. From the final optimization results, except for the smaller dataset1, the adaptive probability matching method is slightly larger than the local strategy priority method, and the adaptive probability matching method is significantly better than the other three methods on dataset3 and dataset5; The results show that the local strategy priority is worse than the adaptive probability matching, but better than the average allocation and global strategy priority; Average allocation and global policy priority are different in three datasets. In terms of convergence rate, the local strategy has the highest preferential convergence rate in 0 ∼ 10 iterations, and the other three strategies have the same preferential convergence rate, because the average allocation is used in the initial value of adaptive probability matching; Within 10 ∼ 50 iterations, the adaptive probability matching takes into account the contribution of each mobile mode, so it increases the utilization rate of better mobile mode, so it achieves better results.

4.3.3 Parameter debugging description

The main parameters of the IGSO algorithm include neighborhood thresholds, sensing radius and learning factors. In the IGSO algorithm debugging experiment, when other parameters remain unchanged, dateset3 is the better and larger scale data set of the IGSO-ISSCTA algorithm, so it is more likely to use this number of data sets in practical application, so dataset3 is selected as the parameter experimental data set.

The independent experiment was repeated 20 times, and Fig. 5 was obtained. The results show that the solution of the IGSO algorithm in the objective function fluctuates with the increase of neighborhood threshold, and the maximum solution is obtained when the value is 8; The results show that the solution of the IGSO algorithm in the objective function first increases, then decreases and remains unchanged with the increase of sensing radius, and the performance is the best when the sensing radius is 30; The results show that the solution of the IGSO algorithm in the objective function first increases and then decreases with the learning factor, and the performance is the best when the learning factor is 0.8.

Fig. 5

The influence of different parameters on the performance.

4.4 Practical application

D₂ is a large data set, including dateset6 ∼ dateset10. According to the discussion of m value, the IGSO-ISSCTA algorithm has a good effect on m ∈ (0, 40). By controlling the time interval and space unit size, the size of space-time unit is controlled to make m ∈ (0, 40). After space-time division, the objective function takes the cumulative value, and the positive incentive index and fair incentive index take the average value. And then Table 9 can be obtained. The objective function value of the IGSO algorithm is always higher than that of comparison algorithm on large-scale data sets, IDFA algorithm and IFA algorithm are lower, and GR algorithm is the lowest. The positive incentive index of strategy 1 is always larger than strategy 3 and strategy 4, and the fair incentive index is always smaller than strategy 3 and strategy 4, which indicates that the scope of positive incentive is larger and the fairness based on service quality allocation is better. Experimental results show that the IGSO-ISSCTA algorithm is still effective in large-scale data sets by dividing space-time units and accumulating calculations.

Table 9
Calculation results of IGSO-ISSCTA algorithm on D₂

Data set Index Objective function value Positive incentive index Equity incentive index

IGSO IDFA IFA GR Str.1 Str. 3 Str. 4 Str. 1 Str. 3 Str. 4

dateset6 2.62E+03 2.52E+03 2.16E+03 1.98E+03 0.6251 0.5516 0.5005 0.8606 0.8644 0.8629

dateset7 1.30E+04 1.28E+04 1.10E+04 1.00E+04 0.6137 0.5363 0.5338 0.8612 0.8624 0.8632

dateset8 2.61E+04 2.57E+04 2.14E+04 1.94E+04 0.6302 0.5866 0.5169 0.8609 0.8693 0.8624

dateset9 5.29E+04 5.03E+04 4.28E+04 3.89E+04 0.6798 0.5273 0.5368 0.8619 0.8626 0.8625

dateset10 1.04E+05 1.01E+05 8.78E+04 7.74E+04 0.6023 0.5275 0.5175 0.8624 0.8653 0.8627

Data set Index	Objective function value	Positive incentive index	Equity incentive index
dateset6	2.62E+03	2.52E+03	2.16E+03	1.98E+03	0.6251	0.5516	0.5005	0.8606	0.8644	0.8629
dateset7	1.30E+04	1.28E+04	1.10E+04	1.00E+04	0.6137	0.5363	0.5338	0.8612	0.8624	0.8632
dateset8	2.61E+04	2.57E+04	2.14E+04	1.94E+04	0.6302	0.5866	0.5169	0.8609	0.8693	0.8624
dateset9	5.29E+04	5.03E+04	4.28E+04	3.89E+04	0.6798	0.5273	0.5368	0.8619	0.8626	0.8625
dateset10	1.04E+05	1.01E+05	8.78E+04	7.74E+04	0.6023	0.5275	0.5175	0.8624	0.8653	0.8627

5 Conclusion

In this paper, the incentive problem in spatial crowd-sourcing task allocation is studied. For the first time, the real benefits of workers are considered from the aspects of task per unit time and online idle time, and a task allocation model based on worker service quality is constructed from these two aspects. In addition, compared with the traditional online Greedy algorithm, this paper designed an algorithm combining “delay matching” with the improved GSO algorithm to calculate the model results. Compared with the travel cost minimization strategy and the randomly selected strategy, the strategy proposed in this paper can motivate workers in a larger range of positive incentives and more equitably. Experimental results on data sets show that the proposed method is effective. However, the effect of the method in this paper is good on small-scale data sets, while the effect decreases on large-scale data sets. At the same time, it should be noted that other Intelligent optimization algorithms such as PSO, ACA and ABC, which can also solve the problem. In the following phase, we will continue to enhance the algorithm and model in order to broaden the spectrum of applications for the approach described in this work, and we will experiment with additional intelligent optimization methods in order to tackle the issue of spatial crowd-sourcing task allocation

Footnotes

Acknowledgments

This work was supported by the Anhui Provincial Natural Science Foundation under Grant No. 1908085QG298, the National Nature Science Foundation of China under Grant No. 91546108, No.71521001, the Fundamental Research Funds for the Central Universities No. JZ2019HGTA0053, No. JZ2019HGBZ0128, and the Open Research Fund Program of Key Laboratory of Process Optimization and Intelligent Decision-making (Hefei University of Technology), Ministry of Education.

References

Tong

Y.X.

, Zhou

Z.M.

and Zeng

Y.X.

, Spatial crowd-sourcing: a survey, The VLDB Journal 29 (2020), 217–250.

Tong

Y.X.

, Yuan

and Cheng

Y.R.

, Survey on spatiotemporal crowdsourced data management techniques, Journal of Software 28 (2017), 35–58.

Kazemi

, Shahabi

and Geocrowd , Enabling query answering with spatial crowdsourcing, In: Proceedings of the 20th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (2012), 189–198.

Tran

, To

and Fan

, A real-time framework for task assignment in hyperlocal spatial crowdsourcing, ACM Transactions on Intelligent Systems and Technology 9 (2018), 1–26.

Cheng

, Lian

and Chen

, Task assignment on multi-skill oriented spatial crowdsourcing, IEEE Transactions on Knowledge and Data Engineering 28 (2016), 2201–2215.

Kalyanasundaram

and Pruhs

, Online weighted matching, Journal of Algorithms 14 (1993), 478–488.

Kooti

, Grbovic

and Aiello

L.M.

, Analyzing uber’s ridesharing economy, In: Proceedings of the 26th International Conference on World Wide Web Companion (2017), 574–582.

, Frazier

P.I.

and Kislev

, Surge pricing moves uber’s driver-partners. In: Proceedings of the 2018 ACM Conference on Economics and Computation (2018), 3.

Banerjee

, Johari

and Riquelme

, Pricing in ride-sharing platforms: A queueing-theoretic approach, In: Proceedings of the 16th ACM Conference on Economics and Computation (2015), 1–54.

10.

Asghari

, Deng

and Shahabi

, Priceaware real-time ride-sharing at scale: an auction-based approach, In: Proceedings of the 24th ACM sigspatial International Conference on Advances in Geographic Information Systems 3 (2016), 1–10.

11.

Zhang

, Wen

and Zeng

, A discounted trade reduction mechanism for dynamic ridesharing pricing, IEEE Transactions on Intelligent Transportation Systems 17 (2016), 1586–1595.

12.

Chen

, Shen

and Tang

, et al., Optimal vehicle dis-patching for ride-sharing platforms via dynamic pricing, In: Companion of The Web Conference (2018), 51–52.

13.

Wang

, He

, Wang

, et al., Quality-assure and budget aware task assignment for spatial crowdsourcing, In: International Conference on Collaborative Computing: Networking, Applications and Work sharing (2016), 60–70.

14.

and Ngai

E.W.

, Toward a real-time and budget-aware task package allocation in spatial crowdsourcing, Decision Support System 110 (2018), 107–117.

15.

Mitsopoulou

, Boutsis

and Kalogeraki

. A cost aware incentive mechanism in mobile crowdsourcing systems. In: 2018 19th IEEE International Conference on Mobile Data Management (2018), 239–244.

16.

Deng

, Xu

, Gao

, et al., A Novel Gate Resource Allocation Method Using Improved PSO-Based QEA, IEEE Transactions on Intelligent Transportation Systems (2020), 2168–2216.

17.

Guo

H.X.

, Luo

Z.B.

, Zhang

J.F.

, et al., Network optimization simulation of wireless temperature sensing device in public area based on ant colony algorithm, In: Proceedings of 2021 6th International Conference on Automation, Control and Robotics Engineering (2021), 7.

18.

Han

P.X.

, Sun

, Jing

X.T.

, et al., An Improved Artificial Bee Colony Algorithm to Port L-AGV Scheduling Problems, In: Proceedings of 2021 6th International Conference on Automation, Control and Robotics Engineering (2021), 6.

19.

Krishnanand

K.N.

and Ghose

, Glowworm swarm based optimization algorithm for multimodal functions with collective robotics applications, Multiagent Grid Systems 2 (2006), 209–222.

20.

Z.W.

, Xiao

H.W.

and Wu

Z.J.

, Attribute selection method based on improved discrete glowworm swarm optimization and fractal dimension, Pattern Recognition & Artificial Intelligence 26(12) (2013), 1169–1178.

21.

Yang

X.S.

. Firefly algorithm. Nature-Inspired Meta heuristic Algorithms (2008), 79–90.

22.

Jie

, Teng

and Yin

, An Improved Discrete Firefly Algorithm Used for Traveling Salesman Problem. In: Advances in Swarm Intelligence, Lecture Notes in Computer Science 10385 (2017), 593–600.

23.

Saifullah , Baizal and Gunawan , Optimization of Tour Scheduling Using Firefly Algorithm, 7th International Conference on Information and Communication Technology (2019), 372–377.

24.

Xia

P.F.

, Ni

Z.W.

and Zhu

X.H.

, et al., Selective ensemble approach based on reverse binary glowworm swarm optimization and diversity measure, Journal of Systems Science and Mathematical Sciences 41(3) (2021), 730–746.

25.

Ran

J.M.

, Ni

Z.W.

and Peng

, Task allocation strategy considering service quality of spatial crowdsourcing workers and its glowworm swarm optimization algorithm solution, Journal of Computer Applications 41 (2021), 794–802.

26.

Christy

, Rekha

, Vijayakumar

, et al., Optimal broadcast scheduling method for VANETs: An adaptive discrete firefly approach, Journal of Intelligent & Fuzzy Systems 39 (2020), 8125–8137.

27.

Z.W.

, Liu

and Zhu

X.H.

, Task Allocation Strategy of Spatial Crowdsourcing Based on Deep Reinforcement Learning, Pattern Recognition and Artificial Intelligence 34 (2021), 191–205.

28.

Hao

, Yang

and Zhang.

Q.W.

, Re discussion on Statistical Measure on Gini Coefficient, Statistics & Decision 37 (2021), 27–32.

29.

Koenker

and Machado

J.A.

, Goodness of fit and related inference processes for quantile regression, Journal of the American Statistical Association 94 (1999), 1296–1310.

30.

B.Y.

, Cheng

Y.R.

and Wang

G.R.

, 3D-online stable matching problem for new spatial crowdsourcing platforms, Journal of Software 12 (2020), 3837–3849.

31.

Geng

H.T.

, Xu

and Dai

Z.B.

, Multi-objective evolutionary algorithm with multiple operators based on double credit assignment, Control and Decision 4 (2021), 1–8.

32.

Liu

S.Y.

, Liu

Y.H.

and Ni

L.M.

, Towards Mobility-based Clustering, In: Proceedings of ACM SIGKDD (2010), 919–927.

33.

Real time congestion details of major cities in China, http://jiaotong.baidu.com/top/congestDetail/citycode 289 (2021), May, 29.

34.

Song

T.S.

, Song

Y.X.

and Wang

L.B.

, Online task assignment for three types of objects under spatial crowdsourcing environment, Journal of Software 3 (2017), 612–630.