面向全局優化的時空眾包任務分配算法

聶茜嬋，張 陽，余敦輝，2*，張興盛

（1.湖北大學計算機與信息工程學院，武漢 430062；2.湖北省教育信息化工程技術研究中心（湖北大學），武漢 430062）

（*通信作者電子郵箱yumhy@hubu.edu.cn）

0 引言

隨著Web2.0 技術的興起，大量在線Web 應用催生了眾包［1-3］這種通過群體智慧求解問題的新興商業生產模式。眾包是指“一種把過去由專職員工執行的工作任務通過公開的Web 平臺，以自愿的形式外包給非特定的解決方案提供者群體來完成的分布式問題求解模式”［4］。而隨著智能移動設備的普及和共享經濟模式的迅猛發展，賦予了眾包任務更多的時空屬性，衍生出一種全新的眾包類型——時空眾包［5-7］。時空眾包是指在時空約束的條件下，將具有時空特性的眾包任務分配給非特定的眾包工人群體，并要求眾包工人以主動或被動的方式來完成眾包任務。近年來，全國流行的各類實時專車類服務平臺，例如滴滴出行、Uber 等，均采用時空眾包方式提供服務。而在很多線上到線下（Online-to-Offline，O2O）應用、災情監控和物流管理等領域，也將時空眾包技術運用其中以提高其服務質量。然而，現有的研究大多局限從眾包平臺或工人的單一角度出發進行優化，且沒有滿足實際應用中連續分配任務的需求。因此，本文提出一種基于預測分析的全局優化在線任務分配算法（Global Optimization online Mission Assignment algorithm based on predictive analysis，GOMA），該算法基于在線隨機森林和門控循環單元網絡預測出下一時間戳內眾包對象（眾包任務和工人）的分布情況，進而結合當前時間戳內眾包對象的情況構造二分圖模型，最后采用帶權二分圖最優匹配算法完成任務分配，從而實現眾包平臺、眾包任務、眾包工人三方綜合效益的全局優化。

本文主要工作在于：

1）提出一種綜合考慮眾包平臺、眾包任務、眾包工人三方效益的在線任務分配算法思想，進行多目標優化，更加切合實際應用中的需要。

2）在任務分配中，考慮眾包工人動態移動的特性，對任務進行連續動態分配。

1 相關研究

任務分配［8-10］作為時空眾包領域研究的核心問題之一［11］，眾多學者對其展開了深入的討論。

文獻［12］在隨機閾值算法的基礎上，提出了面向三類眾包對象的自適應閾值算法，驗證了算法在提高分配效用方面的有效性；文獻［13］以貪心算法作為基線算法，提出了一種基于兩階段框架模型的全球微任務分配算法，在確保算法執行效率的同時提高任務分配的效用；文獻［14］以最大化任務的成功分配數為優化目標，提出了一種基于多臂賭博機的在線任務分配算法，為優化任務分配效用提供了新思路；文獻［15］在眾包工人查詢算法的基礎上，提出了一種基于動態效用的閾值選擇算法，通過動態效用對比以提升分配效用；文獻［16］提出一種基于眾包對象預測的在線任務分配算法，在現有眾包對象的基礎上，采用線性回歸模型預測動態出現的眾包對象，進行任務分配，實現任務分配效用的全局優化。這類方法僅局限于眾包平臺的角度，以任務分配總效用最大化為目標進行優化，而未考慮眾包工人的差旅成本以及眾包任務的等待時間。

文獻［17］在貪心算法的基礎上，提出時間空間預測器對眾包任務進行預測，進而輔助任務分配，旨在最小化一段時間內工人的總體差旅成本；文獻［18］針對最小化最大匹配距離的問題，提出了一種交換鏈算法，有效地解決了最差匹配情況下的匹配距離最小化的問題；文獻［19］面向最小化匹配距離的問題，進行綜合性對比實驗，證明了貪心算法解決該類問題的有效性。這類方法僅局限于眾包工人的角度，以工人平均差旅成本最小化為目標進行優化，而忽略了眾包任務等待時間以及任務分配的總效用，同時也沒有考慮眾包平臺、任務發布者的利益最大化。

