面向全局優(yōu)化的時空眾包任務(wù)分配算法

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

（1.湖北大學(xué)計(jì)算機(jī)與信息工程學(xué)院，武漢 430062；2.湖北省教育信息化工程技術(shù)研究中心（湖北大學(xué)），武漢 430062）

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

0 引言

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

本文主要工作在于：

1）提出一種綜合考慮眾包平臺、眾包任務(wù)、眾包工人三方效益的在線任務(wù)分配算法思想，進(jìn)行多目標(biāo)優(yōu)化，更加切合實(shí)際應(yīng)用中的需要。

2）在任務(wù)分配中，考慮眾包工人動態(tài)移動的特性，對任務(wù)進(jìn)行連續(xù)動態(tài)分配。

1 相關(guān)研究

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

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

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

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

綜上，不難看出現(xiàn)有研究中存在以下幾點(diǎn)不足：

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

2）大多在線任務(wù)分配算法僅依據(jù)當(dāng)前時間戳內(nèi)已有眾包對象進(jìn)行任務(wù)分配，對當(dāng)前時間戳內(nèi)的任務(wù)分配進(jìn)行局部優(yōu)化，而在實(shí)際應(yīng)用中，任務(wù)分配是連續(xù)動態(tài)進(jìn)行的，現(xiàn)有大多任務(wù)分配方案無法滿足連續(xù)分配中全局優(yōu)化的目標(biāo)。而已有基于預(yù)測方法進(jìn)行任務(wù)分配的算法，尚未考慮眾包工人動態(tài)移動的特性，無法滿足實(shí)際應(yīng)用環(huán)境的需要。

本文以實(shí)時專車類時空眾包應(yīng)用作為背景，針對上述問題，從眾包平臺、眾包任務(wù)、眾包工人三方的角度出發(fā)，以提高眾包任務(wù)分配三方的綜合效益指標(biāo)作為優(yōu)化目標(biāo)，針對連續(xù)任務(wù)分配問題，提出了一種采用隨機(jī)森林和門控制循環(huán)單元（Gated Recurrent Unit，GRU）網(wǎng)絡(luò)進(jìn)行預(yù)測分析的全局優(yōu)化在線任務(wù)分配算法，在當(dāng)前時間戳內(nèi)眾包對象分布情況的基礎(chǔ)上，結(jié)合下一時間戳內(nèi)眾包對象的預(yù)測情況進(jìn)行任務(wù)分配，實(shí)現(xiàn)連續(xù)任務(wù)分配過程中眾包任務(wù)分配三方綜合效益全局優(yōu)化的目標(biāo)。

2 問題定義

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

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

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

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

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

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

定義6任務(wù)差旅時間MTm。MTm表示任務(wù)工人分配后，工人到達(dá)任務(wù)地點(diǎn)的時間，即為任務(wù)分配時刻到工人到達(dá)時刻的時間差。當(dāng)工人速度一定時，任務(wù)與工人距離小的優(yōu)先分配。則MTm表示如下：

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

定義7工人機(jī)會成本COw。工人的機(jī)會成本COw表示工人w在平臺上線后處于空閑狀態(tài)到工人被分配處于工作狀態(tài)所花費(fèi)的成本，當(dāng)前已花費(fèi)機(jī)會成本高的工人優(yōu)先分配。COw表示為：

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

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

其中：權(quán)重系數(shù)α、β、γ、η根據(jù)熵權(quán)法確定，AT'm、MT'm和CO'w是離差法標(biāo)準(zhǔn)化處理后的取值。標(biāo)準(zhǔn)化處理方法如下：

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

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

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

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

不變性約束 眾包任務(wù)一旦完成分配，分配結(jié)果則不能改變。

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

3 GOMA

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

GOMA主要可分為以下三步：

1）執(zhí)行基于在線隨機(jī)森林的眾包對象動態(tài)預(yù)測算法（Dynamic Prediction algorithm for crowdsourcing objects based on online Random Forest，DPRF）和基于在線隨機(jī)森林回歸預(yù)測模型，預(yù)測下一時間戳內(nèi)眾包對象動態(tài)出現(xiàn)的情況。

