基于序列化時空殘差網絡預測的順風型空間眾包任務分配算法

胡桂銀 翟東君

1(安徽師范大學計算機與信息學院 安徽 蕪湖 241008) 2(網絡與信息安全安徽省重點實驗室 安徽 蕪湖 241008) 3(蘇州大學計算機科學與技術學院 江蘇 蘇州 215006)

0 引 言

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

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

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

1 相關工作

1.1 任務分配

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

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

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

1.2 任務預測

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

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

2 預測模型

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

圖1 預測模型結構

2.1 任務分布圖

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

給出歷史記錄中的任務分布圖{X0,X1,…,Xt-1}，預測模型的目標就是預測下一時刻的任務分布圖Xt。

2.2 模型概覽

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

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

時間片粒度：{Xt-n,Xt-n+1,…,Xt-1}

(1)

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

(2)

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

(3)

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

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

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

(4)

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

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

Xl=Xl-1+F(X)

(5)

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

合并層用于將任務分布圖一幅一幅地按照順序吸收進模型組件。

(6)

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

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

(7)

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

3 算法設計

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

3.1 順風型任務訂單

在說明順風型任務訂單含義之前，給出一些相關定義。

任務訂單：用o=表示一個任務訂單，其中：os、oe代表了訂單的起始位置和終止位置；ot代表任務訂單的請求時間。

(8)

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

3.2 路徑規(guī)劃

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

(9)

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

3.3 順風型任務分配路徑規(guī)劃算法

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

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

(10)

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

(11)

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

(12)

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

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

(13)

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

算法1展示了所設計的順風型的任務分配路徑規(guī)劃算法的偽代碼。

算法1順風型任務分配的路徑規(guī)劃算法

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

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

4.計算每個任務的剩余可消耗時間RTi←CTi-STi-δ(v,oe)；

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

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

7.將(node,t,sum)壓入隊列，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′的前序點為node；

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

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

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

18.查詢路徑終點v的任務和的最大值，回溯得到路徑P；

19.returnP。

4 實驗與結果分析

4.1 數(shù)據集

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

表1 數(shù)據集

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

4.2 評估指標

本文中主要使用3個評估指標：任務平均等待時間、任務平均完成時間和獨立任務訂單占比。

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

(14)

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

(15)

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

(16)

4.3 實驗結果

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

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

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

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

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

綜上所述，放松任務完成效率比θ的限制可以降低任務平均等待時間和獨立訂單占比，雖然在一定程度上增加了任務平均完成時間，然而通過合理控制可以保證用戶的體驗。因此驗證了基于預測的順風型任務分配機制的有效性。

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

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

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

5 結 語

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