高麗萍,張祥磊,高 麗

1(上海理工大學 光電信息與計算機工程學院,上海 200093)

2(復旦大學 上海數(shù)據(jù)科學重點實驗室,上海 200093)

3(上海理工大學 圖書館,上海 200093)

1 引 言

近年來,移動設備的普遍性和用戶的移動性推動共享經(jīng)濟的發(fā)展,在這種經(jīng)濟中,工作者接受平臺上發(fā)布的且感興趣的任務,以換取一定的報酬.這也促成一種新的分布式問題的解決模式——空間眾包.空間眾包在現(xiàn)實世界中有很多應用,比如報告超市特定產(chǎn)品的價格,在固定地點拍照或現(xiàn)場驗證數(shù)據(jù)[1].它的顯著特點是要求工人在特定的時間前往某個地點或某個區(qū)域完成任務.

以往的多數(shù)研究是基于點任務研究任務分配的,比如外賣配送,固定地點拍照等.大多數(shù)的點任務只需要一人就可以完成,但是區(qū)域任務[2]的特點一般為面積大,執(zhí)行過程復雜且困難,如公園空氣污染檢測,檢測某條道路的交通動態(tài)以及收集某地區(qū)的噪聲等,而像這種任務還需要大量的響應來確保最終結(jié)果的準確性,所以區(qū)域任務需要多個工人去執(zhí)行.由于人力資源有限,這就需要為一個工人分配多個任務或一個任務由多個工人來完成高質(zhì)量,低響應的區(qū)域任務.此外,區(qū)域任務還會涉及到跨區(qū)域的問題,為了鼓勵用戶接受跨區(qū)域的眾包任務,可以通過相應的激勵策略來鼓勵用戶接受跨區(qū)域任務.

在當前的云計算和大數(shù)據(jù)的背景下,不同功能的邊緣設備可以通過自身攜帶的傳感器與任務分配中心的服務器進行協(xié)作[3].由于邊緣設備和遠程的主服務器之間的距離較遠,這會增加邊緣設備的延遲.在這種情況下,眾包任務的參與者在不同時間不同地區(qū)參與眾包過程,使得眾包的范圍不斷擴大,從而大量的數(shù)據(jù)涌入到主服務器,當中心服務器發(fā)生宕機時,會造成短時間內(nèi)服務不可用.由于會產(chǎn)生低時延和服務不可用的問題,提出一種利用從服務器來解決這一問題的方案,從服務器具有靈活性和可擴展性,可以幫助眾包平臺通過不同的節(jié)點協(xié)調(diào)不同區(qū)域的任務.這樣既能解決邊緣設備與服務器的低時延問題,還可以避免主服務器造成單點故障時服務不可用的問題.

空間眾包的任務分配可以分為離線分配和在線分配模型[4],離線分配是指在分配前已經(jīng)獲取到工人和任務的所有信息(如到達順序,地點等),但是這種離線模型沒有考慮到動態(tài)工人和任務的移動性,而且在一些實際場景中并不可用.在在線任務分配過程中,工人或任務的數(shù)量是高度波動的,而任務請求必須在特定的時間內(nèi)提供響應,由于本文研究對區(qū)域任務進行任務分配,區(qū)域任務和工人的信息是未知的,所以本文研究的是一個在線分配問題.

與先前的空間眾包研究不同,跨區(qū)域在線多任務分配(Cross Regional Online Multi-task Allocation,CROMA)問題需要設計一種在預算和時間約束下,能夠保證質(zhì)量得分的區(qū)域任務在線分配方法,該方法需要將未來時間到達的工人或任務考慮其中進行任務分配,并且如果同一區(qū)域內(nèi)存在剩余任務,將會進行一個跨區(qū)域分配,保證每個任務能夠完成.具體來說,本文貢獻如下:

·本文提出在預算和時間約束下,通過工人移動來跨區(qū)域接受任務的問題,并設計了一個基于邊緣服務器的在線任務分配框架來將空間眾包活動分成多個階段.該框架通過最大化工人完成任務所產(chǎn)生的質(zhì)量分數(shù)來選擇合適的工人任務分配對.