2）執(zhí)行基于GRU 的工人移動軌跡預(yù)測算法（Worker Movement Trajectory Prediction algorithm based GRU，WMTP）和基于GRU 循環(huán)神經(jīng)網(wǎng)絡(luò)預(yù)測出當(dāng)前已有眾包工人在下一時間戳?xí)r的空間分布。

3）在當(dāng)前時間戳的眾包對象分布的基礎(chǔ)上，結(jié)合1）、2）預(yù)測的眾包對象的分布情況，執(zhí)行帶權(quán)二分圖最優(yōu)匹配算法，完成任務(wù)分配。

3.1 DPRF

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

對于空間分布預(yù)測，DPRF首先預(yù)測每個小室內(nèi)眾包對象動態(tài)出現(xiàn)個數(shù)，進(jìn)而基于均勻分布的策略預(yù)測出該小室內(nèi)眾包對象空間分布。

對于眾包對象的屬性參數(shù)預(yù)測，DPRF基于當(dāng)前時間戳內(nèi)已有眾包對象的屬性參數(shù)，采用正態(tài)分布的策略完成對應(yīng)的眾包對象屬性參數(shù)預(yù)測。

3.1.1 眾包對象空間分布預(yù)測

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

1）基于在線隨機(jī)森林模型初步預(yù)測小室cell內(nèi)的眾包對象個數(shù)。

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

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

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

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

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

其中preDTi表示第i棵決策樹的預(yù)測結(jié)果。

最終可得到n×n的網(wǎng)格圖中小室celli的初始預(yù)測結(jié)果numcelli，其中numw celli表示該小室內(nèi)眾包工人的初始預(yù)測數(shù)目，numm celli表示該小室內(nèi)眾包任務(wù)的初始預(yù)測數(shù)目。

2）基于滑動窗口確定每個小室cell內(nèi)的眾包對象個數(shù)。

時空眾包中空間位置相近的區(qū)域，眾包對象的出現(xiàn)往往具有相似性，由此DPRF 采用滑動窗口的方式，在初始預(yù)測的基礎(chǔ)上，針對每個小室，結(jié)合滑動窗口對應(yīng)相鄰小室的預(yù)測結(jié)果，根據(jù)滑動窗口的權(quán)重，進(jìn)行加權(quán)計(jì)算，完成眾包對象數(shù)目的預(yù)測（對于網(wǎng)格圖邊緣的小室，無法滿足滑動窗口，則取其剩余相鄰的小室進(jìn)行預(yù)測）。

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

其中：Nw為滑動窗口中小室的數(shù)目（本例中Nw=9），表示滑動窗口對應(yīng)小室的權(quán)重。cellA0中預(yù)測的眾包工人數(shù)目為，眾包任務(wù)數(shù)目為。

圖1 小室cell的待預(yù)測區(qū)域和滑動窗口對應(yīng)的權(quán)重分布示意圖Fig.1 Area to be predicted of a cell and weight distribution corresponding to sliding window

3）采用均勻分布的策略完成眾包對象的空間分布預(yù)測。對于網(wǎng)格圖中每個小室cell內(nèi)預(yù)測的眾包對象，均勻分布在小室四周的網(wǎng)格線上，完成空間分布預(yù)測。

3.1.2 眾包對象參數(shù)屬性預(yù)測

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

其中：agm celli表示小室celli當(dāng)前時間戳內(nèi)眾包任務(wù)的平均回報(bào)值，asw celli表示小室celli當(dāng)前時間戳內(nèi)眾包工人的平均任務(wù)成功率。

綜上，根據(jù)每個小室celli內(nèi)的眾包對象的空間分布和屬性參數(shù)分布完成該小室內(nèi)眾包對象的預(yù)測，進(jìn)而基于每個小室的預(yù)測情況完成整個n×n網(wǎng)格圖中下一時間戳內(nèi)的動態(tài)出現(xiàn)眾包對象預(yù)測。

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

首先定義眾包工人w在時間戳Ti時的軌跡點(diǎn)：

其中：dirw表示工人的移動方向，xc和yc表示工人在二維網(wǎng)格圖中的橫縱坐標(biāo)值。

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

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

圖2 GRU循環(huán)神經(jīng)網(wǎng)絡(luò)時序預(yù)測展開圖Fig.2 GRU recurrent neural network time series prediction expansion diagram

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