文獻［20-21］從眾包平臺和工人的角度出發，文獻［20］根據眾包工人的密度進行眾包任務的范圍調節，提出一種基于統計概率進行預測分析的方法，能夠在提高任務分配總效用的同時降低工人的差旅成本；文獻［21］基于分而治之的思想，提出了一種基于二分法框架模型的在線任務分配算法，力求最大化任務分配數量以提高分配效用，同時最小化工人的差旅成本；文獻［22］從眾包平臺和眾包任務的角度出發，綜合考慮任務分配總效用和任務等待時間，提出一種基于分配時間因子的動態閾值算法，提升分配總效用的同時降低任務的平均等待時間。這類方法從眾包平臺、工人、任務中某兩方的角度出發進行雙目標優化，但沒有從眾包平臺、任務和工人三方角度出發，綜合考慮三方效益，所以仍然存在改進空間。

綜上，不難看出現有研究中存在以下幾點不足：

1）現有研究大多以單目標優化為主，從眾包平臺或工人單一角度出發，聚焦于提升任務分配總效用或降低工人的差旅成本，而少量研究從雙方角度出發，進行雙目標優化。對于從眾包平臺、任務和工人三方角度出發，綜合考慮三方效益的任務分配算法研究尚未出現。而考慮不完善的任務分配算法無法滿足實際應用中的需要。

2）大多在線任務分配算法僅依據當前時間戳內已有眾包對象進行任務分配，對當前時間戳內的任務分配進行局部優化，而在實際應用中，任務分配是連續動態進行的，現有大多任務分配方案無法滿足連續分配中全局優化的目標。而已有基于預測方法進行任務分配的算法，尚未考慮眾包工人動態移動的特性，無法滿足實際應用環境的需要。

本文以實時專車類時空眾包應用作為背景，針對上述問題，從眾包平臺、眾包任務、眾包工人三方的角度出發，以提高眾包任務分配三方的綜合效益指標作為優化目標，針對連續任務分配問題，提出了一種采用隨機森林和門控制循環單元（Gated Recurrent Unit，GRU）網絡進行預測分析的全局優化在線任務分配算法，在當前時間戳內眾包對象分布情況的基礎上，結合下一時間戳內眾包對象的預測情況進行任務分配，實現連續任務分配過程中眾包任務分配三方綜合效益全局優化的目標。

2 問題定義

定義1眾包任務m。m由任務請求者在眾包平臺上發布，通常被定義為如下四元組的形式。其中：lm是任務m在二維坐標系中所處的位置，任務m的發布時間是pm，任務m的截止時間是dm，gm表示完成該任務m的工人所獲得的報酬。

定義2眾包工人w。w是m的完成者，通常被定義為如下六元組的形式。其中lw是工人w在二維坐標系中所處的位置；rw是工人w的范圍半徑，工人w的接單范圍Rangw表示工人w愿意接受的任務的范圍，即以lw為圓心，rw為半徑的區域；dirw表示工人的移動方向dirw={N，S，W，E}；工人w在平臺上線時間是pw，工人w在平臺下線的時間是dw；sw表示工人在平臺上所完成的歷史任務的成功率。對于眾包工人，開始執行一個眾包任務視為工人從平臺下線；執行完一個眾包任務后，若繼續接單則視為工人在眾包平臺重新上線。為簡化計算，本文定義工人的行駛速度均為speed，工人單位路程所花費的成本為per。

定義3任務工人匹配對mp。mp定義為，表示眾包任務m和工人w的組合。

定義4分配效用Up。Up表示將眾包任務m分配給眾包工人w后所產生的效用，即匹配對的效用，定義為任務回報值gm與工人成功率sw的乘積，即：

其中：gm∈(0，1)，sw∈(0，1)，故Up∈(0，1)。

定義5任務等待分配時間ATm。ATm表示眾包任務m在平臺發布后，等待分配的時間，用于衡量任務的等待分配程度，等待程度高的任務優先分配。ATm即為任務發布時刻Pm到任務分配時刻Ta的時間差：

定義6任務差旅時間MTm。MTm表示任務工人分配后，工人到達任務地點的時間，即為任務分配時刻到工人到達時刻的時間差。當工人速度一定時，任務與工人距離小的優先分配。則MTm表示如下：

其中：MDmw表示任務和工人間的曼哈頓距離。

定義7工人機會成本COw。工人的機會成本COw表示工人w在平臺上線后處于空閑狀態到工人被分配處于工作狀態所花費的成本，當前已花費機會成本高的工人優先分配。COw表示為：

