胡桂銀 翟東君

1(安徽師范大學(xué)計(jì)算機(jī)與信息學(xué)院 安徽 蕪湖 241008) 2(網(wǎng)絡(luò)與信息安全安徽省重點(diǎn)實(shí)驗(yàn)室 安徽 蕪湖 241008) 3(蘇州大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 江蘇 蘇州 215006)

0 引 言

隨著移動(dòng)設(shè)備的大量普及，空間眾包已經(jīng)從衣食住行各個(gè)方面融入人們的生活。相對(duì)于傳統(tǒng)眾包，空間眾包增加了對(duì)位置的相關(guān)約束，意味著工人需要移動(dòng)到指定的地點(diǎn)才能完成相應(yīng)的任務(wù)。配備了各種各樣傳感器的移動(dòng)設(shè)備的普及使得空間眾包融入到了人們的生活，由于空間眾包充分利用了工人的靈活性，且空間眾包的成本遠(yuǎn)遠(yuǎn)低于雇傭?qū)I(yè)人才，因此空間眾包具有廣泛的發(fā)展前景?？臻g眾包中最重要的研究方向是任務(wù)分配。任務(wù)分配是指在滿足一定約束的前提下，將空間眾包平臺(tái)收集到的任務(wù)分配給合適的工人，例如，外賣平臺(tái)將配送訂單的任務(wù)分配給合適的騎手。目前的相關(guān)研究大多集中在優(yōu)化空間眾包平臺(tái)的整體效益上，例如旅行開銷[1-2]、任務(wù)完成質(zhì)量[3-4]和任務(wù)分配數(shù)量[5-6]等。為了簡(jiǎn)化算法設(shè)計(jì)，目前大多數(shù)任務(wù)分配方法都假設(shè)平臺(tái)上的任務(wù)和工人是固定不變的。然而，在實(shí)際應(yīng)用中這種假設(shè)過于簡(jiǎn)單，無論是工人還是任務(wù)都在實(shí)時(shí)動(dòng)態(tài)地變化，這種動(dòng)態(tài)性與任務(wù)完成的質(zhì)量和效率息息相關(guān)。如果一個(gè)空間眾包系統(tǒng)在進(jìn)行任務(wù)分配時(shí)僅考慮當(dāng)前時(shí)刻系統(tǒng)內(nèi)的工人和任務(wù)，無論采取哪一種任務(wù)分配機(jī)制，都只能達(dá)到局部最優(yōu)解。如果能捕捉到空間眾包中動(dòng)態(tài)性并用于任務(wù)分配，那么將會(huì)形成一種三贏的局面：工人可以提前到達(dá)任務(wù)現(xiàn)場(chǎng)，完成更多的任務(wù)；任務(wù)發(fā)布者的任務(wù)會(huì)被更快地完成，從而具有更好的用戶體驗(yàn)；平臺(tái)能夠有效配置工人資源，提高平臺(tái)的總收益。

如果平臺(tái)想提供更優(yōu)質(zhì)的服務(wù)，必須考慮工人和任務(wù)在將來一段時(shí)間內(nèi)是如何分布的，即考慮工人和任務(wù)的預(yù)測(cè)問題。為了利用預(yù)測(cè)信息，兼顧工人、任務(wù)發(fā)布者和平臺(tái)三方的收益，需要設(shè)計(jì)一種合理的任務(wù)分配機(jī)制。

基于上述動(dòng)機(jī)，本文設(shè)計(jì)一種同時(shí)考慮多方利益的任務(wù)分配機(jī)制?；陬A(yù)測(cè)信息設(shè)計(jì)了合理的路徑規(guī)劃方案來提高工人順風(fēng)型任務(wù)所獲得的任務(wù)訂單數(shù)量，同時(shí)為了保證任務(wù)發(fā)布者的用戶體驗(yàn)，按一定的任務(wù)完成效率比來限制工人不能無限制地行動(dòng)，進(jìn)而防止任務(wù)完成時(shí)間無限制延長。通過實(shí)驗(yàn)驗(yàn)證了模型的有效性。

