一種基于時(shí)空位置預(yù)測(cè)的空間眾包任務(wù)分配方法

徐天承 喬少杰 武 俊 韓 楠 岳 昆 易玉根 黃發(fā)良 元昌安

1(成都信息工程大學(xué)軟件工程學(xué)院 成都 610225) 2(西南財(cái)經(jīng)大學(xué)證券與財(cái)經(jīng)學(xué)院 成都 610074) 3(成都信息工程大學(xué)管理學(xué)院 成都 610225) 4(云南大學(xué)信息學(xué)院 昆明 650500) 5(江西師范大學(xué)軟件學(xué)院 南昌 330022)6(南寧師范大學(xué)計(jì)算機(jī)與信息工程學(xué)院 南寧 530023)7(廣西教育學(xué)院 南寧 530023)

眾包的概念源于“外包”、“承包”，外包與承包強(qiáng)調(diào)的是專業(yè)化團(tuán)隊(duì)長(zhǎng)期穩(wěn)定的合作，而眾包則不同，將復(fù)雜的任務(wù)拆分為細(xì)粒度的任務(wù)，調(diào)動(dòng)個(gè)體用戶積極參與，尋求跨專業(yè)領(lǐng)域知識(shí)為工作成果帶來創(chuàng)新.當(dāng)前移動(dòng)和可穿戴設(shè)備的普及不僅豐富了人們的日常生活，同時(shí)開辟了一種新的工作模式：空間眾包(spatial crowdsourcing).空間眾包相較傳統(tǒng)眾包，需要眾包工作者在真實(shí)世界中，物理移動(dòng)到任務(wù)所標(biāo)注的特定地點(diǎn)，完成任務(wù)要求，這一模式在生活中存在廣泛的應(yīng)用場(chǎng)景(例如：滴滴打車、美團(tuán)眾包)，它可以幫公司企業(yè)節(jié)省大量成本.

空間眾包框架中任務(wù)請(qǐng)求人可以通過眾包平臺(tái)發(fā)布空間任務(wù)，例如觀察咖啡店是否擁擠、監(jiān)控某條路段的交通狀況等，并交付給真實(shí)世界中的眾包工作者來完成空間任務(wù).服務(wù)器需要基于空間任務(wù)和眾包工人的位置以及其他約束對(duì)其進(jìn)行分配，這一過程被稱為眾包任務(wù)分配問題.在真實(shí)的空間眾包平臺(tái)中任務(wù)和工人都是動(dòng)態(tài)出現(xiàn)的，如果不考慮任務(wù)/工人的動(dòng)態(tài)性，則無法獲得最佳的分配結(jié)果.而現(xiàn)實(shí)生活中眾包任務(wù)的發(fā)布和眾包工人的登錄往往具有非常復(fù)雜的動(dòng)態(tài)規(guī)律，使得傳統(tǒng)的機(jī)器學(xué)習(xí)和統(tǒng)計(jì)學(xué)方法難以對(duì)任務(wù)/工人的發(fā)布分布進(jìn)行準(zhǔn)確預(yù)測(cè).

通過分析滴滴出行分享的GAIA數(shù)據(jù)集，可以發(fā)現(xiàn)每天同一地點(diǎn)的任務(wù)發(fā)布數(shù)量均是隨時(shí)間呈周期變化的.如圖1所示，該圖統(tǒng)計(jì)了以各興趣點(diǎn)(point of interest, POI)為中心，半徑500 m內(nèi)每日不同時(shí)間發(fā)生的任務(wù)數(shù)量.橫軸為按小時(shí)劃分的一天，縱軸為任務(wù)發(fā)布的數(shù)量.每個(gè)種類的線均有7條，代表一周內(nèi)的7天，每種線后的陰影區(qū)域代表該P(yáng)OI處發(fā)布任務(wù)數(shù)量隨時(shí)間變化的趨勢(shì).從圖1中可以發(fā)現(xiàn)，景點(diǎn)2附近在19點(diǎn)時(shí)大概率會(huì)出現(xiàn)任務(wù)數(shù)量的下降，而景點(diǎn)1卻沒有這種現(xiàn)象；火車站每日的任務(wù)數(shù)量高峰期在16～18點(diǎn)產(chǎn)生，而景點(diǎn)1一般在19～23時(shí)達(dá)到高峰.這表明，同一區(qū)域每日任務(wù)發(fā)布的數(shù)量具有相似的變化走勢(shì).通過上述分析，可以得出結(jié)論：進(jìn)行未來時(shí)刻任務(wù)時(shí)空分布預(yù)測(cè)時(shí)需要依據(jù)過去的任務(wù)分布，將時(shí)間和空間作為預(yù)測(cè)所需的特征學(xué)習(xí).

Fig. 1 Quantity trend of different released POI tasks圖1 不同POI任務(wù)發(fā)布數(shù)量趨勢(shì)圖

目前已有許多關(guān)于空間眾包任務(wù)分配的研究，但現(xiàn)有的空間眾包任務(wù)分配方法通常存在2個(gè)方面的局限，有待進(jìn)一步完善.

1) 傳統(tǒng)的任務(wù)/工人分布預(yù)測(cè)方法很少使用工人和任務(wù)的時(shí)空特征，且一般基于網(wǎng)格進(jìn)行預(yù)測(cè)，但網(wǎng)格的不同劃分會(huì)影響到預(yù)測(cè)結(jié)果的準(zhǔn)確性，并且很難找到最優(yōu)的網(wǎng)格劃分方法.本文提出基于軌跡的任務(wù)分布預(yù)測(cè)方法和基于二維核密度估計(jì)的工人分布預(yù)測(cè)方法，學(xué)習(xí)歷史數(shù)據(jù)中任務(wù)/工人的時(shí)空特征，實(shí)現(xiàn)更精確的任務(wù)分配.

2) 空間眾包需要較快的任務(wù)分配效率，面對(duì)大規(guī)模的時(shí)空數(shù)據(jù)，計(jì)算分配的時(shí)間代價(jià)過大會(huì)導(dǎo)致結(jié)果沒有應(yīng)用價(jià)值.本文提出了一種基于任務(wù)/工人預(yù)測(cè)進(jìn)行任務(wù)分配的方法，以最大化目標(biāo)函數(shù)為目的，可以在線性時(shí)間內(nèi)得到有效的任務(wù)分配結(jié)果.

針對(duì)上述不足，本文對(duì)在線情景下空間眾包任務(wù)分配問題進(jìn)行了研究，設(shè)計(jì)了一種基于位置預(yù)測(cè)的空間眾包任務(wù)分配方法，可以有效地計(jì)算全局最優(yōu)的任務(wù)分配問題.本文的主要貢獻(xiàn)有3個(gè)方面：

1) 提出了基于軌跡的任務(wù)分布預(yù)測(cè)模型.不同于網(wǎng)格劃分的整體分布預(yù)測(cè)方法，本文基于拐點(diǎn)劃分軌跡，使用軌跡聚類算法獲得高流量的熱點(diǎn)軌跡，基于軌跡使用圖卷積來捕獲任務(wù)分布的空間特征，并使用核密度估計(jì)預(yù)測(cè)任務(wù)在軌跡上發(fā)布的具體位置，給出了計(jì)算預(yù)測(cè)所得任務(wù)價(jià)值的方法，方便后續(xù)任務(wù)分配時(shí)尋找最優(yōu)解.

2) 提出基于核密度估計(jì)的工人分布預(yù)測(cè)模型.先通過二維核密度估計(jì)來表示空間任務(wù)的分布，使ConvLSTM能更好地提取任務(wù)分布的空間特征，對(duì)于預(yù)測(cè)得到的空間分布核密度估計(jì)矩陣，提出了一種基于消減數(shù)量的方法來還原真實(shí)的任務(wù)分布.

3) 提出了一種基于位置預(yù)測(cè)的任務(wù)分配方法.依據(jù)任務(wù)和工人間的位置關(guān)系，計(jì)算每個(gè)任務(wù)的可用工人集，以此來創(chuàng)建二分圖，設(shè)定搜索增廣路徑上限次數(shù)，優(yōu)先選擇權(quán)值高的任務(wù)進(jìn)行分配，并針對(duì)預(yù)測(cè)任務(wù)設(shè)置了單獨(dú)的權(quán)值比較方法，能在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)尋找盡可能好的任務(wù)分配組合.

1 相關(guān)工作

