周靜，董紅斌，郭田雨

哈爾濱工程大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，黑龍江 哈爾濱 150001

眾包提供了一種匯集群體智慧求解問(wèn)題的新思路，成為當(dāng)前研究的熱點(diǎn)問(wèn)題[1]。近年來(lái)，隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)和線(xiàn)上到線(xiàn)下（online to offline，O2O）商業(yè)模式的興起，時(shí)空眾包逐步走進(jìn)人們的視野。與傳統(tǒng)眾包如在線(xiàn)問(wèn)答系統(tǒng)不同，時(shí)空眾包需要人們實(shí)際在線(xiàn)下進(jìn)行活動(dòng)，因此受到了時(shí)空因素的約束。

目前針對(duì)工人、用戶(hù)2 種角色的研究已經(jīng)頗多[2-9]，然而，新的眾包模式也帶來(lái)了全新的挑戰(zhàn)，平臺(tái)需要將工人、用戶(hù)、工作地點(diǎn)這3 類(lèi)對(duì)象進(jìn)行組合匹配[10-13]。對(duì)于2 類(lèi)對(duì)象的匹配問(wèn)題，大多是微任務(wù)，即任務(wù)在短時(shí)間(幾分鐘)內(nèi)即可完成，如查看超市商品價(jià)格（Gigwalk, http://www.gigwalk.com）、收集停車(chē)場(chǎng)信息（Waze, http://www.waze.com）等。而對(duì)于3 類(lèi)對(duì)象的匹配問(wèn)題，目前涉及的應(yīng)用主要有趣運(yùn)動(dòng)（ InterestingSport,http://www.quyundong.com）和南瓜車(chē)（Nanguache,http://www.nanguache.com）2 類(lèi)。趣運(yùn)動(dòng)是匹配教練進(jìn)行教學(xué)或者匹配球員打球；在南瓜車(chē)中，理發(fā)師為顧客定制理發(fā)服務(wù)。這2 種任務(wù)完成時(shí)間一般至少以小時(shí)為單位，但是現(xiàn)有研究少有考慮到任務(wù)時(shí)長(zhǎng)方面的問(wèn)題。許多研究在一開(kāi)始就假定了工人的最大匹配任務(wù)數(shù)，然后一次性完成匹配，工人依次完成這些任務(wù)，這對(duì)于微任務(wù)是可行的，但是對(duì)于長(zhǎng)時(shí)間任務(wù)則不符合現(xiàn)實(shí)需求。如果一次性為工人分配多個(gè)任務(wù)，則后面的任務(wù)需要等待很久。

因此，本文假定了任務(wù)的工作時(shí)間st，它由任務(wù)指定，但是在工作過(guò)程中可由工人調(diào)節(jié)。對(duì)于趣運(yùn)動(dòng)，st是固定的，多為固定授課時(shí)長(zhǎng)或者預(yù)約2 h 場(chǎng)地打球；而對(duì)于南瓜車(chē)，st無(wú)法立刻確定，可以首先生成最長(zhǎng)st，在用戶(hù)到達(dá)之后，工人再根據(jù)實(shí)際用戶(hù)講述的需求和自身經(jīng)驗(yàn)預(yù)估st，這在實(shí)際應(yīng)用中比較容易實(shí)現(xiàn)。

本文考慮到了工作時(shí)長(zhǎng)對(duì)任務(wù)分配的影響，提出了在線(xiàn)3 類(lèi)對(duì)象動(dòng)態(tài)匹配(online dynamic assginment for three types of objects，ODAT)問(wèn)題，并提出了基于混合遺傳算法（genetic algorithm,GA）的延遲匹配算法和延遲閾值策略，旨在在滿(mǎn)足多種約束的前提下平衡平臺(tái)的利益和用戶(hù)的滿(mǎn)意度。

1 相關(guān)工作

1.1 時(shí)空眾包

眾包環(huán)境下在線(xiàn)匹配問(wèn)題主要結(jié)合實(shí)際場(chǎng)景研究不同約束下的任務(wù)分配問(wèn)題。在線(xiàn)二維匹配場(chǎng)景是工人前往任務(wù)地點(diǎn)完成工作。Kazemi 等[2]最早研究最大化任務(wù)匹配數(shù)問(wèn)題。Tong 等[3]利用離線(xiàn)預(yù)測(cè)進(jìn)行在線(xiàn)分配來(lái)最大化匹配數(shù)。Zheng等[4]考慮到了優(yōu)化雙邊利益，不是單單優(yōu)化平臺(tái)利益，還應(yīng)考慮工人偏好問(wèn)題。Tong 等[5-6]研究雙邊在線(xiàn)微任務(wù)二維分配問(wèn)題，將貪心算法和匈牙利算法結(jié)合，提出了兩階段模型使效用最大化。徐天乘等[7]利用深度學(xué)習(xí)方法設(shè)計(jì)了基于位置預(yù)測(cè)的任務(wù)分配方法。另外還存在一些復(fù)雜任務(wù)，如修理房屋、災(zāi)難恢復(fù)等，一個(gè)任務(wù)需要多個(gè)工人才能完成。Mizuhara 等[8]提出協(xié)同任務(wù)分配問(wèn)題，需要所有工人都到達(dá)后才能開(kāi)始工作。而Liu 等[9]提出了具有依賴(lài)性約束的多階段匹配問(wèn)題，工人需要依次完成任務(wù)。

在線(xiàn)三維匹配場(chǎng)景是工人和用戶(hù)同時(shí)前往第三方地點(diǎn)，借助工作場(chǎng)所的工具來(lái)完成任務(wù)。Song 等[10]提出了眾包環(huán)境下的3 類(lèi)對(duì)象匹配問(wèn)題。Li 等[11]和李博揚(yáng)等[12]針對(duì)三維穩(wěn)定匹配問(wèn)題提出了求解算法。Li 等[13]確保工人和用戶(hù)在給定的寬容時(shí)間內(nèi)到達(dá)匹配的工作場(chǎng)所。