1 相關(guān)工作

1.1 任務(wù)分配

任務(wù)分配一般分為兩種模式：服務(wù)器分配模式(SAT)和工人自主選擇模式(WST)。WST模式是指服務(wù)器發(fā)布空間眾包任務(wù)，工人直接選擇任務(wù)去執(zhí)行。SAT模式則是由服務(wù)器收集工人信息并且基于這些信息為工人分配任務(wù)。

在WST模式下如文獻(xiàn)[7-8]允許用戶瀏覽和接收可接受的空間任務(wù)。這種模式不需要用戶上傳自己的隱私數(shù)據(jù)，在一定程度上可以保護(hù)用戶的隱私，但是會(huì)造成獎(jiǎng)勵(lì)低或者距離遠(yuǎn)的任務(wù)長期不被工人選擇完成的情況。在SAT模式下如文獻(xiàn)[9]給出了一種考慮簡(jiǎn)單度量標(biāo)準(zhǔn)的解決方案，比如最大化服務(wù)器端分配任務(wù)的數(shù)量。文獻(xiàn)[10]提出了一種基于離線指導(dǎo)的在線任務(wù)分配框架，將離線預(yù)測(cè)方法與實(shí)時(shí)任務(wù)分配策略相結(jié)合，能夠在維持高效任務(wù)分配效率的同時(shí)最大化任務(wù)分配數(shù)量。文獻(xiàn)[11]考慮了移動(dòng)用戶可能拒絕執(zhí)行眾包平臺(tái)分配的任務(wù)這一情況，提出了最大化任務(wù)接受率的問題，并設(shè)計(jì)了兩種任務(wù)分配機(jī)制來解決這一問題。文獻(xiàn)[12]考慮如何使得任務(wù)發(fā)布者和工人雙方利益最大化。

與WST相比，SAT能夠從更加全局的視角控制任務(wù)分配，為每個(gè)工人提供均衡的工作負(fù)載，因此SAT更加受到研究者的重視。然而無論WST還是SAT，這些方法都沒有很好地利用預(yù)測(cè)信息，也沒有同時(shí)考慮工人、任務(wù)發(fā)布者和平臺(tái)三方的利益。

1.2 任務(wù)預(yù)測(cè)

在實(shí)際生產(chǎn)生活中，任務(wù)通常是隨機(jī)動(dòng)態(tài)到達(dá)的，因此增加了預(yù)測(cè)的困難性。機(jī)器學(xué)習(xí)近年來被廣泛地應(yīng)用于各種各樣的預(yù)測(cè)問題。深度神經(jīng)網(wǎng)絡(luò)，例如卷積神經(jīng)網(wǎng)絡(luò)(CNN)、循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)使得對(duì)具有復(fù)雜時(shí)空特性的問題的建模變得簡(jiǎn)單。在空間眾包的相關(guān)問題研究中，文獻(xiàn)[13-14]對(duì)工人從接收到任務(wù)到到達(dá)任務(wù)地點(diǎn)所需的旅行時(shí)間進(jìn)行了預(yù)測(cè)。文獻(xiàn)[15-16]對(duì)降水概率進(jìn)行了預(yù)測(cè)。文獻(xiàn)[17]對(duì)人員流動(dòng)性進(jìn)行了預(yù)測(cè)。