與傳統(tǒng)眾包技術(shù)不同，空間眾包需要基于位置信息進(jìn)行工人任務(wù)間的分配.按照任務(wù)復(fù)雜度可將任務(wù)分為原子任務(wù)和復(fù)雜任務(wù)2種，原子任務(wù)可視為能由一位工人完成的簡(jiǎn)單任務(wù)，復(fù)雜任務(wù)可以劃分為多個(gè)原子任務(wù)，需要多種特定技能才能完成，本文將任務(wù)設(shè)定為原子任務(wù).按照任務(wù)發(fā)布模式，可分為服務(wù)器分配任務(wù)(server assigned tasks)模式和工人選擇任務(wù)(worker selected tasks)模式2種，現(xiàn)有的空間眾包系統(tǒng)大多使用服務(wù)器分配任務(wù)模式，在該模式中由服務(wù)器將任務(wù)分配給適當(dāng)?shù)墓と耍@種方法相較后者可以盡可能地減少無人接受的任務(wù)，并實(shí)現(xiàn)一些系統(tǒng)優(yōu)化目標(biāo)，如：技能覆蓋且成本最小.按任務(wù)的物理位置，可以分為特定點(diǎn)、特定區(qū)域和特定路線3種，這3種任務(wù)位置種類分別要求：到達(dá)一個(gè)特定的坐標(biāo)點(diǎn)，到達(dá)特定的建筑區(qū)域，從起始點(diǎn)提取特定物品交付給目標(biāo)客戶.為了簡(jiǎn)化問題，現(xiàn)有的研究大多是基于特定點(diǎn)的眾包任務(wù)研究.按照服務(wù)器分配策略中數(shù)據(jù)的狀態(tài)，可以分為離線場(chǎng)景和在線場(chǎng)景，離線場(chǎng)景下服務(wù)器在一開始就可以獲取完整的信息，在線場(chǎng)景下工人和任務(wù)的登錄信息是動(dòng)態(tài)的，算法將以數(shù)據(jù)流的形式接受工人和任務(wù)的登錄信息.現(xiàn)有的大部分研究都是基于離線場(chǎng)景的假設(shè)，沒有考慮到空間眾包任務(wù)分配的時(shí)空特性，不能得到全局最優(yōu)分配結(jié)果.

文獻(xiàn)[7]首先提出了空間眾包平臺(tái)上的任務(wù)分配問題，設(shè)定服務(wù)器統(tǒng)一管理所有的任務(wù)和工人位置信息，以最大化任務(wù)分配數(shù)量為目的利用貪心策略將任務(wù)分配給各個(gè)工人.文獻(xiàn)[8-11]僅考慮了當(dāng)前系統(tǒng)中存在的工人和任務(wù)，忽略了動(dòng)態(tài)變化的任務(wù)和工人，無法得到最優(yōu)的分配策略.文獻(xiàn)[12]最大化工人的收入為目標(biāo)，并針對(duì)任務(wù)的動(dòng)態(tài)性設(shè)計(jì)了一種平衡影響因素的路線推薦算法，但是該算法沒有考慮動(dòng)態(tài)加入系統(tǒng)的工人.文獻(xiàn)[13]提出了一種基于位置熵最小優(yōu)先級(jí)的候選工人算法，通過計(jì)算曼哈頓距離獲得候選工人，再基于決策樹進(jìn)行任務(wù)分配；文獻(xiàn)[14]考慮到工人是動(dòng)態(tài)移動(dòng)的，設(shè)計(jì)了貪心算法和極值算法2種近似算法，并提出了一種基于反饋的合作機(jī)制進(jìn)行任務(wù)分配；但文獻(xiàn)[13-14]均忽略了動(dòng)態(tài)加入系統(tǒng)的任務(wù).文獻(xiàn)[15-16]以在線算法(online algorithm)的方式來解決新加入系統(tǒng)的空間眾包任務(wù)分配問題.文獻(xiàn)[15]考慮工人—項(xiàng)目—任務(wù)的三色效用，設(shè)計(jì)了基于skyline查詢的解決方案；文獻(xiàn)[16]提出了一種基于空間感知多智能體的動(dòng)態(tài)優(yōu)化算法，并通過基于網(wǎng)格的空間優(yōu)化方法來分解眾包問題，以便解決大規(guī)模數(shù)據(jù)；但這些方法的時(shí)間復(fù)雜度較高，難以應(yīng)用于真實(shí)的眾包平臺(tái).文獻(xiàn)[17]通過預(yù)測(cè)的方式預(yù)估工人和任務(wù)在未來時(shí)刻的空間分布，基于預(yù)測(cè)得到的數(shù)據(jù)以最大化分配質(zhì)量分?jǐn)?shù)為目標(biāo)，基于貪心算法進(jìn)行分配.文獻(xiàn)[18]提出了三階段的啟發(fā)式算法求解最佳任務(wù)分配，通過預(yù)估每個(gè)工人的可用時(shí)間預(yù)測(cè)工人未來時(shí)刻的軌跡，盡可能地最大化工人完成任務(wù)的數(shù)量，使得工人的移動(dòng)距離均勻.但上述基于預(yù)測(cè)的方法沒有考慮到任務(wù)的分布與時(shí)間變化的關(guān)系，且在分布預(yù)測(cè)中均使用基于網(wǎng)格的預(yù)測(cè)方法.本文將以最大化分配價(jià)值，最小化工人移動(dòng)距離為目標(biāo)設(shè)計(jì)任務(wù)分配方法.

2 問題描述

本文要解決的問題中包含2種實(shí)體對(duì)象，在一個(gè)時(shí)間實(shí)例集

P

={1,2,…,

p

,…}中，實(shí)體定義如下：

定義1.

空間任務(wù)

t.

表示為

t

=〈

t.s

,

t.l

,

t.e

,

t.v

〉是一個(gè)在

t.s

時(shí)刻發(fā)生

t.l

位置的任務(wù)，該任務(wù)在

t.e

時(shí)刻前完成被認(rèn)為是有效的

.

完成該任務(wù)后會(huì)產(chǎn)生

t.v

的價(jià)值，其中

t.l

為真實(shí)空間中的坐標(biāo)(

x

,

y

)，實(shí)驗(yàn)中將其視作二維數(shù)據(jù)空間的一個(gè)點(diǎn)

.

定義2.

眾包工人

w.

表示為

w

=〈

w.l

,

w.v

〉，表示一個(gè)在時(shí)刻

p

位置在

w.l

處的眾包工人，其移動(dòng)速度為

w.v.

為簡(jiǎn)單且不失一般性，本文假設(shè)每個(gè)空間任務(wù)只需要分配一個(gè)眾包工人，任務(wù)需要的處理時(shí)間為0，即眾包工人只要到達(dá)任務(wù)處即完成任務(wù)

.

定義3.

最大價(jià)值最小成本任務(wù)分配問題

.T

為時(shí)刻

p

系統(tǒng)中現(xiàn)有的空間任務(wù)和預(yù)測(cè)得到的空間任務(wù)組成的集合；

W

為時(shí)刻

p

系統(tǒng)中現(xiàn)有的眾包工人和預(yù)測(cè)得到的眾包工人組成的集合；

I

為時(shí)刻

p

的任務(wù)分配集，由一組有效的〈

t

,

w

〉分配對(duì)組成，其中

t

∈

T

，

w

∈

W

，分配對(duì)〈

t

,

w

〉需要滿足工人能在任務(wù)截止時(shí)間前到達(dá)任務(wù)所在的位置，且同一時(shí)間一個(gè)工人只能被分配到一個(gè)任務(wù)

.

基于任務(wù)和工人相關(guān)定義，最大價(jià)值最小成本任務(wù)分配問題可以定義為：在給定的時(shí)間實(shí)例集

P

中，最大價(jià)值最小成本任務(wù)分配問題的目標(biāo)為

(1)

(2)

其中，

dist

(

t.l

,

w.l

)表示任務(wù)

t

到工人

w

的歐氏距離，真實(shí)情景下的軌跡分布難以類比為“棋盤格”狀，利用曼哈頓距離計(jì)算得工人距離并不準(zhǔn)確，本文計(jì)算

dist

(

t.l

,

w.l

)是為了對(duì)比不同分配間距離的相對(duì)大小進(jìn)行擇優(yōu)，使用歐氏距離計(jì)算的效果更準(zhǔn)確，故本文選擇使用歐氏距離作為不同分配對(duì)間的成本度量

.

|

I

|表示分配對(duì)的個(gè)數(shù)

.

最大價(jià)值最小成本任務(wù)分配問題的目標(biāo)是最大化分配集