另外，任務(wù)規(guī)劃問(wèn)題也是時(shí)空眾包研究的一個(gè)重要領(lǐng)域。潘慶先等[14]提出了一種自適應(yīng)閾值的禁忌搜索算法，能減少任務(wù)分配中的移動(dòng)成本。Deng 等[15]旨在為工人找到最大化執(zhí)行任務(wù)數(shù)量的工作時(shí)間表。Tao 等[16]研究在用戶(hù)能及時(shí)到達(dá)目的地的前提下完成眾包任務(wù)并使效用最大化。Wu 等[17]基于遺傳算法提出一種尺度自適應(yīng)適應(yīng)度評(píng)估方法，并解決計(jì)算成本較高的眾包配送調(diào)度問(wèn)題。

1.2 遺傳算法

遺傳算法[18]是借鑒大自然進(jìn)化過(guò)程而提出的一種啟發(fā)式搜索方法。其基本思想是采用優(yōu)勝劣汰、適者生存的自然法則選擇個(gè)體，通過(guò)交叉、變異等方式來(lái)產(chǎn)生新一代的種群，逐代進(jìn)化，直到滿(mǎn)足終止條件。

GA 最核心的問(wèn)題就是編碼。目前傳統(tǒng)編碼方法包括二進(jìn)制編碼、排列編碼、值編碼和樹(shù)形編碼等。其中樹(shù)形編碼中每個(gè)染色體是由多個(gè)對(duì)象組成的樹(shù)，比如程序語(yǔ)言中的函數(shù)或者命令[19]。這些編碼的相似點(diǎn)是每個(gè)基因都只涉及一個(gè)對(duì)象，且前后基因具有關(guān)聯(lián)，因此易于實(shí)現(xiàn)。

目前也出現(xiàn)了許多GA 的變體，包括針對(duì)編碼形式、交叉變異算子的改進(jìn)等[20]。GA 還可以被應(yīng)用到多目標(biāo)優(yōu)化問(wèn)題中，如帶精英策略的快速非支配排序遺傳算法(nondominated sorting genetic algorithm II，NSGA-II)[21]。GA 可以很容易地與其他優(yōu)化算法結(jié)合，達(dá)到更好的性能，如模擬退火算法、貪心算法等。

由于GA 的并行性、可擴(kuò)展性等特點(diǎn)，被廣泛應(yīng)用于組合優(yōu)化中的非確定性多項(xiàng)式(nondeterministic polynomial，NP)難問(wèn)題，如運(yùn)籌管理、多媒體和無(wú)線(xiàn)網(wǎng)絡(luò)等領(lǐng)域。

2 問(wèn)題描述

2.1 基本定義

定義1眾包任務(wù)。眾包任務(wù)定義為t=＜lt,rt,ut,bt,et,st＞，表示任務(wù)的位置為歐式空間中的一個(gè)點(diǎn)lt，其移動(dòng)范圍為以lt為圓心、以rt為半徑的區(qū)域，報(bào)酬為ut，出現(xiàn)時(shí)間為bt，截止時(shí)間為et，工作時(shí)長(zhǎng)為st。

定義2眾包工人。眾包工人定義為w=＜lw,rw,cw,qw,bw＞，表示工人的位置為lw，移動(dòng)范圍是以lw為圓心、以rw為半徑的區(qū)域，容量為cw，服務(wù)質(zhì)量qw∈(0,1]，出現(xiàn)時(shí)間為bw。

定義3眾包工作地點(diǎn)。眾包工作地點(diǎn)定義為p=＜lp,bp,cp＞，表示工作地點(diǎn)的位置為歐式空間中的一個(gè)點(diǎn)lp，出現(xiàn)時(shí)間為bp，容量為cp。

為了綜合平臺(tái)的利益和用戶(hù)的滿(mǎn)意度，參照文獻(xiàn)[16]擴(kuò)展到3 類(lèi)對(duì)象匹配問(wèn)題，定義眾包工人在眾包地點(diǎn)完成眾包任務(wù)的效用。

定義4效用。眾包工人w在眾包地點(diǎn)p完成眾包任務(wù)t的效用定義式為

即任務(wù)回報(bào)ut與工人服務(wù)質(zhì)量qw的乘積除以從匹配開(kāi)始到正式開(kāi)始工作需要的趕路時(shí)間，其中dis表示2 點(diǎn)之間的距離，max為取最大值。默認(rèn)速度為1，其中“+1”用于避免零分母。

定義5ODAT 問(wèn)題。給定任務(wù)集T、工人集W、地點(diǎn)集P和效用函數(shù)U(.,.,.,)。求解目標(biāo)是找到T,W,P的任務(wù)分配M?T×W×P，并使總效用最大化max(M)=∑t∈T,w∈W,p∈P U(t,w,p)且滿(mǎn)足以下約束：

1)截止時(shí)間約束：任務(wù)需要在任務(wù)截止時(shí)間之前被分配。

2)空間約束：任務(wù)分配＜t,w,p＞需要滿(mǎn)足p在以lt為中心、以rt為半徑的范圍內(nèi)和以lw為中心、以rw為半徑的范圍內(nèi)。

3)容量約束：對(duì)于任務(wù)，每個(gè)任務(wù)t在M中最多出現(xiàn)一次；對(duì)于工人w，每次只能參與一種匹配，工人完成任務(wù)后才可再次參與匹配，總共最多出現(xiàn)cw次；對(duì)于地點(diǎn)p，其容量可認(rèn)為是多個(gè)工位，每次匹配只占用一個(gè)工位，每個(gè)地點(diǎn)正在工作的工位數(shù)不能超過(guò)cp，工人完成任務(wù)后該工位可被釋放，可再次參與匹配。

4)另外，Li 等[13]考慮到了工人和任務(wù)應(yīng)該同時(shí)到達(dá)的問(wèn)題。本文由于設(shè)置了預(yù)估工作時(shí)長(zhǎng)，可以直接保證工人和任務(wù)互相等待的時(shí)間Twait不超過(guò)給定的時(shí)間。即

