空間眾包下移動(dòng)工人的跨區(qū)域在線多任務(wù)分配

高麗萍,張祥磊,高 麗

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

2(復(fù)旦大學(xué) 上海數(shù)據(jù)科學(xué)重點(diǎn)實(shí)驗(yàn)室,上海 200093)

3(上海理工大學(xué) 圖書(shū)館,上海 200093)

1 引 言

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

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

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

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

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

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

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

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

2 相關(guān)工作

2.1 離線任務(wù)分配

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

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

2.2 在線任務(wù)分配

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

2.3 邊緣服務(wù)器

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

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

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

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

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

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

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

定義3.工人任務(wù)分配集

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

bij=C×dis(lw,lt)

(1)

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

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

通過(guò)每個(gè)工人對(duì)任務(wù)的距離和時(shí)間的不同權(quán)重來(lái)計(jì)算完成任務(wù)的質(zhì)量分?jǐn)?shù):

(2)

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

(3)

定義5.激勵(lì)機(jī)制

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

E=ε×disw+θ×timew

(4)

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

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

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

maxQ(w,t)

(5)

約束條件為:

(6)

∑?〈wi,tj〉∈Cpbij≤B

(7)

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

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

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

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

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

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

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

算法1. Pre-allocation Algorithm(PA)

輸入:工人集W,任務(wù)集T

輸出:預(yù)分配結(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ū)學(xué)習(xí)共同體作為社會(huì)資本是社區(qū)治理的基礎(chǔ)性力量，其能力大小關(guān)乎社區(qū)治理水平和效能。要通過(guò)提煉社區(qū)學(xué)習(xí)共同體社區(qū)治理的核心要素，作為衡量和評(píng)價(jià)其社區(qū)治理能力的指標(biāo)要素。

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

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

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

輸入:工人集W,任務(wù)集T,預(yù)分配結(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ū)域的任務(wù),本文利用定義5的激勵(lì)模型來(lái)為工人支付額外的獎(jiǎng)勵(lì),在算法2中的第16行,即:bwt+Ebwt,其中bwt為工人接受該任務(wù)所得到的報(bào)酬,Ebwt為工人接受跨區(qū)域任務(wù)所得到的額外獎(jiǎng)勵(lì).只要保證不超過(guò)預(yù)算約束,就可以將其作為一個(gè)分配對(duì).如果超出預(yù)算約束,則將該任務(wù)在下一輪分配中,去選擇后續(xù)到達(dá)的工人去完成.

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

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

算法3. Regional Task Decomposition Algorithm(RTDA)

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

輸出:按優(yōu)先級(jí)排列的任務(wù)集合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

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

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

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

(8)

(9)

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

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

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

(10)

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

算法4. Particle Swarm Optimization Algorithm(PSO)

輸入:按優(yōu)先級(jí)排列的任務(wù)集合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′

由于該算法的適應(yīng)度函數(shù)是根據(jù)定義4中每個(gè)工人對(duì)任務(wù)的質(zhì)量分?jǐn)?shù)公式而來(lái),所以在算法迭代的過(guò)程中,對(duì)適應(yīng)度函數(shù)的全局最優(yōu)相當(dāng)于對(duì)質(zhì)量分?jǐn)?shù)的全局最優(yōu)選擇.

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

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

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

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

表1 實(shí)驗(yàn)參數(shù)設(shè)置Table 1 Experimental parameter setting

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

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

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

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

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

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

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

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

5.2.3 不同的預(yù)算

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

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

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

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

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

6 總結(jié)與展望

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

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