文獻(xiàn)[18]將一整個(gè)城市區(qū)域劃分為網(wǎng)格，提出了一個(gè)名為ST-ResNet的模型對(duì)不同網(wǎng)格區(qū)域上進(jìn)出車流量分別進(jìn)行了預(yù)測(cè)。其中，模型運(yùn)用卷積神經(jīng)網(wǎng)絡(luò)對(duì)空間依賴性進(jìn)行建模，使得模型可以學(xué)習(xí)到任意兩個(gè)區(qū)域間的相關(guān)性，然而卻忽略了對(duì)時(shí)間依賴性的建模。文獻(xiàn)[19]使用局部卷積神經(jīng)網(wǎng)絡(luò)對(duì)具有強(qiáng)相關(guān)性的近鄰區(qū)域進(jìn)行建模，對(duì)于弱相關(guān)性的區(qū)域使用了表示學(xué)習(xí)的方法來刻畫整個(gè)區(qū)域的語義信息，對(duì)于時(shí)間依賴性的建模使用了長短期記憶神經(jīng)網(wǎng)絡(luò)。然而在研究過程中，可以發(fā)現(xiàn)在任務(wù)預(yù)測(cè)問題中，長短期記憶神經(jīng)網(wǎng)絡(luò)無法很好地捕獲時(shí)間依賴性。

2 預(yù)測(cè)模型

本節(jié)介紹使用的預(yù)測(cè)模型——序列化時(shí)空殘差網(wǎng)絡(luò)[20]SeqST-ResNet(Sequential Spatial Temporal ResNet)——是一種深度神經(jīng)網(wǎng)絡(luò)模型，如圖1所示，用于捕獲序列化的時(shí)間和空間特征。

圖1 預(yù)測(cè)模型結(jié)構(gòu)

2.1 任務(wù)分布圖

由于準(zhǔn)確地預(yù)測(cè)任務(wù)的出現(xiàn)時(shí)間和地點(diǎn)十分困難，在該模型中將預(yù)測(cè)目標(biāo)松弛到預(yù)測(cè)特定時(shí)空范圍內(nèi)的任務(wù)出現(xiàn)次數(shù)。將一個(gè)特定區(qū)域的地圖劃分為H×W的網(wǎng)格。其中H和W的數(shù)值由需求決定。這種網(wǎng)格劃分在很多時(shí)空問題中得到了廣泛的應(yīng)用。任務(wù)分布圖是由每個(gè)網(wǎng)格中特定時(shí)空范圍出現(xiàn)次數(shù)組成的矩陣X。

給出歷史記錄中的任務(wù)分布圖{X0,X1,…,Xt-1}，預(yù)測(cè)模型的目標(biāo)就是預(yù)測(cè)下一時(shí)刻的任務(wù)分布圖Xt。

2.2 模型概覽

模型主要包括五個(gè)部分：輸入層、卷積層、殘差單元、合并層和融合層。

組件的輸入層是任意一種粒度的序列數(shù)據(jù)，如下：

時(shí)間片粒度：{Xt-n,Xt-n+1,…,Xt-1}

(1)

周級(jí)粒度：{Xt-n×p,Xt-(n-1)×p,…,Xt-p}

(2)

天級(jí)粒度：{Xt-n×q,Xt-(n-1)×q,…,Xt-q}

(3)

式中：p=48，q=48×7，表示將每一天劃分為48個(gè)時(shí)間片，每一周劃分為48×7個(gè)時(shí)間片。

卷積層可以用來捕獲空間依賴性信息，任務(wù)分布圖可以看作一幅圖片，經(jīng)過卷積層后的輸出如下:

X(1)=f(W*X(0)+b)

(4)

式中：W和b為模型學(xué)習(xí)到的參數(shù)；*表示矩陣的哈達(dá)瑪乘積運(yùn)算。

形式上，殘差單元可以給出如下定義：

Xl=Xl-1+F(X)

(5)

式中：Xl和Xl-1分別代表了一個(gè)殘差單元的輸出和輸入；函數(shù)F(·)是一個(gè)包含了很多卷積層、BN(Batch Normalization)操作以及一ReLU激活函數(shù)的殘差函數(shù)。BN操作具有很多優(yōu)點(diǎn)，包括訓(xùn)練更快、可以設(shè)置更高的學(xué)習(xí)率、易初始化網(wǎng)絡(luò)權(quán)重、具有正則化效果、提高網(wǎng)絡(luò)性能等。

合并層用于將任務(wù)分布圖一幅一幅地按照順序吸收進(jìn)模型組件。