式中 abs表示取絕對(duì)值。本文默認(rèn)未設(shè)置等待時(shí)間，這是一種提高用戶(hù)滿(mǎn)意度的方式，在實(shí)際應(yīng)用中可自行設(shè)置。

2.2 問(wèn)題復(fù)雜性

根據(jù)文獻(xiàn)[10]易知空間眾包環(huán)境下的3 類(lèi)對(duì)象在線(xiàn)任務(wù)匹配問(wèn)題是NP 難問(wèn)題，只能求得近似解。

3 延遲貪心算法

貪心算法每次一有新對(duì)象到來(lái)，就立即為其分配當(dāng)前最優(yōu)匹配。眾所周知，在眾包在線(xiàn)分配問(wèn)題中，對(duì)象到達(dá)順序的不同會(huì)直接影響匹配的效用。3 類(lèi)對(duì)象在線(xiàn)分配問(wèn)題在現(xiàn)實(shí)應(yīng)用中對(duì)響應(yīng)時(shí)間的要求不是很高，因此可以通過(guò)延長(zhǎng)一定的任務(wù)匹配時(shí)間，等待盡量多的地點(diǎn)和工人加入到在線(xiàn)平臺(tái)后再進(jìn)行匹配，這樣可以獲得更好的效用。文獻(xiàn)[12]提出了一種延遲匹配算法，僅僅當(dāng)任務(wù)達(dá)到最長(zhǎng)等待時(shí)間后才對(duì)任務(wù)進(jìn)行穩(wěn)定匹配，與本文場(chǎng)景不同。本文將其擴(kuò)展到ODAT 問(wèn)題中，延遲貪心算法的偽代碼如算法1 所示。

算法1延遲貪心(delay greedy, DG)算法

輸入：任務(wù)集T，工人集W，工作地點(diǎn)集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

For each 新出現(xiàn)的眾包對(duì)象vdo

更新任務(wù)完成情況

初始化未匹配的在線(xiàn)任務(wù)集、工人集、地點(diǎn)集

Mwait← {滿(mǎn)足所有約束的任務(wù)匹配}

將Mwait按照效用降序排序，依次加入到M

end

returnM

由于本文將工人動(dòng)態(tài)分配給任務(wù)，所以每次任務(wù)完成后，需要釋放工人和地點(diǎn)，使他們能夠參與到下次的匹配。在每次新對(duì)象到來(lái)后先檢查并更新任務(wù)完成情況，實(shí)際應(yīng)用中可設(shè)置倒計(jì)時(shí)或者進(jìn)行手動(dòng)釋放。

在大多數(shù)算法[5-6,10]中，會(huì)將多個(gè)容量的對(duì)象分解成多個(gè)單容量對(duì)象，但這樣會(huì)增加算法量級(jí)。雖然地點(diǎn)有容量，但是在進(jìn)行匹配時(shí)，只需將其作為一個(gè)對(duì)象，最后將所有可能的匹配按照效用排序，并依次安排到空的工位上，實(shí)驗(yàn)表明這樣能大幅降低時(shí)間復(fù)雜度。注意每次加入匹配前需要再一次判斷是否滿(mǎn)足約束，因?yàn)楹蜻x匹配集中可能有一個(gè)任務(wù)和多個(gè)地點(diǎn)工人匹配的情況，每次一旦加入最大效用的一組匹配后，已經(jīng)匹配的對(duì)象就不能再參與匹配了。排序的作用是防止小效用的任務(wù)占用了大效用的任務(wù)可匹配的工人或者地點(diǎn)。

算法復(fù)雜度：對(duì)于每個(gè)新出現(xiàn)的眾包任務(wù)t∈T、眾包工人w∈W和眾包工作地點(diǎn)p∈P，時(shí)間復(fù)雜度是O(|T||W||P|)。算法需要記錄所有可行匹配和3類(lèi)對(duì)象的信息，空間復(fù)雜度是O(min(|T|,|W|,|P|×cp))。

4 改進(jìn)算法

延遲貪心匹配算法可認(rèn)為是在線(xiàn)3 類(lèi)對(duì)象匹配中的局部最優(yōu)算法。但是其復(fù)雜度過(guò)高，無(wú)法在短時(shí)間內(nèi)得出結(jié)果，這違背了眾包在線(xiàn)分配的實(shí)時(shí)性要求。因此本文提出了基于混合遺傳算法的延遲匹配算法，可以大大減少?gòu)?fù)雜度，同時(shí)還提出了延遲閾值策略來(lái)增加效用。

4.1 混合遺傳算法

4.1.1 編碼與解碼

本文將解直接設(shè)為1 個(gè)個(gè)體，每個(gè)染色體是1 組三維匹配，每對(duì)匹配是1 個(gè)基因。由于1 個(gè)基因又由3 個(gè)對(duì)象組合，每次生成新解和變化解都需要考慮到3 個(gè)對(duì)象的變化。最簡(jiǎn)單的方式是每次在未匹配的任務(wù)、工人、地點(diǎn)中隨機(jī)選出3 個(gè)作為一對(duì)匹配，但是顯然由于存在范圍約束，這會(huì)導(dǎo)致大量無(wú)用解的產(chǎn)生，需要很多次迭代才可能成功產(chǎn)生一個(gè)可行匹配，收斂速度極慢。