其中Lf表示工人處于空閑狀態所行駛的總距離，即工人從平臺上線到下線時間內所行駛的距離（曼哈頓距離）：

定義8任務工人匹配對綜合效益CB（Comprehensive Benefits）。mp具有分配效用Up、任務等待分配時間ATm、任務差旅時間MTm、工人機會成本COw四項屬性，從眾包三方角度考慮，定義綜合效益指標CB用于綜合衡量Up、ATm、MTm、COw四項指標：

其中：權重系數α、β、γ、η根據熵權法確定，AT'm、MT'm和CO'w是離差法標準化處理后的取值。標準化處理方法如下：

其中：xi為該指標當前樣本的原值，max(Xi)為該指標的最大值，min(Xi)為該指標的最小值，x'i為該指標當前樣本處理后的取值。

定義9綜合效益最大化的眾包在線任務分配問題Crowdsourcing online Mission Assignment to Maximize the Comprehensive Benefits，CMA-MCB）。在時空眾包環境下，給定眾包任務集合M、眾包工人集合W和任務工人匹配對綜合效益CB的計算函數，尋求一個任務分配的結果集R使得三方綜合效益最大化，即最大化任務工人匹配對綜合效益CB：

分配結果集R由匹配對mp組成，其中每個匹配對mp需滿足以下基本約束：

時間約束 只有眾包任務m和眾包工人w同時平臺在線時，才能實現分配，且眾包任務m必須在任務的截止時間dm前分配，否則無法完成分配。

不變性約束 眾包任務一旦完成分配，分配結果則不能改變。

空間約束 眾包任務m的空間位置lm必須在分配的眾包工人w的接單范圍內，即|lm-lw|＜rw。

3 GOMA

針對提出的CMA-MCB 問題，首先將一個任務分配周期劃分為n個固定時間長短的時間戳，在每個時間戳內進行任務分配。每輪分配首先設置當前待分配工人的接單范圍，進而執行基于預測分析的全局優化在線任務分配算法（GOMA），引入下一時間戳內眾包對象的分布情況作為當前分配的依據，基于在線隨機森林和GRU 兩種預測模型，預測出下一時間戳內眾包對象分布，結合當前時間戳內眾包對象的分布情況，執行帶權二分圖最優匹配算法（KM 算法），完成本輪任務分配。

GOMA主要可分為以下三步：

1）執行基于在線隨機森林的眾包對象動態預測算法（Dynamic Prediction algorithm for crowdsourcing objects based on online Random Forest，DPRF）和基于在線隨機森林回歸預測模型，預測下一時間戳內眾包對象動態出現的情況。

2）執行基于GRU 的工人移動軌跡預測算法（Worker Movement Trajectory Prediction algorithm based GRU，WMTP）和基于GRU 循環神經網絡預測出當前已有眾包工人在下一時間戳時的空間分布。

3）在當前時間戳的眾包對象分布的基礎上，結合1）、2）預測的眾包對象的分布情況，執行帶權二分圖最優匹配算法，完成任務分配。

3.1 DPRF

對于下一時間戳內新出現眾包對象的預測，DPRF將時空眾包地理場景擬合成n×n的網格圖，基于分而治之的思想，分別對網格圖中每一個小室cell進行預測。每個小室cell預測可分為眾包對象的空間分布預測和眾包對象的屬性參數預測。

對于空間分布預測，DPRF首先預測每個小室內眾包對象動態出現個數，進而基于均勻分布的策略預測出該小室內眾包對象空間分布。

對于眾包對象的屬性參數預測，DPRF基于當前時間戳內已有眾包對象的屬性參數，采用正態分布的策略完成對應的眾包對象屬性參數預測。

3.1.1 眾包對象空間分布預測

時空眾包中眾包任務和工人的動態出現具有相似性，本文采用相同的方法預測眾包任務和工人。DPRF中眾包對象的空間分布預測可分為三步：

1）基于在線隨機森林模型初步預測小室cell內的眾包對象個數。

在時空眾包環境下，一個區域內眾包對象的動態出現與該區域的時空屬性息息相關，本文選取了星期WEEK、一天中的時間段TQ、天氣WEA、區域的繁華程度BQ，作為訓練樣本的四類特征，即隨機森林中決策樹分支的影響因素。其中對于時間段TQ，本文以一個小時為間隔；對于天氣WEA，劃分為晴、大雨、中雨、小雨、陰五種狀況；對于區域的繁華程度BQ，本文也將其劃分為5種等級。