(6)

融合層用一種簡(jiǎn)單的基于參數(shù)矩陣的方法合并三個(gè)序列的輸出，令Xc、Xp、Xq分別為時(shí)間片粒度、周級(jí)粒度和天級(jí)粒度的輸出，則融合層輸出為：

Xout=Wc×Xc+Wp×Xp+Wq×Xq

(7)

預(yù)測(cè)模型使用Adam優(yōu)化算法，學(xué)習(xí)速率設(shè)定為0.003，批處理大小設(shè)定為16，卷積核的大小為3×3，對(duì)于每種粒度的輸入層序列數(shù)據(jù)長度設(shè)定為3，殘差單元L長度設(shè)定為5，更多模型細(xì)節(jié)請(qǐng)參照文獻(xiàn)[20]。

3 算法設(shè)計(jì)

本節(jié)研究并提出一種任務(wù)分配算法，能夠合理地利用預(yù)測(cè)模型產(chǎn)生的預(yù)測(cè)信息為工人合理規(guī)劃路線，同時(shí)考慮了任務(wù)發(fā)布者的用戶體驗(yàn)問題，對(duì)任務(wù)訂單的完成效率比設(shè)定了限制。

3.1 順風(fēng)型任務(wù)訂單

在說明順風(fēng)型任務(wù)訂單含義之前，給出一些相關(guān)定義。

任務(wù)訂單：用o=表示一個(gè)任務(wù)訂單，其中：os、oe代表了訂單的起始位置和終止位置；ot代表任務(wù)訂單的請(qǐng)求時(shí)間。

(8)

當(dāng)任意兩個(gè)任務(wù)訂單同時(shí)被分配給一個(gè)工人時(shí)，為了保證所有用戶的用戶體驗(yàn)，空間眾包平臺(tái)為工人所規(guī)劃的訂單必須保證任意任務(wù)訂單的完成效率比不能夠超過一定閾值θ。為了保證這一限制，當(dāng)想要為工人分配一個(gè)新任務(wù)訂單時(shí)，需要考慮新任務(wù)訂單是否與原本所有任務(wù)訂單均兼容。為此提出順風(fēng)型任務(wù)分配和順風(fēng)型任務(wù)訂單的概念：順風(fēng)型的任務(wù)分配是指在與工人完成當(dāng)前所進(jìn)行的任務(wù)訂單的路徑、時(shí)間不沖突的條件下進(jìn)行任務(wù)分配，一個(gè)任務(wù)訂單與其他訂單兼容(不沖突)可以稱作原訂單的順風(fēng)型任務(wù)訂單。

3.2 路徑規(guī)劃

為了使工人能夠盡可能多地獲得順風(fēng)型任務(wù)訂單，需要基于預(yù)測(cè)信息給工人提供指導(dǎo)，即為工人提供一個(gè)路徑規(guī)劃，使得路徑上所有區(qū)域上在目標(biāo)時(shí)刻的預(yù)測(cè)的任務(wù)分布圖中的任務(wù)數(shù)量最大，即優(yōu)化目標(biāo)為：

(9)

式中：E(pi)為目標(biāo)時(shí)刻任務(wù)分布圖的預(yù)測(cè)結(jié)果Xt中pi區(qū)域的任務(wù)數(shù)量；pi∈P,P={p1,p2,…，pn}。

3.3 順風(fēng)型任務(wù)分配路徑規(guī)劃算法

本文采用動(dòng)態(tài)規(guī)劃來解決路徑規(guī)劃問題。

令O={o1,o2,…，on}為工人當(dāng)前擁有的任務(wù)訂單集合，工人一直遵循之前所規(guī)劃的路徑，到達(dá)了某個(gè)點(diǎn)，此時(shí)恰好有個(gè)新任務(wù)到來o=，此時(shí)若假設(shè)該訂單可分配給工人。首先考慮下一個(gè)需要到達(dá)的任務(wù)終點(diǎn)，選擇從當(dāng)前位置os以最快的旅行時(shí)間能夠到的任務(wù)終點(diǎn)oe′為工人下一個(gè)需要到達(dá)的任務(wù)點(diǎn)，即：