I

的價(jià)值和，并最小化分配集

I

中眾包工人到空間任務(wù)的平均距離

.

3 基于軌跡的任務(wù)分布預(yù)測(cè)模型

空間眾包中任務(wù)的出現(xiàn)受物理世界中時(shí)間和空間因素影響，其中任務(wù)請(qǐng)求人的行為模式在任務(wù)分配中發(fā)揮關(guān)鍵作用.空間眾包平臺(tái)中，眾包工人接收任務(wù)后需要移動(dòng)到任務(wù)標(biāo)注的位置，可以認(rèn)為眾包任務(wù)的發(fā)布位置依附于眾包工人的軌跡，分析數(shù)據(jù)集可知不同地點(diǎn)的任務(wù)發(fā)生數(shù)量按時(shí)間呈周期性的模式變化.本節(jié)給出一種基于圖卷積神經(jīng)網(wǎng)絡(luò)的模型，該模型利用軌跡聚類捕捉任務(wù)分布時(shí)間空間相關(guān)性，可以高效地估計(jì)未來的任務(wù)分布及數(shù)量.

3.1 基于軌跡的位置信息提取

受到Lee等人提出的分段及歸組框架通過軌跡挖掘得到路網(wǎng)信息的啟發(fā)，本節(jié)通過基于特征點(diǎn)的街角提取(characteristic point-based road corner extraction, CP-RCE)選取工人軌跡中的拐點(diǎn)，使用拐點(diǎn)劃分軌跡，并設(shè)定軌跡間的距離函數(shù)使用DBSCAN算法得到處理后的軌跡圖.此外，分時(shí)段選出任務(wù)發(fā)生數(shù)量高于閾值的軌跡，作為預(yù)測(cè)任務(wù)發(fā)布位置的基礎(chǔ)，通過后續(xù)模型學(xué)習(xí)其中的空間特征進(jìn)行任務(wù)分布的預(yù)測(cè).由圖1的分析可知每日不同POI中任務(wù)發(fā)生的數(shù)量隨時(shí)間變化的趨勢(shì)是相似的，可以認(rèn)為每日相同時(shí)間段有相同的任務(wù)分布模式.假設(shè)前后兩日擁有相似的任務(wù)分布模式，那么在第

a

日的

p

時(shí)使用的圖結(jié)構(gòu)是基于第

a

-1日的

p

時(shí)的數(shù)據(jù)生成的.本文提出的基于軌跡的位置信息提取方法包含如下2個(gè)關(guān)鍵步驟.

1) 提取軌跡拐角.通過分析數(shù)據(jù)集中的GPS軌跡，使用基于特征點(diǎn)的街角提取方法提取軌跡中的拐角.具體的說，CP-RCE方法以定寬的窗口來遍歷GPS軌跡，在中心點(diǎn)的左右通過線性擬合的方法生成2條直線，通過計(jì)算軌跡點(diǎn)在兩直線上投影間的夾角，夾角大于閾值的軌跡點(diǎn)就是代表拐角的特征點(diǎn).

Fig. 2 The process of graph construction圖2 圖構(gòu)建過程

2) 構(gòu)建軌跡圖.由上述步驟得到的道路網(wǎng)絡(luò)結(jié)構(gòu)無法以矩陣和向量形式表達(dá)，很難以傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)模型來捕捉各個(gè)路段的空間依賴關(guān)系，故使用這些路段構(gòu)建圖

G

=(

V

,

E

)，以圖的形式來存儲(chǔ)軌跡信息

.

圖

G

中的

V

為結(jié)點(diǎn)集，將軌跡聚類后得到的每一條軌跡視作一個(gè)結(jié)點(diǎn)，故軌跡的個(gè)數(shù)就是圖

G

中結(jié)點(diǎn)的個(gè)數(shù)；

E

為邊集，如果2條軌跡間有連接，則兩結(jié)點(diǎn)間就有邊.圖使用鄰接矩陣和特征矩陣存儲(chǔ).鄰接矩陣表示各結(jié)點(diǎn)間的連接關(guān)系，鄰接矩陣的值為0或1，如果兩結(jié)點(diǎn)之間有連接則為1，反之則為0.特征矩陣包含各結(jié)點(diǎn)代表路段的特征信息，數(shù)據(jù)空間中眾包任務(wù)視作發(fā)生在最近的軌跡路段，

p

時(shí)結(jié)點(diǎn)的特征值為

p

時(shí)內(nèi)軌跡路段上發(fā)生的任務(wù)數(shù)量.圖2(b)圖所示的軌跡被5個(gè)拐點(diǎn)劃分為7條路段，分別被標(biāo)記為①～⑦，方塊代表空間眾包任務(wù).最終生成的圖結(jié)構(gòu)如圖2(c)所示，將各任務(wù)劃分到距離最近的軌跡路段上，可得到各結(jié)點(diǎn)的特征值如圖2(d)表格所示.如果圖有很多結(jié)點(diǎn)的特征長(zhǎng)時(shí)間為0的結(jié)點(diǎn)，會(huì)影響模型的效果.為提高模型預(yù)測(cè)的效果，在每一時(shí)間段篩選掉任務(wù)發(fā)布數(shù)低于閾值的軌跡路段，將這些軌跡代表的結(jié)點(diǎn)從該時(shí)段中刪除.

3.2 基于圖卷積的任務(wù)分布預(yù)測(cè)模型

本節(jié)將基于3.1節(jié)得到的圖結(jié)構(gòu)數(shù)據(jù)通過基于圖卷積的任務(wù)分布預(yù)測(cè)模型來預(yù)測(cè)路段的流量，再使用核密度估計(jì)的方法預(yù)測(cè)各路段任務(wù)發(fā)生的具體位置，最后給出了預(yù)測(cè)要發(fā)生價(jià)值的方法.具體為如下3個(gè)步驟：

Fig. 3 Prediction model of task distribution圖3 任務(wù)分布預(yù)測(cè)模型

(3)

(4)

=

ReLU

(·

ReLU

(··)·),

(5)

(

u

=1,2,…,

k

),

(6)

(

u

=1,2,…,

k

),

(7)

h

={

R

(

K

)}(15)

/

{

m

(

K

)}(25)

R

(

f

″)(15)

n

(15),

(8)

截選圖3(b)中的軌跡路段①如圖4(a)所示，軌跡①在歷史上有3個(gè)任務(wù)發(fā)生，將這些任務(wù)投影到路段①上，可以得到3個(gè)投影點(diǎn)的坐標(biāo)為

l

,

l

,

l

.

使用核密度估計(jì)函數(shù)

f

計(jì)算可以得到任務(wù)發(fā)生位置的概率密度函數(shù)

f

(

x

) 如圖4(b)所示

.

假設(shè)預(yù)測(cè)得到下一時(shí)刻任務(wù)發(fā)布的數(shù)量為

m

，路段從上至下的兩側(cè)的端點(diǎn)坐標(biāo)為(

x

,

y

)、(

x

,

y

)，概率密度函數(shù)

f

(

x

)前

m

高的橫坐標(biāo)集合

X

={

x

,

x

,…,

x

,

x

+1,…,

x

}，則預(yù)測(cè)得到的

m

個(gè)任務(wù)發(fā)布坐標(biāo)(

x

,

y

)可通過式(10)得到：

(9)

(

x

,

y

)=

(10)

其中，

d

為軌跡路段的長(zhǎng)度，(

x

,

y

)和(

x

,

y

)分別表示軌跡路段左端點(diǎn)和右端點(diǎn)的坐標(biāo)，

d

由軌跡路段兩端的坐標(biāo)求歐氏距離計(jì)算；(

x

,

y

)為軌跡路段上預(yù)測(cè)得到的第

i

個(gè)點(diǎn)的坐標(biāo)，

i

的取值為1到

m.

Fig. 4 Diagram of specific location prediction of task publishing圖4 任務(wù)發(fā)布具體位置預(yù)測(cè)示意圖

(11)

(12)

(13)

任務(wù)價(jià)值的預(yù)估可分為如下3種情況：

(14)

(15)

(16)

(17)

4 基于核密度估計(jì)的工人分布預(yù)測(cè)模型