通過(guò)對(duì)約束的分析可以發(fā)現(xiàn)，約束只存在任務(wù)與地點(diǎn)、工人與地點(diǎn)之間，任務(wù)與工人之間是無(wú)約束的，如果需要設(shè)置等待時(shí)間，則這個(gè)約束可以在產(chǎn)生新匹配的時(shí)候進(jìn)行判斷，因?yàn)樗枰蝿?wù)和工人的參與。因此本文將3 類(lèi)對(duì)象構(gòu)造為1 個(gè)任務(wù)森林結(jié)構(gòu)，可以將有約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題，能大概率保證解的成功產(chǎn)生。如圖1所示，其中每個(gè)任務(wù)作為1 個(gè)樹(shù)根，樹(shù)的左子樹(shù)是滿(mǎn)足約束的地點(diǎn)，地點(diǎn)的右子樹(shù)是滿(mǎn)足約束的工人。樹(shù)根的順序以及左子樹(shù)和右子樹(shù)上的結(jié)點(diǎn)順序直接按照到達(dá)順序排列即可。同時(shí)，為了進(jìn)一步優(yōu)化后續(xù)搜索的速度，可對(duì)任務(wù)森林進(jìn)行剪枝，將地點(diǎn)左子樹(shù)為空的任務(wù)結(jié)點(diǎn)刪除，如將圖1 的26 號(hào)結(jié)點(diǎn)刪除。任務(wù)森林類(lèi)似樹(shù)形編碼方式，但是任務(wù)森林一旦確定，不可改變，因此無(wú)法通過(guò)交換部分子樹(shù)等方法實(shí)現(xiàn)交叉操作。通過(guò)構(gòu)造任務(wù)森林結(jié)構(gòu)可以不斷縮小可行解范圍，這樣任務(wù)森林的深度和廣度都不會(huì)很大，可以提高隨機(jī)生成初始解的成功概率和搜索速度。

圖1 任務(wù)森林結(jié)構(gòu)

本文使用隨機(jī)方法產(chǎn)生新的基因，但在初始化和搜索過(guò)程中會(huì)導(dǎo)致優(yōu)秀基因被重復(fù)挑選，相同基因重復(fù)會(huì)導(dǎo)致種群多樣性下降。如果每次都與種群中的所有個(gè)體比較，判斷是否產(chǎn)生重復(fù)匹配，每次需要比較3 個(gè)對(duì)象會(huì)耗費(fèi)大量時(shí)間。為了保證每個(gè)個(gè)體中基因的無(wú)重復(fù)性，本文為每個(gè)個(gè)體設(shè)置3 個(gè)全局標(biāo)記矩陣，可以保證個(gè)體中沒(méi)有重復(fù)匹配。其中任務(wù)和工人每次只能匹配1 次，標(biāo)記矩陣初始設(shè)為-1，匹配成功設(shè)為1；地點(diǎn)矩陣具有容量屬性，初始化為未工作的工位數(shù)量，每次匹配成功則減1。

4.1.2 初始解的生成

由于是在線(xiàn)匹配問(wèn)題，因此不固定種群規(guī)模，而是設(shè)置每輪最大種群規(guī)模數(shù)為未匹配任務(wù)的個(gè)數(shù)。借鑒蒙特卡羅樹(shù)搜索[22]中模擬過(guò)程的思想，將每個(gè)未匹配任務(wù)作為起始節(jié)點(diǎn)，交替隨機(jī)擴(kuò)展任務(wù)和地點(diǎn)節(jié)點(diǎn)，直到?jīng)]有節(jié)點(diǎn)可擴(kuò)展。若地點(diǎn)結(jié)點(diǎn)上存在右子樹(shù)，通過(guò)局部最優(yōu)算子確定工人，此時(shí)確定一個(gè)匹配；若地點(diǎn)節(jié)點(diǎn)無(wú)可匹配工人，則更換地點(diǎn)節(jié)點(diǎn)重新擴(kuò)展；若連續(xù)Smax次適應(yīng)度不變，則停止模擬。

以圖1 中的任務(wù)森林為例，當(dāng)前有4 個(gè)未匹配任務(wù)，所以需要模擬4 次。從任務(wù)22 號(hào)出發(fā)，當(dāng)前有2 個(gè)地點(diǎn)可擴(kuò)展，隨機(jī)選擇一個(gè)4 號(hào)地點(diǎn)，并選擇最大效用的工人，確定一次匹配。接下來(lái)擴(kuò)展任務(wù)節(jié)點(diǎn)，當(dāng)前有3 個(gè)任務(wù)可擴(kuò)展，隨機(jī)選擇18 號(hào)任務(wù)，它有1 個(gè)8 號(hào)地點(diǎn)可擴(kuò)展，以此類(lèi)推直到22 號(hào)任務(wù)結(jié)點(diǎn)模擬結(jié)束。部分模擬過(guò)程如圖2 所示。

圖2 模擬過(guò)程

通過(guò)隨機(jī)模擬生成初始解，可以給每個(gè)未匹配任務(wù)同等優(yōu)先選擇地點(diǎn)的權(quán)力，從而使初始解的多樣性最大化。

4.1.3 遺傳算子

使用局部最優(yōu)算子、雙重變異算子和隨機(jī)部分重啟機(jī)制逐代進(jìn)化，同時(shí)融合貪心算法，只有搜索到比當(dāng)前適應(yīng)度更大的匹配時(shí)才變異基因。這種方式可以保證種群朝最優(yōu)方向進(jìn)化，加快收斂速度。

局部最優(yōu)算子：確定好地點(diǎn)節(jié)點(diǎn)之后，遍歷其右子樹(shù)，找到當(dāng)前未匹配且適應(yīng)度最大的工人。

p 變異算子：在每個(gè)任務(wù)樹(shù)的左子樹(shù)上進(jìn)行隨機(jī)搜索其他地點(diǎn)節(jié)點(diǎn)。

t 變異算子：在任務(wù)森林中隨機(jī)搜索，尋找新的任務(wù)節(jié)點(diǎn)。

隨機(jī)部分重啟機(jī)制：保留大于種群平均適應(yīng)度的個(gè)體，具體如圖3 所示。對(duì)于小于種群平均適應(yīng)度的個(gè)體，在染色體上隨機(jī)設(shè)置2 個(gè)重置點(diǎn)，將重置點(diǎn)中間的匹配進(jìn)行釋放，然后重新隨機(jī)生成新的匹配，該算子有助于跳出局部最優(yōu)解。

圖3 隨機(jī)部分初始機(jī)制