其中：σ表示sigmod 函數(shù)，Wxz、Whz和bz對應(yīng)zt計(jì)算時權(quán)重和偏執(zhí)。同時根據(jù)重置門rt將當(dāng)前輸入xt和上一時刻隱藏狀態(tài)ht-1中信息結(jié)合：

其中Wxr、Whr和br對應(yīng)rt計(jì)算時權(quán)重和偏置。進(jìn)而基于重置門rt和當(dāng)前輸入xt確定候選隱藏狀態(tài)：

其中Wxh、Whh和bh對應(yīng)計(jì)算時權(quán)重和偏置。最后基于上一時間戳隱藏層狀態(tài)ht-1和當(dāng)前時間戳候選隱藏狀態(tài)確定當(dāng)前隱藏層狀態(tài)ht：

圖3 GRU神經(jīng)元內(nèi)部結(jié)構(gòu)Fig.3 GRU neuron internal structure

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

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

由此，根據(jù)上述訓(xùn)練完成的RNN-GRU 模型預(yù)測出當(dāng)前時間戳內(nèi)已有眾包工人w在下一時間戳?xí)r所處空間位置是lnw(xc+1，yc+1)的軌跡點(diǎn)pTc+1。完成已有眾包工人在下一時間戳內(nèi)分布預(yù)測。

3.3 基于KM算法在線任務(wù)分配

在時空眾包任務(wù)分配中，將眾包任務(wù)和工人分別看作是二分圖的兩個點(diǎn)集，可分配任務(wù)工人匹配對集合MP看作邊集，對應(yīng)任務(wù)工人匹配對綜合效益CB作為邊的權(quán)重，執(zhí)行二分圖最優(yōu)匹配算法（KM算法），以完成三方綜合效益全局優(yōu)化的任務(wù)分配。

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

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

3.4 算法具體實(shí)現(xiàn)

GOMA偽代碼如下：

Input：眾包任務(wù)集合M，眾包工人集合W，綜合收益指標(biāo)CB的計(jì)算函數(shù)、已訓(xùn)練完成RNN-GRU預(yù)測模型；

Output：任務(wù)分配的結(jié)果集R。

GOMA 每一時間戳內(nèi)的算法時間復(fù)雜度分析如下：DPRF 的時間復(fù)雜度是O(numSF×numREC)，其中numSF是隨機(jī)森林中決策樹的特征數(shù)量，numREC是決策樹的深度?；贕RU 的工人移動軌跡預(yù)測算法（WMTP 算法）的時間復(fù)雜度為O(numPW×step)，其中numPW是當(dāng)前待預(yù)測的工人數(shù)目，step是GRU 網(wǎng)絡(luò)中輸入軌跡序列中軌跡點(diǎn)的數(shù)目。進(jìn)而執(zhí)行帶權(quán)二分圖最優(yōu)匹配算法的時間復(fù)雜度是O(|Vm|2×|Vw|)，其中|Vm|是二分圖邊集的容量，|Vw|是二分圖點(diǎn)集的容量。所以 GOMA 一輪任務(wù)分配的時間復(fù)雜度是：max(O(numSF×numREC)，O(numPW×step)，O(|Vm|2×|Vw|))。

3.5 算法舉例

假設(shè)當(dāng)前時間戳Ti=15 內(nèi)待分配任務(wù)有m1、m2，待分配工人有w1、w2，平臺工人的接單范圍半徑均為rw=1.5，時間戳?xí)r間間隔|Ti|=3，工人移動速度speed=0.5 單位長度/單位時間，工人的移動成本per=1 單位成本/單位長度，任務(wù)工人匹配對綜合效益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。工人屬性參數(shù)見表1，任務(wù)屬性參數(shù)見表2。

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

表2 實(shí)驗(yàn)數(shù)據(jù)參數(shù)Tab.2 Parameters of experimental data

按照GOMA的執(zhí)行步驟：

1）基于DPRF預(yù)測下一時間戳Ti+1內(nèi)該平臺上新發(fā)布任務(wù)mn1、mn2和新上線工人wn1。