由于空間眾包系統(tǒng)中工人位置信息的強(qiáng)時(shí)效性，為了實(shí)現(xiàn)全局更優(yōu)的分配，需要對(duì)新加入空間眾包系統(tǒng)的工人的位置信息進(jìn)行精確預(yù)測(cè).本節(jié)將介紹一種基于ConvLSTM的工人簽到位置預(yù)測(cè)方法，它可以有效地估計(jì)未來時(shí)刻工人的數(shù)量和位置分布.工人分布預(yù)測(cè)過程的總體結(jié)構(gòu)圖如圖5所示，從左向右，首先通過二維核密度估計(jì)進(jìn)行過去時(shí)間工人簽到位置分布平滑化處理，使得ConvLSTM模塊可以更容易地提取到空間分布的特征.然后，構(gòu)建基于ConvLSTM的2層網(wǎng)絡(luò)模型，在輸入層按照定寬的窗口滑動(dòng)劃分各時(shí)刻的二維核密度估計(jì)矩陣，得到時(shí)序的核密度估計(jì)矩陣投入模型，經(jīng)過隱藏層的ConvLSTM模塊提取空間特征，接著通過輸出層預(yù)測(cè)得到下一時(shí)刻的工人分布的二維核密度估計(jì)矩陣.最后，通過刪減策略的數(shù)量還原過程來精確預(yù)測(cè)未來時(shí)刻工人位置的分布.

Fig. 5 Working mechanism of worker distribution prediction圖5 工人分布預(yù)測(cè)工作原理

4.1 二維核密度估計(jì)位置分布

本節(jié)將任務(wù)的位置分布信息使用其二維核密度圖進(jìn)行表示

.

將真實(shí)世界的地圖視作一個(gè)

U

=[0,1]的二維數(shù)據(jù)空間，對(duì)于每個(gè)時(shí)間實(shí)例的工人簽到位置分布樣本，使用二維核密度估計(jì)可以得到工人分布的概率分布曲線

.

對(duì)數(shù)據(jù)空間

U

中的概率分布曲線進(jìn)行模擬，數(shù)據(jù)空間二維長(zhǎng)度均為0到1，如果不對(duì)估計(jì)函數(shù)歸一化處理，數(shù)據(jù)空間中對(duì)應(yīng)位置的函數(shù)值就是該位置可能簽到的工人數(shù)量

.

二維核密度的估計(jì)函數(shù)為

K

((

x

[

dim

]-

x

[

dim

])

/H

)，其中，

K

(·)為核函數(shù)，

dim

表示維度(

dim

=1表示二維數(shù)據(jù)空間的第一維)，由于后續(xù)分配工人時(shí)會(huì)對(duì)核密度估計(jì)矩陣進(jìn)行向下取整的操作，為避免向下取整丟失較大的小數(shù)值(比如1

.

9取整為1)此處使用均勻核函數(shù)

K

(

x

)=1

/

2，-1≤

x

≤1，

H

為平滑參數(shù)帶寬，計(jì)算方法與3

.

1節(jié)中計(jì)算核密度估計(jì)滑窗的方法類似(

H

，

H

需要分別計(jì)算)

.

通過如圖5所示方法可以得到工人的分布矩陣，該步驟如圖5中二維核密度估計(jì)部分所示，得到的分布矩陣類似圖中的熱力圖，核密度估計(jì)將稀疏的樣本通過帶寬

H

擴(kuò)散到相鄰區(qū)域，使得工人分布矩陣密度變高，方便后續(xù)卷積過程更好地捕捉工人空間分布的特征

.

但也是由于該原因，工人矩陣中的數(shù)量和并不是真正的工人數(shù)量

.

4.2 基于ConvLSTM的工人分布預(yù)測(cè)模型

本節(jié)將通過工人分布預(yù)測(cè)模型提取工人分布核密度估計(jì)矩陣的時(shí)空特征來預(yù)測(cè)下一時(shí)刻的工人分布，并基于核密度估計(jì)原理復(fù)原真實(shí)工人數(shù)量，具體分為如下2個(gè)步驟：

1) 工人預(yù)測(cè)模型網(wǎng)絡(luò)結(jié)構(gòu).由于ConvLSTM模型在時(shí)空數(shù)據(jù)特征提取上性能較佳，本文將其應(yīng)用于預(yù)測(cè)眾包工人登錄位置分布.在ConvLSTM中，要預(yù)測(cè)時(shí)間實(shí)例

p

+1時(shí)的工人位置分布，需要基于設(shè)定的滑窗寬度

s

輸入一組過去工人分布的核密度估計(jì)矩陣的時(shí)間序列

H

={-,-+1,…,-1,}，

H

表示核密度估計(jì)矩陣的時(shí)間序列，為時(shí)刻

p

的核密度估計(jì)矩陣

.

時(shí)間序列

H

為圖5中輸入層的輸入

.

網(wǎng)絡(luò)結(jié)構(gòu)中各參數(shù)的形式化表達(dá)如式(18)～(23)所示：=

Sigmoid

(

Conv

(;)+

Conv

(-1;)+),

(18)

=

Sigmoid

(

Conv

(;)+

Conv

(-1;)+),

(19)

=

Sigmoid

(

Conv

(;)+

Conv

(-1;)+),

(20)

=Tanh(

Conv

(;)+

Conv

(-1;)+),

(21)

=⊙-1+⊙,

(22)

=⊙Tanh(),

(23)

其中，⊙符號(hào)表示矩陣的哈達(dá)瑪乘積，,,分別表示輸入門、遺忘門、輸出門3個(gè)門的程度參數(shù)，是常規(guī)循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network, RNN)步驟得到的特征，為短時(shí)記憶，表示長(zhǎng)時(shí)記憶，

/

分別為輸出給下一單元

/

最后輸出的特征

.

在隱藏層網(wǎng)絡(luò)中，如圖5隱藏層部分，各ConvLSTM單元的長(zhǎng)期記憶隨著輸入序列時(shí)間方向傳播，各單元的輸出隨網(wǎng)絡(luò)的深度方向傳播

.

經(jīng)過2層網(wǎng)絡(luò)提取的時(shí)空特征，輸出結(jié)果經(jīng)圖5中輸出層的全連接網(wǎng)絡(luò)后，可以預(yù)測(cè)得到

p

+1時(shí)刻的工人分布核密度估計(jì)矩陣+1

.

2) 復(fù)原真實(shí)工人數(shù)量

.

通過上述步驟預(yù)測(cè)得的工人分布核密度估計(jì)矩陣+1是

p

+1時(shí)刻工人分布的核密度估計(jì)矩陣，分配工人前需要先對(duì)矩陣進(jìn)行取整操作

.

根據(jù)核密度估計(jì)的原理，核密度估計(jì)矩陣是通過核函數(shù)

K

(·)以帶寬

H

對(duì)每一個(gè)樣本進(jìn)行觀察，并擬合樣本點(diǎn)附近的概率，將所有的概率密度函數(shù)合并得到的，故每個(gè)樣本影響概率分布的范圍為±

H

.

所以，核密度估計(jì)矩陣中對(duì)應(yīng)位置的值并不是真實(shí)工人數(shù)量，若要得到+1中的真實(shí)工人數(shù)量，需要在減少矩陣某位置的數(shù)量時(shí)，同時(shí)減少該位置±

H

范圍的值

.

復(fù)原真實(shí)工人數(shù)量方法如下：假設(shè)核密度估計(jì)時(shí)使用的

H

為矩陣的

len

個(gè)寬度，如果分配矩陣中(

i

,

j

)位置的一個(gè)工人，需要將(

i

,

j

)位置和{

i

-

len

,…,

i

,…,

i

+

len

}?{

j

-

len

,…,

j

,…,

j

+

len

} (?表示笛卡爾積)中元素位置中工人數(shù)量大于零的部分全部減少1

.

以圖5中數(shù)量復(fù)原部分使用虛線框截取矩陣中的一部分為例，箭頭連接的矩陣為該部分工人的分布矩陣，矩陣中的數(shù)字表示對(duì)應(yīng)位置的工人數(shù)量

.

通過模擬分配2個(gè)工人的過程來展示消減數(shù)量策略的過程，如圖6所示:

Fig. 6 Example of quantity reduction圖6 數(shù)量削減過程示例

首先，將圖6中標(biāo)注①的(3,2)位置處的1個(gè)工人進(jìn)行分配，假設(shè)進(jìn)行核密度估計(jì)時(shí)計(jì)算出的

H

在核密度估計(jì)矩陣中寬度為1，則以集合{2,3,4}?{1,2,3}={(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,1),(4,2),(4,3)}的九宮格內(nèi)，數(shù)量大于零的位置工人數(shù)量均要減少1；將標(biāo)注②的(4,4)位置處的1個(gè)工人進(jìn)行分配，矩陣中{3,4,5}?{3,4,5}={(3,3),(3,4),(3,5),(4,3),(4,4),(4,5),(5,3),(5,4),(5,5)}位置的網(wǎng)格中人數(shù)均減1