4.1.4 算法偽代碼

設(shè)最大迭代次數(shù)Emax，同時(shí)若連續(xù)Tmax次種群最大適應(yīng)度不變，則提前停止迭代。使用效用函數(shù)作為適應(yīng)度函數(shù)，目標(biāo)是找到適應(yīng)度最高的種群?；旌线z傳算法的偽代碼如算法2 所示。

算法2混合遺傳算法

輸入：任務(wù)集T，工人集W，工作地點(diǎn)集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

For each 新出現(xiàn)的眾包對(duì)象vdo

更新任務(wù)完成情況

初始化未匹配的在線(xiàn)任務(wù)集、工人集、地點(diǎn)集；初始化任務(wù)森林；初始化標(biāo)記矩陣

生成初始解

fori=0:Emaxdo

p 變異

t 變異

隨機(jī)部分重啟機(jī)制

若連續(xù)Tmax次種群最大適應(yīng)度不變，則停止迭代

end

選出適應(yīng)度最大的個(gè)體，依次取出每個(gè)基因，加入到M中

end

returnM

4.2 延遲閾值策略

現(xiàn)有研究對(duì)于在線(xiàn)3 類(lèi)對(duì)象匹配問(wèn)題一般使用閾值策略來(lái)增加效用，如固定閾值(fixed)、隨機(jī)閾值(random)[10]、自適應(yīng)隨機(jī)閾值(adaptive)[10]等。其中自適應(yīng)隨機(jī)閾值效果最好，固定閾值最差。本文針對(duì)固定閾值策略進(jìn)行改進(jìn)，提出一種延遲閾值策略(delay fixed, DeFixed)，主要思想是保留雖然適應(yīng)度未達(dá)到閾值但是任務(wù)已經(jīng)達(dá)到最長(zhǎng)延遲時(shí)間的匹配。延遲閾值策略的偽代碼如算法3 所示。

算法3延遲閾值策略

輸入：任務(wù)集T，工人集W，工作地點(diǎn)集P，效用函數(shù)U(.,.,.,)

輸出：全局任務(wù)匹配結(jié)果集M

for each 新出現(xiàn)的眾包對(duì)象vdo

使用遺傳算法或者貪心算法找到所有可行的任務(wù)匹配Mwait

for each ＜t,w,p＞minMwaitdo

if m.t.tb+td＜tnowthen

ifUm＜qthen

continue

else

將m加入候選集C

else

將m加入候選集C

將C按照效用降序排序，依次加入到M

end

end

returnM

如果在當(dāng)前時(shí)間tnow時(shí)，任務(wù)t的開(kāi)始時(shí)間tb加上延時(shí)時(shí)間td小于當(dāng)前時(shí)間tnow，而且其形成的任務(wù)分配的效用沒(méi)有達(dá)到閾值θ，則丟棄此次匹配；如果已經(jīng)到達(dá)最長(zhǎng)延時(shí)時(shí)間，且它依舊能形成一個(gè)任務(wù)分配，則忽略閾值，認(rèn)定此次匹配成功。這樣的做法能夠在前期最大程度上保留可能的高效用匹配，在后期保留低效用的匹配，解決了固定閾值任務(wù)分配數(shù)降低的缺點(diǎn)。同時(shí)，最后一刻任務(wù)t依然能夠形成滿(mǎn)足約束的任務(wù)匹配，某種程度上也說(shuō)明匹配的工人和地點(diǎn)對(duì)象其實(shí)也可能長(zhǎng)時(shí)間無(wú)法與其他的對(duì)象形成高匹配。雖然也存在匹配的是新到來(lái)的工人和地點(diǎn)，在未來(lái)可以和其他任務(wù)形成高匹配的可能性，但是保留低效用匹配，讓工人盡快開(kāi)始服務(wù)比無(wú)限時(shí)等待未來(lái)可能的高效用匹配更具有現(xiàn)實(shí)意義。

固定閾值策略和延遲閾值策略都會(huì)最大程度上過(guò)濾掉小于閾值的匹配，這會(huì)讓在線(xiàn)等待匹配的對(duì)象數(shù)量大大增加，運(yùn)行時(shí)間也隨之增長(zhǎng)。

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

通過(guò)實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上分別對(duì)算法的效用和效率進(jìn)行評(píng)估。

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

實(shí)驗(yàn)環(huán)境：處理器為2.9 GHz AMD Ryzen 7 4800H with Radeon Graphics，內(nèi)存容量為2 GB，操作系統(tǒng)為CentOS Linux release 7.5.180 4 (Core)，編程語(yǔ)言為c++。

為驗(yàn)證本文算法的有效性，從時(shí)空眾包平臺(tái)gMission[23]收集真實(shí)數(shù)據(jù)。由于缺少預(yù)估工作時(shí)間和工人容量，采用合成數(shù)據(jù)，3 類(lèi)對(duì)象匹配多是理發(fā)和運(yùn)動(dòng)，設(shè)置工作時(shí)間默認(rèn)值為[30,120] min，工人容量默認(rèn)為5，符合實(shí)際情況。實(shí)驗(yàn)數(shù)據(jù)的參數(shù)設(shè)置見(jiàn)表1，加粗?jǐn)?shù)值為默認(rèn)參數(shù)。

表1 實(shí)驗(yàn)數(shù)據(jù)參數(shù)表

本文還通過(guò)一組合成數(shù)據(jù)集測(cè)試算法的可擴(kuò)展性。任務(wù)、工人和地點(diǎn)以10∶10∶1 的比例在[0，480] min 內(nèi)均勻出現(xiàn)在10 000×10 000 的網(wǎng)格中，位置以二維坐標(biāo)表示，對(duì)工人服務(wù)質(zhì)量和任務(wù)報(bào)酬采用2 種分布情況。合成數(shù)據(jù)集的詳細(xì)信息見(jiàn)表2。

表2 合成數(shù)據(jù)集

評(píng)價(jià)算法有以下7 種：