(10)

此時(shí)需要計(jì)算新任務(wù)訂單是否滿足順風(fēng)型任務(wù)分配策略，首先需要計(jì)算完成任務(wù)的時(shí)間上限CTi(Cell Time)為：

(11)

那么，為了完成后續(xù)每個(gè)任務(wù)所剩余的可消耗時(shí)間RTi(RemainTime)為：

(12)

那么此時(shí)需要為os到oe′之間規(guī)劃順風(fēng)型任務(wù)訂單數(shù)量期望最大的路徑。用t表示從os到某一點(diǎn)u所需的旅行時(shí)間，令node是與點(diǎn)u相連的一條邊的另一端點(diǎn)，若t+δ(u,node)

count(node)=count(u)+w(node)

(13)

式中：w(node)表示node的任務(wù)預(yù)測(cè)數(shù)量。

算法1展示了所設(shè)計(jì)的順風(fēng)型的任務(wù)分配路徑規(guī)劃算法的偽代碼。

算法1順風(fēng)型任務(wù)分配的路徑規(guī)劃算法

輸入：路網(wǎng)信息G=(V,E)，G中任意一點(diǎn)v的任務(wù)預(yù)測(cè)數(shù)量w(v),任務(wù)完成效率比θ,工人w所擁有的訂單集合O={o1,o2,…，on},新到來訂單o=。

輸出：規(guī)劃路徑P。

4.計(jì)算每個(gè)任務(wù)的剩余可消耗時(shí)間RTi←CTi-STi-δ(v,oe)；

5.剩余可消耗時(shí)間RT←min←(RTi)；

6.初始化搜索隊(duì)列Q=?，搜索節(jié)點(diǎn)node←u,u到搜索節(jié)點(diǎn)已花費(fèi)的時(shí)間為t←0,任務(wù)數(shù)量和sum←0

7.將(node,t,sum)壓入隊(duì)列，Q.PUSH(node,t,sum)

8.whileQ≠?do

9.(node,t,sum)←Q.POP()；

10.ifnode≠vthen

11.查詢圖G中與node相連的邊的集合，E′←(node,node′)∈E；

12.forei∈E′do

13.ift+δ(ei)

14.記錄node′的前序點(diǎn)為node；

15.記錄從u到node的旅行時(shí)間為t+δ(ei)；

16.記錄任務(wù)數(shù)量和為sum+w(node′)；

17.Q.PUSH(node′,t+δ(ei),sum+w(node′))；

18.查詢路徑終點(diǎn)v的任務(wù)和的最大值，回溯得到路徑P；

19.returnP。

4 實(shí)驗(yàn)與結(jié)果分析

4.1 數(shù)據(jù)集

本文使用的數(shù)據(jù)集收集自成都市出租車服務(wù)請(qǐng)求數(shù)據(jù)。該數(shù)據(jù)集由滴滴蓋亞計(jì)劃[37]提供。數(shù)據(jù)集如表1所示。

表1 數(shù)據(jù)集

預(yù)測(cè)信息由預(yù)測(cè)模型SeqST-ResNet生成，隨機(jī)抽取軌跡數(shù)據(jù)中的部分?jǐn)?shù)據(jù)作為工人的上線位置，工人數(shù)量限制為[2 000,4 000,6 000,8 000,10 000]，用軌跡數(shù)據(jù)中從一個(gè)網(wǎng)格u到另一個(gè)網(wǎng)格v的平均時(shí)間作為旅行時(shí)間δ(u,v)。由于所使用的數(shù)據(jù)為出租車軌跡數(shù)據(jù)，將每個(gè)工人的負(fù)載上限設(shè)置為4。

4.2 評(píng)估指標(biāo)