.

分配可以持續(xù)到矩陣所有位置的數(shù)量都為0

.

5 基于位置預(yù)測(cè)的任務(wù)分配算法

傳統(tǒng)的任務(wù)分配問題一般可視為最大流問題，本文提出的最大價(jià)值最小成本任務(wù)分配問題可以分類為一種包含位置預(yù)測(cè)數(shù)據(jù)，任務(wù)為結(jié)點(diǎn)和工人為權(quán)值的二分圖最大流問題，并且結(jié)點(diǎn)和邊均帶權(quán)值.解決最大流問題的傳統(tǒng)算法有匈牙利算法和Kuhn-Munkras算法，若圖中結(jié)點(diǎn)有|

V

|個(gè)，邊有|

E

|個(gè)，則前者的時(shí)間復(fù)雜度為

O

(|

V

|×|

E

|)，但不能解決帶權(quán)值的二分圖最大流問題，后者可以解決帶權(quán)值的二分圖最大流問題，但時(shí)間復(fù)雜度為

O

(|

V

|)，難以應(yīng)用于現(xiàn)實(shí)場(chǎng)景.傳統(tǒng)的方法沒有完全適配本文問題的求解方法.故本節(jié)提出一種基于貪心算法和匈牙利算法的啟發(fā)式算法，通過搜索任務(wù)的可用工人集，構(gòu)造二分圖，盡可能尋找符合目標(biāo)函數(shù)式(1)(2)的最優(yōu)分配.

定義4.

任務(wù)可用工人集

.

在理想的眾包系統(tǒng)中，每個(gè)空間任務(wù)的有效工人集由任務(wù)需要的技能和工人擁有的技能、工人的可信度等幾個(gè)因素決定，但現(xiàn)有的數(shù)據(jù)集中缺少這幾種屬性，故本實(shí)驗(yàn)中僅考慮工人是否可以在任務(wù)結(jié)束前到達(dá)任務(wù)位置(不考慮工人執(zhí)行任務(wù)的時(shí)間)

.

在

p

時(shí)，若已存在系統(tǒng)中和預(yù)測(cè)將要加入系統(tǒng)的空間任務(wù)和眾包工人分別有

M

和

N

個(gè)，空間任務(wù)

t

的可用工人集表示為

AW

，且應(yīng)該遵循以下條件：?

w

∈

AW

,1)

dist

(

t

,

w

)≤(

t.e

-

p

)×

w.v

；

其中，

ind

(

w

,

t

)表示一個(gè)指示器，若工人

w

被分配給任務(wù)

t

，則

ind

(

w

,

t

)=1，否則

ind

(

w

,

t

)=0；

dist

(

t

,

w

)為任務(wù)位置

t

.l

到工人位置

w

.l

之間的歐氏距離，若任務(wù)

t

為預(yù)測(cè)得到的任務(wù)，則任務(wù)位置

t

.l

為式(4)計(jì)算得到的坐標(biāo)(

x

,

y

)，若工人

w

為預(yù)測(cè)得到的任務(wù)，則任務(wù)

j

的位置

w

.l

為任務(wù)

j

所在核密度矩陣位置對(duì)應(yīng)網(wǎng)格處的中心坐標(biāo)

.

5.1 基于預(yù)測(cè)數(shù)據(jù)的任務(wù)分配算法

假設(shè)時(shí)間序列

P

中系統(tǒng)中一共存在任務(wù)及工人分別有

M

和

N

個(gè)，算法目的為在多項(xiàng)式時(shí)間復(fù)雜度內(nèi)將

N

個(gè)工人分配給

M

個(gè)任務(wù)，并使分配對(duì)間的平均移動(dòng)距離盡可能低，分配對(duì)的總價(jià)值盡可能高

.

算法1給出基于預(yù)測(cè)數(shù)據(jù)的任務(wù)分配算法的偽代碼

.

算法1.

基于預(yù)測(cè)數(shù)據(jù)的任務(wù)分配算法.輸入：時(shí)間序列

P

={1,2,…,

p

,…}、時(shí)刻

p

任務(wù)集

T

、時(shí)刻

p

工人集

W

；輸出：任務(wù)分配集

I.

② for

p

=1 to

n

then③

T

←

T

+

T

,

W

←

W

+

W

,

T

←?,

W

←?;④

I

←?,

W

←?,

T

←?,

C

←?;

⑥ if 分配對(duì)〈

t

,

w

〉在時(shí)刻

p

存在 then⑦

I

←

I

+〈

t

,

w

〉;⑧ else 將已有的對(duì)象加入

T

或

W

;

⑨ end if

⑩ end for

i

←-1;

5.2 算法復(fù)雜性分析

本文算法中生成所有

AW

的復(fù)雜度約為

O

(

N

×

M

)，分配步驟的復(fù)雜度約為

O

(

M

×log

M

+

M

×

N

×log

N

)，故從整體的角度分析其平均時(shí)間復(fù)雜度約為

O

(

N

×

M

×log

M

)，此處

N

表示工人的數(shù)量，

M

為任務(wù)的數(shù)量

.

Fig. 7 Example of task assignment圖7 任務(wù)分配示例

例1.

如圖7所示，共有4個(gè)任務(wù)(

t

～

t

)和5個(gè)工人(

w

～

w

)，任務(wù)的價(jià)值和工人到各任務(wù)的距離如表1和表2所示

.

首先分配價(jià)值較高的空間任務(wù)

t

，在

t

的可用工人集中，距離最近的是工人

w

，故首先將

w

分配給

t

.

然后分配價(jià)值為4的空間任務(wù)

t

，在

t

的可用工人集中，距離最近的是工人

w

，并且

w

沒有分配給別的任務(wù)，故把

w

分配給任務(wù)

t

.

接著分配任務(wù)

t

，

t

可用的工人中距離最近的工人是

w

，故將

w

分配給任務(wù)

t

.

最后分配

t

，

t

的可用工人

w

和

w

均已經(jīng)被分配，故可以得出沖突任務(wù)集

T

為{〈

t

,

w

〉,〈

t

,

w

〉}，兩沖突分配對(duì)的距離分別為2和4，首先嘗試替換

t

的分配，但

t

沒有其他可用工人，故選擇替換〈

t

,

w

〉為〈

t

,

w

〉

.

最終得到的分配

I

={〈

t

,

w

〉,〈

t

,

w

〉,〈

t

,

w

〉,〈

t

,

w

〉}，而剩余無法被分配的

w

會(huì)留到下一時(shí)刻繼續(xù)參與分配

.

經(jīng)過本文方法分配后，得到的總價(jià)值為14，平均距離為2

.

75；而從價(jià)值高的任務(wù)開始遍歷，每次選取距離最近工人的貪心法取得的總價(jià)值12，平均距離為3，14>12且2

.

75<3，本文的方法明顯更優(yōu)

.

Table 1 Task Value

Table 2 Distance of Task and Worker

6 實(shí) 驗(yàn)

6.1 實(shí)驗(yàn)設(shè)置

本文實(shí)驗(yàn)部分使用滴滴蓋亞開放數(shù)據(jù)計(jì)劃提供的真實(shí)數(shù)據(jù)集，具體在滴滴提供的KDD CUP 2020網(wǎng)約車數(shù)據(jù)集上測(cè)試提出的算法.該數(shù)據(jù)集中包含30天的用戶訂單數(shù)據(jù)和司機(jī)軌跡數(shù)據(jù)，共有7 065 937個(gè)訂單數(shù)據(jù)，來自1 181 180個(gè)司機(jī)的6 105 003條軌跡數(shù)據(jù)，數(shù)據(jù)均來自滴滴公司的網(wǎng)約車服務(wù).本實(shí)驗(yàn)以該數(shù)據(jù)集范圍內(nèi)的區(qū)域(經(jīng)度104.042 102°～104.129 591°和緯度30.652 828°～30.727 818°范圍內(nèi)的區(qū)域)作為實(shí)驗(yàn)的背景地區(qū).實(shí)驗(yàn)將訂單數(shù)據(jù)和司機(jī)軌跡數(shù)據(jù)分別視作最大價(jià)值最小成本任務(wù)分配問題中的空間任務(wù)和眾包工人，具體地說，訂單的發(fā)布時(shí)間視作空間任務(wù)的發(fā)布時(shí)間，訂單的發(fā)布位置視作空間任務(wù)的發(fā)布位置，訂單價(jià)值視作空間任務(wù)的價(jià)值；將每條軌跡的首個(gè)時(shí)間戳和首個(gè)軌跡點(diǎn)坐標(biāo)視作一個(gè)眾包工人的登錄時(shí)間戳和登錄位置.經(jīng)過處理得到的數(shù)據(jù)集包含7 065 937個(gè)眾包任務(wù)和6 105 003個(gè)眾包工人.