基于上述四類特征本文選取分類回歸樹（ClAssification and Regression Tree，CART）作為隨機森林回歸預測算法的基本單元，對于CART 則采用最小均方差原則作為決策樹節點劃分的依據。在決策樹生成過程中，對應的任意劃分點s兩邊劃分成的數據集D1和D2，使得D1和D2各自對應的均方差最小，同時D1和D2的均方差之和最小。即節點選擇條件為：

其中：c1為D1數據集的樣本輸出均值，c2為D2數據集的樣本輸出均值。

進而確定隨機森林中決策樹的個數numDT、每個決策樹的特征數量numSF以及建立決策樹時遞歸次數即樹的深度numREC，據此，從樣本數據集中有放回的隨機抽取numDT次，每次從抽取的樣本中選取numSF個特征用于構建決策樹，進而構建基于CART的隨機森林。

對于小室cell，隨機森林算法將所有決策樹的預測結果的平均值作為最終預測結果，即：

其中preDTi表示第i棵決策樹的預測結果。

最終可得到n×n的網格圖中小室celli的初始預測結果numcelli，其中numw celli表示該小室內眾包工人的初始預測數目，numm celli表示該小室內眾包任務的初始預測數目。

2）基于滑動窗口確定每個小室cell內的眾包對象個數。

時空眾包中空間位置相近的區域，眾包對象的出現往往具有相似性，由此DPRF 采用滑動窗口的方式，在初始預測的基礎上，針對每個小室，結合滑動窗口對應相鄰小室的預測結果，根據滑動窗口的權重，進行加權計算，完成眾包對象數目的預測（對于網格圖邊緣的小室，無法滿足滑動窗口，則取其剩余相鄰的小室進行預測）。

以圖1（a）為例，小室cellA0作為待預測區域，Scell={cellA1，cellA2，cellA3，cellA4，cellA5，cellA6，cellA7，cellA8}作為滑動窗口涉及的相鄰小室；圖1（b）表示滑動窗口對應的權重分布，cellA1、cellA3、cellA6、cellA8小室的權重為w1，cellA2、cellA4、cellA5、cellA7小室的權重為w2，權重分布滿足0 ＜w1 ＜w2 ＜1。預測小室cellA0的眾包對象數目為：

其中：Nw為滑動窗口中小室的數目（本例中Nw=9），表示滑動窗口對應小室的權重。cellA0中預測的眾包工人數目為，眾包任務數目為。

圖1 小室cell的待預測區域和滑動窗口對應的權重分布示意圖Fig.1 Area to be predicted of a cell and weight distribution corresponding to sliding window

3）采用均勻分布的策略完成眾包對象的空間分布預測。對于網格圖中每個小室cell內預測的眾包對象，均勻分布在小室四周的網格線上，完成空間分布預測。

3.1.2 眾包對象參數屬性預測

對于網格圖中小室celli內預測的眾包對象的參數屬性，即眾包工人的任務成功率sw和眾包任務的回報值gm，ORFRP算法采用正態分布的方式為小室celli內預測的對象設置屬性參數。以當前時間戳小室celli內眾包對象平均屬性參數值作為正態分布的均值，以σw作為工人任務成功率的方差，σm作為任務回報值的方差。公式表達如下：

其中：agm celli表示小室celli當前時間戳內眾包任務的平均回報值，asw celli表示小室celli當前時間戳內眾包工人的平均任務成功率。

綜上，根據每個小室celli內的眾包對象的空間分布和屬性參數分布完成該小室內眾包對象的預測，進而基于每個小室的預測情況完成整個n×n網格圖中下一時間戳內的動態出現眾包對象預測。

3.2 基于GRU的工人移動軌跡預測算法（WMTP算法）

首先定義眾包工人w在時間戳Ti時的軌跡點：

其中：dirw表示工人的移動方向，xc和yc表示工人在二維網格圖中的橫縱坐標值。

WMTP算法基于RNN-GRU循環神經網絡回歸預測模型，根據眾包工人w的移動軌跡序列Seqw預測下一時間戳Tc+1任務分配時工人w所處的空間軌跡點。工人移動軌跡序列Seqw由連續n個時間戳的工人的移動軌跡點組成，即Seqw=作為RNN-GRU 預測網絡的輸入，預測網絡輸出下一時間戳Tc+1的軌跡點。據此，工人移動軌跡預測模型的表達式為：