本文中主要使用3個(gè)評(píng)估指標(biāo)：任務(wù)平均等待時(shí)間、任務(wù)平均完成時(shí)間和獨(dú)立任務(wù)訂單占比。

任務(wù)平均等待時(shí)間：一個(gè)任務(wù)訂單o=從發(fā)布到被分配給工人的時(shí)間稱為任務(wù)等待時(shí)間，直觀上，當(dāng)任務(wù)完成效率比θ的限制寬松時(shí)，會(huì)使得任務(wù)平均等待時(shí)間降低。令對(duì)應(yīng)的分配時(shí)間為oa，那么對(duì)于任務(wù)集合O={o1,o2,…，on}，任務(wù)平均等待時(shí)間為：

(14)

任務(wù)平均完成時(shí)間:任務(wù)從開始執(zhí)行到執(zhí)行完成所需要的時(shí)間稱為任務(wù)完成時(shí)間，直觀上，當(dāng)任務(wù)完成效率比θ的限制寬松時(shí)，由于工人會(huì)探索任務(wù)數(shù)量較大的區(qū)域，因此會(huì)使得任務(wù)平均完成時(shí)間變長。令對(duì)應(yīng)的任務(wù)開始執(zhí)行時(shí)間為ob，任務(wù)的完成時(shí)間點(diǎn)為of，則任務(wù)平均完成時(shí)間為：

(15)

獨(dú)立任務(wù)訂單占比:一個(gè)任務(wù)從分配給一個(gè)工人到該工人完成任務(wù)這一時(shí)間段內(nèi)，工人沒有被分配其他任務(wù)，那么稱該任務(wù)為一個(gè)獨(dú)立任務(wù)。為了提高工人的利用效率，需要盡可能地降低獨(dú)立任務(wù)訂單占比，為此需要設(shè)置合理的任務(wù)完成效率比。令NUMit為獨(dú)立任務(wù)訂單數(shù)量，則獨(dú)立任務(wù)訂單占比為：

(16)

4.3 實(shí)驗(yàn)結(jié)果

(1) 任務(wù)完成效率比θ的影響。在該實(shí)驗(yàn)中固定工人數(shù)量為6 000，探究任務(wù)完成效率比θ的影響。

如圖2(a)所示，可以發(fā)現(xiàn)對(duì)于任務(wù)平均等待時(shí)間，θ越大時(shí)，任務(wù)平均等待時(shí)間越小，這是由于當(dāng)任務(wù)完成效率比要求不大時(shí)，會(huì)為工人規(guī)劃任務(wù)數(shù)量和更大的路徑，當(dāng)工人以這種路徑進(jìn)行任務(wù)時(shí)會(huì)產(chǎn)生更多的順風(fēng)型任務(wù)訂單，因此任務(wù)的平均等待時(shí)間會(huì)隨著θ的增大而縮短。同時(shí)，可以發(fā)現(xiàn)當(dāng)θ增大到一定程度時(shí)，任務(wù)平均等待時(shí)間的下降程度變小了，這是由于當(dāng)θ增大到一定程度時(shí)，雖然任務(wù)訂單期望和會(huì)變大，但是工人的負(fù)載上限限制了平均等待時(shí)間的優(yōu)化。

(a) b) (c)圖2 任務(wù)完成效率比θ的影響

如圖2(b)所示，任務(wù)的平均完成時(shí)間隨著θ值增加而變長，這和預(yù)想的一樣，在現(xiàn)實(shí)情況中，任務(wù)完成效率比的要求越低，工人就可以花費(fèi)更多時(shí)間去尋找更多的順風(fēng)型任務(wù)，但是會(huì)使得任務(wù)完成時(shí)間變長。在用戶允許的時(shí)間范圍內(nèi)，這種策略是可以接受的，因?yàn)轫橈L(fēng)型的訂單會(huì)使得工人在一定程度上降低成本，例如可以降低油耗。