·針對CROMA問題,對系統(tǒng)框架的多個階段提出對應的算法.首先,通過歷史的離線數(shù)據(jù)對任務和工人進行預分配,提出一種預分配算法用于后續(xù)的在線算法.然后,根據(jù)預分配結(jié)果和工人的可移動性,進行同一區(qū)域內(nèi)分配和全局分配,提出一種基于移動工人預分配的在線多任務分配,該算法中通過激勵機制鼓勵工人接受跨區(qū)域的任務.由于本文的研究重點是區(qū)域任務的任務分配,所以提出一種任務分解算法將區(qū)域任務分解為多個子區(qū)域,最終通過粒子群優(yōu)化算法來完成最終分配.

·最后,在不同的預算,不同最大可接受任務數(shù),不同工人數(shù)量,不同任務數(shù)量以及激勵機制的權(quán)重參數(shù)不同的情況下,通過真實數(shù)據(jù)集對提出的算法在總質(zhì)量得分和運行時間方面與4種其他算法進行了評估,從而驗證了本文算法的有效性和效率.

2 相關(guān)工作

2.1 離線任務分配

Boutsis等人[5]提出了一種離線任務分配方法,該方法滿足最大化眾包任務中正確響應的概率和在任務期限內(nèi)接收響應的概率,但這對于執(zhí)行需要實時信息的空間任務是不現(xiàn)實的.Xia等人[6]為了使供應鏈平臺尋找利潤最大化的任務分配,提出了利潤驅(qū)動任務分配問題,并建立了一個帶有任務時間約束的任務定價模型,通過一種基于樹分解位置的優(yōu)化算法來實現(xiàn)最優(yōu)分配.在平臺的預算約束下,為了最大化工人任務分配對的數(shù)量,Liu等人[7]提出了一種基于閾值的貪婪算法,該算法利用隨機生成的閾值來剪枝具有較大預算成本的匹配對,隨后對該算法進行了改進,使其從歷史數(shù)據(jù)中學習最優(yōu)閾值來剪枝高成本的匹配對.Menatalla等人[8]討論了移動眾包系統(tǒng)中多工人多任務分配問題,提出了一個基于組的多任務工人選擇的模型,通過遺傳算法將一組工人分配給任務集群,再使用禁忌搜索算法將工人分配給集群內(nèi)的單個任務來最大化任務完成質(zhì)量和最小化任務完成時間.

上述的算法是基于離線數(shù)據(jù)進行的全局任務分配,雖然依據(jù)離線數(shù)據(jù)會產(chǎn)生好的效果,但是實際上,空間眾包中的大多數(shù)任務分配都是使用在線任務分配模型.

2.2 在線任務分配

在線任務分配是指預先未知工人和任務的信息,來進行工人和眾包任務的分配.為了保證任務分配的全局最優(yōu),本文目標是通過考慮當前和未來工人/任務來進行全局分配.Cheng等人[9]定義一個最大質(zhì)量任務分配(MQA)問題,設計了一種基于網(wǎng)格的預測方法來預測未來工人/任務的空間分布,將在線場景轉(zhuǎn)換為離線場景,從而達到已知工人或任務的信息,并提出了MQA貪婪算法和MQA分治算法去解決該問題.為了保證任務分配的總體質(zhì)量,Miao等人[10]研究了移動眾包中的質(zhì)量感知在線任務分配(QAOTA)問題,提出了一個測量任務質(zhì)量的概率模型和描述工人行為的搭便車模型.Qian等人[11]過將在線場景轉(zhuǎn)換為離線場景,提出了一種自適應批處理機制,使用合適的時間戳,將分配過程劃分為多個時間間隔,每個時間間隔的工人和任務的信息是已知的.Chen等人[12]在動態(tài)場景下研究了最小化最大延遲空間眾包(MMD-SC)問題,其中考慮到了工人的旅行成本和任務的緩沖時間,提出了一種基于空間嵌入的雙邊在線隨機算法.在Boutsis等人[5]的研究中,提出了一種多目標在線任務分配機制,該機制利用遺傳算法來識別任務和工人之間的最佳匹配,從而使平臺和工人的效用最大化.

2.3 邊緣服務器

邊緣服務器是建立在邊緣計算器上的服務器.基于云計算技術(shù)和邊緣計算能力,邊緣服務器可以作為主服務器的延展,將計算,存儲等服務擴展到邊緣服務器上.邊緣服務器可以實現(xiàn)多種功能,包括存儲,通信等.Li等人[13]通過提出一種在超密集網(wǎng)絡中部署邊緣服務器的優(yōu)化部署和分配策略,以最小化服務提供商的成本并保證服務完成時間.Wang 等人[14]關(guān)注如何在城市中通過邊緣服務器來優(yōu)化移動邊緣計算網(wǎng)絡性能,文章將該問題描述為一個多目標約束優(yōu)化問題,目標是平衡邊緣服務器的負載并最小化移動用戶與邊緣服務器之間的訪問延遲.Zhang等人[15]提出了一種基于預測的在線任務分配算法,該算法是一種雙階段圖形驅(qū)動的雙邊分配策略,通過邊緣服務器和二部圖來完成任務分配.