本文采用many to one 類型的單層RNN-GRU 循環神經網絡，其展開圖如圖2 所示。在模型訓練和預測的過程中，RNN-GRU 模型每次輸入樣本為連續n個時間戳的工人移動軌跡點序列Seqw（step=n），每個軌跡點pTi具有Ti，dirw，xc，yc四項特征。

圖2 GRU循環神經網絡時序預測展開圖Fig.2 GRU recurrent neural network time series prediction expansion diagram

對于樣本輸入中任意時刻Ti的軌跡點pTi，GRU 處理過程如圖3所示，GRU輸入包括當前軌跡點輸入xt(xt=pTi)和上一時刻的隱藏狀態ht-1（h0=0），GRU 首先基于ht-1和xt通過更新門zt確定上一時刻隱藏狀態中信息的保留程度：

其中：σ表示sigmod 函數，Wxz、Whz和bz對應zt計算時權重和偏執。同時根據重置門rt將當前輸入xt和上一時刻隱藏狀態ht-1中信息結合：

其中Wxr、Whr和br對應rt計算時權重和偏置。進而基于重置門rt和當前輸入xt確定候選隱藏狀態：

其中Wxh、Whh和bh對應計算時權重和偏置。最后基于上一時間戳隱藏層狀態ht-1和當前時間戳候選隱藏狀態確定當前隱藏層狀態ht：

圖3 GRU神經元內部結構Fig.3 GRU neuron internal structure

如果本次樣本輸入的是最后一個時刻xn的數據，則預測模型在本次處理得到隱藏狀態ht的基礎上添加全連接層輸出y，否則ht作為下一時刻的隱藏狀態輸入。

在訓練過程中選用均方差函數作為損失函數，即預測值與真實值之差的平凡的期望值，根據BPTT（Back Propagation Through Time）算法計算梯度，進而更新模型的參數，完成模型訓練。

由此，根據上述訓練完成的RNN-GRU 模型預測出當前時間戳內已有眾包工人w在下一時間戳時所處空間位置是lnw(xc+1，yc+1)的軌跡點pTc+1。完成已有眾包工人在下一時間戳內分布預測。

3.3 基于KM算法在線任務分配

在時空眾包任務分配中，將眾包任務和工人分別看作是二分圖的兩個點集，可分配任務工人匹配對集合MP看作邊集，對應任務工人匹配對綜合效益CB作為邊的權重，執行二分圖最優匹配算法（KM算法），以完成三方綜合效益全局優化的任務分配。

在本文提出的基于預測分析的全局優化在線任務分配算法GOMA中，首先構建基于預測分析的二分圖模型，將當前待分配任務集合Mt和DPRF 預測新出現的任務集合Mnt看作是二分圖的一個點集Vm。當前待分配工人集合Wt、DPRF 預測新出現的工人集合Wnt以及基于WMTP 算法預測出下一時間戳眾包工人集合Wmt看作是二分圖的另一點集Vw。其中：Wmt是將WMTP 算法預測出工人w在下一時間戳所在空間軌跡點pTc+1看作是處于lnw位置，屬性參數相同的眾包工人wm。工人點集中每一個工人與其最適接單范圍內的任務進行預匹配，構成可分配任務工人匹配對mp，進而根據任務工人匹配對集合MP連接二分圖。并假設當前時間CT為分配時間，計算每個任務工人匹配對的Up、TWm、COw三項指標，進而計算綜合匹配效益CB，以CB作為邊的權重。

最后基于上述搭建的二分圖模型執行KM 算法，在算法匹配結果Sp中，將眾包任務和工人均處于當前時間戳內的匹配對mp加入分配結果集R中。對于含有預測任務或工人的匹配對，則表明這些眾包對象在后期分配，會使得全局分配效果更優，故當前時間戳不予分配。

3.4 算法具體實現

GOMA偽代碼如下：

Input：眾包任務集合M，眾包工人集合W，綜合收益指標CB的計算函數、已訓練完成RNN-GRU預測模型；

Output：任務分配的結果集R。