如圖2(c)所示，獨(dú)立訂單的占比隨著θ的增加而降低。假設(shè)一個(gè)任務(wù)十分緊迫，不允許工人為了獲得更高收益而去搜尋任務(wù)期望更高的區(qū)域，那么該任務(wù)很可能獨(dú)占該工人?，F(xiàn)實(shí)生活中這種情況是存在的，很多用戶為了快速到達(dá)目的地，不愿意進(jìn)行拼車，同時(shí)會(huì)在存在繞路情況時(shí)給出差評(píng)。當(dāng)然，也有很多時(shí)間不緊迫的乘客在獲得司機(jī)降低收費(fèi)的承諾下同意拼單。同任務(wù)平均等待時(shí)間的趨勢(shì)一樣，當(dāng)θ增大到一定程度時(shí)，獨(dú)立任務(wù)訂單的占比下降變緩，也是由于工人負(fù)載到達(dá)了上限。

綜上所述，放松任務(wù)完成效率比θ的限制可以降低任務(wù)平均等待時(shí)間和獨(dú)立訂單占比，雖然在一定程度上增加了任務(wù)平均完成時(shí)間，然而通過合理控制可以保證用戶的體驗(yàn)。因此驗(yàn)證了基于預(yù)測(cè)的順風(fēng)型任務(wù)分配機(jī)制的有效性。

(2) 工人數(shù)量的影響。在該實(shí)驗(yàn)中，固定閾值θ=1.6。如圖3(a)所示，隨著工人數(shù)量的增長，任務(wù)平均等待時(shí)間會(huì)有顯著的縮短，這符合實(shí)際情況。當(dāng)工人數(shù)量嚴(yán)重不足時(shí)會(huì)使得用戶等待時(shí)間增長，參考雨雪天氣時(shí)打車排隊(duì)時(shí)間無限延長，此時(shí)不同的預(yù)測(cè)方法帶來的優(yōu)化效果幾乎沒有差別，這是由于訂單的大量積壓導(dǎo)致供不應(yīng)求，在很多區(qū)域都會(huì)有很多積壓訂單，當(dāng)工人未達(dá)到負(fù)載上限時(shí)，會(huì)立即分配訂單。

圖3 工人數(shù)量的影響

如圖3(b)所示，工人數(shù)量對(duì)任務(wù)平均完成時(shí)間的影響不大，這是由于，在θ足夠大時(shí)，可以為工人規(guī)劃路徑使得路徑上產(chǎn)生的任務(wù)訂單足夠到達(dá)他們負(fù)載上限。觀察圖3(c)，在θ足夠大時(shí)，路徑上產(chǎn)生的訂單足夠到達(dá)工人的負(fù)載上限，在工人數(shù)量較少時(shí)負(fù)載上限更容易達(dá)到，對(duì)于當(dāng)前θ，當(dāng)工人數(shù)量增加時(shí)，獨(dú)立訂單占比會(huì)略有上升。

5 結(jié) 語

本文提出一種基于序列化時(shí)空殘差網(wǎng)絡(luò)預(yù)測(cè)的順風(fēng)型任務(wù)分配算法。該機(jī)制設(shè)計(jì)一種路徑規(guī)劃方案來同時(shí)兼顧工人、任務(wù)發(fā)布者、平臺(tái)三方的收益。對(duì)于工人，平臺(tái)通過指導(dǎo)工人可以使其更早地到達(dá)任務(wù)現(xiàn)場(chǎng)，工人可以獲得更多的任務(wù)獲得更多的收益；對(duì)于任務(wù)發(fā)布者，一方面任務(wù)發(fā)布者的任務(wù)可以被更早地分配，另一方面通過任務(wù)完成效率比θ限制了工人在期望提高個(gè)人收益時(shí)需要考慮已有訂單的完成效率，保證了任務(wù)發(fā)布者的用戶體驗(yàn)；對(duì)于平臺(tái)，能夠有效地配置工人資源，提高平臺(tái)的總收益。通過在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)證明了該任務(wù)分配機(jī)制的有效性。