3 相關(guān)概念和系統(tǒng)框架

在本節(jié)中,本文將介紹使用的相關(guān)定義和系統(tǒng)框架,并且定義了本文所解決的問題.

定義1.動態(tài)工人

空間眾包系統(tǒng)中包括一組眾包工人,表示為w∈W,他們在平臺注冊后接收和完成v任務請求者發(fā)布的任務,每個工人都與一組屬性相關(guān)聯(lián),這些屬性表示為w=〈lw,rw,nw,vw,bw〉,其中l(wèi)w表示工人當前的位置,rw表示工人可接受的任務范圍的半徑,nw表示工人可以接受的最大任務數(shù),vw表示工人的移動速度,bw表示工人在bw時進入平臺.在本文中,假設工人在任意時刻可以自由的加入或離開眾包系統(tǒng).

定義2.區(qū)域任務

請求者發(fā)布在空間眾包系統(tǒng)中的每個區(qū)域任務t∈T都與一組屬性關(guān)聯(lián),這些屬性為t=〈idt,lt,areat,σt,bt,et〉,其中idt表示任務的唯一標識符,lt表示任務進入平臺所指的位置,areat表示該區(qū)域任務的面積,σt表示完成該任務所需的時間,bt和et分別表示任務在bt時刻進入平臺,需要在截止時間et之前完成.

定義3.工人任務分配集

在本文中假設每個工人可以接受多個任務,一個區(qū)域任務也可以被多個工人接受.工人任務分配集Cp是由一組工人集W和一組區(qū)域任務集T中選擇合適的工人和任務形成匹配對產(chǎn)生的,形式為〈wi,tj〉,其中每個分配對都與一個質(zhì)量分數(shù)q(wi,tj)(見定義3)和一個旅行成本bij所關(guān)聯(lián),如下:

bij=C×dis(lw,lt)

(1)

其中C為每英里的單位成本,dis(lw,lt)為工人和任務位置之間的距離.

定義4.整體質(zhì)量得分

通過每個工人對任務的距離和時間的不同權(quán)重來計算完成任務的質(zhì)量分數(shù):

(2)

Q(w,t)=∑?〈wi,tj〉∈Cpq(wi,tj)

(3)

定義5.激勵機制

為了鼓勵工人可以接受跨區(qū)域的區(qū)域任務,本文提出了一種激勵工人的機制:

E=ε×disw+θ×timew

(4)

其中,E為每個跨區(qū)域接受任務的工人能得到的額外原始質(zhì)量的百分比,ε為工人與跨區(qū)域任務的距離權(quán)重,θ為工人與跨區(qū)域任務的時間權(quán)重,disw為工人跨區(qū)域接受任務時移動的距離,timew為工人跨區(qū)域完成任務時花費的時間.

定義6.跨區(qū)域在線多任務分配問題(CROMA)

給定一組區(qū)域任務T和一組工人W,所有的工人都是動態(tài)地到達空間眾包平臺,并在不同的區(qū)域完成任務.圖2顯示了本文的任務分配框架.CROMA問題是在給定的區(qū)域任務T和工人W之間找到最優(yōu)的工人任務匹配對,使其滿足任務質(zhì)量得分Q(w,t)最大化,即:

maxQ(w,t)

(5)

約束條件為:

(6)

∑?〈wi,tj〉∈Cpbij≤B

(7)

約束1為每個工人接受任務的數(shù)量不能超過他們可接受的最大任務數(shù)nw,約束2為在每一時刻,所分配工人的總體旅行成本不超過預算B,本文的區(qū)域任務分配框架如圖1所示.

圖1 區(qū)域任務分配框架Fig.1 Regional task allocation framework

4 區(qū)域任務分配算法

本節(jié)將通過一系列的算法來解決區(qū)域任務分配過程.

4.1 基于移動工人的跨區(qū)域在線分配算法