GOMA 每一時間戳內的算法時間復雜度分析如下：DPRF 的時間復雜度是O(numSF×numREC)，其中numSF是隨機森林中決策樹的特征數量，numREC是決策樹的深度。基于GRU 的工人移動軌跡預測算法（WMTP 算法）的時間復雜度為O(numPW×step)，其中numPW是當前待預測的工人數目，step是GRU 網絡中輸入軌跡序列中軌跡點的數目。進而執行帶權二分圖最優匹配算法的時間復雜度是O(|Vm|2×|Vw|)，其中|Vm|是二分圖邊集的容量，|Vw|是二分圖點集的容量。所以 GOMA 一輪任務分配的時間復雜度是：max(O(numSF×numREC)，O(numPW×step)，O(|Vm|2×|Vw|))。

3.5 算法舉例

假設當前時間戳Ti=15 內待分配任務有m1、m2，待分配工人有w1、w2，平臺工人的接單范圍半徑均為rw=1.5，時間戳時間間隔|Ti|=3，工人移動速度speed=0.5 單位長度/單位時間，工人的移動成本per=1 單位成本/單位長度，任務工人匹配對綜合效益CB=0.5Up+0.15AT'm+0.2/MT'm+0.15CO'w，AT'm=ATm/9，MT'm=MTm/4，CO'w=COw/4.5。工人屬性參數見表1，任務屬性參數見表2。

表1 工人信息Tab.1 Information of workers

表2 實驗數據參數Tab.2 Parameters of experimental data

按照GOMA的執行步驟：

1）基于DPRF預測下一時間戳Ti+1內該平臺上新發布任務mn1、mn2和新上線工人wn1。

2）基于WMTP 算法預測當前時間戳的待分配工人w1、w2在下一時間戳空間分布點wm1、wm2。

3）當前對象和預測對象的分布情況如圖4 所示，構建二分圖模型并計算權重。權重計算以為例，Up=0.4875，2/3，。

圖4 眾包任務和眾包工人分布示意圖Fig.4 Crowdsourcing tasks and distribution of crowdsourcing workers

二分圖模型如圖5 所示，然后執行帶權二分圖最優匹配算法（KM算法），得到最優匹配集：

圖5 眾包任務和眾包工人匹配示意圖Fig.5 Matching of crowdsourcing tasks and crowdsourcing workers

4 實驗分析

4.1 實驗數據與環境

為驗證本文算法的有效性，從微軟開源數據集T-Drive 項目中獲得出租車的行駛軌跡點數據作為眾包工人的初始數據集，通過相應的預處理得到15 174 組數據；從時空眾包平臺gMission［23］上爬取了17 296條記錄，進行相應處理取得眾包任務的相應數據。將任務和工人的位置映射在100×100 的網格圖中，得到任務和工人的二維坐標。從處理后的數據集中基于均勻分布的原則選取13 000 組眾包工人和任務進行仿真實驗。

本實驗在處理器為2.3 GHz Inter Core i5-6300HQ，內存為8 GB 的計算機上運行，操作系統為Windows 10。基于Tensorflow 的上層框架Keras進行模型的搭建。實驗使用的編程語言為Python，使用的集成開發環境是PyCharm。

4.2 預測模型參數取值

本文WMTP 算法所設計的工人軌跡預測模型為3 層，分別為輸入層、GRU 隱藏層和輸出層。本文設置GRU 隱藏層神經元節點數CELL_SIZE、輸入層步數step作為模型可調節參數，均方差（Mean Squared Error，MSE）作為模型的評估指標，以確定最佳的模型參數取值。

設置輸入層步數step從3 到7，隱層神經元節點數CELL_SIZE 為同一step下的最優值，不同step對應的模型均方差如圖6所示。

隨著輸入的維度越大，模型的復雜程度越高，預測效果越好，但當輸入維度過高時模型會發生過擬合。根據實驗結果選取step=5作為輸入層序列Seqw中的軌跡點數量，此時模型的預測效果最好。

將連續5 組工人（其中每組包含工人數100 名）的平均移動軌跡點組成軌跡序列Seqw作為網絡輸入，設置5～15 不同的GRU 隱層神經元節點數，評估模型的預測效果，實驗結果如圖7 所示。由圖7 可知，當隱層神經元數目為11時模型均方差最小。表明當輸入層step=5時，隱層神經元個數為11，模型的預測效果最佳。

圖7 GRU神經元均方差分布Fig.7 MSE distribution of GRU neurons

4.3 GOMA有效性實驗