本實(shí)驗(yàn)在該數(shù)據(jù)集上通過3.1節(jié)的軌跡聚類得到315個(gè)拐角和384條軌跡，經(jīng)過圖構(gòu)建過程建立出一個(gè)384個(gè)結(jié)點(diǎn)，806條邊的圖(根據(jù)各路段間的連接情況得到).為驗(yàn)證所提方法的性能，對(duì)最大價(jià)值最小成本任務(wù)分配問題中需要但數(shù)據(jù)集里不存在的屬性進(jìn)行合成，本實(shí)驗(yàn)使用高斯分布來模擬每個(gè)任務(wù)的持續(xù)時(shí)間和工人的速度，此處任務(wù)持續(xù)時(shí)間指的是任務(wù)發(fā)布后的有效時(shí)間，也就是

t.e

-

p

，工人速度指的是工人的移動(dòng)速度，也就是

w.v.

如表3所示，任務(wù)持續(xù)時(shí)間和工人移動(dòng)速度在

N

((

p

+

p

)

/

2,(

p

-

p

))和

N

((

v

+

v

)

/

2,(

v

-

v

))中隨機(jī)取值

.

實(shí)驗(yàn)中選擇前20天的數(shù)據(jù)作為訓(xùn)練集，第21天的數(shù)據(jù)作為驗(yàn)證集，22～30天的數(shù)據(jù)作為測(cè)試集

.

Table 3 Experimental Parameters

6.2 評(píng)價(jià)標(biāo)準(zhǔn)及對(duì)比算法

本實(shí)驗(yàn)根據(jù)預(yù)測(cè)結(jié)果的準(zhǔn)確率以及誤差來評(píng)估本文預(yù)測(cè)方法的有效性；以式(1)中定義的最大化總分配價(jià)值和式(2)最小化分配中工人到空間任務(wù)的平均距離目標(biāo)，衡量分配策略的質(zhì)量，并以最小化計(jì)算所消耗的CPU時(shí)間為目標(biāo)，來衡量分配策略的效率.表3給出本文的實(shí)驗(yàn)參數(shù)設(shè)置，其中默認(rèn)值以黑體顯示.在實(shí)驗(yàn)過程中，每組實(shí)驗(yàn)都會(huì)改變一個(gè)參數(shù)，其他參數(shù)均會(huì)設(shè)置為默認(rèn)值.

在本文的實(shí)驗(yàn)中，任務(wù)預(yù)測(cè)方法的有效性驗(yàn)證采取2種對(duì)比方法：1)單層圖卷積網(wǎng)絡(luò)(GCN-α).該方法使用本文3.2節(jié)中去掉隱藏層2的任務(wù)位置預(yù)測(cè)模型進(jìn)行預(yù)測(cè)；2)基于網(wǎng)格的任務(wù)預(yù)測(cè)方法(grid-based task prediction, GTP).使用基于網(wǎng)格劃分的方法劃分?jǐn)?shù)據(jù)空間，并在各單元格內(nèi)使用線性回歸的方法進(jìn)行任務(wù)數(shù)量預(yù)測(cè)，并假設(shè)任務(wù)發(fā)生在單元格的中心位置.工人位置預(yù)測(cè)方法的有效性驗(yàn)證采取2種對(duì)比方法：1)不使用核密度估計(jì)處理工人分布圖的ConvLSTM模型(ConvLSTM-α).該方法為本文的基于ConvLSTM的工人分布預(yù)測(cè)模型，去掉4.1節(jié)和4.2節(jié)(2)中二維核密度估計(jì)預(yù)處理和還原步驟的工人位置預(yù)測(cè)模型；2)基于網(wǎng)格的任務(wù)預(yù)測(cè)法(grid-based worker prediction, GWP).與GWP相似，網(wǎng)格劃分?jǐn)?shù)據(jù)空間，使用線性回歸法進(jìn)行工人數(shù)量預(yù)測(cè).

分配方法的有效性和效率采用了2種基礎(chǔ)的對(duì)比算法：1)貪心分配算法(greedy).以任務(wù)價(jià)值從高到低的順序選擇任務(wù)，每個(gè)任務(wù)均在其可用工人集中選擇距離最短的工人進(jìn)行分配，若沒有可用工人集，則該任務(wù)當(dāng)前時(shí)間實(shí)例無法分配.與本文基于預(yù)測(cè)數(shù)據(jù)的任務(wù)分配算法相比較，貪心分配算法把其中分配部分替換為貪心算法，平均時(shí)間復(fù)雜度約為

O

(2

M

×

N

+

M

×log

M

).2)隨機(jī)分配算法(random).隨機(jī)選擇一個(gè)任務(wù)，在其可用工人集中隨機(jī)選擇工人進(jìn)行分配，若沒有可用工人集，則該任務(wù)當(dāng)前時(shí)間實(shí)例無法分配，該分配算法的平均復(fù)雜度約為

O

(

M

×

N

+

M

)，其中

M

為任務(wù)數(shù)量，

N

為工人數(shù)量.

本文所有實(shí)驗(yàn)均是在AMD Ryzen 5 3600 CPU@3.6 GHz,16 GB內(nèi)存以及Nvidia GTX 1660s硬件條件下使用Python語言實(shí)現(xiàn)實(shí)驗(yàn)中算法.

6.3 工人和任務(wù)預(yù)測(cè)效果分析

本節(jié)實(shí)驗(yàn)對(duì)工人預(yù)測(cè)效果表現(xiàn)進(jìn)行評(píng)估，并評(píng)估其對(duì)后續(xù)任務(wù)分配步驟的影響.使用前20天的數(shù)據(jù)作為訓(xùn)練集，后9天為測(cè)試集，并通過改變滑窗寬度和訓(xùn)練集大小，來測(cè)試模型準(zhǔn)確度的變化，同時(shí)設(shè)定模型的其他參數(shù)如表3中默認(rèn)值(加黑)所示 .

1) 滑窗寬度的影響.

首先通過改變滑窗寬度來評(píng)估工人和任務(wù)分布預(yù)測(cè)的準(zhǔn)確性，實(shí)驗(yàn)的epoch設(shè)置均為100，分別使用平均絕對(duì)誤差(mean absolute error, MAE)和均方根誤差(root mean square error, RSME)2種誤差來衡量模型的準(zhǔn)確度情況，滑動(dòng)窗口帶寬的取值為4，6，8，10，12.如圖8(a)～(b)所示，對(duì)于任務(wù)分布預(yù)測(cè)模型，可以觀察到隨著滑窗寬度從4增大到8的過程中，預(yù)測(cè)的誤差略有下降，但從8增大到12的這個(gè)過程中，預(yù)測(cè)的誤差基本上停止變化.這是因?yàn)樵?.2節(jié)對(duì)任務(wù)預(yù)測(cè)的模型設(shè)定中，滑窗寬度代表投入模型的歷史數(shù)據(jù)量大小.3.1節(jié)中基于時(shí)間劃分不同模型一定程度上消除任務(wù)位置分布隨時(shí)間變化的影響，對(duì)于任務(wù)位置預(yù)測(cè)模型來說不需要太多的歷史數(shù)據(jù)進(jìn)行學(xué)習(xí).圖8(c)～(d)中工人分布預(yù)測(cè)中滑窗寬度從8增大到12的過程中，誤差反而有所增加，這是因?yàn)楣と说姆植茧S時(shí)間變化較為迅速，使用較多的歷史數(shù)據(jù)反而會(huì)導(dǎo)致模型不能專注于近期的變化，產(chǎn)生較大的誤差.總的來說，2個(gè)模型對(duì)于帶寬的敏感程度都不大，且預(yù)測(cè)效果均較好(MAE和RMSE均小于1)，根據(jù)實(shí)驗(yàn)結(jié)果選擇默認(rèn)的滑動(dòng)窗口大小為8.

Fig. 8 Task/worker prediction model effect圖8 任務(wù)/工人預(yù)測(cè)模型效果

2) 訓(xùn)練集大小的影響.