本節(jié)首先通過歷史的離線數(shù)據(jù)對任務和工人進行預分配,即對當前時刻的工人和任務的信息是已知的,在它們之間進行預分配,將產(chǎn)生的分配對用于后續(xù)的在線算法.

首先匹配在同一區(qū)域的工人和任務,在所有已知的工人集W和任務集T之間進行一個預分配,并且刪除不滿足約束的預分配.此時需要去計算每個工人所接受的任務數(shù)是否超過nw,如果工人所接受的任務數(shù)超過最大的任務數(shù),則刪除分配對中質(zhì)量分數(shù)較低的對,以確保任務的質(zhì)量(1～12行).對沒有超過最大的任務數(shù)的工人進行如下操作,對所有區(qū)域的工人和未分配的任務進行分配,將不再同一個區(qū)域的工人和任務的分配刪掉,保留滿足約束的分配對.在這次匹配中,工人是可以自由移動的,所有這次匹配可以將同一區(qū)域內(nèi)沒有分配成功的任務與工人進行匹配,在匹配過程中也要保證約束條件(13～29行).至此,該算法得到工人和所有任務的預分配對.算法1描述具體的分配過程.

算法1. Pre-allocation Algorithm(PA)

輸入:工人集W,任務集T

輸出:預分配結(jié)果集N

初始化:L=?,Tunassign=?

1.for eachwa∈Wdo

2. for eachtb∈Tdo

3. get a match pair 〈wa,tb〉

4. if(∑?〈wi,tj〉∈Cpbij)+bab≤Bandnwa

5. add 〈wa,tb〉 toL

6. continue

社區(qū)學習共同體作為社會資本是社區(qū)治理的基礎性力量，其能力大小關(guān)乎社區(qū)治理水平和效能。要通過提煉社區(qū)學習共同體社區(qū)治理的核心要素，作為衡量和評價其社區(qū)治理能力的指標要素。

7. else

8. delete the match pair

9. end if

10. end for

11.Tunassign← unassigned tasks

12.end for

13.for eachw∈Wdo

14. for eacht∈Tunassigndo

15. line 3-line 11

16. end for

17.Tunassign←unassigned tasks

18.end for

19.for eachw∈Wdo

20. for eacht∈Tunassigndo

21. if w and t don′t belong to the same area then

22. delete the match pair

23. end if

25. get a match pair 〈w,t〉

26. add 〈w,t〉 toL

27. end if

28. end for

29.end for

30.N←L

31.returnN

由于每個工人都有自己的活動范圍,并且工人不能接受超出該范圍的任務,但工人是可以自由移動的,因此設計一種基于移動工人的跨區(qū)域在線算法,使工人可以跨區(qū)域的去接受任務.針對算法1形成的預分配對,本文提出一種在滿足預算的情況下,實現(xiàn)整體質(zhì)量得分最大的算法,見算法2,該算法首先會對同一區(qū)域的工人和任務進行分配,如果無法生成匹配,則將未分配的任務添加到每個區(qū)域未完成的任務順序中,然后在所有區(qū)域之間進行全局分配.如果在全局分配后存在剩余任務,那么從算法1得到的預分配結(jié)果中選擇工人,即從預分配的分配對中選擇工人來完成該任務.

算法2. Cross-regional Allocation Algorithm based on Mobile Workers(CRMW)

輸入:工人集W,任務集T,預分配結(jié)果集N

輸出:分配結(jié)果集S

初始化:Tunassign=?

1.for eachregioni(i=1,2,3…) do

2. for newly arrived worker(task)i do

3. Get all candidate sets for worker(task)i

4. if ∑?〈wi,tj〉∈Cpbij+bwt≤Bandni

5.S←〈i,j〉

6. end if

7.Tunassign← unassigned tasks

8. if i cannot form a match then

9. line 13

10. end if

11. end for

12.end for

13.for each workerwin different regions do

14. for eacht∈Tunassigndo

15. get a match pair 〈w,t〉

16. if ∑?〈wi,tj〉∈Cpbij+(bwt+bwtE)≤Bandn

17.S←〈w,t〉

18. else

19. continue

20. end if

21.Tunassign← unassigned tasks

22. end for

23.end for

24.for each workerwin different regions do

25. select workers from N to complete the task

26. get a match pair 〈w′,t′〉

27. if ∑?〈wi,tj〉∈Cpbij+bw′t′≤Bandnw′

28.S←〈w′,t′〉

29. end if