本實驗從任務分配成功率、分配的平均綜合效益、工人平均機會成本三個方面對貪心算法、隨機閾值算法和GOMA 進行比較分析，實驗數據的參數設置如表2，其中任務回報值gm和工人的任務成功率sw滿足正態分布。

1）在任務分配成功率方面，具體實驗結果如圖8 所示。GOMA 始終優于貪心算法和隨機閾值算法。當工人數量|W|增加時，三種算法的任務分配成功率均由增長逐漸趨于穩定；當任務數量|M|增加時，由于工人數量相對逐漸減少，三種算法的任務分配成功率均有一定程度的降低；當任務的有效時間上限ETm增加時，待分配任務可參與多輪任務分配，GOMA和貪心算法均有小幅度增長，但隨即閾值算法的波動較大；當工人的接單范圍半徑rw增加時，GOMA 的任務分配成功率增速明顯高于貪心算法和隨機閾值算法。

圖8 三種算法在任務分配成功率方面的實驗結果Fig.8 Experimental results of three algorithms in success rate of task allocation

2）在平均綜合效益方面，具體實驗結果如圖9 所示。GOMA 整體相對穩定，對比貪心算法和隨機閾值算法，平均綜合效益有大幅度的提升。工人數量|W|與任務數量|M|對GOMA 和貪心算法的影響不大，隨機閾值算法由于隨機選取閾值，平均綜合效益變化較大；當任務的有效時間上限ETm和工人的接單范圍半徑rw增加時，可分配的任務工人匹配對數量增加，GOMA和貪心算法的平均綜合效益均有小幅度增長。

3）在工人平均機會成本方面，具體實驗結果如圖10 所示。當工人數量|W|和任務數量|M|增加時，GOMA 的工人平均機會成本有小幅度變化，但一直明顯優于貪心算法和隨機閾值算法；當任務的有效時間上限ETm增加時，GOMA 處于較為穩定狀態，貪心算法和隨即將閾值算法的工人平均機會成本逐漸增大；當工人的接單范圍半徑rw增加時，貪心算法和隨機閾值算法的工人平均機會成本增速明顯高于GOMA。

圖9 三種算法在平均綜合效益方面的實驗結果Fig.9 Experimental results of three algorithms in average comprehensive benefit

從以上實驗不難發現：

1）在任務分配成功率方面，GOMA 始終優于貪心算法和隨機閾值算法。

2）在分配的平均綜合效益方面，工人數量|W|和任務數量|M|的變化對GOMA 影響不大，當任務的有效時間上限ETm和工人的接單范圍半徑rw增加時，GOMA 分配的平均綜合效益逐漸增長并趨于穩定，對比貪心算法和隨機閾值算法具有明顯的優勢。

3）在工人的平均機會成本方面，當工人數量|W|、工人的接單范圍半徑rw增加時，三種算法工人的平均機會成本均逐漸增加，但貪心算法和隨機閾值算法的增速明顯高于GOMA。當任務數量|M|增加時，三種算法的工人平均機會成本均逐漸降低，但GOMA 工人的平均機會成本低于另外兩種算法。當任務的有限時間上限ETm增加時，GOMA 較為穩定，但隨機閾值算法的波動比較大。

綜上，可以看出本文提出的GOMA 具有較好的實際應用價值，能有效地解決本文研究的CMA-MCB問題。

圖10 三種算法在工人平均機會成本方面的實驗結果Fig.10 Experimental results of three algorithms in average opportunity cost of workers

5 結語

本文研究了時空眾包環境下面向全局優化的在線任務分配問題。首先采用基于在線隨機森林的眾包對象動態預測算法（DPRF）預測下一時間戳內眾包對象動態出現的情況，然后利用基于GRU的工人移動軌跡預測算法（WMTP）預測眾包工人的移動軌跡，最后結合當前眾包對象的分布情況，基于帶權二分圖最優匹配算法進行任務分配，能夠有效地提高任務分配的綜合效益。通過實驗證明了本文所提算法在任務分配率、分配的平均綜合效益、工人的平均機會成本方面具有較好的性能表現，能夠有效地解決時空眾包中全局優化的在線任務分配問題。未來的時空眾包研究，可從以下兩個方面展開：1）針對眾包對象的分布情況預測，進行多步時間戳預測，進一步優化任務分配的效果；2）引入強化學習、預訓練等深度學習方法優化預測模型，進一步提高眾包對象分布情況預測的準確率。