1）采用延遲閾值的DG 算法(DG-DeFixed)。

2）采用隨機(jī)閾值的DG 算法(DG-Random)。

3）采用自適應(yīng)閾值的DG 算法(DG-Adaptive)。

由于延遲匹配，將DG-Adaptive 算法中的權(quán)重更新公式改為

式中：ut,k是一輪匹配中使用隨機(jī)閾值算法以ek為閾值獲得的總效用和，Nt,k是一輪匹配中被分配任務(wù)的總數(shù)。

4）采用延遲閾值的GA 算法(GA-DeFixed)。

5）采用隨機(jī)閾值的GA 算法(GA-Random)。

6）采用自適應(yīng)閾值的GA 算法(GA-Adaptive)。

7）NetGA 為文獻(xiàn)[24]提出的一種改進(jìn)遺傳算法。作者使用了遺傳算法解決通信領(lǐng)域中的資源配置問(wèn)題，主要在用戶(hù)、基站、子信道三者之間進(jìn)行分配。其中1 個(gè)基站或子信道可以和多個(gè)用戶(hù)匹配，但是1 個(gè)用戶(hù)只能和1 個(gè)基站、1 個(gè)子信道匹配。使用映射矩陣解決有效覆蓋范圍的約束，染色體設(shè)計(jì)為用戶(hù)與基站的匹配加上用戶(hù)與子信道的匹配。

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

5.2.1 對(duì)比NetGA 算法

由于使用閾值的匹配方式運(yùn)行時(shí)間比沒(méi)有閾值的長(zhǎng)，僅使用無(wú)閾值的DG 算法和GA 算法與NetGA 算法進(jìn)行對(duì)比實(shí)驗(yàn)。NetGA 算法的參數(shù)同GA 算法一致。實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 對(duì)比NetGA 算法

可以看出NetGA 算法在長(zhǎng)時(shí)間運(yùn)行情況下依然無(wú)法獲得很好的結(jié)果，分析原因如下：NetGA 算法[24]的應(yīng)用場(chǎng)景是超密集異構(gòu)網(wǎng)絡(luò)下的離線(xiàn)分配問(wèn)題，基站和子信道都有多個(gè)容量，有效覆蓋范圍矩陣是稠密矩陣，即使對(duì)象數(shù)量少也能生成多個(gè)匹配，在本實(shí)驗(yàn)中3 類(lèi)對(duì)象數(shù)量都不超過(guò)50，所以可以使用該方法。而本文場(chǎng)景每次任務(wù)和工人每次只能匹配1 個(gè)地點(diǎn)，需要在線(xiàn)實(shí)時(shí)分配，數(shù)據(jù)規(guī)模大，有效覆蓋范圍矩陣是稀疏矩陣，在進(jìn)化過(guò)程中會(huì)產(chǎn)生大量失敗匹配和重復(fù)匹配，需要迭代多次才能搜索成功；因而NetGA 算法無(wú)法應(yīng)用到ODAT 問(wèn)題中。

5.2.2 消融實(shí)驗(yàn)

在這組實(shí)驗(yàn)中，首先對(duì)比蒙特卡羅模擬初始化和隨機(jī)初始化(GA-RI)的實(shí)驗(yàn)結(jié)果，然后驗(yàn)證去除隨機(jī)部分重啟機(jī)制(GA-NoRestart)后的實(shí)驗(yàn)結(jié)果，實(shí)驗(yàn)結(jié)果如圖5 所示。算法的效用和匹配數(shù)如圖5(a)和圖5(b)所示，可見(jiàn)當(dāng)使用隨機(jī)生成初始解時(shí)效用小于使用模擬方法生成的初始解，這是因?yàn)殡S機(jī)生成需要確定種群規(guī)模大小，而每次匹配時(shí)在線(xiàn)的對(duì)象數(shù)都是不確定的，同時(shí)隨機(jī)方法會(huì)導(dǎo)致部分優(yōu)秀解的丟失，而去除隨機(jī)部分重啟機(jī)制后效用會(huì)有所降低；運(yùn)行時(shí)間和內(nèi)存占用如圖5(c)和圖5(d)所示，去除隨機(jī)部分重啟機(jī)制會(huì)降低運(yùn)行時(shí)間，內(nèi)存占用都一樣。

圖5 消融實(shí)驗(yàn)對(duì)比結(jié)果

5.2.3 改變閾值

在本組實(shí)驗(yàn)中，對(duì)比延遲閾值策略和固定閾值策略在DG 算法和GA 算法這2 種匹配方式上的結(jié)果，其他參數(shù)使用表1 中的默認(rèn)值。改變閾值的實(shí)驗(yàn)結(jié)果如圖6 所示。算法的效用和匹配數(shù)變化情況如圖6(a)和圖6(b)所示：顯然使用延遲閾值策略的算法效用隨閾值增大而增加，且能保持匹配任務(wù)數(shù)穩(wěn)定；而使用固定閾值策略的算法效用則會(huì)在達(dá)到峰值后迅速下降，匹配數(shù)也會(huì)隨之減少，DG 算法的效用略高于GA 算法。運(yùn)行時(shí)間曲線(xiàn)如圖6(c)所示，DG 算法的運(yùn)行時(shí)間高于GA 算法，同時(shí)延遲閾值策略的運(yùn)行時(shí)間高于固定閾值策略。內(nèi)存占用變化曲線(xiàn)如圖6(d)所示：DG 算法的內(nèi)存占用明顯高于GA 算法，因?yàn)镈G 算法需要存儲(chǔ)所有可行的匹配。

圖6 改變閾值實(shí)驗(yàn)對(duì)比結(jié)果

由以上分析結(jié)果可以看出，延遲閾值策略在效用和匹配數(shù)上明顯優(yōu)于固定閾值策略。雖然運(yùn)行時(shí)間較長(zhǎng)，但是設(shè)置合適的閾值可以保證運(yùn)行時(shí)長(zhǎng)在可接受范圍內(nèi)。

5.2.4 改變半徑