30.Tunassign← unassigned tasks

31.end for

32.returnSandTunassign

33.jump to line 2

在算法2中,為了能使工人更好的接受跨區(qū)域的任務,本文利用定義5的激勵模型來為工人支付額外的獎勵,在算法2中的第16行,即:bwt+Ebwt,其中bwt為工人接受該任務所得到的報酬,Ebwt為工人接受跨區(qū)域任務所得到的額外獎勵.只要保證不超過預算約束,就可以將其作為一個分配對.如果超出預算約束,則將該任務在下一輪分配中,去選擇后續(xù)到達的工人去完成.

4.2 區(qū)域任務分解算法

由于區(qū)域任務的特點一般為面積大,執(zhí)行過程復雜且困難,所以本文將區(qū)域任務分解為多個子區(qū)域,然后將每個子區(qū)域分配給工人執(zhí)行,這樣可以在人力資源有限的情況下,保證響應結(jié)果的速度.算法3對分解算法進行了具體描述.

算法3. Regional Task Decomposition Algorithm(RTDA)

輸入:區(qū)域任務T

輸出:按優(yōu)先級排列的任務集合C

1. for regional tasktarrives do

2. initializationC=?

3. caculate the center position of the task

4. take the shape of the task as a regular shape

5. divide the area into multiple subregions

6. for each subregion do

7. caculate the center position of each subregion

8. caculate the distance between the center position of task and the center position of subregion

9. end for

10. take the distance as the priority and sort from small to large

11. add to the setC

12. end for

13. returnC

該算法是將任務請求者提交的區(qū)域任務分解為一個按優(yōu)先級排列的子區(qū)域任務的集合,然后將子區(qū)域單獨分配給每個工人,算法會從地圖運營商收集區(qū)域任務的形狀,大小等指標來對區(qū)域任務進行分解.該算法的輸入為區(qū)域任務,輸出為按優(yōu)先級排列的任務集合C.首先初始化集合為空,對區(qū)域任務計算其中心的位置,然后將其轉(zhuǎn)化為規(guī)則圖形,按照數(shù)學方法將區(qū)域劃分為大小相近的多個子區(qū)域,每個區(qū)域作為一個任務,計算每個子區(qū)域的中心位置與整個區(qū)域中心位置的距離(3～8行).然后將該距離作為優(yōu)先級對任務進行排序,將排序結(jié)果加入到集合C中.其中,距離越小優(yōu)先級越高,表示會為該區(qū)域優(yōu)先分配工人.

4.3 子區(qū)域任務分配算法

由于算法2為每個區(qū)域任務都分配了一定數(shù)量的工人,并且在算法3中將區(qū)域任務進行分解,所以本小節(jié)的目的是從給定數(shù)量的工人中為子區(qū)域任務進行匹配,通過粒子群優(yōu)化算法來實現(xiàn)工人和子任務的分配.在PSO算法中,使用兩個公式更新第k次迭代時粒子的位置和速度,公式如下:

(8)

(9)

其中δt為單位的時間步長值,r1和r2表示[0,1]間的隨機數(shù),c1,c2表示自我認知因子和社會經(jīng)驗因子,w為慣性因子.粒子的速度更新主要由3部分組成,第1項與慣性因子w有關(guān),較大的慣性因子會使算法可以進行全局探索,較小的慣性因子會使得粒子速度集中在搜索空間的局部區(qū)域;第2項和第3項分別為粒子的自我認知部分和社會經(jīng)驗部分.

由于本文在算法2中,按照約束對工人和任務形成的分配對,所以在該部分無需任何約束,只需按照質(zhì)量分數(shù)為子任務分配更合適的工人即可,所以適用于標準的粒子群優(yōu)化算法.根據(jù)前文,適應度函數(shù)為:

f(x)=α×dis(w,t)+β×σ(w,t)

(10)

α和β分別為權(quán)重參數(shù),將在后續(xù)實驗中介紹.算法4描述了對每個區(qū)域任務進行分解后,通過標準粒子群優(yōu)化算法為生成的子區(qū)域分配工人的具體過程.

算法4. Particle Swarm Optimization Algorithm(PSO)

輸入:按優(yōu)先級排列的任務集合C,工人集合W

輸出:分配結(jié)果M′

1. generate initial swarm with the particle positionXkand velocities randomlyvk

2. caculate the value of fitness function

3. determine first global best of the swarm

4. whilek≤ maxiteration do