① 任務(wù)分布預(yù)測(cè)分析.通過改變訓(xùn)練集大小來評(píng)估工人位置預(yù)測(cè)算法的性能和該部分對(duì)后續(xù)任務(wù)分配的影響.數(shù)據(jù)集的前20天設(shè)定為訓(xùn)練集，訓(xùn)練集的大小取值為30%，40%，60%，80%，100%.對(duì)于任務(wù)位置分布預(yù)測(cè)，使用了2種對(duì)比方法：基于網(wǎng)格的任務(wù)預(yù)測(cè)方法(GTP)，單層圖卷積網(wǎng)絡(luò)(GCN-α).為衡量模型性能，使用一種基于網(wǎng)格的準(zhǔn)確率：將二維數(shù)據(jù)空間分為等大小的網(wǎng)格，通過比較單元中工作者/任務(wù)的估計(jì)數(shù)量

q

′和實(shí)際數(shù)

q

得出準(zhǔn)確率

ACC

=|

q

′-

q

|

/q

×100%.為了測(cè)試位置預(yù)測(cè)效果對(duì)分配結(jié)果的影響，使用本文所提基于位置預(yù)測(cè)的任務(wù)分配算法，基于位置預(yù)測(cè)進(jìn)行了任務(wù)分配，并計(jì)算了分配的總價(jià)值.

在準(zhǔn)確率評(píng)估實(shí)驗(yàn)中，在圖9(a)中可以觀察到，隨著訓(xùn)練集變大，3種方法均有一定程度的準(zhǔn)確率提升.本文方法的準(zhǔn)確率從64.4%提升到了89.1%，比排名第2的GCN-α最終的82.1%高出了7個(gè)百分點(diǎn)，而GTP方法的準(zhǔn)確率最后穩(wěn)定在73.5%左右.在圖9(b)中可以發(fā)現(xiàn)分配得到的價(jià)值隨著3種方法準(zhǔn)確率的增加均有明顯上升.GCN-α和GTP方法在訓(xùn)練集從40%增加到60%的步驟中有較大的價(jià)值提升，這是因?yàn)橛?xùn)練集大小在30%～40%左右時(shí)，GCN-α和GTP的準(zhǔn)確率僅有50%左右，導(dǎo)致產(chǎn)生了大量無效分配，在準(zhǔn)確率提高后分配效果才有所提升.而本文方法的準(zhǔn)確穩(wěn)定在64%以上，故總的分配價(jià)值比較穩(wěn)定.本文方法在3種方法中表現(xiàn)最好，原因在于本文方法使用軌跡路段作為預(yù)測(cè)任務(wù)分布的基礎(chǔ)，相較GTP和GCN-α預(yù)測(cè)方法更加精細(xì)，更加符合工人接受任務(wù)的位置.

② 工人分布預(yù)測(cè)分析.對(duì)于工人的位置分布預(yù)測(cè)，對(duì)比本文方法選擇了2種對(duì)比方法：基于網(wǎng)格的工人預(yù)測(cè)方法(GWP)，不進(jìn)行二維核密度估計(jì)的本文方法(ConvLSTM-α) .為了衡量模型性能，同樣使用

ACC

=|

q

′-

q

|

/q

×100%做為準(zhǔn)確率評(píng)價(jià)標(biāo)準(zhǔn)，與任務(wù)預(yù)測(cè)算法效果實(shí)驗(yàn)中相似，使用基于位置預(yù)測(cè)的任務(wù)分配算法進(jìn)行任務(wù)分配，并比較分配的總價(jià)值.

準(zhǔn)確率評(píng)估實(shí)驗(yàn)如圖10(a)所示，隨著訓(xùn)練集增大，3種方法工人預(yù)測(cè)的準(zhǔn)確率均有的增加.本文方法準(zhǔn)確率最高，其次是GWP和ConvLSTM-α.原因在于本文方法通過核密度估計(jì)把數(shù)據(jù)空間劃分為比GWP方法更精細(xì)的子區(qū)域，使用核密度估計(jì)彌補(bǔ)了工人分布矩陣的稀疏性，相較ConvLSTM-α方法中直接使用ConvLSTM提取時(shí)空特征的做法，可以更好的提取工人分布的空間特征.本文方法工人預(yù)測(cè)準(zhǔn)確率最高可達(dá)73.6%，相比GWP方法高出18.8個(gè)百分點(diǎn).ConvLSTM-α方法的準(zhǔn)確率最終僅達(dá)到52.3%，這是由于沒有經(jīng)過預(yù)處理的工人分布圖過于稀疏，模型不能提取到空間特征，導(dǎo)致預(yù)測(cè)結(jié)果不理想.圖10(b)中，在訓(xùn)練集大小從30%增加到40%的過程中可以觀察到基于ConvLSTM-α方法預(yù)測(cè)的分配結(jié)果反而有所下降，這是由于任務(wù)分配很大程度上依賴位置預(yù)測(cè)的結(jié)果，而ConvLSTM-α預(yù)測(cè)結(jié)果平均準(zhǔn)確度僅有21%，較差的預(yù)測(cè)準(zhǔn)確率會(huì)使分配得到的價(jià)值不穩(wěn)定.

Fig. 9 Performance comparison of task prediction under different training sets圖9 不同訓(xùn)練集下任務(wù)預(yù)測(cè)性能對(duì)比

Fig. 10 Performance comparison of worker prediction under different training sets圖10 不同訓(xùn)練集下工人預(yù)測(cè)性能對(duì)比

6.4 任務(wù)分配效果分析

本節(jié)實(shí)驗(yàn)評(píng)估本文提出的基于位置預(yù)測(cè)的任務(wù)分配算法的有效性，本節(jié)使用任務(wù)分配的總價(jià)值和分配對(duì)任務(wù)/工人間的平均距離評(píng)價(jià)分配策略的效果，使用計(jì)算分配所需的CPU時(shí)間評(píng)價(jià)分配策略的效率.對(duì)比算法選擇貪心分配算法(Greedy)和隨機(jī)分配算法(Random).除了2種基礎(chǔ)的對(duì)比算法，還實(shí)現(xiàn)了3種樸素對(duì)比算法，即3種預(yù)測(cè)算法不使用位置預(yù)測(cè)數(shù)據(jù)，在僅考慮當(dāng)前時(shí)刻任務(wù)/工人分布的情況下進(jìn)行分配.對(duì)比算法分別為：基于位置預(yù)測(cè)的任務(wù)分配算法(本文方法)、貪心分配算法(Greedy)、隨機(jī)分配算法(Random)，和不加位置預(yù)測(cè)的任務(wù)分配算法(本文方法-α)、不加預(yù)測(cè)的貪心分配算法(Greedy-α)、不加預(yù)測(cè)的隨機(jī)分配算法(Random-α).

Fig. 11 Comparison of task assignment performance under different datasets圖11 不同測(cè)試集下任務(wù)分配性能對(duì)比