在本組實(shí)驗(yàn)中，改變?nèi)蝿?wù)和工人的半徑，實(shí)驗(yàn)結(jié)果如圖7 所示，其他參數(shù)使用表1 中的默認(rèn)值。算法的效用和匹配數(shù)如圖7(a)和圖7(b)所示，使用DeFixed 策略的算法效用和匹配數(shù)明顯高于另2 種策略算法，Adaptive 策略其次，Random 最低，DG 算法在同種策略上效用略大于GA 算法；運(yùn)行時(shí)間如圖7(c)所示，所有算法的運(yùn)行時(shí)間隨半徑增加而增大，因?yàn)榭善ヅ涞膶?duì)象數(shù)量增多，DGDeFixed 算法的運(yùn)行時(shí)間明顯高于其他算法，且DG 算法在同種策略上的運(yùn)行時(shí)間也高于GA 算法。內(nèi)存占用如圖7(d)所示，DG 算法的內(nèi)存占用明顯高于GA 算法。

圖7 改變半徑實(shí)驗(yàn)對(duì)比結(jié)果

5.2.5 改變工人容量

在這組實(shí)驗(yàn)中，改變工人的容量，其他參數(shù)使用表1 中的默認(rèn)值。改變工人容量的實(shí)驗(yàn)結(jié)果如圖8 所示。

圖8 改變工人容量實(shí)驗(yàn)對(duì)比結(jié)果

算法的效用和匹配數(shù)如圖8(a)和圖8(b)所示，隨著工人容量的提升，所有算法的效用先逐漸增加然后不變，這是因?yàn)槊看螘?huì)選擇最優(yōu)匹配的工人；運(yùn)行時(shí)間和內(nèi)存占用如圖8(c)和圖8(d)所示：DG 算法的運(yùn)行時(shí)間和內(nèi)存整體都高于GA算法。

5.2.6 改變延遲時(shí)間

在這組實(shí)驗(yàn)中，改變算法的延遲時(shí)間，其他參數(shù)使用表1 中的默認(rèn)值。改變延遲時(shí)間的實(shí)驗(yàn)結(jié)果如圖9 所示。

圖9 改變延遲時(shí)間實(shí)驗(yàn)對(duì)比結(jié)果

算法的效用和匹配數(shù)如圖9(a)和圖9(b)所示，隨著延遲時(shí)間的增加，所有算法的效用也會(huì)隨之增加，因?yàn)榭善ヅ涞膶?duì)象數(shù)量增多，可選擇的范圍也更大，其中使用DeFixed 策略的算法的效用和匹配數(shù)都始終優(yōu)于其他算法；運(yùn)行時(shí)間如圖9(c)所示，所有算法的運(yùn)行時(shí)間都隨延遲時(shí)間增加而逐漸減少，其中DG-DeFixed 算法的運(yùn)行時(shí)間不延遲時(shí)較高，這是因?yàn)镈eFixed 策略會(huì)將不滿(mǎn)足閾值的任務(wù)延遲至最后一刻，增加了匹配時(shí)的復(fù)雜度，GA-DeFixed 算法的運(yùn)行時(shí)間雖然僅次于DG-DeFixed 算法，但是保持在較低水平；內(nèi)存占用如圖9(d)所示，DG 算法的內(nèi)存占用均高于GA 算法。

5.2.7 改變?nèi)蝿?wù)工作時(shí)長(zhǎng)

在這組實(shí)驗(yàn)中，分別對(duì)比了算法在工作時(shí)間為10～30 min 的短時(shí)長(zhǎng)任務(wù)、30～120 min 的中等時(shí)長(zhǎng)任務(wù)和120～300 min 的長(zhǎng)時(shí)長(zhǎng)任務(wù)的實(shí)驗(yàn)結(jié)果，其他參數(shù)使用表1 中的默認(rèn)值。改變?nèi)蝿?wù)的工作時(shí)間的實(shí)驗(yàn)結(jié)果如圖10 所示。算法的效用和匹配數(shù)如圖10(a)和圖10(b)所示，隨著工作時(shí)長(zhǎng)的增加，所有算法的效用都逐漸減少。這是因?yàn)槊看味夹枰蝿?wù)完成后才能釋放工人和地點(diǎn)，當(dāng)匹配時(shí)間點(diǎn)到達(dá)時(shí)，可匹配的對(duì)象也減少了，只能退而求其次，選擇相對(duì)較差的匹配。運(yùn)行時(shí)間和內(nèi)存占用如圖10(c)和圖10(d)所示：算法的運(yùn)行時(shí)長(zhǎng)隨工作時(shí)長(zhǎng)增加會(huì)有所減少，其中使用DeFixed 策略的算法運(yùn)行時(shí)長(zhǎng)最長(zhǎng)，DG 算法的內(nèi)存占用高于GA 算法。

圖10 改變?nèi)蝿?wù)工作時(shí)長(zhǎng)實(shí)驗(yàn)對(duì)比結(jié)果

5.2.8 改變?nèi)蝿?wù)和工人的數(shù)量

本組實(shí)驗(yàn)改變?nèi)蝿?wù)數(shù)量和工人的數(shù)量，其他參數(shù)使用表1 中的默認(rèn)值，實(shí)驗(yàn)結(jié)果如圖11、12 所示。算法的效用和匹配數(shù)如圖11(a)和圖11(b)、圖12(a)和圖12(b)所示，隨著任務(wù)數(shù)量的增加，所有算法的效用和匹配數(shù)都在增大，這是因?yàn)槲雌ヅ淙蝿?wù)數(shù)量增加；隨著工人數(shù)量的增加，算法的效用和匹配數(shù)會(huì)先增加后逐漸平緩，因?yàn)樗惴〞?huì)優(yōu)先選擇高效用的工人，其中使用DeFixed 策略的算法效用最大。運(yùn)行時(shí)間如圖11(c)、圖12(c)所示，所有算法的運(yùn)行時(shí)間都隨著數(shù)量增加而增加，其中DG-DeFixed 算法運(yùn)行時(shí)間增長(zhǎng)最快。內(nèi)存占用如圖11(d)、圖12(d)所示：DG 算法逐漸增加且消耗最多，GA 算法穩(wěn)定在較低水平。