5. update position usingeq.(8)

6. update velocity usingeq.(9)

7. caculate the value of fitness function usingeq.(10)

8. determine best local for each particle

9. determine best global in the swarm

10. update the best global

11. end while

12. returnM′

由于該算法的適應度函數(shù)是根據(jù)定義4中每個工人對任務的質(zhì)量分數(shù)公式而來,所以在算法迭代的過程中,對適應度函數(shù)的全局最優(yōu)相當于對質(zhì)量分數(shù)的全局最優(yōu)選擇.

5 實 驗

本節(jié)使用真實數(shù)據(jù)集測試本文提出的一系列算法.對于真實數(shù)據(jù)集,本文采用的是Foursquare簽到數(shù)據(jù)集[16].在Foursquare數(shù)據(jù)集中,可以通過API獲取到該數(shù)據(jù)集的相關(guān)信息:2153471個用戶,1143092個場所,1021970個簽到記錄.本文從中選取6231個工人和19284個任務,首先初始化一部分的工人和任務到眾包平臺中,隨后為每個工人和任務隨機設置到達時間,以及離開平臺的時間.在實驗過程中,從總質(zhì)量得分和運行時間兩個方面作為算法的評估結(jié)果進行比較分析.

5.1 實驗設置

本文的實驗是在配備 Intel(R)Core(TM)i7-7820X CPU @ 3.60 GHz 和 64GB 的機器上進行的,采用的編程語言為Python3.7.在實驗中,假設區(qū)域任務只會出現(xiàn)在活動范圍內(nèi)或不在活動范圍內(nèi)兩種情況.本文會通過改變每個階段的算法來與本文提出的算法進行比較,基于此可以提出四種對比算法:1)通過貪婪算法進行分配,對區(qū)域任務進行分解,最后對子區(qū)域任務使用粒子群優(yōu)化算法再次分配,記為G-D-P;2)通過基于移動工人預分配的在線分配算法進行分配,對區(qū)域任務進行分解,最后對子區(qū)域任務使用貪婪算法進行再次分配,記為P-D-G;3)通過貪婪算法進行分配,對區(qū)域任務進行分解,對子區(qū)域任務使用貪婪算法進行再次分配,記為G-D-G;4)通過基于移動工人預分配的在線分配算法進行分配,對區(qū)域任務進行分解,最后對子區(qū)域任務使用隨機算法進行再次分配,記為P-D-R.本文根據(jù)總質(zhì)量得分和運行時間來評估所有算法,并研究了不同參數(shù)對其性能的影響,在后續(xù)實驗中,距離權(quán)重α,時間權(quán)重β經(jīng)多次實驗的最優(yōu)值設置為0.8和0.7,具體參數(shù)的設置如表1所示.

表1 實驗參數(shù)設置Table 1 Experimental parameter setting

5.2 實驗結(jié)果

本節(jié)將對提出的算法和其他4種算法在總體質(zhì)量得分和運行時間方面進行比較,通過每次改變一個參數(shù),同時將其他參數(shù)設置為默認值來進行對比實驗.下面將從工人數(shù)量,任務數(shù)量,預算和工人可接受的最大任務數(shù)4個方面的變化情況對總體質(zhì)量得分和時間進行評估.

5.2.1 不同的工人數(shù)量

在圖2中,給出了5種算法在不同的工人數(shù)量時的總體質(zhì)量得分和運行時間的變化情況,其他參數(shù)的默認值設置為表1中的加粗值.圖2(a)表明了隨著工人數(shù)量的增長,總體質(zhì)量得分的變化情況,可以得到5種算法的總體趨勢都是在增加.這是隨著工人數(shù)量增加,工人任務分配對的數(shù)量同時也在增加,從而總體質(zhì)量得分增加.由于工人數(shù)量增加,且P-D-G和P-D-P都包含工人跨區(qū)域接受任務,所以總體質(zhì)量得分要比其他算法高.圖2(b)表明5種算法的運行時間都隨著工人數(shù)量的增加而增加.由于P-D-P和G-D-P使用了PSO算法,該算法的時間復雜度和迭代次數(shù)有關(guān),迭代次數(shù)和工人或者任務的數(shù)量有關(guān),所以運行時間會隨著規(guī)模的增加而增加,但運行時間是可控的,而且PSO的優(yōu)化效果會隨著迭代次數(shù)的增加不斷變化,考慮到這種情況,需要盡可能的增加其迭代次數(shù)來保證得到全局最優(yōu)的結(jié)果.