1) 測(cè)試集大小的影響.實(shí)驗(yàn)選擇22～30天的數(shù)據(jù)作為測(cè)試集，訓(xùn)練集大小取值分別為1天，3天，5天，7天，9天.首先改變測(cè)試集的大小來研究分配算法的性能和時(shí)間效率，也即通過改變參加分配的任務(wù)和工人數(shù)量來測(cè)試算法.價(jià)值評(píng)估實(shí)驗(yàn)如圖11(a) 所示，所有算法分配得的總價(jià)值隨著測(cè)試集大小的增加而增長(zhǎng)；同時(shí)可以觀察到Random算法和Random-α算法計(jì)算得到的分配總價(jià)值最低，而本文提出任務(wù)分配算法得到的分配總價(jià)值最高，隨后是本文方法-α、Greedy和Greedy-α，這是由于本文方法在有任務(wù)無法被分配時(shí)，會(huì)考慮替換已有的分配實(shí)現(xiàn)更好的分配組合.總體上講，所有使用了位置預(yù)測(cè)算法效果均要比沒有使用預(yù)測(cè)的算法好，這是由于基于位置預(yù)測(cè)的分配算法從全局的角度進(jìn)行了分配.而Random-α在一些情況下優(yōu)于Random算法是由于隨機(jī)分配算法有較強(qiáng)的隨機(jī)性，實(shí)驗(yàn)結(jié)果均符合預(yù)期.圖11(b)所示為各算法時(shí)間對(duì)比，該部分統(tǒng)計(jì)的CPU時(shí)間是分配所消耗的總時(shí)間.隨著訓(xùn)練集的增大，各算法計(jì)算所用時(shí)間均呈線性增長(zhǎng)，因?yàn)?種算法的時(shí)間復(fù)雜度均與任務(wù)/工人數(shù)量相關(guān)，任務(wù)/工人數(shù)量的增加導(dǎo)致耗時(shí)增加.可以觀察到所有使用位置預(yù)測(cè)的算法時(shí)間消耗均高于不使用預(yù)測(cè)的算法，這是因?yàn)轭A(yù)測(cè)數(shù)據(jù)本身需要消耗時(shí)間，且預(yù)測(cè)得到的任務(wù)/工人也參與分配增加了3種算法要分配的任務(wù)數(shù)量.本文方法的耗時(shí)最高，這是尋找盡可能多的分配對(duì)需要消耗時(shí)間.圖11(c)為各分配對(duì)間的任務(wù)和工人間的平均距離變化情況.隨著訓(xùn)練集大小的增長(zhǎng)，Greedy算法和本文提出的任務(wù)分配算法的變化較為穩(wěn)定，基于位置預(yù)測(cè)的分配平均距離與不考慮位置預(yù)測(cè)的平均據(jù)接近，同樣穩(wěn)定.但Random算法的平均距離并不穩(wěn)定，這是因?yàn)殡S機(jī)分配有較強(qiáng)的隨機(jī)性，這種分配結(jié)果顯然效果較差，真實(shí)的空間眾包平臺(tái)中工人的移動(dòng)距離必然是越短越穩(wěn)定越好.Greedy算法和本文方法的平均距離接近，但Greedy算法的效果略優(yōu)，這是因?yàn)镚reedy算法為每個(gè)任務(wù)都分配了最近的工人，而本文方法為了分配更多的任務(wù)，選擇將一些工人分配給了較遠(yuǎn)的任務(wù)，這也是本文方法總分配價(jià)值遠(yuǎn)高于Greedy算法的原因.

2) 任務(wù)持續(xù)時(shí)間的影響.接下來通過改變?nèi)蝿?wù)持續(xù)時(shí)間測(cè)試分配方法的效果和效率，任務(wù)持續(xù)時(shí)間為高斯分布[

p

,

p

]區(qū)間內(nèi)隨機(jī)取值.如圖12(a)所示，隨著任務(wù)持續(xù)時(shí)間的增長(zhǎng)，所有方法的分配總價(jià)值均有增長(zhǎng)，這是由于任務(wù)有更長(zhǎng)的持續(xù)時(shí)間意味著原本無法被分配任務(wù)可以在更多的時(shí)間實(shí)例參與分配，使該任務(wù)更可能得到分配.本文分配方法同樣取得了最高的總價(jià)值，所有含位置預(yù)測(cè)的分配方法均要優(yōu)于不含位置預(yù)測(cè)的分配算法，可以證明本文方法的可行性，和預(yù)測(cè)方法的有效性.圖12(b)中統(tǒng)計(jì)的耗時(shí)為進(jìn)行一個(gè)時(shí)刻任務(wù)分配消耗的CPU時(shí)間.可以觀察到，隨著任務(wù)持續(xù)時(shí)間的增加，所有方法的計(jì)算分配所需的時(shí)間都有所增長(zhǎng)，這是因?yàn)槿蝿?wù)的持續(xù)時(shí)間增長(zhǎng)，導(dǎo)致任務(wù)的可用工人集變大，而分配算法的時(shí)間復(fù)雜度與可用工人集大小也有關(guān)，與預(yù)期結(jié)果相符.在最極端的情況下本文方法平均耗時(shí)也僅高于Random算法4.20 s，屬于可以接受的范圍.從圖12(c)中可以觀察到除Random算法外各算法的平均距離均較為穩(wěn)定，同樣證明了本文方法的可行性.3) 工人移動(dòng)速度的影響.實(shí)驗(yàn)通過改變工人移動(dòng)速度測(cè)試分配方法的效果和效率，工人移動(dòng)速度為高斯分布[

v

,

v

]區(qū)間內(nèi)隨機(jī)取值.圖13(a)中，隨著工人移動(dòng)速度增加，所有方法得到的分配總價(jià)值均有增長(zhǎng)，原因與任務(wù)持續(xù)時(shí)間增長(zhǎng)帶來的影響類似.工人移動(dòng)速度增加相等于增加了每個(gè)任務(wù)的可用工人集，而所有的分配算法均是在可用工人集上進(jìn)行的，更多的可用工人可能讓原本無法被分配的任務(wù)更可能得到分配，同樣這增加了需要計(jì)算的任務(wù)/工人數(shù)量，導(dǎo)致了圖13(b)中Random算法外所有算法的耗時(shí)均有明顯增加.圖13(c)所示本文分配算法計(jì)算得的工人平均移動(dòng)距離依舊穩(wěn)定.本文方法僅比Random算法平均多耗時(shí)僅為4.89 s的情況下，取得了優(yōu)于Greedy算法32.7%的分配價(jià)值和穩(wěn)定的工人移動(dòng)距離，可以證明本文方法的有效性.

Fig. 12 Comparison of task assignment performance under different time of duration圖12 不同持續(xù)時(shí)間下任務(wù)分配性能對(duì)比

Fig. 13 Comparison of task assignment performance under different movement speed of workers圖13 不同工人移動(dòng)速度下任務(wù)分配性能對(duì)比

7 結(jié)束語

本文提出一種解決空間眾包任務(wù)分配問題的方法，使用基于軌跡的任務(wù)位置預(yù)測(cè)模型和基于核密度估計(jì)的工人位置預(yù)測(cè)模型預(yù)測(cè)了未來時(shí)刻任務(wù)/工人的分布，設(shè)計(jì)了一種基于位置預(yù)測(cè)的任務(wù)分配方法來尋找盡可能好的分配.本文通過大量實(shí)驗(yàn)證實(shí)了所提方法的效率和有效性，任務(wù)預(yù)測(cè)和工人預(yù)測(cè)的準(zhǔn)確率優(yōu)于其他算法，且分配方法能取得遠(yuǎn)優(yōu)于基礎(chǔ)算法的分配效果.本文通過大量實(shí)驗(yàn)證實(shí)了所提方法的效率和有效性，任務(wù)預(yù)測(cè)和工人預(yù)測(cè)的準(zhǔn)確率優(yōu)于其他算法，且分配方法能取得遠(yuǎn)優(yōu)于基礎(chǔ)算法的分配效果.但在工人預(yù)測(cè)和分配工作中，沒能計(jì)算出預(yù)測(cè)工人的出現(xiàn)概率，只是在預(yù)測(cè)工人沒有出現(xiàn)的情況下盡可能早地把配對(duì)的任務(wù)重新分配，導(dǎo)致工人預(yù)測(cè)不精準(zhǔn)時(shí)分配效果變差.在未來進(jìn)一步研究中會(huì)針對(duì)該問題尋找更優(yōu)的解決辦法，研究更復(fù)雜情景中的任務(wù)分配方法，實(shí)現(xiàn)空間眾包中復(fù)雜任務(wù)(多個(gè)工人分配一個(gè)任務(wù))，及特定路線任務(wù)(根據(jù)工人移動(dòng)路線分配多個(gè)任務(wù))的分配方法.此外，將應(yīng)用文獻(xiàn)[24-27]中位置預(yù)測(cè)算法提高眾包任務(wù)分配的準(zhǔn)確性.

致謝

：本文實(shí)驗(yàn)部分使用的數(shù)據(jù)來自滴滴出行“蓋亞”數(shù)據(jù)開放計(jì)劃(Didi Chuxing GAIA Initiative).

作者貢獻(xiàn)聲明

：徐天承參與研究和文章撰寫，包括算法研究、設(shè)計(jì)論文框架、起草文章和實(shí)驗(yàn)等工作；喬少杰參與研究和文章撰寫，包括算法提出、設(shè)計(jì)研究方案、修訂論文和指導(dǎo)性支持等工作；武俊參與研究，包括采集整理數(shù)據(jù)統(tǒng)計(jì)分析和實(shí)施研究過程等工作；韓楠參與研究，包括采集整理數(shù)據(jù)、算法設(shè)計(jì)等工作；岳昆參與工作支持，包括理論基礎(chǔ)和數(shù)據(jù)支持；易玉根參與研究，包括數(shù)據(jù)采集與處理；黃發(fā)良參與工作支持，包括數(shù)據(jù)和實(shí)驗(yàn)支持；元昌安參與研究，包括算法設(shè)計(jì)及修訂研究方案.