圖11 改變?nèi)蝿?wù)數(shù)量實(shí)驗(yàn)對(duì)比結(jié)果

圖12 改變工人數(shù)量實(shí)驗(yàn)對(duì)比結(jié)果

5.2.9 改變等待時(shí)間

本組實(shí)驗(yàn)改變用戶(hù)的可容忍等待時(shí)間，其他參數(shù)使用表1 中的默認(rèn)值，實(shí)驗(yàn)結(jié)果如圖13 所示。

如圖13(a)和圖13(b)所示，所有算法的效用隨等待時(shí)間波動(dòng)，特別在等待時(shí)間等于5 min 時(shí)，匹配數(shù)大多有所下降，這是因?yàn)橄拗频臈l件過(guò)小不滿(mǎn)足的匹配較多；如圖13(c)和(d)所示，使用DeFixed 策略算法的運(yùn)行時(shí)間最長(zhǎng)，在等待時(shí)間等于5 min 時(shí)運(yùn)行時(shí)間驟增，DG 算法的內(nèi)存占用均高于GA 算法。

5.2.10 測(cè)試算法的可擴(kuò)展性

本組實(shí)驗(yàn)使用合成數(shù)據(jù)集測(cè)試在大規(guī)模數(shù)據(jù)量且服務(wù)質(zhì)量和報(bào)酬具有不同分布下算法的效果，實(shí)驗(yàn)結(jié)果如圖14 和圖15 所示。

圖14 改變對(duì)象數(shù)量（均勻分布)實(shí)驗(yàn)對(duì)比結(jié)果

圖15 改變對(duì)象數(shù)量（正態(tài)分布）實(shí)驗(yàn)對(duì)比結(jié)果

算法的效用和匹配數(shù)如圖14(a)和圖14(b)、圖15(a)和圖15(b)所示，所有算法的效用和匹配數(shù)都隨數(shù)量增加而增加，其中使用DeFixed 策略的算法效用高于其他算法；運(yùn)行時(shí)間如圖14(c)、圖15(c)所示，DG-DeFixed 的運(yùn)行時(shí)間過(guò)長(zhǎng)，甚至可能無(wú)法滿(mǎn)足在線(xiàn)匹配的實(shí)時(shí)性需求，但是GADeFixed 算法的運(yùn)行時(shí)間遠(yuǎn)遠(yuǎn)小于DG-DeFixed 算法；內(nèi)存占用如圖14(d)、圖15(d)所示，DG 算法的內(nèi)存消耗遠(yuǎn)遠(yuǎn)多于GA 算法，因?yàn)殡S著數(shù)據(jù)規(guī)模的增長(zhǎng)，其存儲(chǔ)的匹配也增加。

5.3 實(shí)驗(yàn)總結(jié)

本文使用真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集對(duì)算法的效用和效率進(jìn)行了實(shí)驗(yàn)。整體來(lái)看，GA-DeFixed算法的實(shí)驗(yàn)結(jié)果、運(yùn)行速度和內(nèi)存消耗均優(yōu)于其他算法。實(shí)驗(yàn)首先對(duì)比了NetGA 算法，說(shuō)明其無(wú)法應(yīng)用于本文場(chǎng)景，同時(shí)對(duì)GA 算法做了消融實(shí)驗(yàn)；然后將DeFixed 策略和Fixed 策略進(jìn)行對(duì)比，證明DeFixed 策略在效用和匹配數(shù)上優(yōu)于Fixed策略；后續(xù)實(shí)驗(yàn)中，通過(guò)改變不同參數(shù)，可以發(fā)現(xiàn)DeFixed 策略的效用高于其他閾值策略，且GA 算法的運(yùn)行時(shí)間和內(nèi)存消耗少于DG 算法。通過(guò)在合成數(shù)據(jù)集上的可擴(kuò)展性測(cè)試可以發(fā)現(xiàn)，雖然DG 算法能獲得最優(yōu)的效用，但是在數(shù)據(jù)規(guī)模較大的場(chǎng)景下，無(wú)法滿(mǎn)足實(shí)時(shí)性，運(yùn)行時(shí)間和內(nèi)存消耗都遠(yuǎn)高于GA 算法；GA 算法雖然獲得次優(yōu)解，但是使用DeFixed 策略的GA 算法在效用上高于其他算法，并且運(yùn)行時(shí)間和內(nèi)存占用都較少。

6 結(jié)論

本文研究新型時(shí)空眾包平臺(tái)中3 類(lèi)對(duì)象在線(xiàn)匹配問(wèn)題，針對(duì)工人工作時(shí)長(zhǎng)對(duì)后續(xù)匹配任務(wù)的影響，提出了考慮工作時(shí)長(zhǎng)的在線(xiàn)3 類(lèi)對(duì)象動(dòng)態(tài)匹配問(wèn)題。

1）通過(guò)分析3 類(lèi)對(duì)象的結(jié)構(gòu)和組合關(guān)系，提出了一種混合遺傳算法對(duì)問(wèn)題進(jìn)行求解，并分析多種閾值策略的影響，提出了延遲閾值策略進(jìn)一步提升效用。

2）對(duì)現(xiàn)有算法進(jìn)行改造以適應(yīng)本文場(chǎng)景，通過(guò)在真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上的實(shí)驗(yàn)，驗(yàn)證了該算法在降低任務(wù)分配時(shí)間、提升分配效用上具有良好的表現(xiàn)。

在未來(lái)工作中，首先要進(jìn)一步研究時(shí)間復(fù)雜度和效用之間的平衡；其次將探索更加廣泛適用于眾包場(chǎng)景的通用模型，考慮用戶(hù)、工人和平臺(tái)的多方利益，切合實(shí)際意義。