圖2 不同工人數(shù)量下算法的比較Fig.2 Comparison of algorithms with different numbers of workers

5.2.2 不同的任務數(shù)量

圖3給出了5種算法在不同的任務數(shù)量時的總體質(zhì)量得分和運行時間的變化情況,其他參數(shù)的默認值設置為表1中的加粗值.圖3(a)表明了隨著任務數(shù)量的增長,總體質(zhì)量得分的變化情況,可以看出隨著任務數(shù)量增加,得到的分配對數(shù)量也會增加,故總體質(zhì)量分數(shù)也在增加,其中P-D-P的效果最顯著.圖3(b)表明了算法的運行時間隨著任務數(shù)量的增加的變化情況,由于任務數(shù)量增加,工人任務分配對數(shù)量在增加,系統(tǒng)進行分配的時間也在增加,故5種算法的運行時間也不斷增加.由于P-D-R使用了隨機算法,所以運行時間是最快的,P-D-P和G-D-P使用了PSO算法,故運行時間要比其他算法長,具體原因同上.

圖3 不同任務數(shù)量下算法的比較Fig.3 Comparison of algorithms with different number of tasks

5.2.3 不同的預算

該部分給出了算法在不同預算下的總體質(zhì)量得分和運行時間的變化趨勢,其他參數(shù)的默認值設置為表1中的加粗值.圖4(a)表明了隨著預算的增加,總體質(zhì)量分數(shù)的變化情況.可以得到5種算法的質(zhì)量得分都隨著預算的增加而增加,由于預算的增加,產(chǎn)生的工人任務分配對的數(shù)量也會增加,所以總體質(zhì)量分數(shù)會變大.還可以看出本文提出的算法產(chǎn)生的總體質(zhì)量分數(shù)要比其他4種算法高,其次是P-D-G,這是因為本文的算法激勵工人跨區(qū)域接受了未分配的任務,從而質(zhì)量分數(shù)要比其他算法高.圖4(b)表明了隨著預算的增加,運行時間的變化情況.因為預算的增加,未分配成功的任務可以更好的找到工人進行跨區(qū)域完成,所以P-D-P和P-D-G的運行時間要比其他算法的運行時間長.

圖4 不同預算下算法的比較Fig.4 Comparison of algorithms under different budgets

5.2.4 不同的工人最大可接受任務數(shù)量

圖5給出5種算法在不同的工人最大可接受任務數(shù)量時的總體質(zhì)量得分和運行時間的變化情況,其他參數(shù)的默認值設置為表1中的加粗值.圖5(a)可以得到5種算法都隨著工人接受的最大任務數(shù)量的增加而增加,由于每個工人可接受的任務變多,完成的任務數(shù)量是增加的,所以總體質(zhì)量分數(shù)是增加的.還可以看出使用跨區(qū)域在線分配的算法效果要比其他算法好,這是因為工人跨區(qū)域接受任務,任務得以完成,從而得到相應的質(zhì)量分數(shù).圖5(b)表示的是5種算法運行時間的變化情況,由于每個工人可接受的任務數(shù)量變多,即為工人分配的時間也會變長,算法的運行時間也會增加.

圖5 不同工人最大接受任務數(shù)下算法的比較Fig.5 Comparison of algorithms under the maximum number of tasks accepted by different workers

6 總結(jié)與展望

本文考慮在預算和時間約束下,最大化總體質(zhì)量的區(qū)域任務在線分配問題,基于此提出一個多階段的區(qū)域任務在線任務分配框架,框架中在不同階段提出不同的算法為其選擇合適的工人,首先通過跨區(qū)域在線分配算法為每個區(qū)域任務分配一定數(shù)量的工人,且該過程中設置了激勵模型來鼓勵工人跨區(qū)域接受任務,然后通過任務分解算法將區(qū)域任務分解為多個子區(qū)域任務,最后使用粒子群算法來對子區(qū)域任務進行分配工人.本文通過真實數(shù)據(jù)集進行實驗,與其他4種算法進行對比,證明本文算法的有效性.

在未來的工作中,本文將考慮在工人提交任務后,如何準確地評估工人的響應結(jié)果的質(zhì)量,并對提供質(zhì)量較差的工人的能力進行一次重新評估,以便用于以后的任務分配,從而保證任務的質(zhì)量.