2）基于WMTP 算法預(yù)測當(dāng)前時間戳的待分配工人w1、w2在下一時間戳空間分布點(diǎn)wm1、wm2。

3）當(dāng)前對象和預(yù)測對象的分布情況如圖4 所示，構(gòu)建二分圖模型并計(jì)算權(quán)重。權(quán)重計(jì)算以為例，Up=0.4875，2/3，。

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

二分圖模型如圖5 所示，然后執(zhí)行帶權(quán)二分圖最優(yōu)匹配算法（KM算法），得到最優(yōu)匹配集：

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

4 實(shí)驗(yàn)分析

4.1 實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

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

本實(shí)驗(yàn)在處理器為2.3 GHz Inter Core i5-6300HQ，內(nèi)存為8 GB 的計(jì)算機(jī)上運(yùn)行，操作系統(tǒng)為Windows 10?；赥ensorflow 的上層框架Keras進(jìn)行模型的搭建。實(shí)驗(yàn)使用的編程語言為Python，使用的集成開發(fā)環(huán)境是PyCharm。

4.2 預(yù)測模型參數(shù)取值

本文WMTP 算法所設(shè)計(jì)的工人軌跡預(yù)測模型為3 層，分別為輸入層、GRU 隱藏層和輸出層。本文設(shè)置GRU 隱藏層神經(jīng)元節(jié)點(diǎn)數(shù)CELL_SIZE、輸入層步數(shù)step作為模型可調(diào)節(jié)參數(shù)，均方差（Mean Squared Error，MSE）作為模型的評估指標(biāo)，以確定最佳的模型參數(shù)取值。

設(shè)置輸入層步數(shù)step從3 到7，隱層神經(jīng)元節(jié)點(diǎn)數(shù)CELL_SIZE 為同一step下的最優(yōu)值，不同step對應(yīng)的模型均方差如圖6所示。

隨著輸入的維度越大，模型的復(fù)雜程度越高，預(yù)測效果越好，但當(dāng)輸入維度過高時模型會發(fā)生過擬合。根據(jù)實(shí)驗(yàn)結(jié)果選取step=5作為輸入層序列Seqw中的軌跡點(diǎn)數(shù)量，此時模型的預(yù)測效果最好。

將連續(xù)5 組工人（其中每組包含工人數(shù)100 名）的平均移動軌跡點(diǎn)組成軌跡序列Seqw作為網(wǎng)絡(luò)輸入，設(shè)置5～15 不同的GRU 隱層神經(jīng)元節(jié)點(diǎn)數(shù)，評估模型的預(yù)測效果，實(shí)驗(yàn)結(jié)果如圖7 所示。由圖7 可知，當(dāng)隱層神經(jīng)元數(shù)目為11時模型均方差最小。表明當(dāng)輸入層step=5時，隱層神經(jīng)元個數(shù)為11，模型的預(yù)測效果最佳。

圖7 GRU神經(jīng)元均方差分布Fig.7 MSE distribution of GRU neurons

4.3 GOMA有效性實(shí)驗(yàn)

本實(shí)驗(yàn)從任務(wù)分配成功率、分配的平均綜合效益、工人平均機(jī)會成本三個方面對貪心算法、隨機(jī)閾值算法和GOMA 進(jìn)行比較分析，實(shí)驗(yàn)數(shù)據(jù)的參數(shù)設(shè)置如表2，其中任務(wù)回報(bào)值gm和工人的任務(wù)成功率sw滿足正態(tài)分布。

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

圖8 三種算法在任務(wù)分配成功率方面的實(shí)驗(yàn)結(jié)果Fig.8 Experimental results of three algorithms in success rate of task allocation

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

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

圖9 三種算法在平均綜合效益方面的實(shí)驗(yàn)結(jié)果Fig.9 Experimental results of three algorithms in average comprehensive benefit

從以上實(shí)驗(yàn)不難發(fā)現(xiàn)：

1）在任務(wù)分配成功率方面，GOMA 始終優(yōu)于貪心算法和隨機(jī)閾值算法。

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

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

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

圖10 三種算法在工人平均機(jī)會成本方面的實(shí)驗(yàn)結(jié)果Fig.10 Experimental results of three algorithms in average opportunity cost of workers

5 結(jié)語

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